Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization

Abstract

We study the scalability of consensus-based distributed optimization algorithms by considering two questions: How many processors should we use for a given problem, and how often should they communicate when communication is not free? Central to our analysis is a problem-specific value $r$ which quantifies the communication/computation tradeoff. We show that organizing the communication among nodes as a $k$-regular expander graph (Reingold, Vadhan, and Wigderson, 2002) yields speedups, while when all pairs of nodes communicate (as in a complete graph), there is an optimal number of processors that depends on $r$. Surprisingly, a speedup can be obtained, in terms of the time to reach a fixed level of accuracy, by communicating less and less frequently as the computation progresses. Experiments on a real cluster solving metric learning and non-smooth convex minimization tasks demonstrate strong agreement between theory and practice.

10 Pages, 3 Figures, Appearing at NIPS 2012

Cited by in corpus (9)

• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Distributed Inference with Sparse and Quantized Communication
• Extensions of Fast-Lipschitz Optimization
• Nested Distributed Gradient Methods with Adaptive Quantized Communication
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
• Trajectory Normalized Gradients for Distributed Optimization
• Distributed Dual Coordinate Ascent in General Tree Networks and Communication Network Effect on Synchronous Machine Learning