# Convergence rate of stochastic k-means

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2016.

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

- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Convergence of online k-means](https://mlsanity.com/paper/2202.10640/) (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)
- [Mini-Batch Kernel k-means](https://mlsanity.com/paper/2410.05902/) (2024)
- [Mini-batch k-means terminates within O(d/ε) iterations](https://mlsanity.com/paper/2304.00419/) (2023)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [Robust Clustering on High-Dimensional Data with Stochastic Quantization](https://mlsanity.com/paper/2409.02066/) (2024)

## Abstract (arXiv)

We analyze online citeBottouBengio and mini-batch citeSculley k-means variants. Both scale up the widely used k-means algorithm via stochastic approximation, and have become popular for large-scale clustering and unsupervised feature learning. We show, for the first time, that starting with any initial solution, they converge to a "local optimum" at rate O(frac1t) (in terms of the k-means objective) under general conditions. In addition, we show if the dataset is clusterable, when initialized with a simple and scalable seeding algorithm, mini-batch k-means converges to an optimal k-means solution at rate O(frac1t) with high probability. The k-means objective is non-convex and non-differentiable: we exploit ideas from recent work on stochastic gradient descent for non-convex problems citege:sgdtensor, balsubramani13 by providing a novel characterization of the trajectory of k-means algorithm on its solution space, and circumvent the non-differentiability problem via geometric insights about k-means update.