# Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization

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

## 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 (most cited first, 23 of 23)

- [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)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1907.03793/) (2019)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [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)
- [An Accelerated Linearized Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1401.6607/) (2014)
- [Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization](https://mlsanity.com/paper/2006.00425/) (2020)
- [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020)
- [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018)
- [Adaptive Primal-Dual Stochastic Gradient Method for Expectation-constrained Convex Stochastic Programs](https://mlsanity.com/paper/2012.14943/) (2020)
- [Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming](https://mlsanity.com/paper/1312.2690/) (2013)
- [First-order methods for constrained convex programming based on linearized augmented Lagrangian function](https://mlsanity.com/paper/1711.08020/) (2017)
- [Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems](https://mlsanity.com/paper/2006.08048/) (2020)
- [Zeroth-order Optimization for Composite Problems with Functional Constraints](https://mlsanity.com/paper/2112.11420/) (2021)
- [Computational Complexity of Inexact Gradient Augmented Lagrangian Methods: Application to Constrained MPC](https://mlsanity.com/paper/1302.4355/) (2013)
- [An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization](https://mlsanity.com/paper/1909.09582/) (2019)

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

- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [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)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [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)
- [Sample-wise Constrained Learning via a Sequential Penalty Approach with Applications in Image Processing](https://mlsanity.com/paper/2601.16812/) (2026)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making](https://mlsanity.com/paper/2606.07088/) (2026)
- [PSyGenTAB: A Privacy-Preserving Framework for Synthetic Clinical Tabular Data Generation via Constrained Optimization](https://mlsanity.com/paper/2606.18518/) (2026)
- [Learning Chance-Constrained MDPs with Bellman Distributional Certificates](https://mlsanity.com/paper/2609.30856/) (2026)

## 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.