In this paper, we consider the rate of convergence with sample average approximation (SAA) under heavy tailed distributions and quantify it under both independent identically distributed (iid) sampling and non-iid sampling. We rst derive the polynomial rate of convergence for random variable under iid sampling. Then, the uniform polynomial rates of convergence for both random functions and random setvalued mappings under iid sampling are established. Furthermore, we extend these results to the non-iid sampling case by using a Gartner{Ellis type theorem. Finally, we applied these results to the SAA analysis of stochastic optimization problems, which show the e ectiveness of our results in the discretization of stochastic optimization. The novelty of this paper arises from the fact that our estimation for convergence rate is suitable for heavy tailed distributions, which avoids the somehow limiting light tailed distribution condition in existing works.
Article
View Rates of convergence of sample average approximation under heavy tailed distributions