On Learning for Ambiguous Chance Constrained Problems

We study chance constrained optimization problems minx f(x) s.t. P(left θ: g(x,θ)≤ 0 right)≥ 1-ε where ε∈ (0,1) is the violation probability, when the distribution P is not known to the decision maker (DM). When the DM has access to a set of distributions U such that P is contained in U, then the problem is known as the ambiguous chance-constrained problem citeerdougan2006ambiguous. We study ambiguous chance-constrained problem for the case when U is of the form leftμ:fracμ (y)nu(y)≤ C, forall y∈Theta, μ(y)≥ 0right, where nu is a ``reference distribution.'' We show that in this case the original problem can be ``well-approximated'' by a sampled problem in which N i.i.d. samples of θ are drawn from nu, and the original constraint is replaced with g(x,θi)≤ 0,~i=1,2,ldots,N. We also derive the sample complexity associated with this approximation, i.e., for ε,δ>0 the number of samples which must be drawn from nu so that with a probability greater than 1-δ (over the randomness of nu), the solution obtained by solving the sampled program yields an ε-feasible solution for the original chance constrained problem.