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

2013/11/08 by Matus Telgarsky, Telgarsky, Matus, Sanjoy Dasgupta +1 · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Statistical Methods and Inference #Statistical Methods and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.1311.1903

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≥ 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.

Cited by

• Tradeoffs for Space, Time, Data and Risk in Unsupervised Learning

Related

• Uniform Deviation Bounds for Unbounded Loss Functions like k-Means
• Robust k-means Clustering for Distributions with Two Moments
• Clustering with Spectral Norm and the k-means Algorithm
• Bounding probability of small deviation on sum of independent random variables: Combination of moment approach and Berry-Esseen theorem
• Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means