Is Monte Carlo a bad sampling strategy for learning smooth functions in high dimensions?

Ben Adcock, Simone Brugiapaglia

Abstract

This paper concerns the approximation of smooth, high-dimensional functions from limited samples using polynomials. This task lies at the heart of many applications in computational science and engineering -- notably, those arising from parametric modelling and uncertainty quantification. It is common to use Monte Carlo (MC) sampling in such applications, so as not to succumb to the curse of dimensionality. However, it is well known this strategy is theoretically suboptimal. There are many polynomial spaces of dimension $n$ for which the sample complexity scales log-quadratically in $n$. This well-documented phenomenon has led to a concerted effort to design improved, in fact, near-optimal strategies, whose sample complexities scale log-linearly, or even linearly in $n$. Paradoxically, in this work we show that MC is actually a perfectly good strategy in high dimensions. We first document this phenomenon via several numerical examples. Next, we present a theoretical analysis that resolves this paradox for holomorphic functions of infinitely-many variables. We show that there is a least-squares scheme based on $m$ MC samples whose error decays algebraically fast in $m/\log(m)$, with a rate that is the same as that of the best $n$-term polynomial approximation. This result is non-constructive, since it assumes knowledge of a suitable polynomial space in which to perform the approximation. We next present a compressed sensing-based scheme that achieves the same rate, except for a larger polylogarithmic factor. This scheme is practical, and numerically it performs as well as or better than well-known adaptive least-squares schemes. Overall, our findings demonstrate that MC sampling is eminently suitable for smooth function approximation when the dimension is sufficiently high. Hence the benefits of improved sampling strategies are generically limited to lower-dimensional settings.

Introduction

In fields such as Uncertainty Quantification (UQ) and parametric modeling, researchers often face the challenge of approximating complex, high-dimensional functions—such as the solutions to partial differential equations (PDEs)—using a limited number of samples. Polynomial approximation is a cornerstone technique for this task. However, the choice of sampling strategy is critical.

For over a decade, the prevailing wisdom in numerical analysis has been that Monte Carlo (MC) sampling is a suboptimal choice. Theoretical bounds suggest that to stably approximate a polynomial space of dimension $n$, MC requires $O(n^2 \log n)$ samples. In contrast, specialized "optimal" sampling strategies, often based on Christoffel functions, require only $O(n \log n)$ samples. This perceived gap sparked a decade of research into sophisticated, measure-dependent sampling strategies. This paper challenges this narrative, asking whether this theoretical suboptimality translates to practical performance in high-dimensional settings.

Methodology

The authors investigate the efficacy of MC sampling through three primary lenses:

  1. Theoretical Analysis of Infinite Variables: Moving beyond finite-dimensional "worst-case" bounds, the authors analyze holomorphic functions of infinitely many variables. They prove that for these functions, a Least Squares (LS) approach using MC samples achieves an error decay rate matching the "best $n$-term" polynomial approximation, up to a logarithmic factor.
  2. Adaptive Least Squares (ALS): A greedy algorithm is employed to iteratively construct a polynomial subspace. It selects the most significant terms based on current residuals, allowing for a direct comparison between MC and optimal sampling in an adaptive context.
  3. Compressed Sensing (CS): To address practical scenarios where the most important variables (anisotropy) are unknown, the authors use a weighted square-root LASSO procedure. This approach serves as a robust implementation of their theory.

Results and the Dimension Paradox

The most striking finding is what the authors term the "Dimension Paradox." In low-dimensional settings (e.g., $d=1$), MC sampling is indeed inefficient. The resulting least-squares matrices are ill-conditioned, leading to unstable errors and poor convergence. However, as the dimensionality $d$ increases, the performance gap between MC and "optimal" sampling strategies vanishes.

Comparison of ALS-Opt and ALS-MC across dimensions $d=1, 4, 32$. The top row shows relative error, and the bottom row shows the condition number of the least-squares matrix. As $d$ increases, the MC curves converge to the optimal ones.

As shown in the figure above, at $d=32$, the error curves and condition numbers for MC-based approximation and optimal sampling are virtually indistinguishable. The condition number of the LS matrix for MC sampling improves dramatically with dimension, shifting from exponential growth in $m$ at $d=1$ to a stable profile at $d=32$. This suggests that the "worst-case" theoretical bounds do not dictate performance in high-dimensional practice.

Discussion: Why Monte Carlo Works

The success of MC in high dimensions is largely attributed to anisotropy. Real-world high-dimensional functions are rarely equally sensitive to all inputs; they typically depend strongly on a few variables and weakly on others. The authors demonstrate that this inherent structure prevents the "worst-case" $n^2$ scaling from impacting MC's performance in practice.

Furthermore, MC sampling offers practical advantages. Because MC samples are independent of both the function and the approximation space, they can be generated in parallel or drawn from "legacy" datasets. In contrast, optimal strategies often require prior knowledge of the approximation space, complicating their use in adaptive settings.

Conclusion

This work demonstrates that Monte Carlo sampling is eminently suitable for smooth function approximation when the dimension is sufficiently high (often as low as $d=8$ or $d=16$). The benefits of complex, "optimal" sampling strategies are primarily confined to lower-dimensional settings. While questions remain regarding unbounded domains and functions with sharp discontinuities, these findings suggest that for many high-dimensional applications in UQ and parametric modeling, the simplest sampling strategy—Monte Carlo—is also one of the most effective.

Summary updated

Abstract

This paper concerns the approximation of smooth, high-dimensional functions from limited samples using polynomials. This task lies at the heart of many applications in computational science and engineering -- notably, those arising from parametric modelling and uncertainty quantification. It is common to use Monte Carlo (MC) sampling in such applications, so as not to succumb to the curse of dimensionality. However, it is well known this strategy is theoretically suboptimal. There are many polynomial spaces of dimension $n$ for which the sample complexity scales log-quadratically in $n$. This well-documented phenomenon has led to a concerted effort to design improved, in fact, near-optimal strategies, whose sample complexities scale log-linearly, or even linearly in $n$. Paradoxically, in this work we show that MC is actually a perfectly good strategy in high dimensions. We first document this phenomenon via several numerical examples. Next, we present a theoretical analysis that resolves this paradox for holomorphic functions of infinitely-many variables. We show that there is a least-squares scheme based on $m$ MC samples whose error decays algebraically fast in $m/\log(m)$, with a rate that is the same as that of the best $n$-term polynomial approximation. This result is non-constructive, since it assumes knowledge of a suitable polynomial space in which to perform the approximation. We next present a compressed sensing-based scheme that achieves the same rate, except for a larger polylogarithmic factor. This scheme is practical, and numerically it performs as well as or better than well-known adaptive least-squares schemes. Overall, our findings demonstrate that MC sampling is eminently suitable for smooth function approximation when the dimension is sufficiently high. Hence the benefits of improved sampling strategies are generically limited to lower-dimensional settings.
BibTeX
@misc{adcock2022is,
  author = {Ben Adcock and Simone Brugiapaglia},
  title = {{Is Monte Carlo a bad sampling strategy for learning smooth functions in high dimensions?}},
  year = {2022},
  eprint = {2208.09045},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.09045},
}
Figure