# Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 62 references that are in the map.
- First posted on arXiv 1 Nov 2023.

## Builds on (most cited first, 30 of 33)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Training OOD Detectors in their Natural Habitats](https://mlsanity.com/paper/2202.03299/) (2022)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017)
- [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020)
- [Training neural networks under physical constraints using a stochastic augmented Lagrangian approach](https://mlsanity.com/paper/2009.07330/) (2020)
- [Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2112.14799/) (2021)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints](https://mlsanity.com/paper/1908.00131/) (2019)
- [An Accelerated Linearized Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1401.6607/) (2014)
- [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018)
- [The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates](https://mlsanity.com/paper/1801.01994/) (2018)
- [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization](https://mlsanity.com/paper/2008.01296/) (2020)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence](https://mlsanity.com/paper/1801.03013/) (2018)
- [Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications](https://mlsanity.com/paper/1604.00543/) (2016)
- [Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming](https://mlsanity.com/paper/1606.09155/) (2016)
- [Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints](https://mlsanity.com/paper/2008.07080/) (2020)

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

- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints](https://mlsanity.com/paper/2504.07607/) (2025)
- [A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety](https://mlsanity.com/paper/2410.03955/) (2024)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)
- [Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification](https://mlsanity.com/paper/2507.15240/) (2025)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)
- [A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization](https://mlsanity.com/paper/2412.14488/) (2024)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2506.02504/) (2025)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)
- [Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making](https://mlsanity.com/paper/2606.07088/) (2026)

## Abstract (arXiv)

We analyze the complexity of single-loop quadratic penalty and augmented Lagrangian algorithms for solving nonconvex optimization problems with functional equality constraints. We consider three cases, in all of which the objective is stochastic and smooth, that is, an expectation over an unknown distribution that is accessed by sampling. The nature of the equality constraints differs among the three cases: deterministic and linear in the first case, deterministic, smooth and nonlinear in the second case, and stochastic, smooth and nonlinear in the third case. Variance reduction techniques are used to improve the complexity. To find a point that satisfies varepsilon-approximate first-order conditions, we require widetildeO(varepsilon-3) complexity in the first case, widetildeO(varepsilon-4) in the second case, and widetildeO(varepsilon-5) in the third case. For the first and third cases, they are the first algorithms of "single loop" type (that also use O(1) samples at each iteration) that still achieve the best-known complexity guarantees.