# Stochastic Compositional Optimization with Compositional Constraints

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 9 Sep 2022.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Online Meta-Learning](https://mlsanity.com/paper/1902.08438/) (2019)
- [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)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020)
- [Multi-Level Stochastic Gradient Methods for Nested Composition Optimization](https://mlsanity.com/paper/1801.03600/) (2018)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020)
- [Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structure](https://mlsanity.com/paper/1904.10112/) (2019)
- [Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity](https://mlsanity.com/paper/1811.01182/) (2018)
- [Data-Driven Minimax Optimization with Expectation Constraints](https://mlsanity.com/paper/2202.07868/) (2022)
- [A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints](https://mlsanity.com/paper/1908.03077/) (2019)
- [Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints](https://mlsanity.com/paper/2007.00153/) (2020)
- [A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints](https://mlsanity.com/paper/1908.01086/) (2019)
- [Efficient Algorithms for Distributionally Robust Stochastic Optimization with Discrete Scenario Support](https://mlsanity.com/paper/1909.11216/) (2019)

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

- [Stochastic Methods for AUC Optimization subject to AUC-based Fairness Constraints](https://mlsanity.com/paper/2212.12603/) (2022)
- [Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization](https://mlsanity.com/paper/2308.09604/) (2023)
- [Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees](https://mlsanity.com/paper/2408.12505/) (2024)
- [Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints](https://mlsanity.com/paper/2609.13925/) (2026)

## Abstract (arXiv)

Stochastic compositional optimization (SCO) has attracted considerable attention because of its broad applicability to important real-world problems. However, existing works on SCO assume that the projection within a solution update is simple, which fails to hold for problem instances where the constraints are in the form of expectations, such as empirical conditional value-at-risk constraints. We study a novel model that incorporates single-level expected value and two-level compositional constraints into the current SCO framework. Our model can be applied widely to data-driven optimization and risk management, including risk-averse optimization and high-moment portfolio selection, and can handle multiple constraints. We further propose a class of primal-dual algorithms that generates sequences converging to the optimal solution at the rate of cO(frac1√N)under both single-level expected value and two-level compositional constraints, where N is the iteration counter, establishing the benchmarks in expected value constrained SCO.