Refined Learning Bounds for Kernel and Approximate $k$-Means

Yong LiuNeurIPS 2021 · OpenReview

The Theoretical Gap in Kernel $k$-Means

Clustering is a cornerstone of unsupervised machine learning, with $k$-means being its most famous algorithm. While standard $k$-means creates linear boundaries, kernel $k$-means allows for non-linear clustering by mapping data into a high-dimensional feature space. Despite its popularity, a significant theoretical gap has persisted for decades regarding its statistical efficiency.

Historically, the best-known "risk bounds"—which measure how much the clustering error on a sample differs from the true population error—were $O(k/\sqrt{n})$, where $k$ is the number of clusters and $n$ is the sample size. However, theoretical lower bounds suggested the error should only grow with the square root of the number of clusters, $\Omega(\sqrt{k/n})$. This discrepancy implied that our understanding of the algorithm's efficiency was overly pessimistic.

Furthermore, kernel $k$-means faces a massive computational wall: it requires calculating an $n \times n$ kernel matrix, which is intractable for large datasets. While approximation methods like Nyström sampling exist, it was previously unclear exactly how many landmark points were needed to maintain statistical optimality. This paper closes these long-standing gaps by deriving "nearly optimal" risk bounds and proving the statistical efficiency of Nyström-based approximations.

Bridging the Gap: Methods and Mathematical Breakthroughs

The authors employ a combination of advanced statistical learning theory and algorithmic analysis to achieve these tighter bounds:

  • Refined Rademacher Complexity: The core mathematical breakthrough relies on a recent technique for bounding the Rademacher complexity of Lipschitz functions. By applying this to the $k$-means loss function, the authors successfully reduced the theoretical dependency on $k$ from linear to a square-root, matching the lower bound.
  • Beyond Empirical Risk Minimization (ERM): Because finding the absolute best $k$-means solution is NP-hard, analyzing pure ERM isn't practically sufficient. The authors extended their proofs to "approximate" solutions, specifically analyzing the improved $k$-means++ algorithm with local search, proving it achieves a risk of $O(\sqrt{k/n} + W^*(P))$, where $W^*$ is the optimal clustering risk.
  • Nyström Approximation Analysis: To address the computational bottleneck, they analyzed the statistical effect of projecting the data into a lower-dimensional subspace defined by $m$ "landmark" points. They rigorously investigated how many points are required to ensure the approximation doesn't degrade the optimal learning rate.

Key Insights and Empirical Validation

The paper establishes several major milestones for clustering theory:

  1. The $\sqrt{k}$ Milestone: The paper definitively proves that the excess risk of kernel $k$-means is $O(\sqrt{k/n})$. This is a major win for applications with many clusters (like social network analysis or recommendation systems), demonstrating that the algorithm is much more robust to a large $k$ than previously thought.
  2. Nyström Efficiency: The authors show that you do not need the full kernel matrix. Sampling $\Omega(\sqrt{nk})$ landmark points is sufficient to reach optimal accuracy.
  3. The "Mild Condition" Bonus: If the kernel's eigenvalues decay algebraically—a common trait in many real-world kernels—the requirement for landmark points drops even further to just $\Omega(\sqrt{n})$, completely independent of the number of clusters $k$.

To validate these claims, the authors ran numerical experiments. The empirical "line of best fit" for the error rate aligned almost perfectly with the theoretical $k^{0.5}/n^{0.5}$ curve, providing a satisfying alignment between complex proofs and actual code.

Empirical excess risk vs. sample size $n$ across different cluster counts $k$, demonstrating the $O(\sqrt{k/n})$ rate.

Datasets and Real-World Performance

The authors validated their theoretical findings using both synthetic and real-world benchmarks. Simulated data (a 10-dimensional dataset with specific variances) was used to test the exact relationship between $k$, $n$, and error.

For real-world applicability, they tested on several LIBSVM datasets, ranging from smaller sets like dna (2,000 samples) to massive ones like covtype (581,012 samples). On the mnist and covtype datasets, the Nyström-based kernel $k$-means achieved highly competitive error rates (0.43 and 0.32 respectively) while remaining computationally feasible, proving that the theoretical approximations hold up in practice.

Limitations and Future Directions

While this paper makes significant strides, the authors note a few areas for future exploration:

  • Fast Rates: While $O(\sqrt{k/n})$ is optimal for general distributions, some specific distributions allow for "fast rates" of $O(k/n)$. Proving a bound of $O(\sqrt{k}/n)$ under strict assumptions (like margin conditions) remains an open challenge.
  • Computational Constants: The rate is now proven optimal, but the constant factors hidden by the Big-O notation could still be refined to provide even tighter practical guidance for algorithm design.

Summary updated

Abstract

Kernel $k$-means is one of the most popular approaches to clustering and its theoretical properties have been investigated for decades. However, the existing state-of-the-art risk bounds are of order $\mathcal{O}(k/\sqrt{n})$, which do not match with the stated lower bound $\Omega(\sqrt{k/n})$ in terms of $k$, where $k$ is the number of clusters and $n$ is the size of the training set. In this paper, we study the statistical properties of kernel $k$-means and Nystr\"{o}m-based kernel $k$-means, and obtain optimal clustering risk bounds, which improve the existing risk bounds. Particularly, based on a refined upper bound of Rademacher complexity [21], we first derive an optimal risk bound of rate $\mathcal{O}(\sqrt{k/n})$ for empirical risk minimizer (ERM), and further extend it to general cases beyond ERM. Then, we analyze the statistical effect of computational approximations of Nystr\"{o}m kernel $k$-means, and prove that it achieves the same statistical accuracy as the original kernel $k$-means considering only $\Omega(\sqrt{nk})$ Nystr\"{o}m landmark points. We further relax the restriction of landmark points from $\Omega(\sqrt{nk})$ to $\Omega(\sqrt{n})$ under a mild condition. Finally, we validate the theoretical findings via numerical experiments.
BibTeX
@inproceedings{liu2021refined,
  author = {Yong Liu},
  title = {{Refined Learning Bounds for Kernel and Approximate $k$-Means}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=_tQns0wUl_3},
}
Figure