How is Distributed ADMM Affected by Network Topology?
arXiv:1710.00889
Abstract
When solving consensus optimization problems over a graph, there is often an explicit characterization of the convergence rate of Gradient Descent (GD) using the spectrum of the graph Laplacian. The same type of problems under the Alternating Direction Method of Multipliers (ADMM) are, however, poorly understood. For instance, simple but important non-strongly-convex consensus problems have not yet being analyzed, especially concerning the dependency of the convergence rate on the graph topology. Recently, for a non-strongly-convex consensus problem, a connection between distributed ADMM and lifted Markov chains was proposed, followed by a conjecture that ADMM is faster than GD by a square root factor in its convergence time, in close analogy to the mixing speedup achieved by lifting several Markov chains. Nevertheless, a proof of such a claim is is still lacking. Here we provide a full characterization of the convergence of distributed over-relaxed ADMM for the same type of consensus problem in terms of the topology of the underlying graph. Our results provide explicit formulas for optimal parameter selection in terms of the second largest eigenvalue of the transition matrix of the graph's random walk. Another consequence of our results is a proof of the aforementioned conjecture, which interestingly, we show it is valid for any graph, even the ones whose random walks cannot be accelerated via Markov chain lifting.
References in corpus (6)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
- Adaptive ADMM with Spectral Penalty Parameter Selection
- An Improved Three-Weight Message-Passing Algorithm
- An Empirical Study of ADMM for Nonconvex Problems
- A message-passing algorithm for multi-agent trajectory planning
Cited by in corpus (5)
- ADMM and Accelerated ADMM as Continuous Dynamical Systems
- Distributed and Localized Model Predictive Control via System Level Synthesis
- On the Complexity of the Weighted Fused Lasso
- Tight Linear Convergence Rate of ADMM for Decentralized Optimization
- Bregman Parallel Direction Method of Multipliers for Distributed Optimization via Mirror Averaging