Trajectory of Alternating Direction Method of Multipliers and Adaptive Acceleration

Clarice Poon, Jingwei LiangNeurIPS 2019 · OpenReview

Executive Summary

This paper reveals that the Alternating Direction Method of Multipliers (ADMM) doesn't always move toward a solution in a straight line; instead, it often follows a spiral trajectory, especially when dealing with non-smooth problems. Because standard "inertial" acceleration (like Nesterov’s momentum) assumes a straight-line path, it often fails or slows down ADMM. To address this, the authors propose A³DMM, an adaptive acceleration scheme that recognizes these geometric patterns to significantly speed up convergence.

The Challenge of Accelerating ADMM

ADMM is a workhorse algorithm in machine learning and image processing because it can break complex optimization problems into smaller, manageable pieces. However, making ADMM faster has proven difficult.

The "gold standard" for speeding up first-order methods is inertial acceleration (adding a "momentum" term based on the previous step). While this works wonders for gradient descent (e.g., FISTA), it often behaves erratically with ADMM. Researchers previously didn't have a clear geometric understanding of why this happens. This paper identifies the gap: standard acceleration assumes the algorithm's iterates are heading directly for the goal. However, ADMM’s iterates often "orbit" the solution in a spiral, making simple momentum point in the wrong direction.

Visualizing ADMM trajectories: (a) shows the spiral path often taken by ADMM, while (b) and (d) demonstrate how standard inertial acceleration can lead to erratic oscillations or slowdowns compared to standard ADMM.

Methodology: Trajectory Analysis and A³DMM

The authors' approach bridges theoretical geometric analysis with a novel algorithmic design:

  1. Trajectory Analysis: Using the concept of "partial smoothness," the authors linearize the ADMM steps near the solution. They prove that if the functions being optimized are non-smooth (like the $\ell_1$-norm in LASSO), the iterates follow a spiral. If one function is smooth, the path might be a straight line or a spiral depending on the penalty parameter ($\gamma$).
  2. A³DMM (Adaptive Acceleration for ADMM): Since fixed momentum fails on spirals, the authors propose an adaptive scheme. Instead of just looking at the last step, A³DMM looks at the last $q$ steps (a small buffer). It uses these to estimate the local geometry of the trajectory and performs a multi-step extrapolation. This is mathematically related to classical numerical analysis techniques like Minimal Polynomial Extrapolation (MPE) and Reduced Rank Extrapolation (RRE), but applied dynamically within the optimization loop.

Key Insights

  • The "Spiral" Revelation: The most striking insight is that the trajectory of ADMM is governed by the eigenvalues of a transition matrix. When these eigenvalues are complex, the optimization path forms a spiral. Standard momentum assumes real eigenvalues (straight lines), which explains its frequent failure in this context.
  • Inertia is Blind: The paper demonstrates that if you use standard momentum on a spiral, you can actually move further away from the solution in the short term, leading to the "oscillations" often seen in accelerated ADMM plots.
  • Geometry over Assumptions: Instead of requiring the problem to be "strongly convex" or "smooth" to guarantee acceleration, A³DMM adapts to the actual observed path of the iterates. If the path is a spiral, the extrapolation "cuts the corner" of the spiral to jump closer to the center.

Experimental Results

The authors evaluated their method on several standard optimization benchmarks, including synthetic data for Basis Pursuit (using $\ell_1$, $\ell_{1,2}$, and Nuclear norms) and real-world LIBSVM datasets (covtype, ijcnn1, phishing) for LASSO formulations.

Convergence comparisons across different norms. The proposed A³DMM consistently achieves faster convergence to high-precision solutions compared to standard and inertial ADMM.
  • Consistent Speedup: In tests on LASSO and Basis Pursuit, A³DMM reached high-precision solutions (e.g., $10^{-8}$ error) significantly faster than standard ADMM or fixed inertial ADMM.
  • Robustness to $\gamma$: Standard ADMM is very sensitive to the choice of the penalty parameter $\gamma$. A³DMM proved much more robust, providing acceleration even when $\gamma$ was not tuned perfectly.
  • Low Overhead: The extra computational cost of the adaptive step is very small (roughly $O(nq^2)$), making it practical for high-dimensional problems where $n$ is large but the buffer $q$ is small (e.g., $q=5$ or $10$).

Limitations and Future Work

  • Parameter $q$: While the algorithm is adaptive, the user still needs to choose the buffer size $q$. While small values generally work well, there isn't yet a formal rule for selecting the "optimal" $q$.
  • Global Convergence: The theoretical acceleration guarantees are "local," meaning they are proven to work once the algorithm gets close enough to the solution to see the geometric pattern. While it works well in practice from the start, a global theoretical guarantee for the accelerated rate remains an open challenge.
  • Non-convexity: The current work focuses on convex problems. Extending this geometric trajectory analysis to non-convex ADMM (often used in deep learning) would be a significant next step.

Summary updated

Abstract

The alternating direction method of multipliers (ADMM) is one of the most widely used first-order optimisation methods in the literature owing to its simplicity, flexibility and efficiency. Over the years, numerous efforts are made to improve the performance of the method, such as the inertial technique. By studying the geometric properties of ADMM, we discuss the limitations of current inertial accelerated ADMM and then present and analyze an adaptive acceleration scheme for the method. Numerical experiments on problems arising from image processing, statistics and machine learning demonstrate the advantages of the proposed acceleration approach.
BibTeX
@inproceedings{poon2019trajectory,
  author = {Clarice Poon and Jingwei Liang},
  title = {{Trajectory of Alternating Direction Method of Multipliers and Adaptive Acceleration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=5hY5EwbVMI},
}
Figure