# Monte Carlo approximation certificates for k-means clustering

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

## Key facts

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

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

- [Sketch-and-solve approaches to k-means clustering by semidefinite programming](https://mlsanity.com/paper/2211.15744/) (2022)
- [Forest Fire Clustering for Single-cell Sequencing with Iterative Label Propagation and Parallelized Monte Carlo Simulation](https://mlsanity.com/paper/2103.11802/) (2021)

## Abstract (arXiv)

Efficient algorithms for k-means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect k-means optimality. In this paper, we develop an a posteriori certifier of approximate optimality for k-means clustering. The certifier is a sub-linear Monte Carlo algorithm based on Peng and Wei's semidefinite relaxation of k-means. In particular, solving the relaxation for small random samples of the dataset produces a high-confidence lower bound on the k-means objective, and being sub-linear, our algorithm is faster than k-means++ when the number of data points is large. We illustrate the performance of our algorithm with both numerical experiments and a performance guarantee: If the data points are drawn independently from any mixture of two Gaussians over ℝm with identity covariance, then with probability 1-O(1/m), our operatornamepoly(m)-time algorithm produces a 3-approximation certificate with 99% confidence.