SGD: General Analysis and Improved Rates

By Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtárik. 2019

484 citations recorded by the source corpus.

We propose a general yet simple theorem describing the convergence of SGD under the arbitrary sampling paradigm. Our theorem describes the convergence of an infinite array of variants of SGD, each of which is associated with a specific probability law governing the data selection rule used to form mini-batches. This is the first time such an analysis is performed, and most of our variants of SGD were never explicitly considered in the literature before. Our analysis relies on the recently introduced notion of expected smoothness and does not rely on a uniform bound on the variance of the stochastic gradients. By specializing our theorem to different mini-batching strategies, such as sampling with replacement and independent sampling, we derive exact expressions for the stepsize as a function of the mini-batch size. With this we can also determine the mini-batch size that optimizes the total complexity, and show explicitly that as the variance of the stochastic gradient evaluated at the minimum grows, so does the optimal mini-batch size. For zero variance, the optimal mini-batch size is one. Moreover, we prove insightful stepsize-switching rules which describe when one should switch from a constant to a decreasing stepsize regime.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “While this choice yields fast convergence to the neighborhood of a minimizer, two main problems arise: (a) the optimal � depends on (often unknown) problem parameters — hence often requires heavy tuning ; and (b) it cannot be guaranteed that X ⇤ is reached in the limit [13, 16, 15].”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “…a recent line work that these assumptions might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel and…”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1978; 1983; Nemirovski et al., 2009; Hardt et al., 2016; Gower et al., 2019; 2020; Loizou et al., 2020) is the workhorse for training supervised machine learning problems.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “For the convergence analysis of SGD on smooth convex functions it is typically enough to assume a bound on the noise at the optimum only (Needell et al., 2016; Bottou et al., 2018; Gower et al., 2019; Stich, 2019a).”
Distributed Fixed Point Methods with Compressed Iterates (2019, background): “Finally, Assumption 1 is satisﬁed with ρ = γµ and B > 0 in general, see e.g. [20].”
DeltaGrad: Rapid retraining of machine learning models (2020, neutral): “See e.g., (Gladyshev, 1965; Amari, 1967; Kul’chitskiy & Mozgovoy, 1992; Bert-sekas & Tsitsiklis, 1996; Moulines & Bach, 2011; Karimi et al., 2016; Bottou et al., 2018; Gorbunov et al., 2019; Gower et al., 2019), etc, and references therein.”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, background): “…that it is satisﬁed on each node m P r M s with h “ f m and distribution D m , and we analogously de-ﬁne Assumption 3 holds, for example, for ﬁnite-sum optimization problems with uniform sampling and permits direct extensions to more general settings such as expected smoothness Gower et al. (2019).”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “This mechanism is similar in spirit to how the recently proposed loopless variants of SVRG Hofmann et al. (2015); Kovalev et al. (2020) work in comparison with the original SVRG Johnson & Zhang (2013a); Xiao & Zhang (2014). Once the penalty is sampled by our method, the resultant SGD step can be int”
An Exponential Learning Rate Schedule for Deep Learning (2019, neutral): “1 of Gower et al. (2019), for sufficiently large t, we have E ‖wt −w∗‖2 = O( η Bλ ).”
Meta Learning on a Sequence of Imbalanced Domains with Difficulty Awareness (2021, methodology): “standard SGD analysis [24], we define the convergence speed of meta training as the shrinkage of distance to optimal parameters θ∗ between two consecutive iterations”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “A common iterative approach to solve (1) when X = R d is stochastic gradient descent (SGD) (Robbins & Monro, 1951; Gower et al., 2019), iterates are updated in the negative direction of a gradient computed from a single realization of ξ .”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “The analysis proposed in [21] recovers the linear convergence rate of sketch and project method (Theorem 1) as special case.”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, methodology): “In such a case, Algorithm 7 becomes SGD-AS [5], and we recover its tight convergence rate.”
Better Theory for SGD in the Nonconvex World (2020, methodology): “In the rather general arbitrary sampling paradigm (Gower et al., 2019), one may choose an arbitrary random subset S ⊆ [ n ] of examples, and subsequently g ( x ) is assembled from the information stored in the gradients ∇ f i ( x ) for i ∈ S only.”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “Closely related is the refined notion of expected smoothness, see the discussions in (Gower et al., 2018, 2019).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “5) and many papers devoted to the understanding of its convergence behavior in different applications and under different assumptions on the functions fi [137, 136, 81, 177, 170, 141, 68, 194].”