Accelerated Sparsified SGD with Error Feedback
Preprint
Abstract
A stochastic gradient method for synchronous distributed optimization is studied. For reducing communication cost, we particularly focus on utilization of compression of communicated gradients. Several work has shown that {\it{sparsified}} stochastic gradient descent method (SGD) with {\it{error feedback}} asymptotically achieves the same rate as (non-sparsified) parallel SGD. However, from a viewpoint of non-asymptotic behavior, the compression error may cause slower convergence than non-sparsified SGD in early iterations. This is problematic in practical situations since early stopping is often adopted to maximize the generalization ability of learned models. For improving the previous results, we propose and theoretically analyse a sparsified stochastic gradient method with error feedback scheme combined with {\it{Nesterov's acceleration}}. It is shown that the necessary per iteration communication cost for maintaining the same rate as vanilla SGD can be smaller than non-accelerated methods in convex and even in nonconvex optimization problems. This indicates that our proposed method makes a better use of compressed information than previous methods. Numerical experiments are provided and empirically validates our theoretical findings.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Asynchronous Decentralized Accelerated Stochastic Gradient DescentIEEE Journal on Selected Areas in Information Theory, 2021
- A Distributed Synchronous SGD Algorithm with Global Top-k Sparsification for Low Bandwidth Networks2019
- Sparse Communication for Distributed Gradient Descent2017
- On the Convergence of Decentralized Gradient DescentSIAM Journal on Optimization, 2016
- Accelerated gradient methods for nonconvex nonlinear and stochastic programmingMathematical Programming, 2015
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network ScalingIEEE Transactions on Automatic Control, 2011
- Distributed Subgradient Methods for Multi-Agent OptimizationIEEE Transactions on Automatic Control, 2009