More Like this

1. Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem

   Haque, Shaan Ul; Maguluri, Siva Theja (May 2025, AISTATS)

   Motivated by engineering applications such as resource allocation in networks and inventory systems, we consider average-reward Reinforcement Learning with unbounded state space and reward function. Recent work Murthy et al. (2024) studied this problem in the actor-critic framework and established finite sample bounds assuming access to a critic with certain error guarantees. We complement their work by studying Temporal Difference (TD) learning with linear function approximation and establishing finite-time bounds with the optimal sample complexity. These results are obtained using the following general-purpose theorem for non-linear Stochastic Approximation (SA). Suppose that one constructs a Lyapunov function for a non-linear SA with certain drift condition. Then, our theorem establishes finite-time bounds when this SA is driven by unbounded Markovian noise under suitable conditions. It serves as a black box tool to generalize sample guarantees on SA from i.i.d. or martingale difference case to potentially unbounded Markovian noise. The generality and the mild assumptions of the setup enables broad applicability of our theorem. We illustrate its power by studying two more systems: (i) We improve upon the finite-time bounds of Q-learning in Chen et al. (2024) by tightening the error bounds and also allowing for a larger class of behavior policies. (ii) We establish the first ever finite-time bounds for distributed stochastic optimization of high-dimensional smooth strongly convex function using cyclic block coordinate descent. 

   more » « less
2. Sharp Guarantees and Optimal Performance for Inference in Binary and Gaussian-Mixture Models

   https://doi.org/10.3390/e23020178  

   Taheri, Hossein; Pedarsani, Ramtin; Thrampoulidis, Christos (February 2021, Entropy)

   null (Ed.)

   We study convex empirical risk minimization for high-dimensional inference in binary linear classification under both discriminative binary linear models, as well as generative Gaussian-mixture models. Our first result sharply predicts the statistical performance of such estimators in the proportional asymptotic regime under isotropic Gaussian features. Importantly, the predictions hold for a wide class of convex loss functions, which we exploit to prove bounds on the best achievable performance. Notably, we show that the proposed bounds are tight for popular binary models (such as signed and logistic) and for the Gaussian-mixture model by constructing appropriate loss functions that achieve it. Our numerical simulations suggest that the theory is accurate even for relatively small problem dimensions and that it enjoys a certain universality property. 

   more » « less
3. On Submodularity of Quadratic Observation Selection in Constrained Networked Sensing Systems

   https://doi.org/10.23919/ACC.2019.8814899  

   Ghasemi, Mahsa; Hashemi, Abolfazl; Topcu, Ufuk; Vikalo, Haris (October 2019, 2019 American Control Conference (ACC))

   We study the problem of observation selection in a resource-constrained networked sensing system, where the objective is to select a small subset of observations from a large network to perform a state estimation task. When the measurements are gathered using nonlinear systems, majority of prior work resort to approximation techniques such as linearization of the measurement model to utilize the methods developed for linear models, e.g., (weak) submodular objectives and greedy selection schemes. In contrast, when the measurement model is quadratic, e.g., the range measurements in a radar system, by exploiting a connection to the classical Van Trees' inequality, we derive new optimality criteria without distorting the relational structure of the measurement model. We further show that under certain conditions these optimality criteria are monotone and (weak) submodular set functions. These results enable us to develop an efficient greedy observation selection algorithm uniquely tailored for constrained networked sensing systems following quadratic models and provide theoretical bounds on its achievable utility. Extensive numerical experiments demonstrate efficacy of the proposed framework. 

   more » « less
4. Partial Identifiability in Discrete Data with Measurement Error

   Noam Finkelstein; Roy Adams; Suchi Saria; Ilya Shpitser (July 2021, Proceedings of the Thirty Seventh Conference on Uncertainty in Artificial Intelligence)

   Cassio de Campos; Marloes H. Maathuis (Ed.)

   When data contains measurement errors, it is necessary to make modeling assumptions relating the error-prone measurements to the unobserved true values. Work on measurement error has largely focused on models that fully identify the parameter of interest. As a result, many practically useful models that result in bounds on the target parameter -- known as partial identification -- have been neglected. In this work, we present a method for partial identification in a class of measurement error models involving discrete variables. We focus on models that impose linear constraints on the tar- get parameter, allowing us to compute partial identification bounds using off-the-shelf LP solvers. We show how several common measurement error assumptions can be composed with an extended class of instrumental variable-type models to create such linear constraint sets. We further show how this approach can be used to bound causal parameters, such as the average treatment effect, when treatment or outcome variables are measured with error. Using data from the Oregon Health Insurance Experiment, we apply this method to estimate bounds on the effect Medicaid enrollment has on depression when depression is measured with error. 

   more » « less
5. From Optimization Dynamics to Generalization Bounds via {\L}ojasiewicz Gradient Inequality

   Fusheng Liu; Haizhao Yang; Soufiane Hayou; Qianxiao Li (October 2022, Transactions on machine learning research)

   Yiming Ying (Ed.)

   Optimization and generalization are two essential aspects of statistical machine learning. In this paper, we propose a framework to connect optimization with generalization by analyz- ing the generalization error based on the optimization trajectory under the gradient flow algorithm. The key ingredient of this framework is the Uniform-LGI, a property that is generally satisfied when training machine learning models. Leveraging the Uniform-LGI, we first derive convergence rates for gradient flow algorithm, then we give generalization bounds for a large class of machine learning models. We further apply our framework to three distinct machine learning models: linear regression, kernel regression, and two-layer neural networks. Through our approach, we obtain generalization estimates that match or extend previous results. 

   more » « less