mlsanityData to 14 Oct 2026

Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization

arXiv 2212.09513 ↗First posted 19 Dec 2022math.OC cs.LG cs.NAcited by 19

Not on the map. Why?

Abstract (arXiv)

Many real-world problems not only have complicated nonconvex functional constraints but also use a large number of data points. This motivates the design of efficient stochastic methods on finite-sum or expectation constrained problems. In this paper, we design and analyze stochastic inexact augmented Lagrangian methods (Stoc-iALM) to solve problems involving a nonconvex composite (i.e. smooth+nonsmooth) objective and nonconvex smooth functional constraints. We adopt the standard iALM framework and design a subroutine by using the momentum-based variance-reduced proximal stochastic gradient method (PStorm) and a postprocessing step. Under certain regularity conditions (assumed also in existing works), to reach an varepsilon-KKT point in expectation, we establish an oracle complexity result of O(varepsilon-5), which is better than the best-known O(varepsilon-6) result. Numerical experiments on the fairness constrained problem and the Neyman-Pearson classification problem with real data demonstrate that our proposed method outperforms an existing method with the previously best-known complexity result.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 23 of its 39 references that are in the map. First posted on arXiv 19 Dec 2022.

Builds on

23 of 39 references.

References · 23

  1. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  4. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  5. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  6. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 40
  7. 2019Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimizationcited by 38
  8. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  9. 2019A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimizationcited by 27
  10. 2019Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraintscited by 25
  11. 2017Iteration complexity of inexact augmented Lagrangian methods for constrained convex programmingcited by 21
  12. 2020Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimizationcited by 21
11 more
  1. 2014An Accelerated Linearized Alternating Direction Method of Multiplierscited by 14
  2. 2020Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimizationcited by 14
  3. 2020A global dual error bound and its application to the analysis of linearly constrained nonconvex optimizationcited by 13
  4. 2018Primal-dual stochastic gradient method for convex programs with many functional constraintscited by 12
  5. 2020Adaptive Primal-Dual Stochastic Gradient Method for Expectation-constrained Convex Stochastic Programscited by 10
  6. 2013Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programmingcited by 9
  7. 2017First-order methods for constrained convex programming based on linearized augmented Lagrangian functioncited by 9
  8. 2020Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problemscited by 6
  9. 2021Zeroth-order Optimization for Composite Problems with Functional Constraintscited by 4
  10. 2013Computational Complexity of Inexact Gradient Augmented Lagrangian Methods: Application to Constrained MPCcited by 2
  11. 2019An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 5; 2026: 8.

19 papers.

Sort:

By area:

  1. 2023Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraintscited by 16
  2. 2024Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guaranteescited by 11
  3. 2025A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimizationcited by 9
  4. 2025Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraintscited by 6
  5. 2025Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraintscited by 5
  6. 2024A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safetycited by 4
  7. 2024Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimizationcited by 2
  8. 2024Stochastic interior-point methods for smooth conic optimization with applicationscited by 1
  9. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1
  10. 2026Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularitycited by 1
  11. 2024A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimizationcited by 0
  12. 2025Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimizationcited by 0
7 more
  1. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
  2. 2026Sample-wise Constrained Learning via a Sequential Penalty Approach with Applications in Image Processingcited by 0
  3. 2026Local Constrained Bayesian Optimizationcited by 0
  4. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  5. 2026Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Makingcited by 0
  6. 2026PSyGenTAB: A Privacy-Preserving Framework for Synthetic Clinical Tabular Data Generation via Constrained Optimizationcited by 0
  7. 2026Learning Chance-Constrained MDPs with Bellman Distributional Certificatescited by 0