Stochastic Compositional Optimization with Compositional Constraints

Stochastic compositional optimization (SCO) has attracted considerable attention because of its broad applicability to important real-world problems. However, existing work on SCO typically assumes that the projection within a solution update is straightforward, which is not the case for problem instances where constraints are in the form of expectations, such as empirical conditional value-at-risk constraints. In this paper, we introduce a novel model that integrates single-level expected-value and two-level compositional constraints into the existing SCO framework. Our model has wide applicability to data-driven optimization, fairness optimization, and risk management, including risk-averse optimization and high-moment portfolio selection, and is capable of handling multiple constraints. Additionally, we propose a class of primal-dual algorithms that generate sequences converging to the optimal solution at a rate of $\mathcal{O}\left(N^{-1/2}\right)$ under both single-level and two-level compositional expected-value constraints, where N is the iteration counter, thus establishing benchmarks in expected-value-constrained SCO. Numerical experiments show the efficiency of our algorithm over real-world applications.

Funding: S. Yang’s research was supported by the Research Grants Council of the Hong Kong Special Administrative Region, China [Grant Early Career Scheme 26209422]. W. You’s research is generously supported by the Research Grants Council of the Hong Kong Special Administrative Region, China [Grant Early Career Scheme 26212320 and Grant General Research Fund 16212823].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2023.0024.