A Concentration Bound for Stochastic Approximation via Alekseev’s Formula

Given an ordinary differential equation (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 behavior 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 ϵ > and that the current iterate is in a neighborhood 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 with 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.