A concentration bound for stochastic approximation via Alekseev's formula

DOI10.1287/STSY.2018.0019MaRDI QIDQ5113889zbMATH OpenOpenAlexWikidataFDO

Authors Gugan Thoppe, Vivek Borkar

Publication date 18 June 2020

Published in Stochastic Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1506.08657

zbMATH Keywords

concentration inequalitystochastic approximationconcentration boundAlekseev's formulalocally asymptotically stable equilibrium (LASE)perturbed ODEsum of martingale-differences

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Stochastic approximation (62L20) Perturbations of ordinary differential equations (34D10) Computational methods for problems pertaining to systems and control theory (93-08)

Abstract: 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 $epsilon>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 $epsilon-$ball of this LASE, and ii.) the probability that after this time the iterates are indeed within this $epsilon-$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. %

Recommendations

• Concentration bounds for stochastic approximations
• A concentration bound for contractive stochastic approximation
• Convergence of stochastic approximation via martingale and converse Lyapunov methods
• Stochastic Approximation and Large Deviations: Upper Bounds and <scp>w.p.1</scp> Convergence
• scientific article; zbMATH DE number 622511

Cites work

• scientific article; zbMATH DE number 3177889 (Why is no real title available?)
• scientific article; zbMATH DE number 48727 (Why is no real title available?)
• scientific article; zbMATH DE number 53723 (Why is no real title available?)
• scientific article; zbMATH DE number 140537 (Why is no real title available?)
• scientific article; zbMATH DE number 976356 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 1391397 (Why is no real title available?)
• scientific article; zbMATH DE number 1405930 (Why is no real title available?)
• A Stochastic Approximation Method
• A generalized URN problem and its applications
• Acceleration of Stochastic Approximation by Averaging
• Concentration bounds for stochastic approximations
• Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment
• Method of Variation of Parameters for Dynamic Systems
• On the convergence, lock-in probability, and sample complexity of stochastic approximation
• Ordinary differential equations and dynamical systems
• Perturbations of nonlinear systems of differential equations
• Recuit simulésans potentiel sur une variétériemannienne compacte
• Recursive Stochastic Algorithms for Global Optimization in $\mathbb{R}^d $
• Stochastic approximation and its applications
• Stochastic approximation methods for constrained and unconstrained systems
• Stochastic approximation. A dynamical systems viewpoint.
• Transport-entropy inequalities and deviation estimates for stochastic approximation schemes

Cited in

(13)

• Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning
• Concentration of Contractive Stochastic Approximation and Reinforcement Learning
• Non-asymptotic error bounds for constant stepsize stochastic approximation for tracking mobile agents
• Multi-agent natural actor-critic reinforcement learning algorithms
• Finite sample performance of linear least squares estimation
• A concentration bound for contractive stochastic approximation
• On the sample complexity of actor-critic method for reinforcement learning with function approximation
• Concentration bounds for stochastic approximations
• An improved probability bound for the approximate S-lemma
• Stabilization under round-robin scheduling of control inputs in nonlinear systems
• A concentration bound for \(\operatorname{LSPE}( \lambda )\)
• Finite-time performance of distributed temporal-difference learning with linear function approximation
• Fundamental design principles for reinforcement learning algorithms

This page was built for publication: A concentration bound for stochastic approximation via Alekseev's formula

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113889)