# Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization

arXiv: https://arxiv.org/abs/2008.01296 · HTML: https://mlsanity.com/paper/2008.01296/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2020.

## Built on by (most cited first, 10 of 10)

- [Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating](https://mlsanity.com/paper/2103.00958/) (2021)
- [AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilization](https://mlsanity.com/paper/2109.12519/) (2021)
- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Desirable Companion for Vertical Federated Learning: New Zeroth-Order Gradient Based Algorithm](https://mlsanity.com/paper/2203.10329/) (2022)
- [A Framework of Inertial Alternating Direction Method of Multipliers for Non-Convex Non-Smooth Optimization](https://mlsanity.com/paper/2102.05433/) (2021)
- [Preconditioned Inexact Stochastic ADMM for Deep Model](https://mlsanity.com/paper/2502.10784/) (2025)
- [Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT](https://mlsanity.com/paper/2107.00481/) (2021)
- [A General Continuous-Time Formulation of Stochastic ADMM and Its Variants](https://mlsanity.com/paper/2404.14358/) (2024)
- [A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization](https://mlsanity.com/paper/2412.14488/) (2024)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (2025)

## Abstract (arXiv)

In this paper, we propose a faster stochastic alternating direction method of multipliers (ADMM) for nonconvex optimization by using a new stochastic path-integrated differential estimator (SPIDER), called as SPIDER-ADMM. Moreover, we prove that the SPIDER-ADMM achieves a record-breaking incremental first-order oracle (IFO) complexity of O(n+n1/2ε-1) for finding an ε-approximate stationary point, which improves the deterministic ADMM by a factor O(n1/2), where n denotes the sample size. As one of major contribution of this paper, we provide a new theoretical analysis framework for nonconvex stochastic ADMM methods with providing the optimal IFO complexity. Based on this new analysis framework, we study the unsolved optimal IFO complexity of the existing non-convex SVRG-ADMM and SAGA-ADMM methods, and prove they have the optimal IFO complexity of O(n+n2/3ε-1). Thus, the SPIDER-ADMM improves the existing stochastic ADMM methods by a factor of O(n1/6). Moreover, we extend SPIDER-ADMM to the online setting, and propose a faster online SPIDER-ADMM. Our theoretical analysis shows that the online SPIDER-ADMM has the IFO complexity of O(ε^-frac32), which improves the existing best results by a factor of O(ε^-frac12). Finally, the experimental results on benchmark datasets validate that the proposed algorithms have faster convergence rate than the existing ADMM algorithms for nonconvex optimization.