Lecture 1: The Curse of Dimensionality
Integration, metric entropy, and volume
High-dimensional probability studies what happens where probability meets spaces of many dimensions, and one of its first lessons is that geometric intuition tuned to \(\mathbb R^2\) and \(\mathbb R^3\) is an unreliable guide there: simple questions about the shape, size, or extent of a set in high dimensions routinely have answers that feel wrong even once proved. One of the most effective ways to regain control is, perhaps surprisingly, to bring in randomness. Certain probabilistic phenomena become easier to work with, not harder, as the dimension grows, and they let us bypass difficulties that would otherwise be intractable.
The opening part of this course takes up a question that has to be settled before any of this can be made precise: what does it even mean for a set to be high-dimensional? When a set is not a linear space, the dimension learned in linear algebra may not be defined at all, and even when it is defined, it is often not the notion of size that actually governs the problem at hand. We will develop other, more refined notions of dimension—different ways of measuring how large or complicated a set is—and see how they connect to statistics, approximation theory, optimization, and a range of other phenomena in probability theory, many of which turn out, on inspection, to be facets of this same question.
We start with a concrete problem that already displays the tension between deterministic and probabilistic approaches to a high-dimensional question: approximating an integral.
1 Approximating the integral
Let \(f:[0,1]^d\to\mathbb R\), and suppose we want to estimate its integral from finitely many evaluations of \(f\): \[ I(f)=\int_{[0,1]^d}f(x)\,\mathrm{d}x. \]
Definition 1 (Lipschitz map) Let \((X,d_X)\) and \((Y,d_Y)\) be metric spaces. A map \(f:X\to Y\) is \(L\)-Lipschitz if \[ d_Y\big(f(x),f(x')\big)\leq Ld_X(x,x') \qquad\text{for every }x,x'\in X. \] The least possible \(L\) is the Lipschitz constant of \(f\), denoted \(\operatorname{Lip}(f)\). A map is called Lipschitz if \(\operatorname{Lip}(f)<\infty\).
Convention for these notes. If \(X\subseteq\mathbb R^d\) and \(Y\subseteq\mathbb R^m\) and no metrics are specified, then both spaces are equipped with their Euclidean metrics. In particular, for a function \(f:X\to\mathbb R\), the condition is \[ |f(x)-f(x')|\leq L\|x-x'\|_2 \qquad\text{for every }x,x'\in X. \]
Assume now that \(f\) is \(L\)-Lipschitz. Fix an integer \(m\geq 1\), divide each coordinate interval into \(m\) intervals of length \(h=1/m\), and let \(\mathcal Q_m\) be the resulting partition of \([0,1]^d\) into \(m^d\) cubes. If \(c_Q\) denotes the center of \(Q\), the corresponding midpoint approximation is \[ I_m(f)=\sum_{Q\in\mathcal Q_m}|Q|f(c_Q) =\frac{1}{m^d}\sum_{Q\in\mathcal Q_m}f(c_Q). \] Every \(x\in Q\) satisfies \[ \|x-c_Q\|_2\leq\frac{\sqrt d}{2m}. \] The Lipschitz property therefore gives \[ \begin{aligned} |I(f)-I_m(f)| &\leq \sum_{Q\in\mathcal Q_m} \int_Q |f(x)-f(c_Q)|\,\mathrm{d}x\\ &\leq \sum_{Q\in\mathcal Q_m} |Q|L\frac{\sqrt d}{2m}\\ &=\frac{L\sqrt d}{2m}. \end{aligned} \]
To guarantee an error of at most \(\varepsilon\), it is therefore enough to take \[ m_\varepsilon =\max\left\{1,\left\lceil\frac{L\sqrt d}{2\varepsilon}\right\rceil\right\} \] subintervals in each coordinate. The grid then uses \(N_\varepsilon=m_\varepsilon^d\) evaluations. In the nontrivial regime \(0<\varepsilon\leq L\sqrt d/2\), \[ \left(\frac{L\sqrt d}{2\varepsilon}\right)^d \leq N_\varepsilon \leq \left(\frac{L\sqrt d}{\varepsilon}\right)^d. \] Thus, for fixed \(d\) and \(L\), this grid construction has cost \(N_\varepsilon\asymp_{d,L}\varepsilon^{-d}\). At a fixed accuracy, its cost grows at least exponentially with the dimension. This is a basic instance of what is called the curse of dimensionality: resolving each of \(d\) coordinates at \(m\) possible values produces \(m^d\) combinations. Bellman introduced the phrase in his study of multistage optimization and dynamic programming (Bellman 1957); here our concern is only its elementary appearance in numerical integration.
There is a different strategy. Let \(X_1,\ldots,X_N\) be independent and uniform on \([0,1]^d\), and set \[ \widehat I_N(f)=\frac1N\sum_{i=1}^N f(X_i). \]
Proposition 1 (Monte Carlo integration) If \(f(X_1)\) has finite variance \(\sigma^2\), then \[ \mathbb E\widehat I_N(f)=I(f),\qquad \mathbb E|\widehat I_N(f)-I(f)|^2=\frac{\sigma^2}{N}. \] Consequently, \[ \mathbb P\big\{|\widehat I_N(f)-I(f)|\geq t\big\} \leq \frac{\sigma^2}{Nt^2}. \]
Independence and linearity give \[ \mathbb E\widehat I_N(f)=\mathbb Ef(X_1)=I(f). \] Writing \(Y_i=f(X_i)-I(f)\), the cross terms vanish and hence \[ \mathbb E\left|\frac1N\sum_{i=1}^N Y_i\right|^2 =\frac1{N^2}\sum_{i=1}^N\mathbb EY_i^2 =\frac{\sigma^2}{N}. \] Chebyshev’s inequality gives the probability bound.
The root-mean-square error is \[ \left(\mathbb E|\widehat I_N(f)-I(f)|^2\right)^{1/2} =\frac{\sigma}{\sqrt N}. \] Consequently, to make the root-mean-square error at most \(\varepsilon\), it is enough to take \[ N\geq \frac{\sigma^2}{\varepsilon^2}. \] If instead we want \[ \mathbb P\big\{|\widehat I_N(f)-I(f)|\geq\varepsilon\big\} \leq\delta, \] Chebyshev’s inequality gives the sufficient condition \[ N\geq\frac{\sigma^2}{\delta\varepsilon^2}. \]
Amplifying confidence. The factor \(\delta^{-1}\) comes from the elementary Chebyshev bound, not from a fundamental limitation of randomization. With only a finite-variance assumption, a median-of-means estimator reduces the failure probability to \(\delta\) using \[ N\lesssim \frac{\sigma^2}{\varepsilon^2} \log\frac1\delta \] evaluations. Under bounded or sub-Gaussian assumptions, the ordinary sample mean has a similar exponentially small failure probability. We will develop both mechanisms later.
Thus, when \(\sigma^2\) and the confidence level \(\delta\) are fixed, Monte Carlo uses on the order of \(\varepsilon^{-2}\) function evaluations, rather than the \(\varepsilon^{-d}\) evaluations used by the grid. Still, the exponent \(2\) does not depend on \(d\); any dimensional dependence is confined to \(\sigma^2\).
Remark 1 (A quantifier switch). The two guarantees above are not answers to the same question. The grid bound holds for every \(L\)-Lipschitz \(f\) at once, using one fixed set of \(N_\varepsilon\) points: \[ \sup_{\operatorname{Lip}(f)\leq L}\big|I(f)-I_{m_\varepsilon}(f)\big| \leq\varepsilon. \] The Monte Carlo bound reverses the order of the quantifiers: fix \(f\) first, and only then ask a random set of points to do well, on average, for that one \(f\): \[ \mathbb E\big|\widehat I_N(f)-I(f)\big|^2=\frac{\sigma^2}{N}. \] These are genuinely different tasks. Choosing points after \(f\) is known—or estimating one \(f\) at a time—is far easier than certifying, once and for all, a set of points whose accuracy holds simultaneously across an entire infinite class of functions. Most of what one does in practice looks like the second kind of task, a handful of functions estimated one at a time, which is exactly why Monte Carlo already gets the right answer so often.
Still, the first kind of task is a natural question in its own right: is there a single set of points—deterministic, or produced by some random mechanism—whose accuracy is guaranteed uniformly over every \(L\)-Lipschitz \(f\), at something like Monte Carlo’s cost \(\varepsilon^{-2}\) rather than the grid’s \(\varepsilon^{-d}\)? Answering questions of this kind is one of the goals of this course. Notice, though, that the grid’s exponential cost came entirely from the geometry of the class of \(L\)-Lipschitz functions being approximated, not from any particular choice of algorithm. Before we can ask whether \(\varepsilon^{-2}\) is achievable uniformly over that class, we need a way to measure how large or complicated the class is in the first place.
This is an opening theme of the course: familiar low-dimensional intuition can make high-dimensional geometry and computation look forbidding, while probabilistic methods often reveal dimension-insensitive structure. High-dimensional probability develops the notions of size and complexity—and the probabilistic intuition—needed to understand when this happens and how to use it. The rest of this lecture begins that development, not yet for function classes like the \(L\)-Lipschitz maps, but for more basic geometric objects—cubes and balls—where the right notion of size can be pinned down concretely.
2 Covers and packings
We now turn from approximating a single numerical quantity to measuring the complexity of a set. (Eventually, per Remark 1, we want the set to be a class of functions; for now it is enough to consider an abstract set.) Let \((T,\rho)\) be a metric space. Our goal is to quantify the size, approximability, and complexity of \(T\)—and of its subsets—using only the distances between points. Covering numbers ask how many representative points are needed to approximate a set at a chosen resolution, while packing numbers ask how many mutually distinguishable points it can contain. In Euclidean space these quantities can be compared with volume; in a general metric space they provide a useful substitute for volume.
Definition 2 (Covering number) An \(\varepsilon\)-net of \(T\) is a set \(A\subseteq T\) such that every \(t\in T\) satisfies \(\rho(t,a)\leq\varepsilon\) for some \(a\in A\). The covering number is \[ N(T,\rho,\varepsilon) =\min\{|A|:A\text{ is an }\varepsilon\text{-net of }T\}. \] When the metric is understood, we write \(N(T,\varepsilon)\).
Definition 3 (Packing number) An \(\varepsilon\)-packing is a set \(A\subseteq T\) whose distinct points satisfy \(\rho(a,a')>\varepsilon\). The largest possible size of such a set is the packing number \(M(T,\rho,\varepsilon)\).
Covering asks how economically we can approximate every point. Packing asks how many genuinely distinguishable points the space contains.
Lemma 1 (Covering–packing comparison) For every \(\varepsilon>0\), \[ N(T,\varepsilon) \leq M(T,\varepsilon) \leq N(T,\varepsilon/2), \] provided the relevant maxima and minima exist. The same inequalities hold with the usual infimum and supremum conventions.
Choose a maximal \(\varepsilon\)-separated set \(A\). If some \(t\in T\) were farther than \(\varepsilon\) from every point of \(A\), then \(A\cup\{t\}\) would still be \(\varepsilon\)-separated. Thus \(A\) is an \(\varepsilon\)-net, proving the first inequality.
For the second, cover \(T\) by balls of radius \(\varepsilon/2\). No such ball can contain two points of an \(\varepsilon\)-packing, since two points in one ball are at distance at most \(\varepsilon\). Therefore every packing has at most one point per covering ball.
Example 1 (A grid cover of the cube) For \(T=[0,1]^d\) with the \(\ell^\infty\) metric, a regular grid gives \[ N([0,1]^d,\|\cdot\|_\infty,\varepsilon) \leq \left(1+\frac1\varepsilon\right)^d. \] This is exactly the combinatorial growth encountered in deterministic integration.
3 Volumetric estimates
Volume turns a geometric cover into a counting argument. Let \(B_2^d\) denote the Euclidean unit ball and let \(v_d=\operatorname{vol}(B_2^d)\).
Proposition 2 (Volume of the Euclidean ball) For every \(d\geq1\), \[ v_d=\frac{\pi^{d/2}}{\Gamma(d/2+1)}. \] In particular, \(v_d^{1/d}\asymp d^{-1/2}\).
Evaluate the Gaussian integral in Cartesian coordinates: \[ \int_{\mathbb R^d}e^{-\|x\|_2^2}\,\mathrm{d}x=\pi^{d/2}. \] In polar coordinates the same integral is \[ d v_d\int_0^\infty e^{-r^2}r^{d-1}\,\mathrm{d}r =\frac{d v_d}{2}\Gamma(d/2). \] Since \(\Gamma(d/2+1)=(d/2)\Gamma(d/2)\), the formula follows. Stirling’s formula then gives \(v_d^{1/d}\asymp d^{-1/2}\).
Thus a radius-one Euclidean ball has rapidly vanishing volume, even though its diameter remains \(2\). More importantly, scaling is exponential: \[ \operatorname{vol}(rB_2^d)=r^d v_d. \]
Theorem 1 (Covering a Euclidean ball) For \(0<\varepsilon\leq1\), \[ \varepsilon^{-d} \leq N(B_2^d,\varepsilon) \leq \left(1+\frac{2}{\varepsilon}\right)^d. \]
If \(N\) balls of radius \(\varepsilon\) cover \(B_2^d\), subadditivity of volume gives \[ v_d\leq N\varepsilon^d v_d, \] which proves the lower bound.
For the upper bound, let \(x_1,\ldots,x_M\) be a maximal \(\varepsilon\)-separated subset of \(B_2^d\). The balls \(x_i+(\varepsilon/2)B_2^d\) are disjoint and lie inside \((1+\varepsilon/2)B_2^d\). Comparing volumes gives \[ M(\varepsilon/2)^d v_d \leq (1+\varepsilon/2)^d v_d, \] so \(M\leq(1+2/\varepsilon)^d\). By Lemma 1, this maximal packing is also an \(\varepsilon\)-net.
The theorem is both useful and discouraging. It provides a universal finite discretization of the ball, but the price is exponential in \(d\).
4 A more refined notion of dimension
The number \(d\) in Example 1 and Theorem 1 is the dimension of the ambient space, but the quantity that actually controlled the covering number was volume: how the measure of a ball scales as its radius shrinks. Dimension is only a summary of that scaling, and a lossy one—it says nothing about the position, shape, or sparsity of the set being covered. Ambient dimension is sometimes the right complexity parameter, but often it is too crude. A finite set, a sparse set, or the image of a low-dimensional model may have a much smaller covering number than the entire ambient ball, even though all three sit inside the same \(\mathbb R^d\). Covering numbers, and the volume comparisons used to bound them, are the more faithful notion of size; this is the refinement of dimension we were after, and it is the tool that will let us return to Remark 1 and measure the complexity of a class of functions such as the \(L\)-Lipschitz maps, rather than of a ball or a cube.
The next lectures develop two more flexible ideas:
- approximate a convex combination by a sparse average; and
- measure a set by how large it looks in a random Gaussian direction.
These are early examples of a general strategy: identify the part of the geometry that a random process can actually see.