# Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 16 Sep 2024.

## Builds on (most cited first, 23 of 23)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Scientific Machine Learning through Physics-Informed Neural Networks: Where we are and What's next](https://mlsanity.com/paper/2201.05624/) (2022)
- [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)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2007.10525/) (2020)
- [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)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians](https://mlsanity.com/paper/2106.13015/) (2021)
- [Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems](https://mlsanity.com/paper/2211.15943/) (2022)
- [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 Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization](https://mlsanity.com/paper/2006.00425/) (2020)
- [Accelerating Stochastic Sequential Quadratic Programming for Equality Constrained Optimization using Predictive Variance Reduction](https://mlsanity.com/paper/2204.04161/) (2022)
- [An adaptive stochastic optimization algorithm for resource allocation](https://mlsanity.com/paper/1902.04376/) (2019)
- [Inexact Sequential Quadratic Optimization for Minimizing a Stochastic Objective Function Subject to Deterministic Nonlinear Equality Constraints](https://mlsanity.com/paper/2107.03512/) (2021)
- [Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming](https://mlsanity.com/paper/1312.2690/) (2013)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [A Sequential Quadratic Programming Method for Optimization with Stochastic Objective Functions, Deterministic Inequality Constraints and Robust Subproblems](https://mlsanity.com/paper/2302.07947/) (2023)
- [Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization](https://mlsanity.com/paper/2308.03687/) (2023)

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

- [Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models](https://mlsanity.com/paper/2409.15734/) (2024)
- [Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints](https://mlsanity.com/paper/2504.07607/) (2025)
- [High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise](https://mlsanity.com/paper/2503.19091/) (2025)
- [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)
- [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)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (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)
- [TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.30732/) (2026)

## Abstract (arXiv)

In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an ε-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy ε. However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, making such an ε-stochastic stationary point potentially undesirable due to the risk of significant constraint violations. To address this issue, we propose single-loop variance-reduced stochastic first-order methods, where the stochastic gradient of the stochastic component is computed using either a truncated recursive momentum scheme or a truncated Polyak momentum scheme for variance reduction, while the gradient of the deterministic component is computed exactly. Under the error bound condition with a parameter θ ≥ 1 and other suitable assumptions, we establish that these methods respectively achieve a sample and first-order operation complexity of widetilde O(ε^-maxθ+2, 2θ) and widetilde O(ε^-max4, 2θ) for finding a stronger ε-stochastic stationary point, where the constraint violation is within ε with certainty, and the expected violation of first-order stationarity is within ε. For θ=1, these complexities reduce to widetilde O(ε-3) and widetilde O(ε-4) respectively, which match, up to a logarithmic factor, the best-known complexities achieved by existing methods for finding an ε-stochastic stationary point of unconstrained smooth stochastic optimization problems.