UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Online k-means Clustering

Cohen-Addad, V; Guedj, B; Kanade, V; Rom, G; (2021) Online k-means Clustering. In: Banerjee, A and Fukumizu, K, (eds.) Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. (pp. pp. 1126-1134). Proceedings of Machine Learning Research (PMLR): Virtual conference. Green open access

[thumbnail of cohen-addad21a.pdf]
cohen-addad21a.pdf - Published Version

Download (450kB) | Preview


We study the problem of learning a clustering of an online set of points. 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 by the algorithm 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 in hindsight. We show that provided the data lies in a bounded region, learning is possible, namely an implementation of the Multiplicative Weights Update Algorithm (MWUA) using a discretized grid achieves a regret bound of O~(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, which is known to be NP-hard. In light of this hardness, we consider the slightly weaker requirement of comparing regret with respect to (1+ϵ)OPT and present a no-regret algorithm with runtime O(Tpoly(log(T),k,d,1/ϵ)O(kd)). Our algorithm is based on maintaining a set of points of bounded size which is a coreset that helps identifying the \emph{relevant} regions of the space for running an adaptive, more efficient, variant of the MWUA. We show that simpler online algorithms, such as \emph{Follow The Leader} (FTL), fail to produce sublinear regret in the worst case. We also report preliminary experiments with synthetic and real-world data. Our theoretical results answer an open question of Dasgupta (2008).

Type: Proceedings paper
Title: Online k-means Clustering
Event: 2021 International Conference on Artificial Intelligence and Statistics
Open access status: An open access version is available from UCL Discovery
Publisher version: http://proceedings.mlr.press/v130/cohen-addad21a.h...
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10127230
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item