In KNN, why does the number of training examples needed to learn a decision boundary increase (exponentially) as the number of dimensions increases? In book I'm reading the following is said on k-nearest neighbour algorithms:
"As the number of dimensions goes up, the number of training examples you need to locate the concept's frontiers goes up exponentially. With 20 Boolean attributes(features), there are roughly a million different possible examples"
My questions:
1)why exactly does the number of training examples needed to learn a decision boundary increase (exponentially) as the number of dimensions increases?
2)the quoted paragraph says that we need to have a data point in our training data corresponding to each possible example, but do we really need an actually training data point for each and every possible example?
(I can intuitively guess that performance is of course going to be better if we have training data for each possible example but I'd like to know exactly why?)
3)Does link to how in general statistics, as we introduce more parameters into a model, we need to collect more data?
 A: I'll try to answer your questions as they relate to the case of binary features since this is a much simpler case to think about. However, many of the statements I'll make about this case also apply somewhat to the case of continuous features.
I think your questions are much easier to answer when you can picture what's happening. I'll assume you know how KNN works generally, but consider specifically the case of all binary features. With two features, there are only four possible points an observation can take: {(0,0) (1,0) (0,1) (1,1)}. We can plot them below.

To understand how things change with added dimensions, we also plot all the possible values with three binary features.

Let's start with question two.
2. Do we need a training data point for every possible example?
The answer is no, you don't need an observation for every possible point, but consider what happens in the case where you don't have a point in the training set, and you want to classify it. In the three binary-variable case, imagine we are trying to classify the blue point, but there are no observations at that point. We look elsewhere for the nearest neighbors, and we find that the three red points are each exactly a distance of one away. However, each of those points might correspond to many observations, meaning there may be thousands of observations that are all the same distance away from the position you want to classify. That doesn't prevent you from getting a prediction, but what kind of accuracy would you expect from a prediction that looks at all of those different points? In some cases, especially in higher dimensions, this might not be a problem. But there are many cases where we would not expect the set of all points equidistant away to be informative of the missing point. In the two-variable case we illustrated above, you'll see that each point is equidistant to two other points instead of three. This pattern continues for higher dimensions. In the case of $m$ binary variables, every possible point has $m$ other points that are all the same distance away.
1. Why exactly does the number of training examples needed to learn a decision boundary increase (exponentially) as the number of dimensions increases?
You can create a decision boundary in any number of dimensions with only two points. But, as we've shown, you want to have observations in your training set for every possible point. The number of possible points ($n$) grows exponentially with the number of dimensions ($m$): $n=2^m$. In three dimensions, there are $2^3=8$ possible points, but in twenty dimensions, there are $2^{20}=1048576$
3)Does this link to how in general statistics, as we introduce more parameters into a model, we need to collect more data?
In general, I don't believe the amount of data you need to fit some parameters grows exponentially with respect to the number of parameters. This answer suggests it does not. However, the above reasoning about binary features does generalize roughly to the case of continuous features. In higher dimensions, you'll notice the same trends. With increased dimensions, the volume of space grows exponentially, and more points become close to the same distance away. Many resources discuss issues with high dimensionality. You can search this stack for "curse of dimensionality," for example.
