Alternating direction method of multipliers for convex programming: a lift-and-permute scheme

Shiru Li, Yong Xia, Tao ZhangarXiv 2022 · DOI · arXiv

TL;DR

This paper introduces a "lift-and-permute" framework that unifies several heavy-hitting optimization algorithms—including Balanced ALM, Proximal ADMM, and Douglas-Rachford splitting—under a single theoretical umbrella. By viewing these methods as specific permutations of a "lifted" ADMM, the authors derive the first accelerated versions of Balanced ALM, achieving an optimal $O(1/k^2)$ convergence rate for strongly convex problems.

What Problem Does This Paper Address?

In the world of convex programming, we often want to minimize a function $f(x)$ subject to linear constraints $Ax = b$. The classic tool for this is the Augmented Lagrangian Method (ALM). However, ALM has a notorious "coupling" problem: the quadratic penalty term $\|Ax-b\|^2$ can make the sub-problems incredibly difficult to solve if $f(x)$ isn't particularly friendly with the matrix $A$.

Researchers have developed various workarounds:

  1. Proximal ALM: Adds a "proximity term" to simplify the math, but it often requires tiny step sizes if the matrix $A$ is "large" (high spectral norm), leading to slow convergence.
  2. Balanced ALM: A more recent innovation that removes these step-size restrictions but was previously seen as a somewhat distinct algorithm.
  3. ADMM and Douglas-Rachford Splitting: Popular splitting methods that handle complex objectives by breaking them into smaller pieces.

The gap addressed here is twofold: first, these algorithms were often studied in isolation despite their similarities. Second, while "Balanced" versions of ALM were robust, they lacked the high-speed "accelerated" variants (like Nesterov acceleration) common in other areas of optimization.

Methods

The authors propose a Lift-and-Permute scheme. The technique involves two main steps:

  1. Lifting: They "lift" the dual problem of the original convex program by introducing auxiliary variables. This transforms the problem into a three-block structure that is more flexible.
  2. Permuting: This is the "aha" moment. The authors show that by simply changing the order in which variables (the primal variables, the auxiliary variables, and the Lagrange multipliers) are updated within a standard ADMM cycle, you recover different famous algorithms.

By systematically exploring these permutations, they prove that:

  • One specific order yields the Balanced ALM.
  • Another yields the Dual-Primal Balanced ALM.
  • Others correspond to Proximal ADMM and Douglas-Rachford Splitting.

Finally, they apply Nesterov-like momentum techniques to this unified structure to create Algorithm 7 (Accelerated Balanced ALM) and Algorithm 8 (Accelerated Dual-Primal Balanced ALM).

Datasets

The paper is purely theoretical and focuses on mathematical proofs of equivalence and convergence rates. Consequently, no empirical datasets or benchmarks were used in this study.

Key Insights and Ideas

  • Update Order is Everything: The paper demonstrates that the fundamental difference between several state-of-the-art algorithms isn't necessarily the underlying math, but rather the sequence in which variables are updated. Swapping a primal update with a dual update can transform a "stuck" algorithm into a "balanced" one.
  • The Power of the Dual: By lifting the dual problem rather than the primal, the authors found a more natural way to decouple the constraints from the objective function.
  • Universal Acceleration: Because they successfully mapped Balanced ALM to a specific ADMM structure, they could leverage existing acceleration theories to prove that their new variants hit the $O(1/k^2)$ speed limit for strongly convex functions—a significant jump over the standard $O(1/k)$ rate.

Key Results

  • Theoretical Unification: The authors successfully categorized 24 different update permutations into four main algorithmic families (summarized in the paper's Table 1).
  • Proven Equivalence: They provided rigorous proofs showing that "Algorithm 1" in their scheme is mathematically identical to the Balanced ALM under specific parameter settings.
  • Speedup: They established that for strongly convex objectives, their accelerated lift-and-permute algorithms achieve a worst-case convergence rate of $O(1/k^2)$. This means that to get 10x more precision, you only need roughly 3x more iterations, rather than 10x.

Limitations and Future Work

  • Fixed Permutations: The current scheme relies on a fixed, deterministic order of updates. The authors suggest that exploring randomized update orders could be a fruitful next step, potentially offering even better average-case performance.
  • Equality Constraints Only: The current framework is designed for linear equality constraints ($Ax = b$). While the authors mention that the results can be generalized to inequality constraints, that extension isn't detailed in this paper.
  • Primal Lifting: This work focused on lifting the dual problem. The authors note that applying a similar "lift-and-permute" logic to the primal problem remains an open area for investigation.

Summary updated

Abstract

A lift-and-permute scheme of alternating direction method of multipliers (ADMM) is proposed for linearly constrained convex programming. It contains not only the newly developed balanced augmented Lagrangian method and its dual-primal variation, but also the proximal ADMM and Douglas-Rachford splitting algorithm. It helps to propose accelerated algorithms with worst-case $O(1/k^2)$ convergence rates in the case that the objective function to be minimized is strongly convex.
BibTeX
@misc{li2022alternating,
  author = {Shiru Li and Yong Xia and Tao Zhang},
  title = {{Alternating direction method of multipliers for convex programming: a lift-and-permute scheme}},
  year = {2022},
  eprint = {2203.16271},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.16271},
}
Figure