Combining ADMM and the Augmented Lagrangian Method for Efficiently Handling Many Constraints

Joachim Giesen, Sören Laue

Abstract

Large-scale optimization in machine learning often involves datasets where each data point introduces a unique constraint, leading to significant computational overhead in distributed environments. While the Alternating Direction Method of Multipliers (ADMM) excels at parameter distribution and the Augmented Lagrangian Method (ALM) effectively handles constraints, their naive combination results in an inefficient three-nested-loop structure. This paper proposes a "lazy" ADMM variant that collapses these into a two-loop structure by integrating ALM updates directly into the ADMM steps. We demonstrate that this method maintains convergence guarantees and significantly improves efficiency for large-scale problems like Robust Support Vector Machines (SVMs).

Introduction

In large-scale machine learning, optimization problems frequently scale with the number of data points. For instance, in the "smallest enclosing ball" problem, every data point must satisfy a distance constraint. Distributing such problems across multiple compute nodes typically requires balancing consensus (agreement between nodes) and constraint satisfaction. Standard approaches often lead to a "loop problem": an outer loop for consensus, a middle loop for constraints, and an inner loop for unconstrained subproblems. This triple-nested structure is computationally prohibitive for massive datasets.

Methods

The proposed algorithm addresses this by merging the consensus and constraint-handling loops. Key innovations include:

  1. Constraint Reformulation: Inequality constraints $g_0(x) \leq 0$ are transformed into equivalent equality constraints $g(x) = \max\{0, g_0(x)\}^2 = 0$. This maintains convexity while simplifying the update logic.
  2. "Lazy" Augmented Lagrangian Updates: Instead of solving fully constrained subproblems at each node, nodes solve simpler unconstrained problems using an Augmented Lagrangian function.
  3. Simultaneous Dual Updates: Lagrange multipliers for both consensus and constraints are updated in the same step, reducing the algorithm to a two-loop structure similar to standard ADMM.

Results and Key Insights

The algorithm was evaluated on synthetic Robust SVM datasets, scaling up to 100,000 data points and 10,000 features across 16 nodes.

Convergence metrics for the proposed algorithm, showing objective value ($f^k$), residuals ($\|r_g^k\|, \|r_h^k\|$), and distance to optimality (\|z^k - z^*\|, \|\lambda^k - \lambda^*\|, V^k).

Monotonic Convergence vs. Objective Fluctuation

A critical theoretical insight is that while the objective value $f^k$ may fluctuate or even increase in early iterations (as seen in the objective value plot in Figure 4), the distance to the optimal solution—represented by the Lyapunov function $V^k$—is guaranteed to decrease monotonically. This ensures stable convergence despite the non-linear nature of the reformulated constraints.

Scalability and Efficiency

The method significantly outperforms the traditional three-loop baseline in wall-clock time. Interestingly, the number of iterations required for convergence decreases as the number of data points increases for a fixed feature set. This "more data is better" effect occurs because a larger local dataset provides a more accurate estimate of the global solution, facilitating faster consensus.

Conclusion

By collapsing the nested loops of ADMM and ALM, this "lazy" approach provides a scalable framework for constrained optimization in distributed systems. While the method excels at reaching medium-level precision quickly, future work will focus on establishing theoretical convergence rates and automated hyperparameter tuning for the penalty parameter $\rho$.

Summary updated

Abstract

Many machine learning methods entail minimizing a loss-function that is the sum of the losses for each data point. The form of the loss function is exploited algorithmically, for instance in stochastic gradient descent (SGD) and in the alternating direction method of multipliers (ADMM). However, there are also machine learning methods where the entailed optimization problem features the data points not in the objective function but in the form of constraints, typically one constraint per data point. Here, we address the problem of solving convex optimization problems with many convex constraints. Our approach is an extension of ADMM. The straightforward implementation of ADMM for solving constrained optimization problems in a distributed fashion solves constrained subproblems on different compute nodes that are aggregated until a consensus solution is reached. Hence, the straightforward approach has three nested loops: one for reaching consensus, one for the constraints, and one for the unconstrained problems. Here, we show that solving the costly constrained subproblems can be avoided. In our approach, we combine the ability of ADMM to solve convex optimization problems in a distributed setting with the ability of the augmented Lagrangian method to solve constrained optimization problems. Consequently, our algorithm only needs two nested loops. We prove that it inherits the convergence guarantees of both ADMM and the augmented Lagrangian method. Experimental results corroborate our theoretical findings.
BibTeX
@inproceedings{giesen2019combining,
  author = {Joachim Giesen and Sören Laue},
  title = {{Combining ADMM and the Augmented Lagrangian Method for Efficiently Handling Many Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/629},
}
Figure