Self Equivalence of the Alternating Direction Method of Multipliers

Ming Yan, Wotao YinScientific 2016 · DOI · arXiv · OpenAlex

Abstract

The Alternating Direction Method of Multipliers (ADMM) is a cornerstone of modern large-scale optimization, yet its flexibility often leads to a "paradox of choice" regarding primal, dual, and saddle-point formulations. This paper establishes a theoretical unification of these approaches, proving that many seemingly distinct ADMM variants are mathematically equivalent. By defining equivalence through linear transformations of algorithmic iterates, the authors demonstrate that the choice between primal and dual forms is often cosmetic, shifting the focus of algorithm selection from theoretical performance to computational efficiency.

Introduction

In fields ranging from machine learning to signal processing, ADMM is prized for its ability to decompose complex problems into manageable subproblems. For a standard optimization problem of the form $\min_x u(x) + v(Cx)$, practitioners face a multitude of implementation choices: applying ADMM to the primal form, the Lagrange dual, or a saddle-point formulation. Furthermore, the order of variable updates and the method of introducing auxiliary variables can result in over a dozen different algorithmic trajectories.

Historically, the literature has seen conflicting preferences, with different researchers advocating for specific formulations based on empirical observations. Yan and Yin (2015) address this fragmentation by investigating whether these variations produce truly different algorithms or if they are merely different perspectives on the same underlying mathematical process.

Theoretical Framework: Defining Equivalence

The authors utilize rigorous algebraic proofs to establish "equivalence maps" between algorithmic sequences. Two algorithms are defined as equivalent if the iterates of one can be exactly recovered from the iterates of the other using simple linear transformations. This framework allows the authors to bridge the gap between several major branches of optimization literature.

Primal-Dual Symmetry

A central insight of the paper is the inherent symmetry between primal and dual variables. The authors show that ADMM treats these variables with surprising parity; specifically, the dual variable in a primal ADMM formulation serves as the primal variable in the corresponding dual ADMM formulation. This symmetry underpins the proof that Primal ADMM and Dual ADMM are, in fact, the same algorithm viewed through different lenses.

The Role of Quadratic Objectives

One of the most practical contributions of this work concerns the order of Gauss-Seidel-style updates. In standard ADMM, one typically updates variable $x$ and then variable $y$. The authors prove that if at least one of the objective functions is quadratic (e.g., a least-squares term), the sequence generated by an $x \to y$ update is equivalent to the $y \to x$ update. This "update-order equivalence" simplifies the implementation process for a wide class of problems in statistics and image processing.

Key Results and Theorems

The paper formalizes these insights through several landmark theorems:

  1. Theorem 1 (Primal-Dual Equivalence): Formally establishes that Primal ADMM and Dual ADMM generate equivalent iterate sequences.
  2. Theorem 2 (Saddle-Point Mapping): Demonstrates that ADMM is equivalent to a specific primal-dual algorithm applied to a saddle-point problem, unifying ADMM with the broader class of Primal-Dual Hybrid Gradient (PDHG) methods.
  3. Theorem 3 (Update-Order Equivalence): Proves that the order of variable updates is irrelevant to the algorithm's trajectory provided the proximal operator of one function is affine (a condition met by quadratic functions).

To illustrate these findings, the authors apply their theory to the Total Variation (TV) image denoising model (the ROF model). They demonstrate that for this classic problem, the primal ADMM, dual ADMM, and various saddle-point formulations all collapse into the same mathematical trajectory.

Discussion and Practical Implications

By proving these equivalences, Yan and Yin shift the criteria for choosing an ADMM formulation. Since the mathematical path (and thus the convergence rate) is identical across equivalent forms, the "best" version is simply the one that is most computationally friendly. Practitioners should select the formulation where subproblems yield closed-form solutions or can be solved via efficient operations like the Fast Fourier Transform (FFT).

Limitations

Despite mathematical equivalence, the authors note two critical caveats:

  • Numerical Stability: In practice, different formulations may exhibit varying sensitivity to floating-point round-off errors. One version may be more robust in finite-precision arithmetic than its equivalent counterpart.
  • Non-Quadratic Constraints: The update-order equivalence is strictly dependent on at least one function being quadratic. In problems involving two non-quadratic terms (such as two $L_1$ norms), the update order remains a consequential choice that produces distinct algorithms.

Conclusion

This work provides a significant simplification of the ADMM landscape. By proving that primal, dual, and saddle-point ADMM are often identical, the authors eliminate the need for exhaustive comparison between these forms, allowing researchers to focus on the implementation details that most directly impact computational speed and numerical robustness.

Summary updated

BibTeX
@inproceedings{yan2016self,
  author = {Ming Yan and Wotao Yin},
  title = {{Self Equivalence of the Alternating Direction Method of Multipliers}},
  booktitle = {Scientific},
  year = {2016},
  doi = {10.1007/978-3-319-41589-5\_5},
}
Figure