A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent

By Eduard A. Gorbunov, Filip Hanzely, Peter Richtárik. 2019

171 citations recorded by the source corpus.

In this paper we introduce a unified analysis of a large family of variants of proximal stochastic gradient descent ({\tt SGD}) which so far have required different intuitions, convergence analyses, have different applications, and which have been developed separately in various communities. We show that our framework includes methods with and without the following tricks, and their combinations: variance reduction, importance sampling, mini-batch sampling, quantization, and coordinate sub-sampling. As a by-product, we obtain the first unified theory of {\tt SGD} and randomized coordinate descent ({\tt RCD}) methods, the first unified theory of variance reduced and non-variance-reduced {\tt SGD} methods, and the first unified theory of quantized and non-quantized methods. A key to our approach is a parametric assumption on the iterates and stochastic gradients. In a single theorem we establish a linear convergence result under this assumption and strong-quasi convexity of the loss function. Whenever we recover an existing method as a special case, our theorem gives the best known complexity result. Our approach can be used to motivate the development of new useful methods, and offers pre-proved convergence guarantees. To illustrate the strength of our approach, we develop five new variants of {\tt SGD}, and through numerical experiments demonstrate some of their properties.

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

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “In this subsection we present the main convergence results as presented in Gower et al. (2019) for SGD and in Kovalev et al. (2020); Gorbunov et al. (2020) for L-SVRG.”
Distributed Fixed Point Methods with Compressed Iterates (2019, neutral): “Besides, Assumption 1 is satisﬁed with ρ = γµ and B > 0 in general, see e.g. [19].”
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.”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “While we do not present the convergence rates of the methods here, we shall notice they can be easily obtained using the framework from (Gorbunov et al., 2020).”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, unknown): “gradients by cheaper stochastic estimates [3, 14, 21, 22].”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “(Expected Smoothness) If for all i ∈ [ n ] , f i is convex and L i − smooth, then there exists a constant L ≥ 0 such that for all x ∈ R d and where x ∗ is any minimizer of (1).”
Better Theory for SGD in the Nonconvex World (2020, methodology): “Kovalev et al. (2018) study the same method for spectral distributions and for some of these establish stronger identities of the form E [ ‖xk − x∗‖ ] = α‖x0 − x∗‖, suggesting that the property (9) has the capacity to achieve a perfectly precise mean-square analysis of SGD in this setting.”
Federated Learning Based on Dynamic Regularization (2021, background): “Moreover, there are works that extend analysis of SGD type methods to FL settings (Gorbunov et al., 2020; Khaled et al., 2020b; Li & Richtárik, 2020).”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, background): “Moreover, there are many avenues for extensions, including the use of variable stepsizes or metrics [22,52], the study of convergence rates and development of accelerated variants [104–108], or the design of randomized versions [109–113].”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, methodology): “However, [5] does not capture the best known rates for RCD methods and focuses in orthogonal direction instead – includes non-variance reduced methods.”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, background): “Then, as proven in [19], the value r = max matches the best known convergence rates for these applications, with an exception for some coordinate descent algorithms.”