Source-linked AI summary
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Wei Shi, Qing Ling, Kun Yuan, Gang Wu, Wotao Yin
TL;DR
Decentralized consensus optimization requires agents to minimize local objectives over a common variable while communicating only with neighbors, and the convergence behavior of decentralized ADMM was not fully characterized. The paper reformulates the problem for ADMM, proves linear convergence under strongly convex local objectives, and explicitly relates the rate to network topology, objective properties, and the algorithm parameter. These results provide a performance guarantee and guidance for accelerating convergence.
Problem
The convergence rate of decentralized ADMM and the factors affecting it were unknown, despite its observed fast convergence in decentralized consensus optimization.
Method
The paper reformulates decentralized consensus optimization for ADMM and analyzes its iterates under strongly convex local objective functions.
Results
The decentralized ADMM variables converge linearly, with the rate explicitly determined by network topology, local objective-function properties, and the algorithm parameter.
Takeaways & Limitations
The explicit convergence characterization provides a performance guarantee and guides network construction and algorithm-parameter tuning for faster convergence.
Abstract
from arXiv · showhide
In decentralized consensus optimization, a connected network of agents collaboratively minimize the sum of their local objective functions over a common decision variable, where their information exchange is restricted between the neighbors. To this end, one can first obtain a problem reformulation and then apply the alternating direction method of multipliers (ADMM). The method applies iterative computation at the individual agents and information exchange between the neighbors. This approach has been observed to converge quickly and deemed powerful. This paper establishes its linear convergence rate for decentralized consensus optimization problem with strongly convex local objective functions. The theoretical convergence rate is explicitly given in terms of the network topology, the properties of local objective functions, and the algorithm parameter. This result is not only a performance guarantee but also a guideline toward accelerating the ADMM convergence.
I. INTRODUCTION
Decentralized consensus optimization lets networked agents collaboratively minimize local objectives over a common variable using only neighbor communication. This paper analyzes ADMM because its convergence is empirically fast but its rate and determining factors were previously unclear.
- Problem setting: Agents collaboratively minimize the sum of local objective functions over a common optimization variable using distributed information and neighbor communication.Each agent knows its local objective function fi(˜x); applications include averaging, learning, and estimation.
- Related methods: ADMM is among the decentralized methods considered and has demonstrated fast empirical convergence in applications.Other approaches include distributed subgradient descent, dual averaging, belief propagation, and incremental optimization.
- Research gap: The convergence speed of decentralized ADMM and the factors affecting its rate were previously unknown.Existing ADMM rate analysis was restricted to centralized computation, while general convex centralized ADMM has sublinear rate O(1/k).
- Contributions: The paper establishes a linear convergence rate for decentralized ADMM with strongly convex local objective functions.The result provides a performance guarantee and extends prior analysis tools to the decentralized regime.
- Contributions: The analysis characterizes convergence in terms of network topology, local objective-function properties, and the algorithm parameter.These results are used to guide network design, objective-function splitting, and parameter settings for faster convergence.
C. Paper Organization and Notation
The paper reformulates decentralized consensus optimization so ADMM can solve it through separable local and consensus updates. The resulting algorithm is fully decentralized, with agents using local and neighboring information.
- Problem formulation: The paper reformulates decentralized consensus optimization into an ADMM-compatible constrained problem.The reformulation uses local copies xi of the common variable and auxiliary variables zij to impose consensus between neighbors.
- Problem formulation: Separability of the reformulated constraints enables decentralized computation within the ADMM framework.The objective terms are separable when auxiliary variables are fixed, and the constraints are separable when local copies are fixed.
- Algorithm development: The ADMM iteration alternates minimization of the augmented Lagrangian over x and z, followed by a multiplier update.The algorithm uses a positive parameter c and requires appropriately chosen initial variables for the simplified updates.
- Algorithm development: The decentralized algorithm reduces the ADMM updates to an x-update and a new multiplier update.The simplification uses α = M−β and the network-related incidence, Laplacian, and degree matrices.
- Algorithm development: Each agent’s updates rely only on local and neighboring information, making the algorithm fully decentralized.The local variables xi and multipliers αi are updated using information from the agent and its neighbor set Ni.
III. CONVERGENCE RATE ANALYSIS
The paper establishes linear convergence for decentralized ADMM under strongly convex local objectives and analyzes how parameter tuning can accelerate convergence.
- Convergence rate analysis: The analysis establishes the linear convergence rate of decentralized ADMM for strongly convex local objective functions.The section presents the main theoretical result and discusses parameter tuning for acceleration.
- Convergence rate analysis: The convergence analysis is intended to show how tuning the algorithm parameter can accelerate the ADMM iterations.The paper separates the convergence proof from the subsequent parameter-tuning discussion.
A. Main Theoretical Result
Under strongly convex local objectives with Lipschitz-continuous gradients, the decentralized ADMM iterates converge linearly under a column-space initialization condition. The combined vector u^k=[z^k;β^k] converges Q-linearly, which implies R-linear convergence of x^k to x*; the stated rate bound is probably not tight.
- Assumptions: Strong convexity of each local objective and Lipschitz continuity of its gradient are the main assumptions for the convergence analysis.These properties imply strong convexity and Lipschitz continuity for the aggregate objective f(x).
- Motivation: The analysis addresses linear convergence because decentralized consensus optimization does not satisfy centralized ADMM conditions such as strong convexity of g(z) or full row rank of B.Here, g(z)=0 is not strongly convex and the specified B matrix is not full row rank.
- Theorem 1: Q-linear convergence of u^k implies that x^k converges R-linearly to the optimal x*.The theorem relates the auxiliary primal-dual convergence result to convergence of the primal iterates.
- Theorem 1: If β^0 lies in the column space of M_-^T, then u^k=[z^k;β^k] converges Q-linearly to u*=[z*;β*] for any μ>1.The theorem also uses the unique primal and dual optimal values under the stated assumptions.
- Rate interpretation: A larger δ guarantees faster convergence, while the stated Q-linear convergence-rate bound is probably not tight.The rate discussion connects δ to the convergence guarantee and qualifies the bound's sharpness.
B. Accelerating the Convergence
The paper tunes the free parameter μ and algorithm parameter c to maximize δ and accelerate decentralized ADMM convergence. The resulting theoretical rate depends on network topology, local-objective properties, and the algorithm parameter.
- Rate characterization: The theoretical convergence rate is given in terms of network topology, local objective properties, and the algorithm parameter.The analysis explicitly characterizes the rate through these three categories of quantities.
- Condition numbers: The condition number κ_f summarizes the conditioning of the aggregate objective, with m_f=min_i m_fi and M_f=max_i M_fi.The supplied passages identify κ_f as an upper bound on the condition number of f.
- Condition numbers: Larger σmax(L+) and ˜σmin(L−) indicate stronger network connectedness, whereas a larger graph condition number κ_G indicates weaker connectedness.σmax(L+) is described as the weaker of the two connectedness measures.
- Parameter tuning: The optimized δ decreases with κ_f and κ_G, so smaller objective and graph condition numbers lead to faster convergence.As either condition number tends to infinity, δ tends to 0 and convergence can become arbitrarily slow.
IV. NUMERICAL EXPERIMENTS
The experiments validate the theoretical convergence analysis across network connectivity, objective conditioning, topology, and ADMM parameter choices. They use decentralized consensus least squares instances with randomly generated connected networks and report primal error alongside running geometric-average convergence rates.
- Experimental Settings: Networks contain L agents, are generated connected, and use connectivity ratio p defined from the actual number of edges.The experiments vary network connectivity while retaining connectedness.
- Experimental Settings: Iterations stop when ∥xk − x∗∥2 reaches 10^-15 or k reaches 4000, whichever occurs first.
- Metrics: The experiments report primal error ∥xk − x∗∥2 and running geometric-average convergence rates because the alternative metric incurs substantial computation for large L.Primal error is not necessarily monotonic in k, motivating the running geometric-average rate ¯ρk and its steady-state value ¯ρ.
- The experiments study how connectivity, algorithm parameter c, objective condition number κf, and network topology affect convergence rate.The study includes comparisons with theoretical and hand-tuned parameters and summarizes the experiments in Table II.
B. Linear Convergence
The experiments demonstrate linear convergence of ADMM on randomly generated connected networks and examine how connectivity and parameter selection affect the observed rate. They also compare the analytically chosen parameter with practical tuning.
- Connectivity: The running geometric-average rate ¯ρk stabilizes within 10 iterations, and changing p within [0.08, 1] does not significantly change convergence rate in these random networks.Higher connectivity leads to faster convergence overall, but beyond a threshold its influence on κG is limited.
- Linear Convergence: ADMM exhibits linear convergence, whereas diminishing-stepsize DGD remains sublinear and slow even on a complete graph.The comparison uses networks with L = 200 agents and varying connectivity ratios.
- Algorithm Parameter: The theoretical parameter c = ct optimizes an upper bound but does not provide the best practical performance; consistently, ct is larger than the best practical c∗.Using c = c∗ significantly improves convergence relative to c = ct.
- Algorithm Parameter: Choosing c = θct with θ ≃ 0.5 is a good overall choice for the evaluated dataset.Smaller θ risks slower convergence when κG is small.
D. Condition Number of the Objective Function
The experiments examine how objective conditioning and network topology relate to ADMM convergence. They find that theoretical rates worsen with objective condition number, while network condition number is a stronger practical indicator across tested network sizes and topologies.
- Objective Conditioning: The theoretical convergence rate ρt increases monotonically as the objective condition number κf increases, consistent with Theorem 2.
- Objective Conditioning: When connectivity ratios p are small, observed ¯ρ can disagree with theory because the convergence-rate upper bound becomes loose for poorly connected networks.For well-connected networks such as p = 1, the observed trend is consistent with the theoretical analysis.
- Network Topology: Network condition number κG is a good indicator of convergence rate, with steady-state ¯ρ and theoretical ρt showing consistent trends.The experiments sample κG through many connected-network trials because it is difficult to design precisely.
- Network Topology: Convergence is closely related to κG and less related to agent count L; sufficiently small κG is associated with reaching a target convergence rate.For L = 200, p = 0.1 can yield small κG and thus fast convergence in the reported experiments.
- Network Topology: At the same κG, star-topology networks converge much faster than random networks.The experiments also compare line, cycle, complete, star, and grid topologies.
2) Network Diameter:
The experiments examine how network topology and related structural measures affect ADMM convergence. In general, larger network diameter worsens the network condition number and slows convergence, while higher geometric average degree improves connectedness and convergence, with topology-dependent interference.
- Network Diameter: 4000 randomly generated connected networks with L = 200 agents were used to study how network diameter affects convergence.The experiment also included line, cycle, star, complete, and grid topologies.
- Network Diameter: A larger network diameter generally worsens the network condition number and slows convergence, although network properties interfere with this relationship.The observed diameter groups were D = 2, 3 ≤D ≤4, and 5 ≤D ≤198.
- Geometric Average Degree: A larger geometric average degree ds generally implies better convergence, consistent with the conclusion for network diameter.The geometric average degree reflects the agents’ number of neighbors in a geometric average sense.
- Bipartite-Network Imbalance: For bipartite networks with the same κG, larger imbalance Ld is associated with faster convergence, with the star topology as an extreme example.The experiments considered random and star topologies with L = 200 agents.
- Bipartite-Network Imbalance: Assigning a few relay “hot spots” can support fast convergence at fixed κG, but relaying agents may face communication burden and create robustness or scalability issues.The paper frames this as a tradeoff between fast convergence and robustness or scalability in network design.
APPENDIX
The appendix derives the convergence result from the ADMM updates and KKT conditions. It bounds successive error terms under strong convexity and Lipschitz-gradient assumptions, then obtains R-linear convergence of xk to x∗.
- Proof: The proof begins by comparing the ADMM updates with the KKT conditions and subtracting the corresponding equations.This establishes relations used in the subsequent error bounds.
- Proof: The analysis splits the relevant expression into two terms and rewrites it using the compact G-weighted form involving uk, uk+1, and u∗.The reformulation uses the definition of u and G and an associated quadratic identity.
- Assumptions and Bounds: Strong convexity and Lipschitz-continuous gradients provide bounds for the primal and dual error terms.The proof also assumes a positive algorithm parameter c and initializes β0 in the column space of MT.
- Convergence Bound: Combining the derived inequalities proves the stated contraction relation and bounds the successive dual-error norm.The argument then transfers the bound to the primal iterates.