2020

On the Convergence of SGD with Biased Gradients

Ajalloeian, Ahmad, Stich, Sebastian U.

Understand

We analyze the complexity of biased stochastic gradient methods (SGD), where individual updates are corrupted by deterministic, i.e.

biased error terms.
We derive convergence results for smooth (non-convex) functions and give improved rates under the Polyak-Lojasiewicz condition.
We quantify how the magnitude of the bias impacts the attainable accuracy and the convergence rates (sometimes leading to divergence).

Built on

Introduction to Optimization
Boris T. Polyak · 1987
Earlier work this paper cites.
Nonlinear Programming
Dimitri Bertsekas · 2002
Earlier work this paper cites.
Biased stochastic gradient descent for conditional stochastic optimization
Original
Yifan Hu, Siqi Zhang, Xin Chen, and Niao He · 2002
Earlier work this paper cites.
Introductory Lectures on Convex Optimization - A Basic Course , volume 87 of
Yurii Nesterov · 2004
Earlier work this paper cites.
Smooth optimization with approximate gradient
Alexandre d’Aspremont · 2008
Earlier work this paper cites.
Estimate sequence methods: extensions and approximations
Michel Baes · 2009
Earlier work this paper cites.
Large-scale machine learning with stochastic gradient descent
Léon Bottou · 2010
Earlier work this paper cites.
Stochastic first order methods in smooth convex optimization
Olivier Devolder · 2011
Earlier work this paper cites.
Hogwild: A lock-free approach to parallelizing stochastic gradient descent
Original
Feng Niu, Benjamin Recht, Christopher Re, and Stephen Wright · 2011
Earlier work this paper cites.
Convergence rates of inexact proximal-gradient methods for convex optimization
Original
Mark Schmidt, Nicolas L. Roux, and Francis R. Bach · 2011
Earlier work this paper cites.
Randomized smoothing for stochastic optimization
Original
John C Duchi, Peter L. Bartlett, and Martin J Wainwright · 2012
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Alex Krizhevsky · 2012
Earlier work this paper cites.
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
Original
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach · 2012
Earlier work this paper cites.
First-order methods of smooth convex optimization with inexact oracle
Olivier Devolder, François Glineur, and Yurii Nesterov · 2014
Earlier work this paper cites.
Communication efficient distributed machinelearning with the parameter server
Mu Li, David G. Andersen, Alexander J. Smola, and Kai Yu · 2014
Earlier work this paper cites.
Asynchronous stochastic convex optimization: the noise is in the noise and SGD don’t care
Sorathan Chaturapruek, John C Duchi, and Christopher Ré · 2015
Earlier work this paper cites.

Similar

Coordinate descent converges faster with the Gauss-Southwell rule than random selection
Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke · 2015
Cited alongside, same era.
Highly-smooth zero-th order online optimization
Francis Bach and Vianney Perchet · 2016
Cited alongside, same era.
Communication quantization for data-parallel training of deep neural networks
N. Dryden, T. Moon, S. A. Jacobs, and B. V. Essen · 2016
Cited alongside, same era.
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2016
Cited alongside, same era.
(bandit) convex optimization with biased noisy gradient oracles
Xiaowei Hu, Prashanth L. A., András György, and Csaba Szepesvári · 2016
Cited alongside, same era.
Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition
Hamed Karimi, Julie Nutini, and Mark Schmidt · 2016
Cited alongside, same era.
Universal adversarial perturbations
Original
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard · 2016
Cited alongside, same era.
Parallel coordinate descent methods for big data optimization
Peter Richtárik and Martin Takác · 2016
Cited alongside, same era.
Inexact coordinate descent: Complexity and preconditioning
Rachael Tappenden, Peter Richtárik, and Jacek Gondzio · 2016
Cited alongside, same era.
Sparse communication for distributed gradient descent
Original
Alham Fikri Aji and Kenneth Heafield · 2017
Cited alongside, same era.
QSGD: Communication-efficient SGD via gradient quantization and encoding
Original
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic · 2017
Cited alongside, same era.
ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh · 2017
Cited alongside, same era.

Then

The convergence of sparsified gradient methods
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli · 2018
Later among the works it cites.
Optimization methods for large-scale machine learning
Original
L. Bottou, F. Curtis, and J. Nocedal · 2018
Later among the works it cites.
Stochastic gradient descent with biased but consistent gradient estimators
Original
Jie Chen and Ronny Luss · 2018
Later among the works it cites.
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems
Sai Praneeth Reddy Karimireddy, Sebastian Stich, and Martin Jaggi · 2018
Later among the works it cites.
Deep gradient compression: Reducing the communication bandwidth for distributed training
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally · 2018
Later among the works it cites.
Zeroth-order stochastic variance reduction for nonconvex optimization
Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini · 2018
Later among the works it cites.
Sparsified SGD with memory
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi · 2018
Later among the works it cites.
ATOMO: communication-efficient learning via atomic sparsification
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary B. Charles, Dimitris S. Papailiopoulos, and Stephen Wright · 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.
Efficient greedy coordinate descent for composite problems
Sai Praneeth Karimireddy, Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi · 2019
Later among the works it cites.
Pytorch: An imperative style, high-performance deep learning library
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala · 2019
Later among the works it cites.
Unified optimal analysis of the (stochastic) gradient method
Original
Sebastian U. Stich · 2019
Later among the works it cites.
The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication
Original
Sebastian U. Stich and Sai Praneeth Karimireddy · 2019
Later among the works it cites.
On biased compression for distributed learning
Original
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan · 2020
Closest in time.
Finite-time error bounds for biased stochastic approximation with applications to q-learning
Gang Wang and Georgios B. Giannakis · 2020
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…