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.

蒙特卡洛积分（Monte Carlo integration）是一类用于求解难解积分的常用技术，传统观点普遍认为其在极高维积分场景下表现欠佳。为证明该论断并非始终成立，本文借助高维统计学领域的研究方法，通过放宽积分维度的约束对蒙特卡洛积分展开研究。在此过程中，我们通过集中不等式（concentration inequalities），针对若干通用函数类推导得到近似解的相对误差与绝对误差的非渐近界。我们提供了具体示例：保证一致估计所需的采样点数量的规模变化范围可从多项式级跨越至指数级，且理论上任意快慢的收敛速率均有可能实现。这表明蒙特卡洛积分在高维场景下的表现并不统一。通过本研究提出的方法，我们还获得了无论采样点数量多寡均有效的非渐近置信区间。