A Note on Monte Carlo Integration in High Dimensions

Monte Carlo integration is a commonly used technique to compute intractable integrals and is typically thought to perform poorly for very high-dimensional integrals. To show that this is not always the case, we examine Monte Carlo integration using techniques from the high-dimensional statistics literature by allowing the dimension of the integral to increase. In doing so, we derive nonasymptotic bounds for the relative and absolute error of the approximation for some general classes of functions through concentration inequalities. We provide concrete examples in which the magnitude of the number of points sampled needed to guarantee a consistent estimate varies between polynomial to exponential, and show that in theory arbitrarily fast or slow rates are possible. This demonstrates that the behavior of Monte Carlo integration in high dimensions is not uniform. Through our methods we also obtain nonasymptotic confidence intervals which are valid regardless of the number of points sampled.

Automated summary

This study investigates the performance of Monte Carlo integration in high-dimensional integrals by applying techniques from high-dimensional statistics. The nonasymptotic bounds for relative and absolute error of the approximation for certain classes of functions are derived through concentration inequalities. Concrete examples show that the number of points sampled needed for a consistent estimate can vary between polynomial and exponential, indicating the non-uniform behavior of Monte Carlo integration in high dimensions. Moreover, nonasymptotic confidence intervals are obtained, which are valid regardless of the number of points sampled.