# Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2016.

## Built on by (most cited first, 30 of 54)

- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Transformers versus the EM Algorithm in Multi-class Clustering](https://mlsanity.com/paper/2502.06007/) (2025)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Self-Supervised Metric Learning in Multi-View Data: A Downstream Task Perspective](https://mlsanity.com/paper/2106.07138/) (2021)
- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)
- [Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks](https://mlsanity.com/paper/2311.15598/) (2023)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [Variational Estimators of the Degree-corrected Latent Block Model for Bipartite Networks](https://mlsanity.com/paper/2206.08465/) (2022)
- [Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data](https://mlsanity.com/paper/2209.15097/) (2022)
- [An Improved Algorithm for Clustered Federated Learning](https://mlsanity.com/paper/2210.11538/) (2022)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)

## Abstract (arXiv)

Clustering is a fundamental problem in statistics and machine learning. Lloyd's algorithm, proposed in 1957, is still possibly the most widely used clustering algorithm in practice due to its simplicity and empirical performance. However, there has been little theoretical investigation on the statistical and computational guarantees of Lloyd's algorithm. This paper is an attempt to bridge this gap between practice and theory. We investigate the performance of Lloyd's algorithm on clustering sub-Gaussian mixtures. Under an appropriate initialization for labels or centers, we show that Lloyd's algorithm converges to an exponentially small clustering error after an order of log n iterations, where n is the sample size. The error rate is shown to be minimax optimal. For the two-mixture case, we only require the initializer to be slightly better than random guess. In addition, we extend the Lloyd's algorithm and its analysis to community detection and crowdsourcing, two problems that have received a lot of attention recently in statistics and machine learning. Two variants of Lloyd's algorithm are proposed respectively for community detection and crowdsourcing. On the theoretical side, we provide statistical and computational guarantees of the two algorithms, and the results improve upon some previous signal-to-noise ratio conditions in literature for both problems. Experimental results on simulated and real data sets demonstrate competitive performance of our algorithms to the state-of-the-art methods.