A Unified Inexact Stochastic ADMM for Composite Nonconvex and Nonsmooth Optimization

Yuxuan Zeng, Jianchao Bai, Shengjia Wang, Zhiguo WangarXiv 2024 · DOI · arXiv

In the world of large-scale machine learning, optimization is the engine under the hood. While the Alternating Direction Method of Multipliers (ADMM) has long been a favorite for solving problems with linear constraints, applying it to modern "messy" problems—those that are both nonconvex (like neural networks) and nonsmooth (like sparsity-inducing penalties)—remains a significant challenge.

A recent paper titled "A Unified Inexact Stochastic ADMM for Composite Nonconvex and Nonsmooth Optimization" introduces a powerful new framework to bridge this gap. The researchers propose a versatile system that not only simplifies the analysis of existing algorithms but also paves the way for a high-performance newcomer: AH-SADMM.

TL;DR

The authors present a unified framework (UI-SADMM) for analyzing stochastic ADMM algorithms, covering popular methods like SVRG-ADMM and SPIDER-ADMM. They introduce a novel accelerated hybrid algorithm (AH-SADMM) that uses a "hybrid" gradient estimator to balance variance and bias, achieving faster convergence and better accuracy on complex nonconvex tasks.

What Problem Does This Paper Address?

Most modern machine learning models involve "finite-sum" optimization—where you minimize an average loss over millions of data points. Deterministic ADMM is too slow here because it requires calculating the gradient for the entire dataset at every step. Stochastic versions (S-ADMM) solve this by using small batches, but they introduce "noise" (variance) that can slow down convergence.

Furthermore, many real-world objectives are nonconvex (they have many local minima) and nonsmooth (they have "kinks," like the $L_1$ norm used for sparsity). Existing stochastic ADMM variants often struggle with these properties, requiring massive memory to store gradients or being overly sensitive to the "dual stepsize"—the parameter that controls how constraints are enforced.

Methods

The paper makes three major contributions:

  1. UI-SADMM (The Framework): A unified analysis framework for inexact stochastic ADMM. "Inexact" means the algorithm doesn't need to solve its internal sub-problems perfectly, which is a huge win for computational efficiency.
  2. AH-SADMM (The Algorithm): The authors design an Accelerated Hybrid Stochastic ADMM. Its secret sauce is a hybrid gradient estimator that blends a biased recursive estimator (similar to SARAH) with an unbiased one. This allows the algorithm to "trade-off" between variance reduction and bias to find the fastest path to a solution.
  3. Flexible Dual Stepsize: Traditionally, the dual stepsize $s$ was restricted to a narrow range (around 1.618). The authors prove that their framework remains stable for $s \in (0, 2)$, offering more flexibility and better numerical performance.

Datasets

The researchers validated their approach on several standard benchmarks from the LIBSVM library and computer vision:

  • Binary Classification: Used ijcnn1, a9a, w8a, and covtype.binary datasets to test nonconvex sigmoid loss with SCAD (Smoothly Clipped Absolute Deviation) penalties.
  • Image Classification: Used MNIST and CIFAR-10 to perform "weight pruning" on the LeNet-5 neural network architecture, demonstrating how the algorithm handles nonsmooth sparsity constraints in deep learning.

Key Insights and Ideas

  • The Power of Hybridization: The hybrid estimator is a "best of both worlds" approach. By tuning a parameter ($\alpha$), the algorithm can act more like a recursive method (fast but biased) or a standard stochastic method (unbiased but high variance).
  • Potential Function Analysis: To prove convergence for such a broad class of algorithms, the authors constructed a sophisticated "potential function." This mathematical tool tracks the progress of the algorithm across primal variables, dual variables, and the constraints simultaneously.
  • Linear Convergence: The paper establishes that under "error bound conditions" (a common property in many ML problems), the algorithm doesn't just crawl toward the solution—it converges at a linear rate, which is exceptionally fast for stochastic methods.

Key Results

  • Superior Speed: In numerical experiments, AH-SADMM consistently outperformed standard SADMM, SVRG-ADMM, and SPIDER-ADMM in terms of "effective passes" (how many times the algorithm looks at the data).
  • Better Generalization: On the ijcnn1 and a9a datasets, the proposed method reached higher test accuracy faster than its competitors.
  • Neural Network Pruning: When training LeNet-5, AH-SADMM achieved lower training loss and higher test accuracy while effectively enforcing the sparsity required for weight pruning.
  • Theoretical Robustness: The framework preserves $\mathcal{O}(1/T)$ sublinear convergence even when sub-problems are solved inexactly, making it highly practical for real-world code.

Limitations and Future Work

While the framework is highly versatile, the authors note that the current work focuses on centralized optimization. They suggest that a promising next step is extending this unified stochastic ADMM framework to distributed problems, where data is spread across multiple servers or devices (Federated Learning). Additionally, while they provide a theoretical guide for the hybrid parameter $\alpha$, finding the "optimal" $\alpha$ automatically for any given dataset remains an open area for exploration.

Summary updated

Abstract

In this paper, we propose a unified framework of inexact stochastic Alternating Direction Method of Multipliers (ADMM) for solving nonconvex problems subject to linear constraints, whose objective comprises an average of finite-sum smooth functions and a nonsmooth but possibly nonconvex function. The new framework is highly versatile. Firstly, it not only covers several existing algorithms such as SADMM, SVRG-ADMM, and SPIDER-ADMM but also guides us to design a novel accelerated hybrid stochastic ADMM algorithm, which utilizes a new hybrid estimator to trade-off variance and bias. Second, it enables us to exploit a more flexible dual stepsize in the convergence analysis. Under some mild conditions, our unified framework preserves $\mathcal{O}(1/T)$ sublinear convergence. Additionally, we establish the linear convergence under error bound conditions. Finally, numerical experiments demonstrate the efficacy of the new algorithm for some nonsmooth and nonconvex problems.
BibTeX
@misc{zeng2024unified,
  author = {Yuxuan Zeng and Jianchao Bai and Shengjia Wang and Zhiguo Wang},
  title = {{A Unified Inexact Stochastic ADMM for Composite Nonconvex and Nonsmooth Optimization}},
  year = {2024},
  eprint = {2403.02015},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.02015},
}
Figure