Moment-based Uniform Deviation Bounds for $k$-means and Friends

Matus Telgarsky, Sanjoy Dasgupta

Abstract

This paper addresses the fundamental question of how well a $k$-means solution derived from a finite sample generalizes to the underlying distribution, particularly when the data is not bounded or subgaussian. By assuming only $p \ge 4$ finite moments, we establish the first finite-sample uniform deviation bounds for $k$-means and soft clustering variants like Gaussian Mixture Models (GMMs). We introduce a technical mechanism termed "Outer Bracketing" to control deviations in the presence of unbounded parameter sets and heavy-tailed distributions. Our results show that the difference between sample and distribution costs decays at a rate of $m^{\min\{-1/4, -1/2+2/p\}}$, approaching the $O(m^{-1/2})$ rate as the number of moments increases.

Introduction

In statistical learning theory, uniform deviation bounds are essential for understanding the generalization performance of empirical risk minimizers. For clustering tasks, such as $k$-means, we seek to ensure that the centers found by minimizing the cost on a training sample $m$ will perform similarly on the true distribution $\rho$.

Traditionally, these bounds have relied on restrictive assumptions: either the data must reside within a bounded ball or follow a light-tailed distribution (e.g., subgaussian). However, real-world data often exhibits heavy tails, where outliers occur more frequently than Gaussian models predict. In such cases, the $k$-means cost function becomes unbounded, causing standard statistical tools like Rademacher complexity or standard covering numbers to fail. This work bridges this gap by providing rigorous guarantees using only moment-based assumptions.

Methodology: The Outer Bracketing Mechanism

To handle the challenges of unboundedness, we introduce a "divide and conquer" strategy for the probability space called Outer Bracketing. This approach splits the analysis into two distinct regions:

  1. Local Deviations: Within a sufficiently large ball containing the "bulk" of the distribution, the cost function is effectively bounded. Here, standard covering number arguments can be applied to control the variance of the empirical cost.
  2. Outer Deviations: In the regions outside this ball, the cost function can grow significantly. However, the probability of encountering data points in these regions is extremely low.

By constructing an "Outer Bracket"—a pair of functions that sandwich the cost function in these remote regions—and applying the dominated convergence theorem alongside Chebyshev-style inequalities, we prove that the influence of these far-away points remains negligible as long as the distribution has at least four bounded moments ($p \ge 4$).

Scope of Application

The mechanism is applied to two primary clustering frameworks:

  • Hard $k$-means: We generalize the standard $k$-means problem using Bregman Divergences, allowing for a broader class of distance measures.
  • Soft Clustering (GMMs): We analyze the log-likelihood of Gaussian Mixture Models. To prevent the likelihood from becoming degenerate, we assume the covariance matrices have a bounded spectrum, where eigenvalues are constrained within a positive interval $[\sigma_1, \sigma_2]$.

Key Theoretical Insights

The Reference Score Loophole

A significant hurdle in analyzing $k$-means is that the centers could theoretically be placed anywhere in the space. We resolve this by constraining the analysis to solutions that outperform a "reference score" $c$ (such as the variance of the data). This is a practical assumption, as even basic heuristics like Lloyd's algorithm or a single center placed at the mean will satisfy this condition. This constraint allows us to focus on the "interesting" regions of the parameter space.

Bracketing vs. Covering

Unlike standard covering arguments that approximate a function class with a finite set of its own members, our bracketing approach utilizes functions that may exist outside the class. For instance, a bracket might consist of a function that is zero inside a ball and grows rapidly outside it. This flexibility is what allows the theory to accommodate heavy-tailed distributions.

Results and Convergence Rates

We establish concrete convergence rates for the deviation between the sample cost and the distribution cost:

  • $k$-means Rate: For a distribution with $p \ge 4$ moments, the deviation decays at $O(m^{\min\{-1/4, -1/2 + 2/p\}})$. As $p \to \infty$, this recovers the optimal $O(m^{-1/2})$ rate.
  • GMM Rate: For Gaussian Mixture Models, the analysis requires $p \ge 8$ moments, yielding a rate of $O(m^{-1/2 + 3/p})$.
  • Refined Constants: We further demonstrate that if the underlying distribution possesses a clear cluster structure (well-separated data), the constants within these bounds improve significantly, reflecting the easier nature of the clustering task.

Conclusion

This work provides a robust theoretical foundation for clustering algorithms operating on heavy-tailed data. By moving beyond the limitations of bounded or subgaussian assumptions, we show that $k$-means and GMMs remain statistically sound under minimal moment conditions. The "outer bracketing" technique presented here offers a generalizable framework for future research into other unbounded cost functions in machine learning.

Summary updated

Abstract

Suppose $k$ centers are fit to $m$ points by heuristically minimizing the $k$-means cost; what is the corresponding fit over the source distribution? This question is resolved here for distributions with $p\geq 4$ bounded moments; in particular, the difference between the sample cost and distribution cost decays with $m$ and $p$ as $m^{\min\{-1/4, -1/2+2/p\}}$. The essential technical contribution is a mechanism to uniformly control deviations in the face of unbounded parameter sets, cost functions, and source distributions. To further demonstrate this mechanism, a soft clustering variant of $k$-means cost is also considered, namely the log likelihood of a Gaussian mixture, subject to the constraint that all covariance matrices have bounded spectrum. Lastly, a rate with refined constants is provided for $k$-means instances possessing some cluster structure.
BibTeX
@inproceedings{telgarsky2013moment,
  author = {Matus Telgarsky and Sanjoy Dasgupta},
  title = {{Moment-based Uniform Deviation Bounds for $k$-means and Friends}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=W1yzGBufN1a},
}
Figure