### Transport-Entropy inequalities and deviation estimates for stochastic approximation schemes

**Max Fathi**

*(Université Pierre & Marie Curie)*

**Noufel Frikha**

*(Université Paris Diderot)*

#### Abstract

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 in [Frikha, Menozzi, 2012]. 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 bound for stochastic approximation with averaging of trajectories, in particular we prove that averaging a stochastic approximation algorithm with a slow decreasing step sequence gives rise to optimal concentration rate.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-36

Publication Date: July 6, 2013

DOI: 10.1214/EJP.v18-2586

#### References

- A. Alfonsi and A. Kohatsu-Higa and B. Jourdain: Pathwise optimal transport bounds between a one-dimensional diffusion and its Euler scheme. arXiv.org:1209.0576
- Bally, Vlad; Talay, Denis. The law of the Euler scheme for stochastic differential equations. II.
Convergence rate of the density.
*Monte Carlo Methods Appl.*2 (1996), no. 2, 93--128. MR1401964 - F. Barthe and C. Bordenave: Combinatorial optimization over two random point sets. To appear in Séminaire de Probabilités, arXiv.org:1103.2734
- Blower, Gordon; Bolley, François. Concentration of measure on product spaces with applications to Markov
processes.
*Studia Math.*175 (2006), no. 1, 47--72. MR2261699 - Boissard, Emmanuel. Simple bounds for convergence of empirical and occupation measures in
1-Wasserstein distance.
*Electron. J. Probab.*16 (2011), no. 83, 2296--2333. MR2861675 - Bolley, François; Villani, Cédric. Weighted Csiszár-Kullback-Pinsker inequalities and applications to
transportation inequalities.
*Ann. Fac. Sci. Toulouse Math. (6)*14 (2005), no. 3, 331--352. MR2172583 - Bolley, François; Guillin, Arnaud; Villani, Cédric. Quantitative concentration inequalities for empirical measures on
non-compact spaces.
*Probab. Theory Related Fields*137 (2007), no. 3-4, 541--593. MR2280433 - Djellout, H.; Guillin, A.; Wu, L. Transportation cost-information inequalities and applications to random
dynamical systems and diffusions.
*Ann. Probab.*32 (2004), no. 3B, 2702--2732. MR2078555 - Duflo, Marie. Algorithmes stochastiques.
(French) [Stochastic algorithms] Mathématiques & Applications (Berlin) [Mathematics &
Applications], 23.
*Springer-Verlag, Berlin,*1996. xiv+319 pp. ISBN: 3-540-60699-8 MR1612815 - Frikha, Noufel; Menozzi, Stéphane. Concentration bounds for stochastic approximations.
*Electron. Commun. Probab.*17 (2012), no. 47, 15 pp. MR2988393 - Gozlan, Nathael; Léonard, Christian. A large deviation approach to some transportation cost
inequalities.
*Probab. Theory Related Fields*139 (2007), no. 1-2, 235--283. MR2322697 - Gozlan, N.; Léonard, C. Transport inequalities. A survey.
*Markov Process. Related Fields*16 (2010), no. 4, 635--736. MR2895086 - Johnson, W. B.; Schechtman, G.; Zinn, J. Best constants in moment inequalities for linear combinations of
independent and exchangeable random variables.
*Ann. Probab.*13 (1985), no. 1, 234--253. MR0770640 - Kushner, Harold J.; Yin, G. George. Stochastic approximation and recursive algorithms and
applications.
Second edition.
Applications of Mathematics (New York), 35. Stochastic Modelling and Applied Probability.
*Springer-Verlag, New York,*2003. xxii+474 pp. ISBN: 0-387-00894-2 MR1993642 - Laruelle, Sophie; Pagès, Gilles. Stochastic approximation with averaging innovation applied to
finance.
*Monte Carlo Methods Appl.*18 (2012), no. 1, 1--51. MR2908605 - Lemaire, V.; Menozzi, S. On some non asymptotic bounds for the Euler scheme.
*Electron. J. Probab.*15 (2010), no. 53, 1645--1681. MR2735377 - Malrieu, Florent; Talay, Denis. Concentration inequalities for Euler schemes.
*Monte Carlo and quasi-Monte Carlo methods 2004,*355--371,*Springer, Berlin,*2006. MR2208718 - Polyak, B. T.; Juditsky, A. B. Acceleration of stochastic approximation by averaging.
*SIAM J. Control Optim.*30 (1992), no. 4, 838--855. MR1167814 - Robbins, Herbert; Monro, Sutton. A stochastic approximation method.
*Ann. Math. Statistics*22, (1951). 400--407. MR0042668 - Rachev, Svetlozar T.; Rüschendorf, Ludger. Mass transportation problems. Vol. II.
Applications.
Probability and its Applications (New York).
*Springer-Verlag, New York,*1998. xxvi+430 pp. ISBN: 0-387-98352-X MR1619171 - Ruppert, David. Stochastic approximation.
*Handbook of sequential analysis,*503--529, Statist. Textbooks Monogr., 118,*Dekker, New York,*1991. MR1174318 - Talay, Denis; Tubaro, Luciano. Expansion of the global error for numerical schemes solving stochastic
differential equations.
*Stochastic Anal. Appl.*8 (1990), no. 4, 483--509 (1991). MR1091544

This work is licensed under a Creative Commons Attribution 3.0 License.