Source-linked AI summary
A General Analysis of the Convergence of ADMM
Robert Nishihara, Laurent Lessard, Benjamin Recht, Andrew Packard, Michael I. Jordan
TL;DR
The paper addresses how to establish linear convergence of ADMM when one objective term is strongly convex without fixing particular algorithm parameters. It uses a dynamical-systems and semidefinite-programming framework to derive convergence bounds, parameter-selection guidance, and a nearly matching worst-case lower bound.
Problem
Existing ADMM convergence analysis is limited in handling parameterized variants and does not generally provide tuning guidance without fixed parameter choices.
Method
The paper casts over-relaxed ADMM as a discrete-time dynamical system and verifies convergence through a numerically solved 4×4 semidefinite program.
Results
The paper derives an upper bound and nearly matching lower bound for the linear convergence rate of over-relaxed ADMM.
Takeaways & Limitations
The framework supports practical parameter selection and makes it straightforward to analyze algorithmic variants with additional parameters.
Takeaways & Limitations
The convergence analysis assumes strong convexity of f; without it, Assumption 3 may fail.
Abstract
from arXiv · showhide
We provide a new proof of the linear convergence of the alternating direction method of multipliers (ADMM) when one of the objective terms is strongly convex. Our proof is based on a framework for analyzing optimization algorithms introduced in Lessard et al. (2014), reducing algorithm convergence to verifying the stability of a dynamical system. This approach generalizes a number of existing results and obviates any assumptions about specific choices of algorithm parameters. On a numerical example, we demonstrate that minimizing the derived bound on the convergence rate provides a practical approach to selecting algorithm parameters for particular ADMM instances. We complement our upper bound by constructing a nearly-matching lower bound on the worst-case rate of convergence.
1. Introduction
ADMM solves a constrained optimization problem through alternating updates, including an over-relaxed variant with parameter α. The paper develops convergence-rate bounds and an SDP-based framework that supports parameter tuning and analysis of algorithm variants.
- ADMM addresses a constrained optimization problem with variables x and z, matrices A and B, and constraint Ax + Bz = c.
- ADMM updates are attractive in many settings because they can support parallel implementations.
- Over-relaxed ADMM introduces α into the z and u updates; α = 1 recovers the standard algorithm.
- The conventional no-tuning heuristic often fails in practice, making ρ and α difficult to select, especially for over-relaxed ADMM.
- The paper gives upper and nearly matching lower bounds on Algorithm 2's linear convergence rate for all ρ and α.
- Convergence rates can be established by numerically solving a 4×4 semidefinite program, automating analysis when algorithm parameters change.
2. Preliminaries and Notation
The preliminaries define the function classes, convexity properties, operator concepts, and matrix notation used to analyze ADMM. Strong convexity and gradient regularity provide the main assumptions for the smooth objective term.
- A differentiable convex function is strongly convex with parameter m > 0 when it satisfies the paper's stated quadratic lower-bound condition.
- S_d(m, L) contains differentiable convex functions that are m-strongly convex and have L-Lipschitz gradients.
- For f ∈ S_d(m, L), cocoercivity of the gradient supports the matrix inequality used in Lemma 1.
- For general convex f, the subdifferential is treated as a monotone operator.
- The matrix condition number is defined using the ratio of largest to smallest singular values, while κ_f records the function conditioning parameters.
3. ADMM as a Dynamical System
The analysis recasts over-relaxed ADMM as a discrete-time dynamical system under convexity, strong convexity, and rank assumptions. Auxiliary sequences and transformed operators connect the algorithm updates to the system's state, inputs, and outputs.
- The analysis assumes closed proper convex f and g, strongly convex smooth f, invertible A, and full-column-rank B.
- Over-relaxed ADMM is represented as a discrete-time dynamical system with state ξ_k, input ν_k, and output sequences.
- The transformed formulation uses a left inverse of B, an indicator of im B, and a normalized conditioning quantity κ.
- The sequences r_k = Ax_k and s_k = Bz_k, together with ξ_k, organize the algorithm variables for the dynamical-system representation.
- Proposition 4 introduces β_k = ∇f̂(r_k) and γ_k ∈ ∂ĝ(s_k) to express the transformed updates.
- Rewriting the x, z, and u updates and combining their relations verifies the state recursion and output equations.
4. Convergence Rates from Semidefinite Programming
Theorem 6 reduces convergence-rate certification for over-relaxed ADMM to a 4×4 semidefinite-program feasibility test. Binary search over the rate yields numerical guarantees and supports parameter-selection experiments.
- Theorem 6: Theorem 6 certifies convergence when a 4×4 linear matrix inequality has a positive definite 2×2 matrix P and nonnegative multipliers λ1, λ2.The sequences are generated by Algorithm 2 with step size ρ = (m̂L̂)^(1/2)ρ0 and over-relaxation parameter α.
- Theorem 6: The certified Lyapunov inequality contracts the quadratic error by a factor τ^2 at each iteration.The inequality is written for the state sequence ξk relative to its fixed point ξ*.
- Numerical rate computation: For fixed α, ρ0, m̂, L̂, and τ, feasibility of the linear matrix inequality is a semidefinite program in P, λ1, and λ2.The method searches for the smallest feasible τ by binary search.
- Numerical rate computation: Figures 1 and 2 vary κ and ε with α = 1.5, plotting the minimal feasible τ and the iteration proxy −1/log τ.The latter is used to represent the iterations required to reach a desired accuracy.
- Parameterization: For ρ0 = κε, the linear matrix inequality depends on κ rather than separately on m̂ and L̂, motivating this step-size family.The choices ε = 0 and ε = 0.5 trade stronger information requirements against weaker guarantees.
- Limitation: A limitation of Theorem 6 is that its rate is not initially expressed as a function of κ, requiring a separate feasibility search for each specified condition number.The paper addresses this limitation later by deriving a symbolic rate as a function of ρ, α, and κ.
5. Symbolic Rates for Various ρ and α
The paper derives symbolic linear-convergence rates for over-relaxed ADMM across α and step-size choices, using semidefinite certificates and asymptotic matrix analysis. The resulting upper bound is within a factor of four of the lower bound, while allowing iteration-varying step sizes.
- Theorem 7: Theorem 7 generalizes cases studied with ε = 0 and with α = 1, ε = 0.5.These correspond to prior analyses by Giselsson and Boyd, and Deng and Yin, respectively.
- Rate tightness: Theorem 7’s rate is loose by a factor of four relative to the lower bound in Theorem 8.The constant-factor weakening makes it easier to find a certificate for the semidefinite condition.
- Theorem 7: Theorem 7 proves linear convergence for α ∈ (0, 2) and step sizes ρ = (m̂L̂)^(1/2)κε with ε ∈ (−∞, ∞), for sufficiently large κ.The proof establishes feasibility of the linear matrix inequality asymptotically by analyzing leading principal minors.
- Proof strategy: For sufficiently large κ, positivity of the leading principal minors implies that the certificate matrix M is positive semidefinite.The argument treats ε ≥ 0 and ε < 0 separately, with positive leading coefficients in both cases.
- Proof consequence: The proof remains valid when the step size changes at each iteration because the certificate matrix P does not depend on ρ.This extends the symbolic-rate argument beyond a fixed step-size sequence.
6. Lower Bounds
The paper constructs nearly matching lower bounds for over-relaxed ADMM by analyzing a quadratic instance and its iteration-matrix eigenvalues. The lower and upper convergence-rate bounds agree visually across tested parameter choices, indicating practical tightness.
- Quadratic construction: A quadratic problem instance reduces Algorithm 2 to an update rule expressed purely in terms of z, with eigenvalues determined by eigenvalues of Q.The construction uses A = I_d, B = −I_d, c = 0, and a quadratic strongly convex objective.
- Lower-bound construction: The eigenvalue construction supplies a lower bound on the worst-case convergence rate of Algorithm 2.The paper explicitly uses this setup to construct the lower bound in Theorem 8.
- Lower-bound construction: For ε ≥ 0, initializing z with the relevant eigenvector yields a linear rate exactly given by (16), which lower bounds the stated expression.The argument chooses δ = 0 and λ = m.
- Lower-bound construction: For ε < 0, a corresponding eigenvector initialization yields a linear rate given exactly by the left side of (17), which lower bounds the expression in (15).The argument chooses δ = L and λ = L.
- Tightness comparison: The lower and upper bounds agree visually for α = 1.5 across the depicted ε choices, demonstrating practical tightness over a large parameter range.Figure 3 compares the lower bound from (16) with Theorem 6's upper bound.
7. Related Work
Prior work establishes linear convergence for several ADMM and operator-splitting settings, but the theory for over-relaxed ADMM is more limited. This paper's framework extends rate certification to arbitrary parameter choices through a small semidefinite program.
- Prior convergence results: Earlier results prove linear convergence for strongly convex ADMM, specialized distributed problems, and multiterm objectives under differing structural assumptions.The cited multiterm result does not require strong convexity.
- Operator splitting: Operator-splitting literature analyzes several related schemes, including forward-backward and Douglas–Rachford splitting.These results provide broader context for ADMM's relationship to operator-splitting methods.
- Over-relaxed ADMM: Existing over-relaxed ADMM work proves convergence without a rate, while later studies analyze rates in varied settings.Related work also derives ADMM rates through its connection to Douglas–Rachford splitting on the dual problem.
- Framework comparison: Unlike prior work, the proposed framework requires no assumptions on Algorithm 2's parameter choices and certifies rates by checking a 4 × 4 semidefinite program.The paper states that this check is essentially instantaneous compared with formulating a new proof.
8. Selecting Algorithm Parameters
The paper selects over-relaxation and step-size parameters by minimizing Theorem 6's rate bound, then evaluates the approach on a distributed Lasso problem. The predicted and observed performance largely track each other, and the suggested parameters perform near the best tested choices.
- Parameter-selection method: Parameter selection searches over α and ρ for the choices minimizing Theorem 6's upper bound at a given condition number κ.The paper demonstrates this grid-search approach numerically for distributed Lasso.
- Over-relaxation range: More values of α, including α > 2, can yield linear convergence because feasibility of the small semidefinite program extends beyond the usual parameter range.Figure 4 plots the largest feasible α as a function of κ with ε = 0.
- Distributed Lasso: The distributed Lasso experiment uses N = 5, tall full-column-rank matrices, and synthetic 600 × 500 Gaussian design matrices with sparse signals and Gaussian noise.The construction makes the first objective term strongly convex with a Lipschitz-continuous gradient.
- Distributed Lasso: Figure 5 evaluates Theorem 6's rate bounds over 85 α values and 50 geometrically spaced ρ values, omitting infeasible parameter settings.The analysis suggests α = 2.0 and ρ = 1.7.
- Experimental results: Observed iteration counts largely track the predicted bounds, smaller α appears more robust to poor ρ choices, and the suggested parameters perform close to the best tested choices.Iterations are measured until z^k is within 10^-6 of a precomputed reference solution, with runs exceeding 1000 iterations omitted.
9. Discussion
The paper presents semidefinite-programming tools that unify convergence analysis and parameter selection for ADMM variants. It also identifies strong convexity of f as a likely requirement and notes applicability to other operator-splitting methods.
- Framework and extensions: A semidefinite-programming framework unifies convergence-rate analysis for ADMM variants with additional parameters.The framework establishes rates and supports analyzing new algorithmic variants through parameterized guarantees.
- Framework and extensions: The framework can guide practical parameter selection for ADMM by evaluating convergence-rate guarantees.The paper applies this use to parameter selection in practice, including settings of Algorithm 2 parameters.
- Limitations: When Assumption 3 fails, the paper identifies missing strong convexity of f as the most likely cause.The discussion presents lack of strong convexity as the principal scope concern for this condition.
- Numerical illustration: Figure 6 measures iterations needed for z_k to approach a reference solution within 10^-6 across selected α and ρ values, omitting runs exceeding 1000 iterations.The experiment uses 85 evenly spaced α values from 0.1 to 2.2 and 50 geometrically spaced ρ values from 0.1 to 10, while displaying only a subset of α values.
- Framework and extensions: The same framework can also accommodate Douglas–Rachford splitting and forward-backward splitting.The paper states that these operator-splitting methods can be cast in the framework and analyzed with its tools.