Deviation inequalities for stochastic approximation by averaging

DOI10.1016/J.SPA.2022.07.002zbMATH Open1502.60055arXiv2102.08685OpenAlexW3130172249WikidataQ114130694 ScholiaQ114130694MaRDI QIDQ2169079FDOQ2169079

Authors: Xiequan Fan, Pierre Alquier, Paul Doukhan 

Publication date: 29 August 2022

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: We introduce a class of Markov chains, that contains the model of stochastic approximation by averaging and non-averaging. Using martingale approximation method, we establish various deviation inequalities for separately Lipschitz functions of such a chain, with different moment conditions on some dominating random variables of martingale differences.Finally, we apply these inequalities to the stochastic approximation by averaging and empirical risk minimisation.

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

Recommendations

• Some results about averaging in stochastic approximation
• scientific article; zbMATH DE number 1293593
• On stochastic approximation procedures with averaging
• On a stochastic approximation procedure based on averaging
• On extensions of Polyak's averaging approach to stochastic approximation
• Deviation Inequalities for the Estimator of Linear Parameter in Stochastic Processes

zbMATH Keywords

martingalesempirical risk minimizationiterated random functionsdeviation inequalitiesstochastic approximation by averaging

Mathematics Subject Classification ID

Large deviations (60F10) Inequalities; stochastic orderings (60E15) Martingales with discrete parameter (60G42) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Prediction of time series by statistical learning: general losses and fast rates
• Acceleration of Stochastic Approximation by Averaging
• A general class of exponential inequalities for martingales and ratios
• Limit theory for moderate deviations from a unit root
• Towards a unified asymptotic theory for autoregression
• Regression Theory for Near-Integrated Time Series
• A Bernstein type inequality and moderate deviations for weakly dependent sequences
• Estimates for the distribution of sums and maxima of sums of random variables without the Cramér condition
• Moment inequalities for sums of dependent random variables under projective conditions
• Large deviations for martingales.
• Large deviations of sums of independent random variables
• Iterated Random Functions
• Hoeffding's inequality for supermartingales
• On McDiarmid's concentration inequality
• Nonparametric time series prediction through adaptive model selection
• Large and moderate deviations for the left random walk on \(GL_d(\mathbb{R})\)
• Model selection for weakly dependent time series forecasting
• Some probabilistic inequalities for martingales
• Deviation inequalities for martingales with applications
• Deviation inequalities for separately Lipschitz functionals of iterated random functions
• Best possible bounds of the von Bahr-Esseen type
• Exponential inequalities for nonstationary Markov chains
• Fast learning from \(\alpha\)-mixing observations
• High-dimensional VAR with low-rank transition
• Deviation inequalities for separately Lipschitz functionals of composition of random functions

Cited In (2)

• Asymptotic behavior of average \(L_p\)-discrepancies
• Transport-entropy inequalities and deviation estimates for stochastic approximation schemes

This page was built for publication: Deviation inequalities for stochastic approximation by averaging

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