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

Abstract

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.

arXiv comment38 pages, 4 figures, 2 tables

References in corpus (14)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Scaling Distributed Machine Learning with In-Network Aggregation
• Distributed Learning with Compressed Gradient Differences
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Stochastic Dual Ascent for Solving Linear Systems
• SEGA: Variance Reduction via Gradient Sketching
• SGD: General Analysis and Improved Rates
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• Coordinate Descent Face-Off: Primal or Dual?

Cited by in corpus (11)

• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Local SGD: Unified Theory and New Efficient Methods
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Convex optimization based on global lower second-order models
• About some works of Boris Polyak on convergence of gradient methods and their development
• The Wasserstein Proximal Gradient Algorithm
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning