On the linear convergence of the alternating direction method of multipliers

Mingyi Hong, Zhi-Quan Luo

TL;DR

This paper tackles a crucial limitation of the Alternating Direction Method of Multipliers (ADMM), a popular optimization algorithm. It proves that ADMM can achieve linear convergence (meaning it gets faster and faster as it approaches the solution) even when dealing with more than two blocks of variables or when the objective function isn't strictly convex. This is a significant theoretical breakthrough that broadens ADMM's applicability to a wider range of complex problems.

What Problem Does This Paper Address?

The Alternating Direction Method of Multipliers (ADMM) is a powerful tool for solving large-scale optimization problems, especially those that can be broken down into smaller, separable parts. Think of problems where you want to minimize a sum of functions, each depending on a different subset of variables, subject to some linear constraints. ADMM excels at this by breaking down the problem into smaller, manageable subproblems.

However, existing theoretical analyses of ADMM's convergence rate primarily focused on two scenarios:

  1. Two Blocks of Variables: The objective function was the sum of only two convex functions.
  2. Strong Convexity: The objective function was "strongly convex," meaning it had a clear, unique minimum and a well-behaved curvature.

The problem is, ADMM is often used in practice for problems with more than two blocks of variables, and many real-world applications don't satisfy the strong convexity assumption. This created a gap: while ADMM worked well numerically in these more general settings, its theoretical guarantees of linear convergence (a desirable property indicating rapid progress towards the solution) were missing. This paper aims to bridge that gap by proving linear convergence for ADMM in these more general, multi-block, and non-strongly convex scenarios.

Methods

The core of this paper's contribution lies in its novel theoretical analysis. The authors establish the global linear convergence of ADMM for minimizing the sum of any number of convex separable functions, even without strong convexity.

Key to their approach is:

  • Error Bounds: They leverage a concept called "error bounds," which relate the distance of an iterate to the optimal solution set to a measure of how close the current solution is to satisfying the optimality conditions (a "proximity residual"). This is a crucial tool for proving convergence rates.
  • Proximal Gradient: They utilize the notion of a proximal gradient, which is a generalization of the gradient for non-smooth functions. This allows them to analyze the behavior of ADMM even when the objective functions are not differentiable everywhere.
  • Dual Ascent and Augmented Lagrangian: The analysis builds upon the framework of dual ascent methods and the augmented Lagrangian function, which are standard tools in optimization theory.
  • Careful Lemma Development: The paper meticulously develops a series of lemmas that bound various quantities related to the primal and dual optimality gaps, the distance to optimal solutions, and the gradient of the dual function. These lemmas are essential for constructing the overall convergence proof.

The proof strategy is to show that the sum of the primal and dual optimality gaps decreases at each iteration, provided the dual step size is chosen sufficiently small. This, combined with the error bounds, ultimately leads to the linear convergence of both the primal and dual iterates.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and convergence guarantees, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • ADMM is More Powerful Than We Thought: The paper demonstrates that ADMM's linear convergence is not limited to the restrictive cases of two blocks or strong convexity. This significantly expands the theoretical underpinnings of its practical success.
  • Error Bounds are Key: The reliance on local error bounds is a critical insight. These bounds provide a way to quantify how "close" a solution is to optimality, which is essential for proving convergence rates in non-smooth settings.
  • Sum of Gaps Decreases: A surprising result is that while the primal and dual gaps might individually fluctuate, their sum consistently decreases when the step size is chosen appropriately. This is a clever way to ensure overall progress towards the solution.
  • Practical Implications for LASSO and Beyond: The theoretical results directly imply linear convergence for ADMM in many contemporary applications like LASSO, Group LASSO, and Sparse Group LASSO, even without assuming strong convexity. This is a major practical benefit.

Key Results

  • Global Linear Convergence for Multi-Block ADMM: The paper establishes that ADMM achieves global linear convergence for minimizing the sum of any number of convex separable functions, subject to linear constraints, even without strong convexity.
  • Linear Convergence for Common Applications: This theoretical result directly implies linear convergence for ADMM applied to problems like LASSO, Group LASSO, and Sparse Group LASSO, without requiring strong convexity assumptions.
  • Boundedness of Iterates: Under certain conditions (e.g., polyhedral feasible sets), the paper shows that the primal and dual iterates remain bounded, which is important for the convergence analysis.
  • Error Bounds for Primal and Dual Solutions: The paper derives crucial error bounds that relate the distance to optimal solutions to the norm of certain residuals.

Limitations and Future Work

  • Step Size Selection: While the paper provides a condition for choosing the dual step size (α) to guarantee linear convergence, this condition can be conservative and difficult to compute in practice. The authors suggest that finding "good practical stepsize rules for dual update" is an interesting direction for future research. They propose exploring adaptive stepsize rules.
  • Generalization of Error Bounds: The analysis relies on specific forms of error bounds. Further research could explore if these results can be extended to more general classes of objective functions or constraints.
  • Variants of ADMM: The paper briefly touches upon variants like Proximal ADMM and Jacobi updates, suggesting that the convergence analysis can be extended. Further investigation into the convergence properties of these variants would be valuable.

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