Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
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~\cite{kRegExpanders} 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationMetric LearningSimilar Papers 제목 키워드 기반
Distributed Consensus Optimization with Consensus ALADIN
TThe paper proposes the Consensus Augmented Lagrange Alternating Direction Inexact Newton (Consensus ALADIN) algorithm, a novel approach for solving distributed consensus optimization problems (DC). Consensus ALADIN allo…
Computational EfficiencyAsynchronous Distributed Consensus with Minimum Communication
In this paper, the communication effort required in a multi-agent system (MAS) is minimized via an explicit optimization formulation. The paper considers a MAS of single-integrator agents with bounded inputs and a time-i…
Distributed Optimization for Smart Cyber-Physical Networks
The presence of embedded electronics and communication capabilities as well as sensing and control in smart devices has given rise to the novel concept of cyber-physical networks, in which agents aim at cooperatively sol…
Distributed Optimizationglobal-optimizationLearning to Act and Cooperate for Distributed Black-Box Consensus Optimization
Distributed blackbox consensus optimization is a fundamental problem in multi-agent systems, where agents must improve a global objective using only local objective queries and limited neighbor communication. Existing me…
Distributed Maximum Consensus over Noisy Links
We introduce a distributed algorithm, termed noise-robust distributed maximum consensus (RD-MC), for estimating the maximum value within a multi-agent network in the presence of noisy communication links. Our approach en…
Distributed Optimization