A concentration bound for stochastic approximation via Alekseev's formula

DOI10.1287/STSY.2018.0019zbMATH Open1442.62187arXiv1506.08657OpenAlexW2964258803WikidataQ128308466 ScholiaQ128308466MaRDI QIDQ5113889FDOQ5113889

Authors: Gugan Thoppe, Vivek Borkar 

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

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. %

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

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

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)

Cites Work

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

Cited In (12)

• 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
• An improved probability bound for the approximate S-lemma
• Finite-Time Performance of Distributed Temporal-Difference Learning with Linear Function Approximation
• Stabilization under round-robin scheduling of control inputs in nonlinear systems
• A concentration bound for \(\operatorname{LSPE}( \lambda )\)
• 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)