Paper Info
Title
Online K-Means Clustering
Abstract
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 (root 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 centers at each round) implies an offine 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 + epsilon)OPT and present a no-regret algorithm with runtime O T poly(log(T), k, d, 1/epsilon)(O(kd))). Our algorithm is based on maintaining a set of points of bounded size which is a coreset that helps identifying the relevant regions of the space for running an adaptive, more efficient, variant of the MWUA. We show that simpler online algorithms, such as 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).
Year
Venue
DocType
2021
24TH INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS (AISTATS)
Conference
Volume
ISSN
Citations 
130
2640-3498
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Vincent Cohen-Addad18525.47
Benjamin Guedj298.82
Varun Kanade312221.94
Rom Guy400.34