Skip to Main content Skip to Navigation
Conference papers

Online $k$-means Clustering

Vincent Cohen-Addad 1 Benjamin Guedj 2, 3, 4, 5, 6 Varun Kanade 7 Guy Rom 7 
5 MODAL - MOdel for Data Analysis and Learning
LPP - Laboratoire Paul Painlevé - UMR 8524, Université de Lille, Sciences et Technologies, Inria Lille - Nord Europe, METRICS - Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Polytech Lille - École polytechnique universitaire de Lille
Abstract : 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 ($\mathcal{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 $\tilde{O}(\sqrt{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 + \epsilon) \mathcal{C}$ and present a no-regret algorithm with runtime $O\left(T(\mathrm{poly}(log(T),k,d,1/\epsilon)^{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\"{i}ve online algorithms, such as \emph{Follow The Leader}, fail to produce sublinear regret in the worst case. We also report preliminary experiments with synthetic and real-world data.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Benjamin Guedj Connect in order to contact the contributor
Submitted on : Monday, December 9, 2019 - 9:17:14 PM
Last modification on : Wednesday, March 23, 2022 - 3:51:07 PM
Long-term archiving on: : Tuesday, March 10, 2020 - 10:56:01 PM


Files produced by the author(s)


  • HAL Id : hal-02401290, version 1
  • ARXIV : 1909.06861


Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy Rom. Online $k$-means Clustering. AISTATS 2021 - The 24th International Conference on Artificial Intelligence and Statistics, Apr 2021, Virtual, France. ⟨hal-02401290⟩



Record views


Files downloads