# 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?

## 1 Answer

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.

• Nice visualizations and good answer. However where does isotropic/non-isotropic property of the neighborhood come into this picture? And also why should we fix the neighborhood side length for all dimensions? Aug 9 '20 at 11:57
• There are several approximations going on here. I think HTF are using the phrase "isotropic neighborhood" as a fancy word for a ball, since a ball is the "same in all directions." The first approximation I used was to use cubes to approximate balls, because the volume between differs by a constant if the dimension $d$ is fixed, namely, if $B$ is a ball with radius $\delta/2$, then Volume$(B) = \pi^{d/2}/\Gamma(d/2 + 1) (\delta/2)^d$, and the volume of the cube-shaped neighborhoods of side length $\delta$ was $\delta^d$. Aug 9 '20 at 19:49
• Since the problem was the volume of the neighborhoods, the same problem applies to the volume of the balls, not just to the cubes. It still scales exponentially with the dimension $d$, whether the neighborhoods are cube-shaped or ball-shaped. Aug 9 '20 at 19:51
• If we don't fix the neighborhood size (at least approximately) in all dimensions, then we aren't talking about isotropic neighborhoods, since isotropic means "same in all directions." Your quote from HTF is saying exactly this in the last sentence, "all methods that overcome the dimensionality problems [...] basically [do] not allow the neighborhood to be simultaneously small in all directions." Read that as "all methods that overcome the dimensionality problem do not have a fixed side length in all directions." Aug 9 '20 at 19:55