Bridging the gap between constant step size stochastic gradient descent and Markov chains

DOI10.1214/19-AOS1850zbMath1454.62242arXiv1707.06386MaRDI QIDQ2196224

Alain Durmus, Francis Bach, Aymeric Dieuleveut

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainsstochastic gradient descent

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Stochastic programming (90C15) Stochastic approximation (62L20) Stochastic learning and adaptive control (93E35)

Related Items

Some Limit Properties of Markov Chains Induced by Recursive Stochastic Algorithms, Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates, Unnamed Item, On sampling from a log-concave density using kinetic Langevin diffusions, An iteratively regularized stochastic gradient method for estimating a random parameter in a stochastic PDE. A variational inequality approach, Bayesian Inverse Problems Are Usually Well-Posed, Unnamed Item, Unnamed Item, A new regularized stochastic approximation framework for stochastic inverse problems, Statistical Analysis of Fixed Mini-Batch Gradient Descent Estimator, High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling, Estimation and inference by stochastic optimization, Unnamed Item, Unnamed Item, Analysis of stochastic gradient descent in continuous time, A regularized stochastic subgradient projection method for an optimal control problem in a stochastic partial differential equation, Dimension independent excess risk by stochastic gradient descent, Unnamed Item, Convergence of Recursive Stochastic Algorithms Using Wasserstein Divergence, On the Effectiveness of Richardson Extrapolation in Data Science, Hausdorff dimension, heavy tails, and generalization in neural networks*

Uses Software

• Pegasos
• ImageNet
• AlexNet

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonparametric stochastic approximation with large step-sizes
• An optimal method for stochastic composite optimization
• Pegasos: primal estimated sub-gradient solver for SVM
• On recursive estimation for time varying autoregressive processes
• Théorèmes de convergence presque sure pour une classe d'algorithmes stochastiques à pas decroissant
• Stochastic approximation methods for constrained and unconstrained systems
• About the multidimensional competitive learning vector quantization algorithm with constant gain
• Asymptotic bias of stochastic gradient search
• Statistical inference for model parameters in stochastic gradient descent
• Nonasymptotic convergence analysis for the unadjusted Langevin algorithm
• Confidence level solutions for stochastic programming
• A Liapounov bound for solutions of the Poisson equation
• Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise.
• High Order Numerical Approximation of the Invariant Measure of Ergodic SDEs
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
• Applications of a Kushner and Clark lemma to general classes of stochastic algorithms
• Markov Chains and Stochastic Stability
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stochastic Minimization with Constant Step-Size: Asymptotic Laws
• Acceleration of Stochastic Approximation by Averaging
• Analysis of recursive stochastic algorithms
• Convergence of stochastic algorithms: from the Kushner–Clark theorem to the Lyapounov functional method
• A remark on the stability of the l.m.s. tracking algorithm
• On a Perturbation Approach for the Analysis of Stochastic Tracking Algorithms
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
• Asymptotic Behavior of a Markovian Stochastic Algorithm with Constant Step
• A Dynamical System Approach to Stochastic Approximations
• Co-Coercivity and Its Role in the Convergence of Iterative Schemes for Solving Variational Inequalities
• Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
• Expansion of the global error for numerical schemes solving stochastic differential equations
• A Stochastic Approximation Method
• Ordinary Differential Equations
• Optimal Transport
• Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm