A Concentration Bound for Stochastic Approximation via Alekseev’s Formula

References

• 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
• Arthur WB (1994) Increasing Returns and Path Dependence in the Economy (University of Michigan Press, Ann Arbor).Google Scholar
• Artur B, Ermol’ev YM, Kaniovskii YM (1983) A generalized urn problem and its applications. Cybernetics Systems Anal. 19(1):61–71.Google Scholar
• Bainov DD, Simeonov PS (1992) Integral Inequalities and Applications (Springer, Berlin).Google Scholar
• Benaïm M (1999) Dynamics of stochastic approximation algorithms. Seminaire de Probabilites XXXIII (Springer, New York), 1–68.Google Scholar
• Benveniste A, Métivier M, Priouret P (1990) Adaptive Algorithms and Stochastic Approximations (Springer, Berlin).Google Scholar
• Borkar VS (2008) Stochastic Approximation (Hindustan Publishing Agency, New Dehli, India).Google Scholar
• Borkar VS, Pattathil S (2018) Concentration bounds for two time scale stochastic approximation. arXiv:1806.10798.Google Scholar
• Bovier A, den Hollander F (2016) Metastability: A Potential-Theoretic Approach, Grundlehren der mathematischen Wissenschaften, vol. 351 (Springer, New York).Google Scholar
• Brauer F (1966) Perturbations of nonlinear systems of differential equations. J. Math. Anal. Appl. 14(2):198–206.Google Scholar
• Breiman L (1992) Probability, 1968 reprint ed. (SIAM, Philadelphia).Google Scholar
• Chen HF (2002) Stochastic Approximation and its Applications (Kluwer Academic, Dordrecht, Netherlands).Google Scholar
• 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
• 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
• Duflo M (1997) Random Iterative Models (Springer, Berlin).Google Scholar
• Fathi M, Frikha N (2013) Transport-entropy inequalities and deviation estimates for stochastic approximation schemes. Electronic J. Probab. 18:1–36.Google Scholar
• Freidlin MI, Wentzell AD (2014) Random Perturbations of Dynamical Systems (Springer, New York).Google Scholar
• Frikha N, Menozzi S (2012) Concentration bounds for stochastic approximations. Electronic Comm. Probab. 17:1–15.Google Scholar
• Gelfand SB, Mitter SK (1991) Recursive stochastic algorithms for global optimization in Rd. SIAM J. Control Optim. 29(5):999–1018.Google Scholar
• 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
• 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
• Khalil HK (2001) Nonlinear Systems, 3rd ed. (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Krasovskii NN (1963) Stability of Motion (Stanford University Press, Stanford, CA).Google Scholar
• Kumar B, Borkar V, Shetty A (2018) Bounds for tracking error in constant stepsize stochastic approximation. arXiv:1802.07759.Google Scholar
• Kushner HJ, Clark DS (1978) Stochastic Approximation Methods for Constrained and Unconstrained Systems (Springer, New York).Google Scholar
• Kushner HJ, Yin G (2003) Stochastic Approximation and Recursive Algorithms and Applications, 2nd ed. (Springer, New York).Google Scholar
• Lakshmikantham V, Deo S (1998) Method of Variation of Parameters for Dynamic Systems (CRC Press, Boca Raton, FL).Google Scholar
• 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
• Miclo L (1992a) Recuit simulé sans potentiel sur un ensemble fini. Séminaire Probabilités Strasbourg 26:47–60.Google Scholar
• Miclo L (1992b) Recuit simulé sans potentiel sur une variété riemannienne compacte. Stochastics Stochastic Rep. 41(1/2):23–56.Google Scholar
• Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838–855.Google Scholar
• Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Google Scholar
• Teschl G (2012) Ordinary Differential Equations and Dynamical Systems, Graduate Studies in Mathematics, vol. 140 (American Mathematical Society, Providence, RI).Google Scholar
• Vapnik V (2013) The Nature of Statistical Learning Theory (Springer Science & Business Media, New York).Google Scholar