Why isn't a gaussian kernel subject to the curse of dimensionality?

Question

This has been bugging me for a while now. I understand from this answer why gaussian kernels are effective. But I can't wrap my head around the intuition of why the infinite dimensional feature map 𝜙(𝑥) in the gaussian kernel is not subject to problems arising in this infinite dimensional space. I know that the "feature mapped" vector is never directly computed, but the inner product for example is evaluated and used as a measure of similarity between vectors.

But let's assume we are working with data sampled from a hypersphere, if in higher dimensions, the data becomes subject to problems like the concentration of measure phenomenon where everything shrinks to near zero volume and sampled points becomes randomly distributed/orthogonal on average, how would a gaussian kernel benefit in this setting since it would be taking the input data and mapping it to infinite dimensional space where in theory, all points should be uniformly close together around the center of the sphere and orthogonal on average, thus providing no insight for classification/clustering?

Or does the gaussian kernel map these points to a different geometrical structure in infinite dimensional Hilbert space? If so, why is this not then subject to other problems that arise due to the curse of dimensionality?

Answer 1

If we're taking, say, $\mathcal N(0, I)$ in increasing dimensions, then sample points eventually end up uniform on the surface of a sphere. Since most directions are orthogonal in high dimensional Euclidean space, most samples end up with inner product zero.

The Gaussian feature map brings points to $\phi(X)$ in the RKHS. It's interesting to note that $\lVert \phi(x) \rVert^2 = \langle \phi(x), \phi(x) = k(x, x) = 1$ for any point $x$; that is, any point is mapped onto the surface of a sphere in the RKHS.

But are they uniform on that sphere? No: $$\langle \phi(x), \phi(y) \rangle = k(x, y) > 0$$ for any points $x$, $y$, but if the points were uniform, we'd expect inner products to be positive half the time and negative half the time.

We can choose a kernel so that points are usually approximately orthogonal to one another; just take $\sigma$ really small so that $k(x, y)$ is usually almost zero. They still won't be uniform (no negative inner products) but they'll be pretty "spread out." We can also get them to almost collapse in on themselves: if we take $\sigma \to \infty$, then $$\frac{\langle \phi(x), \phi(y) \rangle }{ \lVert \phi(x) \rVert \lVert \phi(y) \rVert } \approx 1$$ for all $x$ and $y$.

But neither of these are very useful kernels, so we don't usually use them. Instead we pick a $\sigma$ such that many points do have inner products in reasonable ranges. This avoids the usual problems associated with the curse of dimensionality.

Answer 2

I think the Gaussian kernel does suffer from the curse of dimensionality. In the machine learning setting, especially the regression setting, we are trying to recover a $d$-dimension function from the noise data. But we can not just search within the whole space of $L_2(\mathbb{R}^d)$: it is just so big that the bias-variance trader-off is ruined (and I doubt if there is any procedures can direct do this).

We usually need to search within a sub-space of $L_2(\mathbb{R}^d)$: we can search within the $d$-dimension Sobolev space (which itself is an RKHS), which is a space that is big enough so that usually the true function indeed lies in this space. Or we can search within the RKHS related to the Gaussian kernel, by using Gaussian kernel as the kernel function in your favorite machine learning algorithm. However, this space is surprisingly small: which is smaller than any $d$-dimension Sobolev space, i.e. the function in this RKHS is super smooth. Therefore, if you assume \textbf{your regression function indeed lie in this super small function space} and try to learn it from data, you would get a pretty nice dependency on the dimension.

However, if your true regression does not lie in this space, you need to suffer a huge approximation error, which potentially would cause more trouble.

It sounds like you have basic familiarity with high-dimensional statistics: the Wainwright 2019 book on high-dimensional statistics would be a nice starting point. You can read his discussion in chapter 12 on RKHS: pay attention to the eigenvalue decay rate.