Source-linked AI summary
Explicit Convergence Rate of a Distributed Alternating Direction Method of Multipliers
Franck Iutzeler, Pascal Bianchi, Philippe Ciblat, Walid Hachem
TL;DR
Distributed optimization asks how agents with private convex costs can reach a common minimizer through ADMM. The paper develops a framework spanning communication architectures and analyzes its convergence rate; under its stated curvature and differentiability assumptions, convergence is linear with an explicit rate.
Problem
The paper seeks an exact, informative convergence-rate characterization for distributed ADMM, where prior analysis left a substantial gap between its bound and practice.
Source: §I · p. 2Method
It reformulates consensus optimization using agent subsets to cover pairwise, cluster-level, and centralized architectures, and analyzes quadratic affine dynamics and their perturbations.
Source: §I · p. 1Results
ADMM converges linearly to consensus with an explicit rate tied to aggregate Hessians and the communication network, and the rate is tight under mild conditions.
Source: §I · p. 1, §VII · p. 11Takeaways & Limitations
The rate analysis can predict ADMM performance and help optimize the step-size and communication graph; the method may inform augmented ADMM designs with enhanced convergence rates.
Source: §VII · p. 11The convergence-rate result assumes an attained minimizer, twice-differentiable local costs there, and a positive-definite sum of their Hessians.
Source: §I · p. 1
Abstract
from arXiv · showhide
Consider a set of N agents seeking to solve distributively the minimization problem $\inf_{x} \sum_{n = 1}^N f_n(x)$ where the convex functions $f_n$ are local to the agents. The popular Alternating Direction Method of Multipliers has the potential to handle distributed optimization problems of this kind. We provide a general reformulation of the problem and obtain a class of distributed algorithms which encompass various network architectures. The rate of convergence of our method is considered. It is assumed that the infimum of the problem is reached at a point $x_\star$, the functions $f_n$ are twice differentiable at this point and $\sum \nabla^2 f_n(x_\star) > 0$ in the positive definite ordering of symmetric matrices. With these assumptions, it is shown that the convergence to the consensus $x_\star$ is linear and the exact rate is provided. Application examples where this rate can be optimized with respect to the ADMM free parameter $\rho$ are also given.
I. INTRODUCTION
The introduction presents a distributed ADMM framework spanning communication architectures and an explicit convergence-rate analysis under local smoothness and aggregate curvature assumptions. It also outlines an equivalent reformulation and a proof strategy based on quadratic dynamics.
I. INTRODUCTION
- A decentralized iteration updates each agent’s local estimate using its private cost and information from neighboring agents, aiming for consensus at an aggregate-cost minimizer.The introduction cites learning, resource allocation, and sensor-network estimation as application settings.Source: §I · p. 1
- The framework uses agent subsets to span pairwise communication, cluster-level coordination, and centralized reduction, yielding a continuum of distributed algorithms.The subsets need not be edges of a pre-existing graph.Source: §I · p. 1
- Under attainment, twice differentiability at x*, and a positive-definite aggregate Hessian, ADMM converges linearly with an explicitly provided rate.The rate can be used to assess network and step-size effects, and the paper gives examples optimizing the step-size.Source: §I · p. 1
- The proof analyzes quadratic-cost ADMM as an affine iteration, then treats the general twice-differentiable case as a perturbation whose eigenspace structure preserves the analysis.The method is proposed as potentially applicable to constrained minimization with objectives smooth near the solution.Source: §I · pp. 1–2
- Prior distributed ADMM analysis gave a uniform primal-error upper bound but left a substantial gap to practice; this paper seeks an exact characterization under weaker assumptions.The cited bound applies to strongly convex local functions with Lipschitz-continuous gradients.Source: §I · p. 2
A. Assumptions and problem reformulation
- Assumption 3 makes the reformulation equivalent; local costs need only be twice differentiable at attained x*, with aggregate Hessian positive definite, not individually strongly convex.The paper also assumes no global gradient property such as Lipschitz continuity.Source: A. Assumptions and problem reformulation · pp. 2–3
B. An illustration
The illustration shows how overlapping agent subsets impose a shared consensus constraint. The ADMM formulation is then connected to distributed updates and convergence to the unique solution.
B. An illustration
- With three components, Mx groups agents as (1,2), (4,5), and (2,3,4); the illustrated component vectors repeat a value within each group.The indicator g is finite only for vectors in the illustrated subspace, which requires all agent components of x to agree.Source: B. An illustration · p. 3
C. Instancianting ADMM
- The reformulated problem is solved with ADMM iterations using an augmented Lagrangian and a positive penalty parameter ρ.The text proceeds to make the x- and z-updates explicit for distributed implementation.Source: C. Instancianting ADMM · p. 3
- Under Assumptions 1–3, the ADMM iterates converge from any initial (z0, λ0) to a saddle point corresponding to the unique solution of the original problem.The saddle point has primal component 1_N ⊗ x*.Source: C. Instancianting ADMM · p. 3
D. Distributed ADMM (General case)
The general implementation coordinates agents within overlapping subsets and exchanges information across subsets. Pairwise subsets allow execution directly at the agent level, while larger subsets can use cluster coordination.
D. Distributed ADMM (General case)
- Agents in each subset Aℓ are assumed connected; when every subset has two agents, members exchange estimates and compute their average without a cluster head or gossiping.That special case is fully distributed at the agent level.Source: D. Distributed ADMM (General case) · p. 4, Distributed-ADMM (General case) · p. 4
- In the general case, each agent stores its current estimate and auxiliary variables, computes a new estimate, and participates in subset-level coordination at each iteration.The iteration outline assigns local estimate updates to agents and coordination to the members or cluster head of each subset.Source: D. Distributed ADMM (General case) · p. 4, Distributed-ADMM (General case) · p. 4
- Without a cluster head, the subset average can instead be computed by distributed gossiping.This is presented as an alternative for computing the subset quantity.Source: Distributed-ADMM (General case) · p. 4
E. Distributed ADMM (Special cases)
The section illustrates the framework with centralized ADMM and a graph-based distributed ADMM. In the graph case, edges define the agent subsets, and connectedness makes Problems (1) and (2) equivalent.
Example 1
- In the centralized example, a dedicated device computes the agents’ average estimate and broadcasts it to all agents.Source: E. Distributed ADMM (Special cases) · p. 4
Example 2
- In the graph example, each edge forms a subset Aℓ; when the graph is connected, Assumption 3 holds and Problems (1) and (2) are equivalent.Source: E. Distributed ADMM (Special cases) · p. 4
- For an edge joining agents n and m, the edge estimate is their average, while each agent’s neighborhood estimate is based on its neighbors’ estimates.Source: E. Distributed ADMM (Special cases) · p. 5
- Each agent keeps x^k(n), bar x^k(n), and delta^k(n); the update adds half the difference between x^(k+1)(n) and bar x^(k+1)(n) to delta^k(n).Source: E. Distributed ADMM (Special cases) · p. 5
Special case
- In a special case, the algorithm reduces to the algorithm of [11].Source: E. Distributed ADMM (Special cases) · p. 5
III. MAIN RESULT
Theorem 2 gives a subunit spectral-radius expression for the ADMM convergence rate and identifies when its asymptotic bound is tight. Special-case analyses show how the rate depends on ρ.
III. MAIN RESULT
- α = r((Πspan(P + Q) − (P + Q))(I − 2P)) is below one, and the consensus-error rate is tight for almost all initializations when the stated matrix condition holds.The tightness condition is described as mild and is trivially satisfied for a centralized network.Source: §III · p. 5
IV. SPECIAL CASES
- For K = 1 with a common positive second derivative across agents, the special-case analysis yields simple, insightful rate expressions.The common-derivative assumption is not mandatory.Source: §IV · p. 5
A. The centralized network
- The centralized-network rate is optimally 1/2 when the step-size is ρ = σ²⋆, providing a parameter-selection target even when σ²⋆ is unknown.The result potentially supports adaptive step-size selection strategies.Source: A. The centralized network · p. 5
- When the second derivatives differ, a closed-form centralized rate still exists, but its expression is tedious and depends on ρ’s position on the real axis.The paper defers discussion of this case to the numerical section.Source: A. The centralized network · pp. 5–6
B. The ring network
For a ring network, the paper gives a rate expression for ADMM and examines how the rate varies with the penalty parameter. Its proof strategy uses an affine-iteration analysis, supported by algebraic properties of the network matrices.
B. The ring network
- The ring-network convergence rate α(ρ) is given by Corollary 2 under the stated assumptions.The network is a cycle with edges joining consecutive agents and the last agent to the first.Source: B. The ring network · p. 6
- For N-agent rings, the rate is reported to be continuous and decreasing over a stated interval, and the asymptotic expression suggests scaling the step-size with N.The supplied asymptotic fragment gives 4π + o(N) and says this suggests the step-size should increase at the rate N.Source: B. The ring network · p. 6
V. PROOF OF THEOREM 2
- The proof studies ADMM through ζ_k = λ_k + ρz_k, whose evolution is an affine transformation in the quadratic case.The general-case perturbation terms lie in a subspace that leaves the quadratic-case analysis essentially effective.Source: §V · p. 6
A. Preliminary results
- The preliminary matrix results characterize the intersection of the relevant spans as span(1_T) and establish that S maps 1_N to 1_T.Source: A. Preliminary results · p. 7
B. The proximity operator
The section recalls two properties of proximity operators used in the analysis: non-expansiveness and equivalence to projection for an indicator function.
B. The proximity operator
- The section cites for these two standard proximity-operator lemmas.Source: B. The proximity operator · p. 7
- The proximity operator prox_h is non-expansive: its output distance is no greater than the input distance.Source: B. The proximity operator · p. 7
- For a closed convex set C, prox_{ι_C}(x) is the orthogonal projection of x onto C.Source: B. The proximity operator · p. 7
C. The quadratic case
In the quadratic case, ADMM is represented by an affine transformation of a state vector, enabling its behavior to be studied through the matrix spectrum. The iterates are related to a fixed point by repeated application of that matrix.
C. The quadratic case
- For quadratic local objectives, the functions have symmetric nonnegative matrices Φ_n, and the ADMM update can be written as a single affine transformation.The update derives the x-step from an invertible matrix H = Φ + ρM*M before forming the state evolution.Source: C. The quadratic case · p. 7
- The proof identifies the state sequence as autonomous and completely characterizing ADMM, connecting the analysis to Douglas–Rachford splitting [25],.Source: C. The quadratic case · p. 7
- The matrix R has spectral radius at most one, no unit-modulus eigenvalues other than 1, and no nontrivial Jordan blocks.Source: C. The quadratic case · p. 7
- The eigenvalue 1 is tied to the null space of Q − P, and the fixed points of the affine transformation are characterized using that subspace.Source: C. The quadratic case · p. 8
- The quadratic-case state error satisfies ζ_k − ζ⋆ = R^k(ζ_0 − ζ⋆), expressing the iterates through repeated application of R.Source: C. The quadratic case · p. 8
D. The general case
For twice-differentiable objectives near the minimizer, the ADMM update becomes a perturbed affine transformation based on the Hessian at the minimizer. The analysis uses this local representation to establish convergence and a rate bound.
D. The general case
- Near the minimizer, the general-case x-update is expressed using the Hessian at x⋆ plus a remainder that is small relative to the displacement.The local expansion applies once the iterates are in a neighborhood where the functions are differentiable.Source: D. The general case · p. 9
- The state evolution is a perturbed affine transformation whose matrix R is formed using the Hessian at x⋆.The text states that the spectral lemmas established for the quadratic case remain true for these R and Q matrices.Source: D. The general case · p. 9
- For initial conditions outside a set of Lebesgue measure zero, the proof establishes a lower bound on the asymptotic logarithmic convergence rate by log α.Source: D. The general case · p. 10
VI. NUMERICAL ILLUSTRATIONS
The numerical illustrations show that the characterized rate closely matches observed ADMM convergence, and they examine how network architecture and the step size affect the rate.
Numerical illustrations
- With σ²⋆ = 16, the centralized network's optimal ρ equals σ²⋆ and is independent of N, whereas the ring-network rate depends on both ρ and N.The figures plot rate α against ρ for the centralized network and against ρ and N for the ring network.Source: Figure 3 · p. 10, Figure 4 · p. 10, §VI · p. 10
- For a centralized network with five agents and distinct second derivatives, the rate α is plotted against ρ.The agents' second derivatives at x⋆ are 4, 9, 16, 25, and 39.Source: §VI · p. 10, Figure 5 · p. 11
- For exponential functions, the rate is tight as −k−1 log ∥xk −x⋆∥ numerically converges to −log α, and Shi et al.’s bound is undefined.In the other simulation, the characterization fits empirical ADMM performance while a gap exists between it and; ρ is set to 100.Source: Figure 6 · p. 11, §VI · p. 11
VII. CONCLUSION
The conclusion presents an explicit characterization of ADMM's linear convergence rate for distributed optimization and describes its practical uses in evaluating and optimizing algorithm parameters and communication graphs.
VII. CONCLUSION
- The convergence rate is explicitly characterized through the spectral radius of a matrix depending on the aggregate Hessian and communication network.The result concerns distributed minimization with private convex functions twice differentiable at the minimizer.Source: §VII · p. 11
- Under mild conditions, the characterized rate is tight, in the sense that actual convergence is no faster than the obtained rate.Source: §VII · p. 11
- The analysis can accurately predict ADMM performance and help optimize the step size and communication graph.The paper also suggests that the method may support designing augmented ADMM methods with enhanced convergence rates.Source: §VII · p. 11
APPENDIX
The appendix uses the structure of block circulant matrices to analyze eigenvalues and derive the convergence-rate expression. It then establishes a monotonicity property of the rate as a function of ρ.
Appendix
- The eigenvalue spectrum of the block circulant matrix is obtained from a trigonometric matrix polynomial evaluated at λ = 2πk/N.The matrix is formed from the three blocks G−1, G0, and G1.Source: APPENDIX · p. 12
- For the ring-network analysis, the eigenvalues of the sampled matrix polynomial are found by solving a quadratic equation.Source: APPENDIX · p. 12
- The resulting rate α(ρ) is continuous and decreases on the interval (0, σ²⋆).The analysis of the solutions for all k leads to the expression in Corollary 2.Source: APPENDIX · p. 13