2019

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

Gorbunov, Eduard, Hanzely, Filip, Richtárik, Peter

Understand

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.

Built on

A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
Robust stochastic approximation approach to stochastic programming
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro · 2009
Earlier work this paper cites.
LibSVM: A library for support vector machines
Chih-Chung Chang and Chih-Jen Lin · 2011
Earlier work this paper cites.
Efficiency of coordinate descent methods on huge-scale optimization problems
Yurii Nesterov · 2012
Earlier work this paper cites.
A stochastic gradient method with an exponential convergence rate for finite training sets
Nicolas Le Roux, Mark Schmidt, and Francis Bach · 2012
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Stochastic dual coordinate ascent methods for regularized loss
Shai Shalev-Shwartz and Tong Zhang · 2013
Earlier work this paper cites.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien · 2014
Earlier work this paper cites.
1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu · 2014
Earlier work this paper cites.
Understanding machine learning: from theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Earlier work this paper cites.
Communication-efficient distributed optimization using an approximate Newton-type method
Ohad Shamir, Nati Srebro, and Tong Zhang · 2014
Earlier work this paper cites.
Randomized iterative methods for linear systems
Robert M Gower and Peter Richtárik · 2015
Earlier work this paper cites.
Stochastic dual ascent for solving linear systems
Original
Robert M Gower and Peter Richtárik · 2015
Earlier work this paper cites.
Deep learning with limited numerical precision
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan · 2015
Earlier work this paper cites.
Variance reduced stochastic gradient descent with neighbors
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams · 2015
Earlier work this paper cites.

Similar

Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Deanna Needell, Nathan Srebro, and Rachel Ward · 2015
Cited alongside, same era.
Quartz: Randomized dual coordinate ascent with arbitrary sampling
Zheng Qu, Peter Richtárik, and Tong Zhang · 2015
Cited alongside, same era.
Stochastic optimization with importance sampling for regularized loss minimization
Peilin Zhao and Tong Zhang · 2015
Cited alongside, same era.
Mini-batch semi-stochastic gradient descent in the proximal setting
Jakub Konečný, Jie Lu, Peter Richtárik, and Martin Takáč · 2016
Cited alongside, same era.
Coordinate descent with arbitrary sampling I: Algorithms and complexity
Zheng Qu and Peter Richtárik · 2016
Cited alongside, same era.
On optimal probabilities in stochastic coordinate descent methods
Peter Richtárik and Martin Takáč · 2016
Cited alongside, same era.
QSGD: Communication-efficient SGD via gradient quantization and encoding
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic · 2017
Cited alongside, same era.
Random gradient-free minimization of convex functions
Yurii Nesterov · 2017
Cited alongside, same era.
SARAH: A novel method for machine learning problems using stochastic recursive gradient
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč · 2017
Cited alongside, same era.
Stochastic reformulations of linear systems: algorithms and convergence theory
Original
Peter Richtárik and Martin Takáč · 2017
Cited alongside, same era.
Terngrad: Ternary gradients to reduce communication in distributed deep learning
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li · 2017
Cited alongside, same era.
ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang · 2017
Cited alongside, same era.

Then

SEGA: Variance reduction via gradient sketching
Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik · 2018
Later among the works it cites.
Randomized distributed mean estimation: accuracy vs communication
Jakub Konečný and Peter Richtárik · 2018
Later among the works it cites.
SGD and Hogwild! Convergence without the bounded gradients assumption
Lam Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takáč · 2018
Later among the works it cites.
Gradient sparsification for communication-efficient distributed optimization
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang · 2018
Later among the works it cites.
SGD: General analysis and improved rates
Original
Robert M Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik · 2019
Closest in time.
Accelerated coordinate descent with arbitrary sampling and best rates for minibatches
Filip Hanzely and Peter Richtárik · 2019
Closest in time.
Stochastic distributed learning with gradient quantization and variance reduction
Original
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik · 2019
Closest in time.
Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop
Original
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik · 2019
Closest in time.
Estimate sequences for variance-reduced stochastic composite optimization
Original
Andrei Kulunchakov and Julien Mairal · 2019
Closest in time.
Distributed learning with compressed gradient differences
Original
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik · 2019
Closest in time.
99% of parallel optimization is inevitably a waste of time
Original
Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik · 2019
Closest in time.
Scaling distributed machine learning with in-network aggregation
Original
Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik · 2019
Closest in time.
Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization
Original
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen · 2019
Closest in time.
Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron
Sharan Vaswani, Francis Bach, and Mark Schmidt · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…