mlsanityData to 14 Oct 2026

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

arXiv 2311.00678 ↗First posted 1 Nov 2023math.OC cs.LG stat.MLcited by 16

Not on the map. Why?

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.

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

33 of 62 references.

References · 33

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  3. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  4. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  5. 2022Training OOD Detectors in their Natural Habitatscited by 86
  6. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  7. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 58
  8. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  9. 2019Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimizationcited by 38
  10. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  11. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  12. 2019Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraintscited by 25
21 more
  1. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  2. 2017Iteration complexity of inexact augmented Lagrangian methods for constrained convex programmingcited by 21
  3. 2020Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimizationcited by 21
  4. 2020Training neural networks under physical constraints using a stochastic augmented Lagrangian approachcited by 20
  5. 2021Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimizationcited by 19
  6. 2022Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimizationcited by 19
  7. 2019Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraintscited by 17
  8. 2014An Accelerated Linearized Alternating Direction Method of Multiplierscited by 14
  9. 2018A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimizationcited by 14
  10. 2018The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and ratescited by 13
  11. 2020A global dual error bound and its application to the analysis of linearly constrained nonconvex optimizationcited by 13
  12. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12
  13. 2020Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimizationcited by 10
  14. 2021GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learningcited by 8
  15. 2018Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergencecited by 7
  16. 2016Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applicationscited by 6
  17. 2016Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programmingcited by 6
  18. 2020Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraintscited by 6
  19. 2022On the Iteration Complexity of Smoothed Proximal ALM for Nonconvex Optimization Problem with Convex Constraintscited by 6
  20. 2023A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guaranteescited by 6
  21. 2021Dual Descent ALM and ADMMcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 7; 2026: 4.

16 papers.

Sort:

  1. 2024Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guaranteescited by 11
  2. 2025A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimizationcited by 9
  3. 2025Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraintscited by 6
  4. 2025Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraintscited by 5
  5. 2024A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safetycited by 4
  6. 2024Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimizationcited by 2
  7. 2025Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classificationcited by 2
  8. 2024Stochastic interior-point methods for smooth conic optimization with applicationscited by 1
  9. 2026Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularitycited by 1
  10. 2024A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimizationcited by 0
  11. 2025Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimizationcited by 0
  12. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
4 more
  1. 2025Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferentialcited by 0
  2. 2026Local Constrained Bayesian Optimizationcited by 0
  3. 2026MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimizationcited by 0
  4. 2026Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Makingcited by 0