Concentration bounds for stochastic approximations

DOI10.1214/ECP.V17-1952MaRDI QIDQ456280zbMATH OpenFDO

Authors Noufel Frikha, Stéphane Menozzi

Publication date 23 October 2012

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3730

zbMATH Keywords

Euler schemestochastic approximation algorithmsGaussian concentrationnon asymptotic bounds

Mathematics Subject Classification ID

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

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 the Euler 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. For the first case, as opposed to the previous work of Lemaire and Menozzi (EJP, 2010), we do not have any systematic bias in our estimates. Also, no specific non-degeneracy conditions are assumed.

Recommendations

• On some non asymptotic bounds for the Euler scheme
• Transport-entropy inequalities and deviation estimates for stochastic approximation schemes
• A concentration bound for contractive stochastic approximation
• Stochastic Approximation and Large Deviations: Upper Bounds and <scp>w.p.1</scp> Convergence
• A concentration bound for stochastic approximation via Alekseev's formula

Cited in

(22)

• Sharp non-asymptotic concentration inequalities for the approximation of the invariant distribution of a diffusion
• Conditional quantile sequential estimation for stochastic codes
• Non-asymptotic error bounds for the multilevel Monte Carlo Euler method applied to SDEs with constant diffusion coefficient
• Non-asymptotic Gaussian estimates for the recursive approximation of the invariant distribution of a diffusion
• Concentration of Contractive Stochastic Approximation and Reinforcement Learning
• Approximation of the invariant distribution for a class of ergodic jump diffusions
• Asymptotic behavior of constrained stochastic approximations via the theory of large deviations
• Concentration bounds for temporal difference learning with linear function approximation: the case of batch data and uniform sampling
• A concentration bound for contractive stochastic approximation
• Multi-level stochastic approximation algorithms
• Transport-entropy inequalities and deviation estimates for stochastic approximation schemes
• An improved probability bound for the approximate S-lemma
• Corrigendum to: ``A concentration bound for contractive stochastic approximation
• scientific article; zbMATH DE number 4113792 (Why is no real title available?)
• On the Lock-in Probability of Stochastic Approximation
• A multi-step Richardson-Romberg extrapolation method for stochastic approximation
• On some non asymptotic bounds for the Euler scheme
• Optimal bounds in normal approximation for many interacting worlds
• Unifying presampling via concentration bounds
• A constructive proof of a concentration bound for real-valued random variables
• A concentration bound for stochastic approximation via Alekseev's formula
• Recursive estimation in a class of models of deformation

This page was built for publication: Concentration bounds for stochastic approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456280)