MixML: A Unified Analysis of Weakly Consistent Parallel Learning
arXiv:2005.06706
Abstract
Parallelism is a ubiquitous method for accelerating machine learning algorithms. However, theoretical analysis of parallel learning is usually done in an algorithm- and protocol-specific setting, giving little insight about how changes in the structure of communication could affect convergence. In this paper we propose MixML, a general framework for analyzing convergence of weakly consistent parallel machine learning. Our framework includes: (1) a unified way of modeling the communication process among parallel workers; (2) a new parameter, the mixing time tmix, that quantifies how the communication process affects convergence; and (3) a principled way of converting a convergence proof for a sequential algorithm into one for a parallel version that depends only on tmix. We show MixML recovers and improves on known convergence bounds for asynchronous and/or decentralized versions of many algorithms, includingSGD and AMSGrad. Our experiments substantiate the theory and show the dependency of convergence on the underlying mixing time.
References in corpus (18)
- Adam: A Method for Stochastic Optimization
- An overview of gradient descent optimization algorithms
- On the Convergence of Adam and Beyond
- Revisiting Distributed Synchronous SGD
- Don't Use Large Mini-Batches, Use Local SGD
- Staleness-aware Async-SGD for Distributed Deep Learning
- D: Decentralized Training over Decentralized Data
- Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
- Stochastic Gradient Push for Distributed Deep Learning
- Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
- Distributed Delayed Stochastic Optimization
- Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
- On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
- Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training
- Distributed Learning over Unreliable Networks
- Distributed Learning with Sublinear Communication
- Fault Tolerance in Iterative-Convergent Machine Learning
- Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent