# A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 64 references that are in the map.
- First posted on arXiv 31 Jan 2025.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Points](https://mlsanity.com/paper/2212.00927/) (2022)
- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints](https://mlsanity.com/paper/1710.06612/) (2017)
- [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)
- [On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming](https://mlsanity.com/paper/1603.05738/) (2016)
- [A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs](https://mlsanity.com/paper/1512.08370/) (2015)
- [Ghost Penalties in Nonconvex Constrained Optimization: Diminishing Stepsizes and Iteration Complexity](https://mlsanity.com/paper/1709.03384/) (2017)
- [Goldstein Stationarity in Lipschitz Constrained Optimization](https://mlsanity.com/paper/2310.03690/) (2023)
- [Linearly-constrained nonsmooth optimization for training autoencoders](https://mlsanity.com/paper/2103.16232/) (2021)
- [An Inexact Augmented Lagrangian Algorithm for Training Leaky ReLU Neural Network with Group Sparsity](https://mlsanity.com/paper/2205.05428/) (2022)
- [A Smooth Inexact Penalty Reformulation of Convex Problems with Linear Constraints](https://mlsanity.com/paper/1808.07749/) (2018)
- [Huber Loss-Based Penalty Approach to Problems with Linear Constraints](https://mlsanity.com/paper/2311.00874/) (2023)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)

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

- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [A stochastic smoothing framework for nonconvex-nonconcave minEmax problems with applications to Wasserstein distributionally robust optimization](https://mlsanity.com/paper/2502.17602/) (2025)
- [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025)
- [First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints](https://mlsanity.com/paper/2603.05774/) (2026)
- [Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation](https://mlsanity.com/paper/2605.15388/) (2026)
- [Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2506.02504/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)

## Abstract (arXiv)

Many real-world problems, such as those with fairness constraints, involve complex expectation constraints and large datasets, necessitating the design of efficient stochastic methods to solve them. Most existing research focuses on cases with no constraint or easy-to-project constraints or deterministic constraints. In this paper, we consider nonconvex nonsmooth stochastic optimization problems with expectation constraints, for which we build a novel exact penalty model. We first show the relationship between the penalty model and the original problem. Then on solving the penalty problem, we present a single-loop SPIDER-type stochastic subgradient method, which utilizes the subgradients of both the objective and constraint functions, as well as the constraint function value at each iteration. Under certain regularity conditions (weaker than Slater-type constraint qualification or strong feasibility assumed in existing works), we establish an iteration complexity result of O(ε-4) to reach a near-ε stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an (ε,ε)-KKT point of the original problem is obtained. For a few scenarios, our complexity of either the objective sample subgradient or the constraint sample function values can be lower than the state-of-the-art results by a factor of ε-2. Moreover, on solving two fairness-constrained problems and a multi-class Neyman-Pearson classification problem, our method is significantly (up to 466 times) faster than the state-of-the-art algorithms, including switching subgradient method and inexact proximal point methods.