ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization

Yi Xu, Mingrui Liu, Qihang Lin, Tianbao YangNeurIPS 2017 · OpenReview

The Alternating Direction Method of Multipliers (ADMM) is a powerhouse algorithm for optimization, widely used in machine learning, statistics, and signal processing to solve problems with structured, non-smooth regularizers (such as LASSO or low-rank constraints). However, ADMM is notoriously sensitive to its "penalty parameter."

This paper introduces a novel adaptive penalization scheme that adjusts this parameter based on the objective function's "local sharpness." This approach leads to provably faster convergence rates in both deterministic and stochastic settings, without requiring traditional smoothness or strong convexity assumptions.

The Penalty Parameter Problem

ADMM's efficiency depends heavily on the penalty parameter ($\beta$) applied to its equality constraints. If $\beta$ is poorly chosen, convergence can be painfully slow. While "self-adaptive" methods—like residual balancing—exist to tune $\beta$ on the fly, they generally lack theoretical proof that they actually improve the convergence rate. Furthermore, most existing adaptive schemes do not translate well to the stochastic setting, where algorithms only have access to noisy gradients.

The authors bridge this gap by creating an adaptive ADMM that is both practically robust and theoretically superior.

Locally Adaptive ADMM (LA-ADMM)

The authors introduce Locally Adaptive ADMM (LA-ADMM) and its stochastic counterpart, LA-SADMM. The core innovation is tying the penalty parameter to a property called the Local Error Bound (LEB), or "local sharpness."

  • Local Sharpness ($\theta$): This parameter characterizes how fast the objective function grows as you move away from the optimal solution set. For example, polyhedral functions (like those in linear programming) have $\theta = 1$, while piecewise quadratic functions have $\theta = 1/2$.
  • Multi-Stage Strategy: Instead of tweaking $\beta$ every iteration, the algorithms operate in stages. At the end of each stage, the penalty parameter $\beta$ is doubled.
  • Linearization: To handle complex constraints where the standard update step is difficult, the authors incorporate a linearized version of ADMM, making the subproblems easier to solve.
  • Domain Shrinking (Stochastic): In the stochastic version (LA-SADMM), the algorithm also "shrinks" the feasible domain at each stage. This helps control the variance of the stochastic noise as the algorithm homes in on the true solution.

Theoretical and Empirical Speedups

The most significant insight of this work is that the local geometry of the objective function can be exploited to accelerate ADMM. By increasing the penalty parameter at a rate dictated by this sharpness, the algorithm achieves better complexity than standard ADMM.

In the deterministic setting, standard ADMM has a complexity of $O(1/\epsilon)$. LA-ADMM improves this to $O(1/\epsilon^{1-\theta})$. If the problem is "sharp" enough ($\theta=1$), the algorithm achieves linear convergence—a major theoretical win for a non-smooth, non-strongly convex solver. For stochastic optimization, standard methods usually suffer from $O(1/\epsilon^2)$ complexity. LA-SADMM reduces this to $\tilde{O}(1/\epsilon^{2(1-\theta)})$, making it vastly more efficient for large-scale problems.

Empirical comparison of LA-ADMM and LA-SADMM against standard baselines across multiple datasets and tasks.

The authors evaluated their algorithms on several standard benchmarks, including real-world datasets from the LIBSVM library (w8a and gisette) for SVM classification, and synthetic data for robust regression and low-rank representation. In experiments, LA-ADMM and LA-SADMM consistently converged faster than standard ADMM, even when the standard version's penalty parameter was manually fine-tuned. They also outperformed popular adaptive schemes like Residual Balancing (ADMM-RB) and Adaptive Penalty (ADMM-AP).

Practical Implementation: The Restarting Heuristic

One limitation of the foundational LA-ADMM framework is parameter dependency. The theoretical optimal stage length ($t$) and initial penalty ($\beta_1$) depend on the sharpness exponent $\theta$ and a constant $c$, which are often unknown in practice.

Algorithms 5 and 6 detail the Restarting variants of LA-ADMM and LA-SADMM.

To address these unknown parameters, the authors propose "Restarting" variants of the algorithms. While these restarting mechanisms add a layer of heuristic complexity to the implementation, they allow the algorithms to dynamically adjust without requiring prior knowledge of the function's exact sharpness, making them highly effective in practice.

Overall, this paper provides a rigorous foundation for why and how we should adapt ADMM's penalty parameter, turning a common "dark art" of optimization into a principled, high-performance technique.

Summary updated

Abstract

Alternating direction method of multipliers (ADMM) has received tremendous interest for solving numerous problems in machine learning, statistics and signal processing. However, it is known that the performance of ADMM and many of its variants is very sensitive to the penalty parameter of a quadratic penalty applied to the equality constraints. Although several approaches have been proposed for dynamically changing this parameter during the course of optimization, they do not yield theoretical improvement in the convergence rate and are not directly applicable to stochastic ADMM. In this paper, we develop a new ADMM and its linearized variant with a new adaptive scheme to update the penalty parameter. Our methods can be applied under both deterministic and stochastic optimization settings for structured non-smooth objective function. The novelty of the proposed scheme lies at that it is adaptive to a local sharpness property of the objective function, which marks the key difference from previous adaptive scheme that adjusts the penalty parameter per-iteration based on certain conditions on iterates. On theoretical side, given the local sharpness characterized by an exponent $\theta\in(0, 1]$, we show that the proposed ADMM enjoys an improved iteration complexity of $\widetilde O(1/\epsilon^{1-\theta})$\footnote{$\widetilde O()$ suppresses a logarithmic factor.} in the deterministic setting and an iteration complexity of $\widetilde O(1/\epsilon^{2(1-\theta)})$ in the stochastic setting without smoothness and strong convexity assumptions. The complexity in either setting improves that of the standard ADMM which only uses a fixed penalty parameter. On the practical side, we demonstrate that the proposed algorithms converge comparably to, if not much faster than, ADMM with a fine-tuned fixed penalty parameter.
BibTeX
@inproceedings{xu2017admm,
  author = {Yi Xu and Mingrui Liu and Qihang Lin and Tianbao Yang},
  title = {{ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=rJ4dJ_Wd-S},
}
Figure