Transport-entropy inequalities and deviation estimates for stochastic approximation schemes

DOI10.1214/EJP.V18-2586zbMATH Open1284.60137arXiv1301.7740OpenAlexW1989260982MaRDI QIDQ388949FDOQ388949

Authors: Max Fathi, Noufel Frikha 

Publication date: 17 January 2014

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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 work available at URL: https://arxiv.org/abs/1301.7740

Recommendations

• Concentration bounds for stochastic approximations
• Deviation inequalities for stochastic approximation by averaging
• Concentration inequalities for Euler schemes
• On some non asymptotic bounds for the Euler scheme
• Weak transport inequalities and applications to exponential and oracle inequalities

zbMATH Keywords

Euler schemedeviation boundsstochastic approximation algorithmsstochastic approximation with averagingtransportation-entropy inequalities

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)

Cited In (7)

• Concentration bounds for temporal difference learning with linear function approximation: the case of batch data and uniform sampling
• Multi-level stochastic approximation algorithms
• Free transport-entropy inequalities for non-convex potentials and application to concentration for random matrices
• Concentration bounds for stochastic approximations
• Central limit theorems for entropy-regularized optimal transport on finite spaces and statistical applications
• A multi-step Richardson-Romberg extrapolation method for stochastic approximation
• A concentration bound for stochastic approximation via Alekseev's formula

This page was built for publication: Transport-entropy inequalities and deviation estimates for stochastic approximation schemes

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