Why the number of training points to densely cover the space grows exponentially with the dimension?

Question

In this lecture (minute 42), the professor says that the number of training examples we need to densely cover the space of training vectors grows exponentially with the dimension of the space. So we need $4^2=16$ training data points if we're working on $2D$ space. I'd like to ask why this is true and how is it proved/achieved? The professor was talking before about K-Nearest Neighbors and he was using $L^{1}$ and $L^{2}$ metrics. I don't think these metrics induce a topology that makes a discrete set of points dense in the ambient space.

Answer 1

First, let's try to build some intuition for what we mean when we say that we want to "densely cover" a $d$-dimensional space $\mathbb{R}^d$ of real numbers. For simplicity, let's assume that all values in all dimensions are restricted to lie in $[0, 1]$. Even with just a single dimension $d=1$, there are actually already infinitely many different possible values even in such a restricted $[0, 1]$ range.

But generally we don't actually care about literally covering every single possible value. Generally, we expect that points in this $d$-dimensional space that are "close" to each other also "behave" similarly, that there's some level of "continuity". Hence, to get "sufficient" or "good" or "dense" coverage of the space, you can somewhat informally assume that every data point you have occupies some space around it. This is the intuition behind Lutz Lehmann's comment under your question: you can think of every point as being a $d$-dimensional cube occupying some volume of your $d$-dimensional space.

Now, if you have a $d$-dimensional space of size $[0, 1]$ along every dimension, and you have little cubes that occupy a part of that space (for instance, cubes of size $0.1$ in every dimension), you will indeed find that the number of cubes you need to fill up your space scales exponentially in $d$. The basic idea is: if some number of cubes $K$ is sufficient to fill up the $d$-dimensional space, and if you then increase the dimensionality to $d+1$, you'll need $dK$ cubes to fill the new space. When you add a new dimension, the complete previous space becomes essentially just one "slice" of the new space.

For dimensions $d = 1, 2, 3$, this is fairly easy to visualise. If you have $d=1$, your space is really just a line, or a line segment if you constrain the values to lie in $[0, 1]$. If you have a $[0, 1]$ line segment, and you have little cubes of length $0.1$, you'll need just ten of them to fill up the line.

Now imagine that you add the second dimension. Suddenly your line becomes an entire plane, or a $10\times10$ square grid. The $10$ cubes are now only sufficient to fill up a single row, and you'll have to repeat this $10$ times over to fill up the entire $2$D space; you need $10^2 = 100$ cubes.

Now imagine that you add the third dimension. What used to be a plane gets "pulled out" into an entire three-dimensional cube -- a large cube, which will require many little cubes to fill! The plane that we had previously is again just a flat slice in this larger $3$D space, and the entire strategy for filling up a plane will have to be repeated $10$ times over to fill up $10$ such slices of the $3$D space; this now requires $10^3 = 1000$ cubes.

Past $3$ dimensions, the story continues in exactly the same way, but is a bit harder for us humans to visualise.