# A Concentration Bound for Stochastic Approximation via Alekseev's Formula

arXiv: https://arxiv.org/abs/1506.08657 · HTML: https://mlsanity.com/paper/1506.08657/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2015.

## Built on by (most cited first, 16 of 16)

- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators](https://mlsanity.com/paper/2106.12729/) (2021)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [A Concentration Bound for TD(0) with Function Approximation](https://mlsanity.com/paper/2312.10424/) (2023)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging](https://mlsanity.com/paper/2505.21796/) (2025)
- [Multi-agent Natural Actor-critic Reinforcement Learning Algorithms](https://mlsanity.com/paper/2109.01654/) (2021)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [A Concentration Bound for LSPE(λ)](https://mlsanity.com/paper/2111.02644/) (2021)
- [A Concentration Bound for Distributed Stochastic Approximation](https://mlsanity.com/paper/2210.04253/) (2022)
- [Choose Your Battles: Distributed Learning Over Multiple Tug of War Games](https://mlsanity.com/paper/2509.20147/) (2025)
- [Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach](https://mlsanity.com/paper/2607.17595/) (2026)
- [A Concentration Bound for Two-Timescale Actor-Critic Algorithm](https://mlsanity.com/paper/2609.29117/) (2026)
- [Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD](https://mlsanity.com/paper/2609.39144/) (2026)

## Abstract (arXiv)

Given an ODE and its perturbation, the Alekseev formula expresses the solutions of the latter in terms related to the former. By exploiting this formula and a new concentration inequality for martingale-differences, we develop a novel approach for analyzing nonlinear Stochastic Approximation (SA). This approach is useful for studying a SA's behaviour close to a Locally Asymptotically Stable Equilibrium (LASE) of its limiting ODE; this LASE need not be the limiting ODE's only attractor. As an application, we obtain a new concentration bound for nonlinear SA. That is, given ε >0 and that the current iterate is in a neighbourhood of a LASE, we provide an estimate for i.) the time required to hit the ε-ball of this LASE, and ii.) the probability that after this time the iterates are indeed within this ε-ball and stay there thereafter. The latter estimate can also be viewed as the `lock-in' probability. Compared to related results, our concentration bound is tighter and holds under significantly weaker assumptions. In particular, our bound applies even when the stepsizes are not square-summable. Despite the weaker hypothesis, we show that the celebrated Kushner-Clark lemma continues to hold. %