# On the optimality of kernels for high-dimensional clustering

arXiv: https://arxiv.org/abs/1912.00458 · HTML: https://mlsanity.com/paper/1912.00458/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2019.

## Built on by (most cited first, 2 of 2)

- [Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models](https://mlsanity.com/paper/2110.09476/) (2021)
- [A Reproduction Study: The Kernel PCA Interpretation of Self-Attention Fails Under Scrutiny](https://mlsanity.com/paper/2505.07908/) (2025)

## Abstract (arXiv)

This paper studies the optimality of kernel methods in high-dimensional data clustering. Recent works have studied the large sample performance of kernel clustering in the high-dimensional regime, where Euclidean distance becomes less informative. However, it is unknown whether popular methods, such as kernel k-means, are optimal in this regime. We consider the problem of high-dimensional Gaussian clustering and show that, with the exponential kernel function, the sufficient conditions for partial recovery of clusters using the NP-hard kernel k-means objective matches the known information-theoretic limit up to a factor of √2 for large k. It also exactly matches the known upper bounds for the non-kernel setting. We also show that a semi-definite relaxation of the kernel k-means procedure matches up to constant factors, the spectral threshold, below which no polynomial-time algorithm is known to succeed. This is the first work that provides such optimality guarantees for the kernel k-means as well as its convex relaxation. Our proofs demonstrate the utility of the less known polynomial concentration results for random variables with exponentially decaying tails in a higher-order analysis of kernel methods.