Abstract
The Alternating Direction Method of Multipliers (ADMM) is a cornerstone of convex optimization, yet its efficacy in nonconvex settings remains largely empirical. This study provides a comprehensive "stress test" of ADMM across several challenging nonconvex applications, including $\ell_0$ regularization and phase retrieval. By comparing Vanilla ADMM with automated tuning methods like Residual Balancing and Adaptive ADMM (AADMM), we demonstrate that spectral adaptivity significantly improves convergence reliability and solution quality. Our findings highlight a substantial gap between the practical robustness of ADMM and current theoretical understanding.
Introduction
ADMM is widely utilized for its ability to decompose complex, constrained problems into manageable subproblems. While its convergence is well-established for convex problems, many modern applications—such as sparse signal recovery and phase retrieval—are inherently nonconvex. In these regimes, practitioners often rely on ADMM as a heuristic, facing significant challenges in parameter selection and convergence stability. This paper moves beyond theoretical limitations to provide an empirical roadmap for deploying ADMM in nonconvex landscapes.
Methodology
The study evaluates three primary variants of ADMM:
- Vanilla ADMM: Employs a constant, manually selected penalty parameter ($\tau$).
- Residual Balancing: Dynamically adjusts $\tau$ to maintain parity between primal and dual residuals.
- Adaptive ADMM (AADMM): Utilizes a spectral (Barzilai-Borwein) rule to tune the penalty parameter based on local problem curvature.
These methods were tested across four nonconvex domains: $\ell_0$ regularized linear regression, $\ell_0$ regularized image denoising, phase retrieval, and eigenvector computation. Benchmarks included both synthetic data and real-world datasets such as the UCI repository sets and classic grayscale images (e.g., "Barbara", "Lena").
Key Insights: The "Diva" Parameter and Adaptivity
A central finding of this study is the extreme sensitivity of Vanilla ADMM to the initial penalty parameter $\tau_0$. As shown in Figure 1, poorly chosen parameters can lead to stagnation or erratic behavior in non-adaptive versions.
Adaptive ADMM (AADMM) emerged as the clear winner. It consistently achieved faster convergence and often located superior local minima, resulting in lower objective values or higher Peak Signal-to-Noise Ratio (PSNR) compared to its counterparts. The spectral tuning rule allows the algorithm to adjust to the local curvature of the nonconvex landscape automatically.
Quantitative Results
The performance gains offered by adaptive methods are stark. Table 1 details the convergence and quality metrics across various datasets, highlighting the efficiency of AADMM.
Notable results include:
- Efficiency: In $\ell_0$ linear regression on the "Diabetes" dataset, AADMM converged in just 28 iterations, whereas Vanilla ADMM failed to converge within a 2000-iteration limit.
- Image Restoration: For the "Cameraman" dataset, AADMM achieved a PSNR of 27.8, significantly outperforming the 25.9 PSNR reached by non-adaptive versions.
- Phase Retrieval: On synthetic complex-valued signals, AADMM reached a solution in 46 iterations, compared to over 200 for Vanilla ADMM.
Discussion and Limitations
Despite the lack of global convergence proofs for these nonconvex cases, ADMM proved remarkably robust in practice. However, some limitations remain. While AADMM provides a high performance "floor," a meticulously hand-tuned Vanilla ADMM can occasionally match or slightly exceed its performance. Furthermore, the order of variable updates can impact reliability in specific tasks like phase retrieval. This study underscores a significant theoretical gap: ADMM is far more effective for nonconvex optimization than current mathematical frameworks can guarantee.
Conclusion
This empirical study validates ADMM as a powerful tool for nonconvex optimization, particularly when paired with adaptive penalty tuning. Adaptive ADMM (AADMM) effectively mitigates the sensitivity of the algorithm to initial parameters, offering a reliable and efficient path to high-quality solutions in sparse recovery and imaging tasks.
Summary updated