# Nested Mini-Batch K-Means

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2016.

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

- [A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource](https://mlsanity.com/paper/2211.12875/) (2022)
- [Transductive Few-Shot Learning: Clustering is All You Need?](https://mlsanity.com/paper/2106.09516/) (2021)
- [Towards Controllable Time Series Generation](https://mlsanity.com/paper/2403.03698/) (2024)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [Accelerating spherical K-means clustering for large-scale sparse document data](https://mlsanity.com/paper/2411.11300/) (2024)

## Abstract (arXiv)

A new algorithm is proposed which accelerates the mini-batch k-means algorithm of Sculley (2010) by using the distance bounding approach of Elkan (2003). We argue that, when incorporating distance bounds into a mini-batch algorithm, already used data should preferentially be reused. To this end we propose using nested mini-batches, whereby data in a mini-batch at iteration t is automatically reused at iteration t+1. Using nested mini-batches presents two difficulties. The first is that unbalanced use of data can bias estimates, which we resolve by ensuring that each data sample contributes exactly once to centroids. The second is in choosing mini-batch sizes, which we address by balancing premature fine-tuning of centroids with redundancy induced slow-down. Experiments show that the resulting nmbatch algorithm is very effective, often arriving within 1% of the empirical minimum 100 times earlier than the standard mini-batch algorithm.