# Primal-dual stochastic gradient method for convex programs with many functional constraints

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2018.

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

- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems](https://mlsanity.com/paper/2110.00604/) (2021)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [FedDRO: Federated Compositional Optimization for Distributionally Robust Learning](https://mlsanity.com/paper/2311.12652/) (2023)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints](https://mlsanity.com/paper/2605.16262/) (2026)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)
- [Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making](https://mlsanity.com/paper/2606.07088/) (2026)

## Abstract (arXiv)

Stochastic gradient method (SGM) has been popularly applied to solve optimization problems with objective that is stochastic or an average of many functions. Most existing works on SGMs assume that the underlying problem is unconstrained or has an easy-to-project constraint set. In this paper, we consider problems that have a stochastic objective and also many functional constraints. For such problems, it could be extremely expensive to project a point to the feasible set, or even compute subgradient and/or function value of all constraint functions. To find solutions of these problems, we propose a novel (adaptive) SGM based on the classical augmented Lagrangian function. Within every iteration, it inquires a stochastic subgradient of the objective, and a subgradient and the function value of one randomly sampled constraint function. Hence, the per-iteration complexity is low. We establish its convergence rate for convex problems and also problems with strongly convex objective. It can achieve the optimal O(1/√k) convergence rate for convex case and nearly optimal Obig((log k)/kbig) rate for strongly convex case. Numerical experiments on a sample approximation problem of the robust portfolio selection and quadratically constrained quadratic programming are conducted to demonstrate its efficiency.