# Clustering Semi-Random Mixtures of Gaussians

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

## Key facts

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

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

- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Private Training & Data Generation by Clustering Embeddings](https://mlsanity.com/paper/2506.16661/) (2025)
- [BalLOT: Balanced k-means clustering with optimal transport](https://mlsanity.com/paper/2512.05926/) (2025)

## Abstract (arXiv)

Gaussian mixture models (GMM) are the most widely used statistical model for the k-means clustering problem and form a popular framework for clustering in machine learning and data analysis. In this paper, we propose a natural semi-random model for k-means clustering that generalizes the Gaussian mixture model, and that we believe will be useful in identifying robust algorithms. In our model, a semi-random adversary is allowed to make arbitrary "monotone" or helpful changes to the data generated from the Gaussian mixture model. Our first contribution is a polynomial time algorithm that provably recovers the ground-truth up to small classification error w.h.p., assuming certain separation between the components. Perhaps surprisingly, the algorithm we analyze is the popular Lloyd's algorithm for k-means clustering that is the method-of-choice in practice. Our second result complements the upper bound by giving a nearly matching information-theoretic lower bound on the number of misclassified points incurred by any k-means clustering algorithm on the semi-random model.