Accelerated Sparsified SGD with Error Feedback

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.

arXiv comment25 pages, 16 figures

References in corpus (15)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Revisiting Distributed Synchronous SGD
• Optimal Distributed Online Prediction using Mini-Batches
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Asynchronous Stochastic Gradient Descent with Delay Compensation
• Communication Complexity of Distributed Convex Learning and Optimization
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization
• Optimal Algorithms for Distributed Optimization
• Asynchronous decentralized accelerated stochastic gradient descent