# Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 45 references that are in the map.
- First posted on arXiv 22 Jun 2021.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Conservative Stochastic Optimization with Expectation Constraints](https://mlsanity.com/paper/2008.05758/) (2020)
- [Adaptive Primal-Dual Stochastic Gradient Method for Expectation-constrained Convex Stochastic Programs](https://mlsanity.com/paper/2012.14943/) (2020)
- [A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints](https://mlsanity.com/paper/1908.03077/) (2019)
- [Stochastic Approximation Proximal Method of Multipliers for Convex Stochastic Programming](https://mlsanity.com/paper/1907.12226/) (2019)

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

- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization](https://mlsanity.com/paper/2205.09571/) (2022)
- [Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints](https://mlsanity.com/paper/2212.11143/) (2022)
- [Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making](https://mlsanity.com/paper/2606.07088/) (2026)
- [Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints](https://mlsanity.com/paper/2609.13925/) (2026)

## Abstract (arXiv)

This paper considers the problem of minimizing a convex expectation function with a set of inequality convex expectation constraints. We present a computable stochastic approximation type algorithm, namely the stochastic linearized proximal method of multipliers, to solve this convex stochastic optimization problem. This algorithm can be roughly viewed as a hybrid of stochastic approximation and the traditional proximal method of multipliers. Under mild conditions, we show that this algorithm exhibits O(K-1/2) expected convergence rates for both objective reduction and constraint violation if parameters in the algorithm are properly chosen, where K denotes the number of iterations. Moreover, we show that, with high probability, the algorithm has O(log(K)K-1/2) constraint violation bound and O(log3/2(K)K-1/2) objective bound. Some preliminary numerical results demonstrate the performance of the proposed algorithm.