Concentration bounds for stochastic approximations

Noufel Frikha (Université Denis Diderot)
Stéphane Menozzi (Universite d'Évry Val d'Essonne)

Abstract


We obtain non asymptotic concentration bounds for two kinds of stochastic approximations. We first consider the deviations between the expectation of a given function of an Euler like discretization scheme of some diffusion process at a fixed deterministic time and its empirical mean obtained by the Monte Carlo procedure. We then give some estimates concerning the deviation between the value at a given time-step of a stochastic approximation algorithm and its target. Under suitable assumptions both concentration bounds turn out to be Gaussian. The key tool consists in exploiting accurately the concentration properties of the increments of the schemes. Also, no specific non-degeneracy conditions are assumed.

An Erratum is available in ECP volume 17 paper number 60.


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

Pages: 1-15

Publication Date: October 7, 2012

DOI: 10.1214/ECP.v17-1952

References

  • Bally, V.; Talay, D. The law of the Euler scheme for stochastic differential equations. I. Convergence rate of the distribution function. Probab. Theory Related Fields 104 (1996), no. 1, 43--60. MR1367666
  • Bhattacharya, R. N.; Ranga Rao, R. Normal approximation and asymptotic expansions. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, 1976. xiv+274 pp. MR0436272
  • 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; 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
  • 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
  • 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
  • Konakov, Valentin; Mammen, Enno. Local limit theorems for transition densities of Markov chains converging to diffusions. Probab. Theory Related Fields 117 (2000), no. 4, 551--587. MR1777133
  • Konakov, Valentin; Mammen, Enno. Local approximations of Markov random walks by diffusions. Stochastic Process. Appl. 96 (2001), no. 1, 73--98. MR1856681
  • Konakov, Valentin; Mammen, Enno. Edgeworth type expansions for Euler schemes for stochastic differential equations. Monte Carlo Methods Appl. 8 (2002), no. 3, 271--285. MR1931967
  • 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
  • Shiryaev, A. N. Probability. Translated from the first (1980) Russian edition by R. P. Boas. Second edition. Graduate Texts in Mathematics, 95. Springer-Verlag, New York, 1996. xvi+623 pp. ISBN: 0-387-94549-0 MR1368405
  • 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
Bookmark and Share


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