On the Linear Convergence of the Alternating Direction Method of Multipliers

Mingyi Hong, Zhi‐Quan Luo

Abstract

This paper provides a rigorous theoretical foundation for the Alternating Direction Method of Multipliers (ADMM) by establishing its global linear convergence for problems involving any number of variable blocks. Crucially, the authors remove the standard requirement for strong convexity in the objective function, instead utilizing a proximal error bound analysis. This result bridges the long-standing gap between ADMM's empirical success in multi-block applications—such as LASSO and Robust PCA—and its formal mathematical guarantees. By requiring only a sufficiently small dual stepsize, the authors prove that ADMM achieves a geometric rate of convergence for a wide class of contemporary optimization problems.

Introduction

The Alternating Direction Method of Multipliers (ADMM) has emerged as a "workhorse" algorithm in modern data science and large-scale optimization. Its popularity stems from its ability to decompose complex, constrained problems into smaller, manageable subproblems that can be solved sequentially or in parallel. Despite its widespread use, a significant disconnect existed between the algorithm's practical performance and its theoretical underpinnings.

Historically, formal convergence proofs for ADMM were largely restricted to two-block variable cases ($K=2$). Furthermore, guaranteeing a "linear" convergence rate—where the error decreases geometrically—typically required the objective function to be strongly convex. However, many critical applications in machine learning and signal processing, such as LASSO, Group LASSO, and Sparse Group LASSO, involve convex but non-strongly convex objectives. This paper addresses these gaps by establishing global linear convergence for an arbitrary number of blocks without the necessity of strong convexity.

The Multi-Block Challenge

Prior to this work, the application of ADMM to problems with three or more blocks ($K \ge 3$) was considered mathematically "risky," even though researchers frequently reported success in fields like Robust Principal Component Analysis (PCA). The primary challenge in the multi-block setting is that the standard "contraction" arguments used for two-block ADMM do not easily generalize.

Additionally, the absence of strong convexity in many $L_1$-regularized models meant that researchers could only guarantee sublinear convergence rates at best, which did not reflect the high-speed convergence often observed in practice. The authors set out to determine if the inherent structure of these problems—specifically those involving polyhedral sets and separable convex functions—could be leveraged to prove faster convergence.

Methodology: The Proximal Error Bound

The core innovation of this paper is the departure from traditional contraction-based analysis in favor of an error bound condition. The authors analyze the standard ADMM algorithm, which updates primal variable blocks in a Gauss-Seidel fashion followed by a dual variable update.

To prove linear convergence, they employ a "proximal residual" to estimate the distance from a current iteration to the set of optimal primal-dual solutions. This residual essentially measures how much the variables change during a single optimization step. The proof demonstrates that if the problem structure satisfies certain error bound properties (which are common in contemporary models), the sum of the primal and dual optimality gaps is guaranteed to decrease geometrically.

The Role of the Dual Stepsize

A critical requirement for this convergence guarantee is that the dual stepsize ($\alpha$) must be sufficiently small. The authors show that the dual update is the most sensitive component of the multi-block system. By adopting a conservative stepsize, the algorithm stabilizes the interactions between multiple variable blocks, ensuring that the feasibility violation (the degree to which linear constraints are broken) also vanishes at a linear rate.

Key Insights and Applications

Beyond Strong Convexity

The paper’s most significant insight is that strong convexity is not a prerequisite for linear convergence. Instead, the "error bound" property—inherent in many $L_1$ and polyhedral problems—is sufficient. This unified framework covers a massive range of models, including:

  • LASSO and Group LASSO: Standard tools for sparse feature selection.
  • Principal Component Analysis (PCA): Specifically versions involving linear constraints and separable objectives.
  • Support Vector Machines (SVM): When formulated in a separable, constrained manner.

Algorithm Variants

The authors extend their proof beyond the "classic" ADMM to include:

  1. Proximal ADMM: Useful when subproblems are difficult to solve exactly and require an additional proximal term for stability.
  2. Jacobi ADMM: A modified version where blocks are updated in parallel rather than sequentially, which is vital for distributed computing environments.

Conclusion and Limitations

This work settles a key debate in the optimization community by formally justifying the use of ADMM for $K \ge 3$ blocks. It provides the first proof of global linear convergence for multi-block ADMM without requiring strong convexity, aligning theoretical expectations with empirical reality.

However, some limitations remain for future exploration:

  • Conservative Stepsizes: The theoretical bound for the dual stepsize $\alpha$ provided in the proof is often much smaller than what is used in practice. Real-world implementations often converge with larger stepsizes, suggesting that the theoretical bounds may be pessimistic.
  • Compactness Assumption: The primary proof assumes that the feasible sets for the variables are compact (bounded). While the authors provide corollaries to relax this, it remains a constraint on the most general form of the mathematical proof.
  • Parameter Estimation: The constants required to determine the exact convergence rate (such as the error bound constant $\tau$) are often difficult to compute for a specific problem instance, making it challenging to predict the exact number of iterations required for a given problem beforehand.

Summary updated

Abstract

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.
BibTeX
@article{hong2017linear,
  author = {Mingyi Hong and Zhi‐Quan Luo},
  title = {{On the Linear Convergence of the Alternating Direction Method of Multipliers}},
  journal = {Math. Program.},
  year = {2017},
  doi = {10.1007/s10107-016-1034-2},
}
Figure