Source-linked AI summary
On the Linear Convergence of the Alternating Direction Method of Multipliers
Mingyi Hong, Zhi-Quan Luo
TL;DR
The paper addresses missing convergence-rate guarantees for ADMM with more than two nonsmooth convex blocks and without strong convexity. It develops error-bound-based analysis for ADMM and proves global linear convergence, including feasibility and, under the stated conditions, objective values, when the dual stepsize is sufficiently small.
Problem
Prior ADMM rate analyses generally lacked guarantees for more than two blocks or without strong convexity, despite the method’s use in such settings.
Method
The analysis uses local error bounds connecting proximal residuals and dual gradients to distances from primal and dual optimal solution sets.
Results
ADMM converges globally linearly to an optimal primal-dual solution for arbitrary block counts when the dual stepsize is sufficiently small.
Takeaways & Limitations
The result covers multi-block ADMM and applications including LASSO, Group LASSO, and Sparse Group LASSO without requiring strong convexity.
Takeaways & Limitations
The guarantee requires the paper’s standing assumptions and a sufficiently small dual-update stepsize; a single Gauss-Seidel sweep may leave primal iterates away from augmented-Lagrangian minimizers.
Abstract
from arXiv · showhide
We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global linear convergence of the ADMM for minimizing the sum of any number of convex separable functions. This result settles a key question regarding the convergence of the ADMM when the number of blocks is more than two or if the strong convexity is absent. It also implies the linear convergence of the ADMM for several contemporary applications including LASSO, Group LASSO and Sparse Group LASSO without any strong convexity assumption. Our proof is based on estimating the distance from a dual feasible solution to the optimal dual solution set by the norm of a certain proximal residual, and by requiring the dual stepsize to be sufficiently small.
1 Introduction
The paper studies ADMM for separable nonsmooth convex optimization with arbitrary numbers of variable blocks, motivated by applications such as compressive sensing and robust PCA. It addresses convergence-rate gaps in multi-block and non-strongly-convex settings by establishing global linear convergence under an error-bound condition.
- Problem setting: The optimization model minimizes a sum of K separable nonsmooth convex functions subject to linear equality constraints.Inequality constraints can be reformulated as equality constraints by adding a nonnegative slack block.
- Applications: Three- and four-block formulations arise in compressive sensing and stable robust PCA through slack variables and noise modeling.Nonnegative constraints introduce additional blocks, while robust PCA uses low-rank, sparse, noise, and possibly slack variables.
- ADMM method: ADMM adds a quadratic penalty, cyclically minimizes variable blocks in Gauss-Seidel fashion, and then updates the dual multiplier.The penalty improves numerical tractability but couples the blocks, motivating inexact cyclic minimization.
- Prior convergence analysis: For two blocks, prior rate analyses generally require strong convexity or additional smoothness and rank assumptions.Earlier results included sublinear objective-value rates, while linear convergence was known under stronger conditions or special cases.
- Contribution: The paper proves global linear convergence for ADMM with arbitrary K under an error-bound condition covering applications including LASSO, Group LASSO, and Sparse Group LASSO.The error bound relates distance to the optimal solution set to a proximity residual.
2 Technical Preliminaries
The technical preliminaries establish assumptions ensuring well-posed primal and dual problems, differentiable dual functions, and error bounds. These ingredients connect proximal residuals and dual gradients to distances from the relevant optimal solution sets.
- Assumptions: The standing assumptions allow nonsmooth convex components, possibly absent strongly convex parts, while imposing structural conditions on submatrices and feasible sets.The feasible sets are assumed compact and polyhedral, and each submatrix E_k has full column rank.
- Assumptions: Under the assumptions, primal and dual optimal values are attained and equal, although primal or dual optimal solutions may be nonunique.Compactness supports the error bounds used later in the convergence analysis.
- Dual properties: The augmented dual function is differentiable everywhere, with gradient ∇d(y) = q − Ex(y) for any minimizer x(y).The constraint image Ex is invariant across minimizers of the augmented Lagrangian.
- Dual properties: On suitable dual level sets, the dual gradient satisfies a Lipschitz continuity property derived from the augmented-Lagrangian minimizers.The proof uses ρ∥E(x′ − x)∥ ≤ ∥y′ − y∥ together with the gradient representation.
- Error bounds: Proximal error bounds control distance to minimizers by a proximal-gradient residual over polyhedral, and under compactness broader, feasible domains.The constants can be chosen independently of y, extending the usual local bounds over compact sets.
- Error bounds: A dual error bound relates dist(y, Y*) to ∥∇d(y)∥ when the dual iterate lies on an appropriate level set and has sufficiently small gradient.This bound supplies the link between dual residuals and distance to the optimal dual solution set.
3 Linear Convergence of ADMM
The analysis proves linear convergence of ADMM by showing that combined primal and dual optimality gaps decrease geometrically when the dual stepsize is sufficiently small. Under the stated assumptions, primal-dual iterates and feasibility violations converge linearly, with extensions covering weaker compactness requirements and applications.
- Proof strategy: The proof bounds dual and primal optimality gaps using error bounds, descent estimates, proximity residuals, and induction on the combined gap.The argument first estimates gap sizes and reductions, then chooses α small enough to maintain descent across iterations.
- Gap reduction: The sum of primal and dual optimality gaps decreases at every ADMM iteration when the dual stepsize α is sufficiently small.Neither gap must decrease separately; the combined descent establishes the contraction used in the proof.
- Main convergence theorem: Under Assumption A and sufficiently small α, ADMM iterates converge linearly to an optimal primal-dual solution, while feasibility violations also converge linearly.The theorem states linear convergence for both the iterates and ∥Exr − q∥.
- Dual convergence: The dual sequence converges R-linearly because the dual-gradient residual converges R-linearly and bounds distance to the optimal dual solution set.The same estimates imply linear convergence of primal residuals and the distance between ADMM iterates and exact augmented-Lagrangian minimizers.
- Primal convergence: The primal iterates also converge R-linearly to an optimal solution after the proof establishes linear decay of the relevant primal gap and augmented-Lagrangian distance.The limit argument uses that each exact minimizer belongs to X(yr) and minimizes the Lagrangian over the feasible set.
- Scope extensions: The compactness requirement can be relaxed for polyhedral feasible sets when primal-dual iterates remain bounded, preserving the theorem's conclusions and linear convergence of function values.The corollary replaces compactness of X with boundedness of the generated primal-dual sequence under additional stated conditions.
4 Variants of ADMM
The paper extends linear-convergence guarantees to proximal and Jacobi variants of ADMM, using proximal regularization or explicit stepsize control to preserve the proof's descent and residual bounds.
- Proximal ADMM: The proximal ADMM modifies each block subproblem by adding a quadratic proximal term, making updates easier when the nonsmooth component is separable.For compressive sensing with an ℓ1 nonsmooth term, the resulting subproblem has a component-wise soft-thresholding solution.
- Proximal ADMM: The convergence results of Theorem 3.1 remain valid for proximal ADMM, including without the full-rank assumption on the block matrices when the proximal parameter is sufficiently large.The proximal term makes each subproblem strongly convex without requiring full column rank of the block matrix.
- Proximal ADMM: A sufficient-descent inequality bounds the augmented-Lagrangian decrease by γ∥x^(r+1) − x^r∥^2, with γ > 0 independent of the multiplier iterate.The estimate is obtained by summing the blockwise descent bounds over all blocks.
- Jacobi Update: Direct Jacobi updates may not decrease the augmented Lagrangian, so the paper introduces an intermediate variable and explicit stepsize control.The modified update uses a stepsize of 1/K for each variable block.
- Jacobi Update: With stepsize control, the Jacobi variant satisfies the required lemmas and inherits the convergence results of Theorem 3.1.The paper states this for the modified Jacobi scheme after adapting the descent and optimality arguments.
5 Concluding Remarks
The paper establishes convergence rates for classical ADMM with more than two blocks and without strong convexity, using an error bound and a sufficiently small dual stepsize.
- Scope and analysis: The analysis covers classical ADMM with an arbitrary number of variable blocks and does not require strong convexity of the objective or row independence of the constraint matrix.These are explicit departures from the conventional weighted-norm contraction analysis.
- Proof mechanism: A local error bound and sufficiently small dual-update stepsize make the sum of primal and dual optimality gaps decrease at every ADMM iteration.The two gaps may increase separately even though their sum decreases.
- Open issue: A practical open issue is identifying effective dual-stepsize rules, because the bound suggested by the analysis may be conservative and cumbersome to compute.The paper mentions adaptive dual stepsizes as one possible direction for further research.
6 Appendix
The appendix proves a local dual error bound by reformulating the problem and applying a polyhedral multifunction argument, yielding distance to the dual solution set proportional to the dual residual.
- Proof assumptions: The proof relies on Lipschitz continuity and strong convexity of the smooth functions together with properties of the quadratic penalization.These assumptions supply the constants used in the final bound.
- Reformulation: The appendix rewrites the primal problem with an auxiliary scalar s and expresses the polyhedral constraint set through linear inequalities.For fixed y, an optimal pair (x(y), s(y)) is selected, and equivalence links dual optima to primal optima.
- Error-bound construction: The set-valued mapping M associates residual data (d,e) with tuples satisfying the reformulated optimality system.Its local Lipschitzian continuity is established using a polyhedral multifunction result.
- Error-bound result: The resulting error bound states that, near the dual solution set and for sufficiently small ∥∇d(y)∥, dist(y,Y*) ≤ τ∥∇d(y)∥.The constants δ and τ are independent of the choice of y, and τ is also independent of the coefficients of the linear term s.