Monte Carlo and the Curse of Dimensionality
We use Monte Carlo integration as a backdrop to explore how introducing probablistic ideas help alleviate the curse of dimensionality.
19 March 2025
The curse of dimensionality is easy to understand - volume grows exponentially with dimension. This implies we need to sample exponentially many data points relative to the number of features in order to have anything meaningful. What isn't so clear is why injecting randomness helps alleviate the issue. We use Monte Carlo integration as a backdrop to investigate this phenomenon.
We open with a seemingly unrelated lemma. In time, we will see that this lemma is the backbone to this phenomenon.
Lemma. On a bounded domain , for we have the inclusion . In fact, up to a constant which is independent of the dimension,
Proof. This is an straightforward application of Hölder's inequality. We begin by setting as the Hölder conjugate to . We compute
Taking -th roots gives the claim.
Actually, for our purposes, we'll need to control only the variance of a random variable . In this case, we can achieve a (usually) sharper constant of . For this, we only need the convexity of the -norms.
Lemma. For a random variable with , we have
In other words, the standard deviation of is controlled by all its higher moments.
Proof. This is a simple application of Jensen's inequality. When applied to the -norm for , it states
Applying this to , we see
Let's turn to integration. Let be a box. Clasically, we'd draw evenly spaced grid lines and integrate by sampling along all corners. As discussed, this is a bad idea by the curse of dimensionality. Instead, let denote the uniform measure on , and we draw iid samples in . For conveneince, set as an auxillary random variable also sampled from . Our first goal is to show the random Riemann sum forms an unbiased estimator for the true integral . We compute
By SLLN, as , we get that almost surely. As with all these asymptotic results, they're useless in practice. We need information on the rate of convergence. Henceforth, assume for some . For example, if is closed and is continuous, we automatically get that . Rates of convergence are measured in the sense (why?), so setting we see
where the last equality follows from our initial lemma. In fact, we could set this constant to be with our second lemma. Either way, this means the expected error of Monte Carlo integration is dimension independent with rate when measured in an sense.