# Conservative Stochastic Optimization with Expectation Constraints

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2020.

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

- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm](https://mlsanity.com/paper/2106.11577/) (2021)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [Safe Reinforcement Learning for Power System Control: A Review](https://mlsanity.com/paper/2407.00681/) (2024)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [Automatic debiasing of neural networks via moment-constrained learning](https://mlsanity.com/paper/2409.19777/) (2024)
- [Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback](https://mlsanity.com/paper/2301.11267/) (2023)

## Abstract (arXiv)

This paper considers stochastic convex optimization problems where the objective and constraint functions involve expectations with respect to the data indices or environmental variables, in addition to deterministic convex constraints on the domain of the variables. Although the setting is generic and arises in different machine learning applications, online and efficient approaches for solving such problems have not been widely studied. Since the underlying data distribution is unknown a priori, a closed-form solution is generally not available, and classical deterministic optimization paradigms are not applicable. State-of-the-art approaches, such as those using the saddle point framework, can ensure that the optimality gap as well as the constraint violation decay as Oleft(T^-frac12right) where T is the number of stochastic gradients. The domain constraints are assumed simple and handled via projection at every iteration. In this work, we propose a novel conservative stochastic optimization algorithm (CSOA) that achieves zero constraint violation and Oleft(T^-frac12right) optimality gap. Further, the projection operation (for scenarios when calculating projection is expensive) in the proposed algorithm can be avoided by considering the conditional gradient or Frank-Wolfe (FW) variant of the algorithm. The state-of-the-art stochastic FW variants achieve an optimality gap of Oleft(T^-frac13right) after T iterations, though these algorithms have not been applied to problems with functional expectation constraints. In this work, we propose the FW-CSOA algorithm that is not only projection-free but also achieves zero constraint violation with Oleft(T^-frac14right) decay of the optimality gap. The efficacy of the proposed algorithms is tested on two relevant problems: fair classification and structured matrix completion.