Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains

Abstract

We consider the minimization of an 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 (non-quadratic) 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.

References in corpus (7)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Stochastic Gradient Descent as Approximate Bayesian Inference
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• A Variational Analysis of Stochastic Gradient Algorithms
• Convergence diagnostics for stochastic gradient descent with constant step size
• Why do partitions occur in Faa di Bruno's chain rule for higher derivatives?

Cited by in corpus (20)

• Stochastic Gradient Descent as Approximate Bayesian Inference
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Communication trade-offs for synchronized distributed SGD with large step size
• A generalization of regularized dual averaging and its dynamics
• On Learning Rates and Schrödinger Operators
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Reducing the variance in online optimization by transporting past gradients
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Approximate Newton-based statistical inference using only stochastic gradients
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms
• Error Lower Bounds of Constant Step-size Stochastic Gradient Descent
• Error Bounds and Applications for Stochastic Approximation with Non-Decaying Gain
• On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
• Variance-Reduced Accelerated First-order Methods: Central Limit Theorems and Confidence Statements
• Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
• Mixing of Stochastic Accelerated Gradient Descent
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• Gen-Oja: A Two-time-scale approach for Streaming CCA
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization