distance based learning algorithms in high dimensions

My question wasn't specifically about classification only (e.g., KNN vs other classification algorithms). I meant any learning algorithm that depends on pairwise distances at some stage. So even clustering algorithms such as k-means might also face this problem in high dimensions. So I wanted to know if there are any generic (or even specific, customized for a learning algorithm) suggestions proposed in literature to address such pathological cases.

On a somewhat different note, one of the nice things about KNN is that it can represent non-linear boundaries without having to use kernels. I was wondering if a kernelized SVM too would face problems in high dimensions because computing the kernel matrix also requires computing distances. Well, of course, probably you wouldn't want to kernelize if you already are in a high dimensional space (please correct me if there are cases when you would still want to kernelize high dimensional data) but let's assume if the data is at least "moderately" high dimensional and you want to kernelize your SVM, would the kernel matrix be reliable (and the subsequent decision boundary given by SVM which depends on the pairwise distances or "similarities" of a test point with support vectors in the RHKS)?

Well, about KNN not using kernels, this is not exactly true. Since it only depends on distances, you can always start from any kernel matrix and define dist(a,b) = K(a,a) + K(b,b) - 2K(a,b). The same trick works for k-means, btw. In this sense, both KNN and K-means already kind of use kernels to do what they do, and a lot of preprocessing steps people use with these methods (centering and normalizing the data, or removing correlations between the dimensions) can be seen as specific kernels. To be clear, since it depends on pairwise dot products, it is already using kernels implicitly.

What people usually do in very high dimensional cases, I think, is to use some sort of dimensionality reduction. Usually PCA, random projections, truncated SVD, neural network autoencoders, ICA, etc.

About the reliability of the kernel matrix, this is controlled by the fact that the SVM classifier is highly regularized, which limits the complexity of the models you get out of it, helping generalization. One of the main reasons it makes more sense to use an SVM for this sort of problem instead of a KNN is that the SVM model will be "simpler", even though it also depends on the pairwise distances. It is hard to do complexity control with KNN (you can only tweak the value of K, which might be problematic if your points are not uniformly spaced), and this makes a hard problem a lot worse. But sometimes even SVMs suffer from very high dimensional spaces, specially with kernels (since it's not so easy to ignore irrelevant features if you're in a projected space, which will make your classifier use far more support vectors than it would otherwise need). For this sort of situation a neural network sounds attractive, since you can learn the "support vectors", and avoiding using support vectors (that is, the weights of the nodes) that have high values for irrelevant features (which is impossible for SVMs, since the support vectors are constrained to be from the training set).

So my point, compressed, is that KNN ends up being just like gaussian SVMs (with the sigma parameter tuned so that the variance usually covers about K neighbors) but with poorer support vector selection, and, hence, complexity control; so, in a sense, it is guaranteed to generalize worse.

Even when faced with very high dimensions we expect that the data will be highly nonlinear still. So in order to address the curse of the dimensionality pointed out in the question, we can first do some cheap (linear) dimensionality reduction (PCA, random projections...). But to address the issue of nonlinearity a second nonlinear reduction like kernel-PCA should be used. That's what I would do, but isn't there an alternative way to cope with this problem? Also my concern is that the initial PCA uses the pairwise-distances (implicitly), and if these are blurred in the high dimensional space how is the PCA to infer a decent subspace? Because of this I would expect a very slow decay of the singular values in high-dimensional spaces.

I agree that cosine works in high dim (at least on text data with normalized bag of words repr). However it is directly related to the euclidean distance:

||a - b||^2 = a^2 + b^2 - 2 <a, b> = 2 - 2 * cosinesim(a, b)

So the fact that it works so well is probably not related to intrinsics properties of cosinesim itself but to the some statistical properties of normalized bags of words that might not be generalisable to other kinds of high dim datasets (although I would love to be proven wrong).

Actually I just read Bob Durrant's answer and he seems to have pushed this reasoning forward :)

Good point! However, they are related only if you normalize the vectors beforehand. This shows that the normalization is the key here. In the case of document classification, thanks to normalization, long documents and short documents are treated equally. Actually, many learning algorithms include the norm of the data in their bounds.