Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization

By Konstantinos I. Tsianos, Sean F. Lawlor, Michael G. Rabbat. 2012

84 citations recorded by the source corpus.

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 [1] 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.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “Some initial investigations along these lines were presented in [94] in the context of stochastic optimization, where progressively more time is spent calculating gradients between each round of communication as the number of iterations progresses.”
Deep Learning of Representations: Looking Forward (2013, background): “Another interesting consideration is the optimization of trade-off between communication cost and computation cost in distributed optimization algorithms, e.g., as discussed in Tsianos et al. (2012).”
Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control (2014, unknown): “The first rigorous analysis of this problem was given in [58] and the problem has received considerable attention in recent years due its repeated appearance throughout distributed computing and multi-agent control; we mention [58, 59, 52, 70, 72, 42, 41, 79, 81, 80, 84, 34, 35, 8, 51, 37, 76, 17], ”
Distributed Gradient Methods for Convex Machine Learning Problems in Networks: Distributed Optimization (2020, methodology): “Subsequently, many distributed methods have been developed, such as those with a faster convergence [19], [20] and with emphasis on the communication and computation tradeoffs [21], [22].”
Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent (2013, background): “All these issues are related to the tradeoff between communication and computation [22, 24].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “Recently there has been an increasing interest in applying mulitagent optimization methods to solve convex and non-convex optimization problems arising in machine learning [189, 105, 4, 5, 25, 95, 83].”
Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging (2014, unknown): “To this end, we adapt the approach of [31] for modelling runtimes of distributed optimization methods.”
Communication-Censored ADMM for Decentralized Consensus Optimization (2019, unknown): “Nevertheless, the communication-computation tradeoff is essential [12]–[15].”
Balancing Communication and Computation in Distributed Optimization (2017, background): “The goal of [53] was to show that speed-up is possible when the agents communicate less frequently.”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, unknown): “Recently there has been an increasing interest in applying mulitagent optimization methods to solve convex and non-convex optimization problems arising in machine learning [80, 39, 1, 2, 9, 36, 32].”
Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “Our work is closely related to a few lines of research that we delineate below: 1) distributed first-order primal algorithms [9]–[11], [29]–[32]: methods that use only gradient information, 2) nested [11], [33]–[35]: methods that decompose the communication and computation steps, 3) communication ef”
Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates. (2018, background): “…In contrast to [20], with additional smoothness assumptions we improve the convergence rate to O (1 /k 2 / 3 ) and the MSE-communication is further Finally, we review the class of works that are concerned with designing distributed methods that achieve communication efﬁciency, e.g., [2], [22]–[27].”
A Survey on Distributed Machine Learning (2019, background): “Designing a generic system that enables an ecient distribution of regular Machine Learning is challenging since every algorithm has a distinct communication pattern [78][106][128][146][150][152].”
Asynchronous Gradient Push (2018, unknown): “4 This matrix-based formulation describes how the agents’ values evolve at those times t [ k + 1] ∈ T = { t [1] , t [2] , t [3] , . . . , } when one or more agents complete an update, which in this case consists of summing received messages.”
Data-Dependent Convergence for Consensus Stochastic Optimization (2016, background): “This reduction can improve the overall running time (“wall time”) of the algorithm because communication latency can hinder the convergence of many algorithms in practice [23].”