Robust and Communication-Efficient Collaborative Learning
arXiv:1907.10595
Abstract
We consider a decentralized learning problem, where a set of computing nodes aim at solving a non-convex optimization problem collaboratively. It is well-known that decentralized optimization schemes face two major system bottlenecks: stragglers' delay and communication overhead. In this paper, we tackle these bottlenecks by proposing a novel decentralized and gradient-based optimization algorithm named as QuanTimed-DSGD. Our algorithm stands on two main ideas: (i) we impose a deadline on the local gradient computations of each node at each iteration of the algorithm, and (ii) the nodes exchange quantized versions of their local models. The first idea robustifies to straggling nodes and the second alleviates communication efficiency. The key technical contribution of our work is to prove that with non-vanishing noises for quantization and stochastic gradients, the proposed method exactly converges to the global optimal for convex loss functions, and finds a first-order stationary point in non-convex scenarios. Our numerical evaluations of the QuanTimed-DSGD on training benchmark datasets, MNIST and CIFAR-10, demonstrate speedups of up to 3x in run-time, compared to state-of-the-art decentralized optimization methods.
References in corpus (22)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- Speeding Up Distributed Machine Learning Using Codes
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
- Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- An Exact Quantized Decentralized Gradient Descent Algorithm
- DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
- Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
- Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
- Asynchronous Decentralized Parallel Stochastic Gradient Descent
- Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
- Anytime MiniBatch: Exploiting Stragglers in Online Distributed Optimization
- Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
- Nested Distributed Gradient Methods with Adaptive Quantized Communication
- Asynchronous decentralized accelerated stochastic gradient descent
- Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs
- Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks