cs.LGJul 20, 2026

Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach

Authors: Siddharth Chandak

Organizations: Department of Electrical Engineering, Stanford University, Stanford, 94305, CA, USA

Abstract

We establish mean-square and concentration bounds for stochastic approximation (SA) with arbitrary norm contractive mappings, under a multiplicative noise model where the noise may scale affinely with the norm of the iterates, and the iterates are potentially unbounded. These settings arise in reinforcement learning, where operators are often contractive in the ℓ∞\ell_\infty norm and the noise scales with the iterates. To address the arbitrary norm, earlier works replace the non-smooth squared norm with a smooth Lyapunov function constructed via the generalized Moreau envelope. For concentration analysis, these works handle multiplicative noise and unbounded iterates through a multi-stage bootstrapping argument that starts from a time-varying worst-case bound and iteratively refines it. We instead present a unified and elementary analysis that yields both bounds. Using an averaged noise sequence and corresponding auxiliary iterates, we obtain a one-step Lyapunov drift inequality for the normed error directly, without smoothing the norm or constructing an envelope. For the mean-square bound, we combine this drift inequality with an induction argument showing that the iterates remain bounded in expectation. For the concentration bound, we develop a probabilistic induction over a sequence of "good" events on which the iterates are controlled, allowing the standard Azuma-Hoeffding bound to be applied. Our approach yields the first sub-Gaussian tailed maximal (all-time) concentration bound for SA under multiplicative noise, by allowing the stepsize to depend logarithmically on the confidence level. Beyond the specific setting considered here, we discuss the generalizability of these proof techniques to other noise models and iterative algorithms.

Explore similar work

CardsList
May 20, 2026math.PR

Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian component plus a Martingale-difference component. When the Martingale-difference noise is bounded, we show that the tail of the error can be sub-Gaussian, sub-Weibull, or something lighter than any Pareto but heavier than any Weibull, depending on the step size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. Our analysis relies on a novel Lyapunov function involving the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. We complement the upper bounds with worst-case examples showing that qualitatively sharper bounds are impossible. We further study the case of unbounded Martingale-difference noise when the average operator is contractive, and the step sizes are of order 1/k1/k. In this setting, we show that if the random operator is almost surely non-expansive, then the error tail is at most three times heavier than the noise tail, whereas if the random operator is expansive with positive probability, then the error may have substantially heavier tails. These results are obtained through a novel black-box truncation argument that reduces the unbounded-noise setting to the bounded-noise case.
Shubhada Agrawal, Siva Theja Maguluri, Martin Zubeldia
Stochastic ApproximationConcentration InequalitiesLarge Step SizesTruncation
AskPDF
May 29, 2026cs.LG

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations Fˉ(x)=x\bar{F}(x)=x, where the operator Fˉ(⋅)\bar{F}(\cdot) can only be accessed through a noisy oracle. We first focus on the standard setting in which Fˉ(⋅)\bar{F}(\cdot) is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.
Zaiwei Chen, Siva Theja Maguluri
Stochastic ApproximationFinite Time AnalysisLyapunov FunctionContractionConvergence
AskPDF
Sep 14, 2026stat.ML

Steady-State Convergence of Stochastic Approximation

For constant-stepsize stochastic approximation (SA), the iterates converge in distribution to a stationary law that depends on the stepsize α.α. Steady-state convergence (SSC) concerns the limit of the scaled stationary distribution as α↓0.α\downarrow 0. Existing SSC theory requires i.i.d. or additive noise and global differentiability of the mean operator, and yields suboptimal rates. We develop a unified SSC theory for constant-stepsize contractive SA driven by Markovian, multiplicative noise, covering both locally differentiable and locally nondifferentiable mean operators. A key methodological contribution is a multi-step universality framework that progressively reduces the original stochastic recursion to tractable auxiliary dynamics while preserving its steady-state limit. Under local quadratic linearization at the fixed point, we obtain a Gaussian approximation of the scaled steady state at the optimal rate O(α)O(\sqrtα) in Wasserstein-2 distance, which further gives finite-time Gaussian approximations for the raw iterates. In the locally nondifferentiable regime, we establish a general SSC result and show that the leading-order asymptotic bias can be of order α\sqrtα, in contrast to the αα-order bias in the smooth regime. We apply the theory to Markovian linear SA and asynchronous Q-learning, neither of which is covered by prior results. We further propose a bias-reduction scheme for Q-learning that requires no knowledge of the local smoothness regime, validated by numerical experiments.
Yixuan Zhang, Qiaomin Xie
Stochastic Approximation
AskPDF