A Concentration Bound for Stochastic Approximation via Alekseev’s Formula

By Gugan Thoppe, Vivek Shripad Borkar. Stochastic Systems, 2015

52 citations recorded by the source corpus.

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

Subfields: Mathematical Physics, Modeling and Simulation, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/2feb83c630b333b7b41aad6180fe2c138d935d60

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Modeling and Simulation

In Statistics and Probability

Citations in the corpus

Convergence of Learning Dynamics in Stackelberg Games (2019, methodology): “The key technique in proving the above theorem (which is done in detail in Borkar and Pattathil [12] using results from Thoppe and Borkar [57]), is taking a union bound of the errors over all the continuous time intervals defined for n ≥ n0.”