Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means

Rong Yin, Yong Liu, Weiping Wang, Dan MengNeurIPS 2022 · OpenReview

Introduction

Clustering is a cornerstone of unsupervised learning, and Kernel $k$-means is one of its most powerful variants. By leveraging the "kernel trick," it can identify complex, non-linear clusters that standard $k$-means would completely miss. However, this paper addresses a massive catch: scalability.

To run exact kernel $k$-means on $n$ samples, one typically needs to compute and store an $n \times n$ kernel matrix. This results in $O(n^2)$ space and time complexity. If a dataset contains a million samples, $n^2$ is a trillion—far beyond the memory capacity of most modern workstations. While researchers have previously attempted to approximate this using "sketches" (compressed versions of the data), earlier methods either converged too slowly or required very large sketch dimensions and strong assumptions to reach an "optimal" error rate.

This paper introduces a unified framework for "sketching" kernel $k$-means clustering, allowing it to scale to massive datasets without sacrificing accuracy. The authors prove that a sketch dimension of only $\Omega(\sqrt{n})$ is needed to achieve the same statistical optimality as the full, computationally expensive version, effectively slashing time and memory requirements from quadratic to sub-quadratic.

A Unified Randomized Sketches Framework

Instead of working with the full $n$-dimensional embeddings, the authors propose projecting the data into a much lower $m$-dimensional space using a sketch matrix $R$. They highlight three specific types of sketches within this unified framework:

  1. Sub-Gaussian Sketches: Uses sparse random matrices (via hash functions) to compress the data.
  2. Randomized Orthogonal System (ROS) Sketches: Uses the Fast Hadamard Transform (FFT-like) to fuse features efficiently.
  3. Nyström Kernel $k$-means: A popular method that subsamples $m$ landmark points to represent the entire dataset.

The core algorithm involves sampling $m$ points, constructing the sketch matrix, and then running a standard $k$-means algorithm on the resulting $m$-dimensional vectors. Crucially, this is integrated with $k$-means++ initialization to ensure the algorithm finds high-quality cluster centers.

Theoretical Breakthroughs: The $\sqrt{n}$ Threshold

The most significant insight of this work is the mathematical proof that a sketch dimension of $m = \Omega(\sqrt{n})$ is sufficient to achieve the optimal excess risk bound of $O(\sqrt{k/n})$. To the authors' knowledge, this is the first time such a result has been proven for unsupervised learning without requiring restrictive assumptions about the underlying data distribution.

Theoretical comparison of space, time, and risk bounds across different kernel k-means approaches.

By reducing the dimensionality to $\sqrt{n}$, the space complexity drops dramatically from $O(n^2)$ to $O(n\sqrt{n})$. For a dataset with 1,000,000 points, this reduces memory needs from roughly 4 Terabytes to just 4 Gigabytes. Furthermore, the ROS sketches leverage the Fast Hadamard Transform, allowing the "fusion" of data features in $O(m \log m)$ time rather than $O(m^2)$. Ultimately, the paper proves that while the method relies on approximation, it does not lose statistical "truth"—the sketched version reaches the same theoretical accuracy limit as the exact version.

Empirical Validation

The researchers validated their framework using both simulated data (Gaussian distributions in 8 dimensions) and nine real-world datasets from the LIBSVM repository, ranging from small (dna, 2,000 samples) to very large (covtype, 581,012 samples).

Accuracy and computational time comparisons as the sketch dimension m increases.

The empirical results strongly support the theoretical claims:

  • Massive Speedups: On the w7a dataset (~50k samples), exact kernel $k$-means took nearly 30 seconds. The proposed sketched methods (Sub-Gaussian, ROS, Nyström) all finished in less than 0.4 seconds while maintaining identical accuracy.
  • Handling Large Data: On the largest dataset (covtype, >580k samples), exact kernel $k$-means and previous state-of-the-art approximations failed entirely due to memory or time limits. The proposed framework successfully clustered the data in about 1 second.
  • Stability: As shown in the experiments, once the sketch dimension $m$ reaches the $\sqrt{n}$ threshold, the clustering accuracy stabilizes, confirming the theoretical predictions.

Limitations and Future Work

While the paper provides a massive leap in efficiency, some limitations remain. Even $O(n\sqrt{n})$ memory can eventually become a bottleneck as $n$ reaches the billions; further research might look into $O(n \cdot \text{polylog } n)$ approaches. Additionally, like all kernel methods, performance heavily depends on choosing the right kernel (e.g., Gaussian) and its hyperparameters, which this sketching framework does not inherently solve. Finally, while $k$-means++ helps, the algorithm still converges to local optima. Exploring global optimization within this sketched framework remains a fruitful next step for future research.

Summary updated

Abstract

Kernel $k$-means is arguably one of the most common approaches to clustering. In this paper, we investigate the efficiency of kernel $k$-means combined with randomized sketches in terms of both statistical analysis and computational requirements. More precisely, we propose a unified randomized sketches framework to kernel $k$-means and investigate its excess risk bounds, obtaining the state-of-the-art risk bound with only a fraction of computations. Indeed, we prove that it suffices to choose the sketch dimension $\Omega(\sqrt{n})$ to obtain the same accuracy of exact kernel $k$-means with greatly reducing the computational costs, for sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystr\"{o}m kernel $k$-means, where $n$ is the number of samples. To the best of our knowledge, this is the first result of this kind for unsupervised learning. Finally, the numerical experiments on simulated data and real-world datasets validate our theoretical analysis.
BibTeX
@inproceedings{yin2022randomized,
  author = {Rong Yin and Yong Liu and Weiping Wang and Dan Meng},
  title = {{Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=GCR27k2UkWb},
}
Figure