ABSTRACT. Non-asymptotic central limit theorem (CLT) rates play a central role in modern machine learning and operations research. In this paper, we study CLT rates for multivariate dependent data in Wasserstein-$p$ ($\mathcal W_p$) distance, for general $p\ge 1$. We focus on two fundamental dependence structures that commonly arise in practice: locally dependent sequences and geometrically ergodic Markov chains. In both settings, we establish the \textit{first optimal} $\mathcal O(n^{-1/2})$ rate in $\mathcal W_1$, as well as the first $\mathcal W_p$ ($p\ge 2$) CLT rates under mild moment assumptions, substantially improving the best previously known bounds in these dependent-data regimes. As an application of our optimal $\mathcal W_1$ rate for locally dependent sequences, we further obtain the first optimal $\mathcal W_1$-CLT rate for multivariate $U$-statistics.

On the technical side, we derive a tractable auxiliary bound for $\mathcal W_1$ Gaussian approximation errors that is well suited for studying dependent data. For Markov chains, we further prove that the regeneration time of the split chain associated with a geometrically ergodic chain has a geometric tail without assuming strong aperiodicity or other restrictive conditions. These tools may be of independent interest and enable our optimal $\mathcal W_1$ rates and underpin our $\mathcal W_p$ ($p\ge 2$) results.

ABSTRACT. We study online learning for new products on a platform that makes capacity-constrained assortment decisions on which products to offer. For a newly listed product, its quality is initially unknown, and quality information propagates through social learning: when a customer purchases a new product and leaves a review, its quality is revealed to both the platform and future customers. Since reviews require purchases, the platform must feature new products in the assortment ("explore") to generate reviews to learn about new products. Such exploration is costly because customer demand for new products is lower than for incumbent products. We characterize the optimal assortments for exploration to minimize regret, addressing two questions. (1) Should the platform offer a new product alone or alongside incumbent products? The former maximizes the purchase probability of the new product but yields lower short-term revenue. Despite the lower purchase probability, we show it is always optimal to pair the new product with the top incumbent products. (2) With multiple new products, should the platform explore them simultaneously or one at a time? We show that the optimal number of new products to explore simultaneously has a simple threshold structure: it increases with the "potential" of the new products and, surprisingly, does not depend on their individual purchase probabilities. We also show that two canonical bandit algorithms, UCB and Thompson Sampling, both fail in this setting for opposite reasons: UCB over-explores while Thompson Sampling under-explores. Our results provide structural insights on how platforms should learn about new products through assortment decisions.

ABSTRACT. Natural policy gradient (NPG) is a central tool in modern reinforcement learning, with variants such as TRPO and PPO serving as major workhorses in today’s applications. Despite extensive study, existing convergence analyses either do not provide sharp guarantees, such as distribution-free global geometric convergence, or obtain such guarantees only through additional regularization or adaptive stepsizes. A key difficulty is that, unlike classical dynamic programming methods such as value iteration and policy iteration, gradient-based methods are often viewed as departing from Bellman-operator-based algorithm design and analysis, making it difficult to directly exploit defining features of the Bellman operator, such as contraction and monotonicity. In this talk, we present a new perspective showing that NPG belongs to a unified framework, which we call doubly smoothed policy iteration, where the policy is updated by taking a smoothed greedy step with respect to a weighted average of historical Q-functions. This framework includes NPG, policy iteration, dual-averaged policy iteration, and general policy dual averaging as special cases. By leveraging the contraction and monotonicity properties of the Bellman operator, this viewpoint yields strong convergence guarantees for a broad class of algorithms through a simpler analysis. The same algorithmic and analytical framework also extends to stochastic shortest path and average-reward problems.

ABSTRACT. This work focuses on learning from a large number of devices with each device holding only a single sample of privacy-sensitive data. Several real-world applications exist to this one sample per client setup up including learning from fitness trackers, data/app usage aggregators, body-worn sensing devices, and daily event monitors to name a few. When a client has only one sample, the standard federated learning paradigm breaks down as a local update based on that single point is far from being useful, especially in the earlier rounds for estimation of the model coefficients. This utility is further weakened by the privacy-inducing noise applied at every round. This work caters to this problem to enable such clients to collaboratively contribute to effectively learn a global model without leaking the privacy of their data. The proposed approach injects a single, carefully calibrated noisy perturbation to transform the sample at each client, followed by a post-processed representation which is shared with the server. These representations aggregated at the server are processed to obtain an unbiased gradient update that in expectation matches the non-private centralized gradient while preserving data privacy. This approach is different than traditional private federated learning, where the communication payloads involve model coefficients as opposed to privately transformed data samples. This method enables devices with extremely limited data to collaborate and learn accurate, privacy-preserving models without requiring large local datasets or sacrificing individual privacy.

ABSTRACT. Spectral optimizers such as Muon, and the more general Freon family D = (GGT) −cG, have shown strong empirical performance in large-scale learning. Recent evidence suggests their success may not rely on an exact target geometry: randomizing the singular values (the Kaon variant) performs comparably to carefully whitened updates. We turn this observation into a communication question for distributed learning: if exact spectral geometry is unnecessary for optimization, must we communicate the exact spectrum? We propose Sketch-Kaon and SketchFreon, communication-efficient federated optimizers that transmit only a two-round randomized low-rank subspace sketch of the aggregated gradient while replacing the exact singular values with randomized or coarsely quantized ones. To stabilize training under client heterogeneity and a noisy uplink, we introduce a client-split alignment estimator γˆ that adapts the global step size using agreement between two independently aggregated client groups— computed by reusing already-received uploads, hence at no additional communication. We give convergence, sketchapproximation, and safe-step analyses, and evaluate on synthetic distributed regression, a controlled spectrum ablation, federated edge modulation classification, and federated wireless channel prediction. Across these settings the exact singular values can be randomized with negligible effect at identical communication, and the sketched methods achieve markedly better bits-to-accuracy than full-gradient spectral descent while being more robust to a noisy uplink.

ABSTRACT. We investigate decentralized gradient descent (DGD) with emphasis on efficient communication and computation resource utilization under budget constraints. Specifically, we propose and analyze a multi-consensus decentralized gradient descent (mcDGD) scheme, where the number of consensus rounds and the stepsize are allowed to vary across iterations. Building on a unified analytical framework for DGD, we derive finite-time convergence bounds that explicitly characterize the interaction between consensus quality and optimization dynamics. Our analysis requires only convexity of the local objective functions while assuming smoothness and strong convexity of the global objective. The resulting bounds enable a principled communication allocation strategy under resource constraints, including structural properties of optimal consensus scheduling. Numerical experiments corroborate the theoretical findings and demonstrate improved communication-computation efficiency compared to fixed-consensus decentralized optimization methods.

ABSTRACT. We study the problem of system identification in heterogeneous settings, where different systems may follow distinct underlying dynamics. Existing clustered system identification approaches often rely on iterative training-based cluster assignment, which can be sensitive to learning uncertainty and model initialization. In contrast, we propose a one-shot, training-free clustering method that identifies similar systems using the structure of their locally observed data. Specifically, each system estimates a local state covariance matrix, and cluster identities are inferred by measuring the alignment between the leading covariance eigenspaces of different systems. We provide a mathematical interpretation of the proposed similarity score and develop a finite-sample analysis that characterizes how covariance estimation error induces eigenspace perturbations in terms of the underlying system dynamics. We then derive a probability bound for pairwise false merges and a global clustering success guarantee. Numerical experiments demonstrate that the proposed eigenspace-based clustering method effectively identifies systems with shared dynamics, leading to lower personalized model-estimation error compared with training-based clustering and non-clustered baselines.

ABSTRACT. Private Information Retrieval (PIR) and Private Set Intersection (PSI) are fundamental privacy-enhancing primitives with growing relevance in cloud-based applications. In the multi-server setting, information-theoretically secure PSI can be obtained from information-theoretically secure symmetric PIR. We extend this connection to the single-server setting by relaxing the security requirement from information-theoretic to computational guarantees. Our main result shows that any computationally secure symmetric PIR protocol can be transformed into a computationally secure PSI scheme, enabling a generic way to define new PSI schemes under widely used cryptographic assumptions.

ABSTRACT. With the recent boom in data science, the demand for privacy protection in data analytics has increased. In particular, private selection tasks for extracting significant information from data are essential, and the development and application of trustworthy methods to address them while satisfying differential privacy have been actively pursued. However, within existing mechanisms, there remains considerable room for further refinement of the concepts of sensitivity that determine the noise scale. Theoretically, enhancing these concepts allows stricter and smaller perturbations, thereby improving the reliability of the analysis results. Therefore, this study proposes novel differentially private selection mechanisms using enhanced sensitivity concepts. First, the concepts of global and smooth sensitivity are enhanced to simultaneously handle changes in the values of both the target and the other candidates. In addition, direction-aware concepts are proposed that consider the direction of changes as well. Furthermore, enhanced concepts are proposed that can be employed when using a one-sided noise distribution along with rigorous theoretical guarantees. Experiments using genomic statistical analysis as an example demonstrated that the proposed mechanism using enhanced and direction-aware smooth sensitivity with a one-sided distribution can provide higher accuracy than existing methods. Overall, this study can serve as a critical foundation for the development of optimal and reliable methods for differentially private selection. The Python implementation of the experiments and the supplemental results are available at https://github.com/ay0408/EnhancedSPS.

ABSTRACT. We study private Boolean function evaluation in 2.5D/3D heterogeneous systems, where a small trusted chiplet coordinates with isolated but untrusted chiplets. The function is known, but the private input and all input-dependent intermediate values must remain hidden. Since the input is private, a natural approach is to use k-server Private Information Retrieval (PIR) over the function truth table: the trusted chiplet acts as the PIR client, and the isolated untrusted chiplets act as replicated non-colluding PIR servers. However, direct PIR is infeasible because an n-input Boolean function has a truth table with 2^n entries. We propose Private Information Retrieval for Directed Acyclic Graphs (PIR-DAG), which maps the Boolean function onto a directed acyclic graph (DAG) of q-input lookup tables (LUTs), where q is typically around 4, and evaluates each LUT truth table through a PIR-protected evaluation. This changes the PIR database used in each evaluation from the full 2^n-entry truth table to a 2^q -entry LUT truth table, giving an exponential reduction in per-evaluation database size, and a large reduction in total trusted-to-untrusted communication, relative to direct full truth table PIR. PIR-DAG therefore replaces one infeasible full truth table PIR execution with a sequence of small LUT-level PIR executions. We prove that this sequential evaluation preserves information-theoretic privacy against any individual honest-but-curious untrusted chiplet, even when later LUT indices depend on previously reconstructed intermediate values. We evaluate PIR-DAG against conventional full truth table PIR under finite trusted-to-untrusted upload bandwidth on ISCAS ’85 benchmarks.

ABSTRACT. A robot is fundamentally a device that takes converts information about the world into useful physical work. Inside the robot are a series of information processing computations going by names such as observation, representation, prediction, and planning that all slowly prune away information. We build on this information-centric view to inform the design of minimalist resource-efficient robots, asking questions like: What does a robot learner need to sense & attend to at each stage of computation to learn and perform a task? How does this vary as a function of task characteristics, agent characteristics, and learning phase? I will present a series of empirical results that offer clues towards some of the answers, while staying grounded in the modern practice of robot learning.

ABSTRACT. Robots are starting to integrate into manufacturing, healthcare, and our daily lives. However, their development remains largely an iterative and intuition-driven process. Robot structures are typically designed, fabricated, and tested manually, followed by the development of control policies to achieve desired behaviors. This separation between design and control often leads to suboptimal performance and repeated manufacturing iterations. I aim to overcome these challenges with a unified, data-driven co-design framework for robots. Such a framework integrates simulation, optimization, and machine learning to automatically generate and evaluate robot designs, along with their corresponding control policies. With an end-to-end approach, we can not only optimize for single tasks, but also uncover physically intelligent designs that simplify the control problem, enabling robust performance across varying use cases. I will show how this computational approach yields robots that are not only customizable but fundamentally more generalizable than human-designed baselines, paving the way to unlocking capabilities previously thought to be infeasible.