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

By Aymeric Dieuleveut, Alain Oliviero Durmus, Francis R. Bach. 2017

191 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Repurposing Pretrained Models for Robust Out-of-domain Few-Shot Learning (2021, background): “This approach can be related with the fact that lower stepsizes should be taken for SGD when the gradients are very noisy (Dieuleveut et al., 2020).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “In the case of constant step size, the iterates of serial SGD converge to a limit distribution πη that depends on the step size (Dieuleveut et al., 2017).”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, methodology): “…1 and 2 and Equation (S25) we get, under conditions on the learning rates α, γ similar to the ones in Theorems S4 and S5, that And by induction: From the contraction above, it is easy to derive the existence of a unique stationnary limit distribution: we use Picard ﬁxed point theorem, as in [9].”
Understanding the Role of Momentum in Stochastic Gradient Methods (2019, methodology): “[6, 4] prove many properties of limiting behavior of SGD with constant step size by using tools from Markov chain theory.”
Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling (2018, background): “For more details, see Dieuleveut et al. (2017).”
Batch normalization provably avoids ranks collapse for randomly initialised deep networks (2020, methodology): “First, inspired by [10] and leveraging tools from Markov Chain theory, our main result proves that the rank of linear batch-normalized networks scales with their width as Ω( √ width ) .”
On the Intrinsic Privacy of Stochastic Gradient Descent (2019, background): “Dieuleveut et al. view SGD with constant step size as a homogeneous Markov chain which converges to a stationary distribution in the convex case, but they do not further characterise this distribution [13].”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, methodology): “First, we study the convergence rate of DSG with constant stepsize which is used in many practical applications (Alghunaim and Sayed (2019, 2018); Dieuleveut et al. (2017)).”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, background): “[DDB17] Aymeric Dieuleveut, Alain Durmus, and Francis Bach.”
On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, unknown): “Adapted from Dieuleveut et al. (2019). we will assume that x t has an asymptotic expansion of the form where x ∗ is the desired output, g t ∈ R d is the asymptotic equivalent of x t − x ∗ , and h t = o ( g t ). is k k The key question in extrapolation the following: from the knowledge of x t for…”
On Learning Rates and Schrödinger Operators (2020, background): “Our work is motivated in part by the recent progress on Langevin dynamics, in particular in nonconvex settings [Vil09, Pav14, HKN04, BGK05].”
Communication trade-offs for Local-SGD with large step size (2019, methodology): “This type of analysis has been successfully used recently [10, 15, 25, 26].”