×

A concentration bound for stochastic approximation via Alekseev’s formula. (English) Zbl 1442.62187

Summary: 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 \(\epsilon > 0\) and that the current iterate is in a neighborhood 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 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.

MSC:

62L20 Stochastic approximation
93-08 Computational methods for problems pertaining to systems and control theory
60G42 Martingales with discrete parameter
34D10 Perturbations of ordinary differential equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alekseev VM (1961) An estimate for the perturbations of the solutions of ordinary differential equations (Russian). Westnik Moskov Univ. Ser. 1:28-36.Google Scholar
[2] Arthur WB (1994) Increasing Returns and Path Dependence in the Economy (University of Michigan Press, Ann Arbor).Google Scholar
[3] Artur B, Ermol’ev YM, Kaniovskii YM (1983) A generalized urn problem and its applications. Cybernetics Systems Anal. 19(1):61-71.Google Scholar · Zbl 0534.90049
[4] Bainov DD, Simeonov PS (1992) Integral Inequalities and Applications (Springer, Berlin).Google Scholar · Zbl 0759.26012
[5] Benaïm M (1999) Dynamics of stochastic approximation algorithms. Seminaire de Probabilites XXXIII (Springer, New York), 1-68.Google Scholar · Zbl 0955.62085
[6] Benveniste A, Métivier M, Priouret P (1990) Adaptive Algorithms and Stochastic Approximations (Springer, Berlin).Google Scholar · Zbl 0752.93073
[7] Borkar VS (2008) Stochastic Approximation (Hindustan Publishing Agency, New Dehli, India).Google Scholar · Zbl 1159.60002
[8] Borkar VS, Pattathil S (2018) Concentration bounds for two time scale stochastic approximation. arXiv:1806.10798.Google Scholar
[9] Bovier A, den Hollander F (2016) Metastability: A Potential-Theoretic Approach, Grundlehren der mathematischen Wissenschaften, vol. 351 (Springer, New York).Google Scholar
[10] Brauer F (1966) Perturbations of nonlinear systems of differential equations. J. Math. Anal. Appl. 14(2):198-206.Google Scholar · Zbl 0156.09805
[11] Breiman L (1992) Probability, 1968 reprint ed. (SIAM, Philadelphia).Google Scholar
[12] Chen HF (2002) Stochastic Approximation and its Applications (Kluwer Academic, Dordrecht, Netherlands).Google Scholar · Zbl 1008.62071
[13] Dalal G, Szörényi B, Thoppe G, Mannor S (2018a) Finite sample analyses for TD (0) with function approximation. Cohn A, ed. Proc. 32nd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 6144-6160.Google Scholar
[14] Dalal G, Thoppe G, Szörényi B, Mannor S (2018b) Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. Proc. Machine Learn. Res. 75:1199-1233.Google Scholar
[15] Duflo M (1997) Random Iterative Models (Springer, Berlin).Google Scholar · Zbl 0868.62069
[16] Fathi M, Frikha N (2013) Transport-entropy inequalities and deviation estimates for stochastic approximation schemes. Electronic J. Probab. 18:1-36.Google Scholar · Zbl 1284.60137
[17] Freidlin MI, Wentzell AD (2014) Random Perturbations of Dynamical Systems (Springer, New York).Google Scholar
[18] Frikha N, Menozzi S (2012) Concentration bounds for stochastic approximations. Electronic Comm. Probab. 17:1-15.Google Scholar · Zbl 1252.60065
[19] Gelfand SB, Mitter SK (1991) Recursive stochastic algorithms for global optimization in Rd. SIAM J. Control Optim. 29(5):999-1018.Google Scholar · Zbl 0753.65051
[20] Herrmann S, Imkeller P, Pavlyukevich I, Peithmann D (2013) Stochastic Resonance: A Mathematical Approach in the Small Noise Limit, Mathematical Surveys and Monographs, vol. 194 (American Mathematical Society, Providence, RI).Google Scholar
[21] Kamal S (2010) On the convergence, lock-in probability, and sample complexity of stochastic approximation. SIAM J. Control Optim. 48(8):5178-5192.Google Scholar · Zbl 1208.62128
[22] Khalil HK (2001) Nonlinear Systems, 3rd ed. (Prentice Hall, Upper Saddle River, NJ).Google Scholar
[23] Krasovskii NN (1963) Stability of Motion (Stanford University Press, Stanford, CA).Google Scholar · Zbl 0109.06001
[24] Kumar B, Borkar V, Shetty A (2018) Bounds for tracking error in constant stepsize stochastic approximation. arXiv:1802.07759.Google Scholar
[25] Kushner HJ, Clark DS (1978) Stochastic Approximation Methods for Constrained and Unconstrained Systems (Springer, New York).Google Scholar · Zbl 0381.60004
[26] Kushner HJ, Yin G (2003) Stochastic Approximation and Recursive Algorithms and Applications, 2nd ed. (Springer, New York).Google Scholar · Zbl 1026.62084
[27] Lakshmikantham V, Deo S (1998) Method of Variation of Parameters for Dynamic Systems (CRC Press, Boca Raton, FL).Google Scholar · Zbl 0920.34001
[28] Liu Q, Watbled F (2009) Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment. Stochastic Processes Their Appl. 119(10):3101-3132.Google Scholar · Zbl 1177.60043
[29] Miclo L (1992a) Recuit simulé sans potentiel sur un ensemble fini. Séminaire Probabilités Strasbourg 26:47-60.Google Scholar · Zbl 0770.60090
[30] Miclo L (1992b) Recuit simulé sans potentiel sur une variété riemannienne compacte. Stochastics Stochastic Rep. 41(1/2):23-56.Google Scholar · Zbl 0758.60033
[31] Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838-855.Google Scholar · Zbl 0762.62022
[32] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400-407.Google Scholar · Zbl 0054.05901
[33] Teschl G (2012) Ordinary Differential Equations and Dynamical Systems, Graduate Studies in Mathematics, vol. 140 (American Mathematical Society, Providence, RI).Google Scholar · Zbl 1263.34002
[34] Vapnik V (2013) The Nature of Statistical Learning Theory (Springer Science & Business Media, New York). · Zbl 0934.62009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.