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.
Methodology: Trajectory Analysis and A³DMM
The authors' approach bridges theoretical geometric analysis with a novel algorithmic design:
- 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$).
- 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.
- 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