Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization

Abstract

In this paper, we study a class of stochastic optimization problems, referred to as the Conditional Stochastic Optimization (CSO), in the form of _x X _f_(_|[g_(x,)]), 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 () and samples from the conditional distribution (|), 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 (d/^4) to (d/^3) when assuming smoothness of the outer function, and further to (1/^2) when the empirical function satisfies the quadratic growth condition. We also establish the sample complexity of a modified SAA, when and are independent. Several numerical experiments further support our theoretical findings. Keywords: stochastic optimization, sample average approximation, large deviations theory

Tasks

Reproductions