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:
- 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.
- "Lazy" Augmented Lagrangian Updates: Instead of solving fully constrained subproblems at each node, nodes solve simpler unconstrained problems using an Augmented Lagrangian function.
- 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.
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