Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methods
In this paper, we study the almost sure boundedness and the convergence of the stochastic approximation (SA) algorithm. At present, most available convergence proofs are based on the ODE method, and the almost sure boundedness of the iterations is an assumption and not a conclusion. In Borkar-Meyn (2000), it is shown that if the ODE has only one globally attractive equilibrium, then under additional assumptions, the iterations are bounded almost surely, and the SA algorithm converges to the desired solution. Our objective in the present paper is to provide an alternate proof of the above, based on martingale methods, which are simpler and less technical than those based on the ODE method. As a prelude, we prove a new sufficient condition for the global asymptotic stability of an ODE. Next we prove a "converse" Lyapunov theorem on the existence of a suitable Lyapunov function with a globally bounded Hessian, for a globally exponentially stable system. Both theorems are of independent interest to researchers in stability theory. Then, using these results, we provide sufficient conditions for the almost sure boundedness and the convergence of the SA algorithm. We show through examples that our theory covers some situations that are not covered by currently known results, specifically Borkar-Meyn (2000).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
The Robbins-Siegmund theorem establishes the convergence of stochastic processes that are almost supermartingales and is one of the most commonly used approaches for analyzing stochastic iterative algorithms in stochasti…
Reinforcement LearningThe ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
Stochastic approximation is a class of algorithms that update a vector iteratively, incrementally, and stochastically, including, e.g., stochastic gradient descent and temporal difference learning. One fundamental challe…
reinforcement-learningReinforcement LearningConvergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence
The nonlinear two-time-scale stochastic approximation is widely studied under conditions of bounded variances in noise. Motivated by recent advances that allow for variability linked to the current state or time, we cons…
Bilevel OptimizationSemimartingale and continuous-time Markov chain approximation for rough stochastic local volatility models
Rough volatility models have recently been empirically shown to provide a good fit to historical volatility time series and implied volatility smiles of SPX options. They are continuous-time stochastic volatility models,…
CPUTime SeriesTime Series AnalysisNormal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
We provide non-asymptotic convergence rates of the Polyak-Ruppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twice-differentiable test functions. A crucial intermediate step is pr…
parameter estimationvalid