# Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradients](https://mlsanity.com/paper/2510.23049/) (2025)
- [MPO: An Efficient Post-Processing Framework for Mixing Diverse Preference Alignment](https://mlsanity.com/paper/2502.18699/) (2025)
- [Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization](https://mlsanity.com/paper/2205.14278/) (2022)
- [Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization](https://mlsanity.com/paper/2206.01991/) (2022)
- [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023)
- [Federated Conditional Stochastic Optimization](https://mlsanity.com/paper/2310.02524/) (2023)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Deep Learning for Computing Convergence Rates of Markov Chains](https://mlsanity.com/paper/2405.20435/) (2024)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming](https://mlsanity.com/paper/2401.00664/) (2024)
- [On the KL-Divergence-based Robust Satisficing Model](https://mlsanity.com/paper/2408.09157/) (2024)
- [Iterative Sampling Methods for Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2512.12550/) (2025)
- [Maximin Robust Bayesian Experimental Design](https://mlsanity.com/paper/2603.14094/) (2026)
- [Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization](https://mlsanity.com/paper/2603.13048/) (2026)

## Abstract (arXiv)

In this paper, we study a class of stochastic optimization problems, referred to as the Conditional Stochastic Optimization (CSO), in the form of minx ∈ X EExif_xiBig(EEη|xi[gη(x,xi)]Big), which finds a wide spectrum of applications including portfolio selection, reinforcement learning, robust learning, causal inference and so on. Assuming availability of samples from the distribution PP(xi) and samples from the conditional distribution PP(η|xi), we establish the sample complexity of the sample average approximation (SAA) for CSO, under a variety of structural assumptions, such as Lipschitz continuity, smoothness, and error bound conditions. We show that the total sample complexity improves from cO(d/eps4) to cO(d/eps3) when assuming smoothness of the outer function, and further to cO(1/eps2) when the empirical function satisfies the quadratic growth condition. We also establish the sample complexity of a modified SAA, when xi and η are independent. Several numerical experiments further support our theoretical findings. Keywords: stochastic optimization, sample average approximation, large deviations theory