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

2020/06/01 by Aymeric Dieuleveut, Alain Durmus, Francis Bach · 84 citations
Computer Science · Engineering · Mathematics · #Applied mathematics #Constant (computer programming) #Convex function #Extrapolation #Gradient descent #Iterated function #Markov Chains and Monte Carlo Methods #Markov chain #Mathematical analysis #Mathematical optimization #Mathematics #Quadratic equation #Regular polygon #Sparse and Compressive Sensing Techniques #Statistics #Stochastic Gradient Optimization Techniques #Stochastic gradient descent

paper · pdf · doi:10.1214/19-aos1850

published in The Annals of Statistics 48(3) (Institute of Mathematical Statistics)

openalex publication_date 2020/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We consider the minimization of a strongly convex objective function given access to unbiased estimates of its gradient through stochastic gradient descent (SGD) with constant step size. While the detailed analysis was only performed for quadratic functions, we provide an explicit asymptotic expansion of the moments of the averaged SGD iterates that outlines the dependence on initial conditions, the effect of noise and the step size, as well as the lack of convergence in the general (nonquadratic) case. For this analysis we bring tools from Markov chain theory into the analysis of stochastic gradient. We then show that Richardson–Romberg extrapolation may be used to get closer to the global optimum, and we show empirical improvements of the new extrapolation scheme.

Cited by

• A Defense of the Quadratic Model
• Robust equilibria in continuous games: From strategic to dynamic robustness
• Multi-agent learning under uncertainty: Recurrence vs. concentration
• Large-scale empirical tuning and comparison of default optimizers for variational inference
• Statistical Inference for Linear Functionals of Online Least-squares SGD when t \gtrsim d^1+δ
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent
• A Stochastic Differential Equation Framework for Multi-Objective LLM Interactions: Dynamical Systems Analysis with Code Generation Applications
• SALAD: Self-Adaptive Link Adaptation
• Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds
• A Unifying Framework for Global Optimization: From Theory to Formalization
• Explainable Learning Rate Regimes for Stochastic Optimization
• High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
• An Exponential Averaging Process with Strong Convergence Properties
• Sharp Gaussian approximations for Decentralized Federated Learning
• Randomised Splitting Methods and Stochastic Gradient Descent
• Towards Weaker Variance Assumptions for Stochastic Optimization
• A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression