# Online k-means Clustering

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2019.

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

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Active clustering with bandit feedback](https://mlsanity.com/paper/2406.11485/) (2024)
- [ALPS: An Auto-Labeling and Pre-training Scheme for Remote Sensing Segmentation With Segment Anything Model](https://mlsanity.com/paper/2406.10855/) (2024)
- [Online k-means Clustering on Arbitrary Data Streams](https://mlsanity.com/paper/2102.09101/) (2021)
- [A Batch-to-Online Transformation under Random-Order Model](https://mlsanity.com/paper/2306.07163/) (2023)
- [Learning from Streaming Data when Users Choose](https://mlsanity.com/paper/2406.01481/) (2024)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)
- [Online Performance Estimation with Unlabeled Data: A Bayesian Application of the Hui-Walter Paradigm](https://mlsanity.com/paper/2401.09376/) (2024)
- [Evolving Restricted Boltzmann Machine-Kohonen Network for Online Clustering](https://mlsanity.com/paper/2402.09167/) (2024)
- [Minimizing Human Intervention in Online Classification](https://mlsanity.com/paper/2510.23557/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)
- [Learning-Augmented Algorithms for k-median via Online Learning](https://mlsanity.com/paper/2603.18157/) (2026)
- [Co-Evolving Zero-Day Jamming: Adaptive Attack Synthesis and Graph Attention-Based Online Detection](https://mlsanity.com/paper/2609.21334/) (2026)

## Abstract (arXiv)

We study the problem of online clustering where a clustering algorithm has to assign a new point that arrives to one of k clusters. The specific formulation we use is the k-means objective: At each time step the algorithm has to maintain a set of k candidate centers and the loss incurred is the squared distance between the new point and the closest center. The goal is to minimize regret with respect to the best solution to the k-means objective (C) in hindsight. We show that provided the data lies in a bounded region, an implementation of the Multiplicative Weights Update Algorithm (MWUA) using a discretized grid achieves a regret bound of tildeO(√T) in expectation. We also present an online-to-offline reduction that shows that an efficient no-regret online algorithm (despite being allowed to choose a different set of candidate centres at each round) implies an offline efficient algorithm for the k-means problem. In light of this hardness, we consider the slightly weaker requirement of comparing regret with respect to (1 + ε) C and present a no-regret algorithm with runtime Oleft(T(poly(log(T),k,d,1/ε)k(d+O(1))right). Our algorithm is based on maintaining an incremental coreset and an adaptive variant of the MWUA. We show that na"ive online algorithms, such as Follow The Leader, fail to produce sublinear regret in the worst case. We also report preliminary experiments with synthetic and real-world data.