Transport-entropy inequalities and deviation estimates for stochastic approximation schemes. (English) Zbl 1284.60137

Summary: We obtain new transport-entropy inequalities and, as a by-product, new deviation estimates for the laws of two kinds of discrete stochastic approximation schemes. The first one refers to the law of an Euler-like discretization scheme of a diffusion process at a fixed deterministic date and the second one concerns the law of a stochastic approximation algorithm at a given time-step. Our results notably improve and complete those obtained by N. Frikha and S. Menozzi [Electron. Commun. Probab. 17, Paper No. 47, 15 p. (2012; Zbl 1252.60065)]. The key point is to properly quantify the contribution of the diffusion term to the concentration regime. We also derive a general non-asymptotic deviation bound for the difference between a function of the trajectory of a continuous Euler scheme associated to a diffusion process and its mean. Finally, we obtain non-asymptotic bounds for stochastic approximations with averaging of trajectories, in particular, we prove that averaging a stochastic approximation algorithm with a slow decreasing step sequence gives rise to an optimal concentration rate.


60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
65C30 Numerical solutions to stochastic differential and integral equations
65C05 Monte Carlo methods


Zbl 1252.60065
Full Text: DOI arXiv