What is the relationship between Curse of Dimensionality and isotropic neighborhoods? I am currently reading The Elements of Statistical Learning by Hastie, Tibshirani and Friedman. At the end of the very insightful section 2.7 the authors say this.

Any method that attempts to produce locally varying functions in small isotropic neighborhoods will run into problems in high dimensions—again the curse of dimensionality. And conversely, all methods that overcome the dimensionality problems have an associated—and often implicit or adaptive—metric for measuring neighborhoods, which basically does not allow the neighborhood to be simultaneously small in all directions.

I am not at all clear what the connection between isotropic neighborhood and curse of dimensionality is. The authors have previously presented linear regression as a model that does not suffer from curse of dimensionality, but k-nearest neighbor suffers heavily from it.
How does isotropic/non-isotropic neighborhood fit into that picture? What about non-linear models such as neural networks and random forest?
 A: The problem that Hastie, Tibshirani, and Friedman are talking about here is that the number of fixed-size neighborhoods goes up exponentially with the dimension.
If you're trying to get some intuition for how isotropic neighborhoods are affected by the curse of dimensionality, think about approximating ball-shaped (isotropic) neighborhoods with cube-shaped neighborhoods. Suppose we have an $d$-dimensional unit cube $[0, 1]^d$ that we want to divide up into cube-shaped neighborhoods. If I want a neighborhood of side length $\delta = 0.1$, in one dimension this requires $10^1 = 10$ neighborhoods. In two dimensions, this requires $10^2 = 100$ neighborhoods. In three dimensions, this requires $10^3 = 1000$ neighborhoods (see image below).

If we were given some data $\{ (x_i, y_i) \}_{i=1}^n$ where $y_i = f(x_i)$ is computed from an unknown function $f : [0, 1]^d \to \mathbb{R}$ that we want to estimate using the data. A very simple way to estimate $f$ would be to use the mean of all of the points $y_i$ in a particular neighborhood to estimate $f$ in that neighborhood. A simple experiment with $d = 1$, $f(x) = \sin(2 \pi x)$, $\delta = 0.1$, and $n = 100$ shows that this works reasonably well if $f$ is continuous (see image below).

The problem is that if we want to use the same technique in higher dimensions, the amount of data we need increases exponentially. If I have only $n = 100$ data points for the square and I want to use the same technique, even if the data is uniformly distributed some of the neighborhoods are empty (see image below). Try the same $n=100$ with three dimensions and now at best 90% of the neighborhoods are empty. The mean also becomes a worse estimate of the true value of $f$ in each neighborhood with fewer points, so this is bad even for the neighborhoods that aren't empty.

So in summary, this method I described for estimating $f$ stops working well unless the amount of data increases exponentially with the dimension. If you were doing an application with images, for example, you might have 3 color channels and a 100x100 pixel image (a relatively small image), which would effectively be a 30,000-dimensional space. Dividing up that space into 10 sub-intervals like I did in the examples above would $10^{30,000}$ neighborhoods, a frightfully large number. Obviously you cannot even collect one data point for every neighborhood, so this method is doomed. While the method of using the mean on each neighborhood is very simple, $k$-nearest neighbors is only a slightly more complex version of this, so it suffers similarly. The comment about other methods is simply the converse of this realization: if a method successfully overcomes the curse of dimensionality, then it must be different than this method, such as linear regression, neural networks, and random forests, which are not built on these local neighborhoods.
