2015/06/26 by Gugan Thoppe, Thoppe, Gugan, Vivek S. Borkar +1 · 2 citations
Economics, Econometrics and Finance · Mathematics · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #FOS: Mathematics #Mathematical Biology Tumor Growth #Optimization and Control (math.OC) #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.1506.08657
openalex publication_date 2015/06/26 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Given an ODE and its perturbation, the Alekseev formula expresses the\nsolutions of the latter in terms related to the former. By exploiting this\nformula and a new concentration inequality for martingale-differences, we\ndevelop a novel approach for analyzing nonlinear Stochastic Approximation (SA).\nThis approach is useful for studying a SA's behaviour close to a Locally\nAsymptotically Stable Equilibrium (LASE) of its limiting ODE; this LASE need\nnot be the limiting ODE's only attractor. As an application, we obtain a new\nconcentration bound for nonlinear SA. That is, given \ε >0 and that the\ncurrent iterate is in a neighbourhood of a LASE, we provide an estimate for i.)\nthe time required to hit the \ε-ball of this LASE, and ii.) the\nprobability that after this time the iterates are indeed within this\n\ε-ball and stay there thereafter. The latter estimate can also be\nviewed as the `lock-in' probability. Compared to related results, our\nconcentration bound is tighter and holds under significantly weaker\nassumptions. In particular, our bound applies even when the stepsizes are not\nsquare-summable. Despite the weaker hypothesis, we show that the celebrated\nKushner-Clark lemma continues to hold. %\n