An Empirical Study of ADMM for Nonconvex Problems

Zheng Xu, Soham De, Mário A. T. Figueiredo, Christoph Studer, Tom GoldsteinarXiv 2016 · arXiv

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:

  1. Vanilla ADMM: Employs a constant, manually selected penalty parameter ($\tau$).
  2. Residual Balancing: Dynamically adjusts $\tau$ to maintain parity between primal and dual residuals.
  3. 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.

Figure 1: Performance metrics (iterations and objective/PSNR) as a function of the initial penalty parameter. Adaptive ADMM (blue) demonstrates significantly higher robustness compared to Vanilla (green) and Residual Balancing (magenta).

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.

Table 1: Quantitative comparison of ADMM variants. Bold values indicate superior performance by Adaptive ADMM in terms of iterations and solution quality (Objective/PSNR).

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

Abstract

The alternating direction method of multipliers (ADMM) is a common optimization tool for solving constrained and non-differentiable problems. We provide an empirical study of the practical performance of ADMM on several nonconvex applications, including l0 regularized linear regression, l0 regularized image denoising, phase retrieval, and eigenvector computation. Our experiments suggest that ADMM performs well on a broad class of non-convex problems. Moreover, recently proposed adaptive ADMM methods, which automatically tune penalty parameters as the method runs, can improve algorithm efficiency and solution quality compared to ADMM with a non-tuned penalty.
BibTeX
@misc{xu2016empirical,
  author = {Zheng Xu and Soham De and Mário A. T. Figueiredo and Christoph Studer and Tom Goldstein},
  title = {{An Empirical Study of ADMM for Nonconvex Problems}},
  year = {2016},
  eprint = {1612.03349},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.03349},
}
Figure