# Consistency of Lloyd's Algorithm Under Perturbations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 68 references that are in the map.
- First posted on arXiv 1 Sep 2023.

## Builds on (most cited first, 25 of 25)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015)
- [Impact of regularization on Spectral Clustering](https://mlsanity.com/paper/1312.1733/) (2013)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014)
- [Moment-based Uniform Deviation Bounds for k-means and Friends](https://mlsanity.com/paper/1311.1903/) (2013)
- [Variational Inference for Stochastic Block Models from Sampled Data](https://mlsanity.com/paper/1707.04141/) (2017)
- [Some compact notations for concentration inequalities and user-friendly results](https://mlsanity.com/paper/1912.13463/) (2019)
- [Clustering Stable Instances of Euclidean k-means](https://mlsanity.com/paper/1712.01241/) (2017)
- [Estimation of subgraph density in noisy networks](https://mlsanity.com/paper/1803.02488/) (2018)
- [Exact Cluster Recovery via Classical Multidimensional Scaling](https://mlsanity.com/paper/1812.11954/) (2018)
- [Gaussian Mixture Clustering Using Relative Tests of Fit](https://mlsanity.com/paper/1910.02566/) (2019)
- [Correlation networks, dynamic factor models and community detection](https://mlsanity.com/paper/2307.09970/) (2023)

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

- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)

## Abstract (arXiv)

In the context of unsupervised learning, Lloyd's algorithm is one of the most widely used clustering algorithms. It has inspired a plethora of work investigating the correctness of the algorithm under various settings with ground truth clusters. In particular, in 2016, Lu and Zhou have shown that the mis-clustering rate of Lloyd's algorithm on n independent samples from a sub-Gaussian mixture is exponentially bounded after O(log(n)) iterations, assuming proper initialization of the algorithm. However, in many applications, the true samples are unobserved and need to be learned from the data via pre-processing pipelines such as spectral methods on appropriate data matrices. We show that the mis-clustering rate of Lloyd's algorithm on perturbed samples from a sub-Gaussian mixture is also exponentially bounded after O(log(n)) iterations under the assumptions of proper initialization and that the perturbation is small relative to the sub-Gaussian noise. In canonical settings with ground truth clusters, we derive bounds for algorithms such as k-means++ to find good initializations and thus leading to the correctness of clustering via the main result. We show the implications of the results for pipelines measuring the statistical significance of derived clusters from data such as SigClust. We use these general results to derive implications in providing theoretical guarantees on the misclustering rate for Lloyd's algorithm in a host of applications, including high-dimensional time series, multi-dimensional scaling, and community detection for sparse networks via spectral clustering.