# Convergence of online k-means

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [On the Global Convergence of (Fast) Incremental Expectation Maximization Methods](https://mlsanity.com/paper/1910.12521/) (2019)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Convergence rate of stochastic k-means](https://mlsanity.com/paper/1611.05132/) (2016)

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

- [Evaluating Generalizability of Fine-Tuned Models for Fake News Detection](https://mlsanity.com/paper/2205.07154/) (2022)
- [Learning from Streaming Data when Users Choose](https://mlsanity.com/paper/2406.01481/) (2024)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [Disciplined Biconvex Programming](https://mlsanity.com/paper/2511.01813/) (2025)

## Abstract (arXiv)

We prove asymptotic convergence for a general class of k-means algorithms performed over streaming data from a distribution: the centers asymptotically converge to the set of stationary points of the k-means cost function. To do so, we show that online k-means over a distribution can be interpreted as stochastic gradient descent with a stochastic learning rate schedule. Then, we prove convergence by extending techniques used in optimization literature to handle settings where center-specific learning rates may depend on the past trajectory of the centers.