# Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 7 Oct 2026).
- Builds on 25 of its 39 references that are in the map.
- First posted on arXiv 10 Apr 2025.

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

- [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)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Training OOD Detectors in their Natural Habitats](https://mlsanity.com/paper/2202.03299/) (2022)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020)
- [Training neural networks under physical constraints using a stochastic augmented Lagrangian approach](https://mlsanity.com/paper/2009.07330/) (2020)
- [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)
- [Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs](https://mlsanity.com/paper/1802.03504/) (2018)
- [An Accelerated Linearized Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1401.6607/) (2014)
- [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018)
- [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [Adaptive Primal-Dual Stochastic Gradient Method for Expectation-constrained Convex Stochastic Programs](https://mlsanity.com/paper/2012.14943/) (2020)
- [Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications](https://mlsanity.com/paper/1604.00543/) (2016)
- [Strongly convex functions, Moreau envelopes and the generic nature of convex functions with strong minimizers](https://mlsanity.com/paper/1507.07144/) (2015)
- [Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function](https://mlsanity.com/paper/2008.00562/) (2020)
- [An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems](https://mlsanity.com/paper/2110.11151/) (2021)
- [Network Slicing for Service-Oriented Networks Under Resource Constraints](https://mlsanity.com/paper/1708.07463/) (2017)
- [Decentralized Non-Convex Learning with Linearly Coupled Constraints](https://mlsanity.com/paper/2103.05378/) (2021)

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

- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Benchmarking Stochastic Approximation Algorithms for Fairness-Constrained Training of Deep Neural Networks](https://mlsanity.com/paper/2507.04033/) (2025)
- [humancompatible.train: Implementing Optimization Algorithms for Stochastically-Constrained Stochastic Optimization Problems](https://mlsanity.com/paper/2509.21254/) (2025)
- [First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints](https://mlsanity.com/paper/2603.05774/) (2026)
- [Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making](https://mlsanity.com/paper/2606.07088/) (2026)

## Abstract (arXiv)

We propose smoothed primal-dual algorithms for solving stochastic and smooth nonconvex optimization problems with linear inequality constraints. Our algorithms are single-loop and only require a single stochastic gradient based on one sample at each iteration. A distinguishing feature of our algorithm is that it is based on an inexact gradient descent framework for the Moreau envelope, where the gradient of the Moreau envelope is estimated using one step of a stochastic primal-dual augmented Lagrangian method. To handle inequality constraints and stochasticity, we combine the recently established global error bounds in constrained optimization with a Moreau envelope-based analysis of stochastic proximal algorithms. For obtaining varepsilon-stationary points, we establish the optimal O(varepsilon-4) sample complexity guarantee for our algorithms and provide extensions to stochastic linear constraints. We also show how to improve this complexity to O(varepsilon-3) by using variance reduction and the expected smoothness assumption. Unlike existing methods, the iterations of our algorithms are free of subproblems, large batch sizes or increasing penalty parameters and use dual variable updates to ensure feasibility.