Online k-means Clustering

Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, Guy RomAISTATS 2021 · OpenReview

Online k-means Clustering: Balancing Regret and Runtime

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 $\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, 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\left(T \mathrm{poly}(\log(T),k,d,1/\epsilon)^{O(kd)}\right)$. 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).

Introduction

In the online clustering setting, data points arrive sequentially. For each point, an algorithm must select $k$ cluster centers before the point is revealed. The objective is to minimize cumulative regret: the difference between the algorithm's total loss and the loss of the optimal $k$ centers chosen in hindsight. This problem, posed as an open question by Sanjoy Dasgupta in 2008, presents a significant challenge in balancing statistical efficiency (sublinear regret) with computational tractability, given that offline $k$-means is NP-hard.

Theoretical Hardness and the $(1+\epsilon)$ Approximation

A key contribution of this work is an online-to-offline reduction. We demonstrate that a polynomial-time, no-regret online algorithm for $k$-means would imply a polynomial-time solution for the offline $k$-means problem. To circumvent this NP-hardness, we relax the objective to $(1+\epsilon)$-regret, comparing the algorithm's performance against a $(1+\epsilon)$ approximation of the optimal hindsight solution. This compromise allows for a computationally feasible approach.

The Mass Tree Multiplicative Weights Update Algorithm

To achieve sublinear regret, we propose a progression of techniques:

  1. Grid-based MWUA: A standard MWUA over a discretized grid achieves $O(\sqrt{T})$ regret but suffers from an exponential explosion in the number of experts as dimensionality and $k$ increase.
  2. Incremental Coresets: We utilize coresets—weighted subsets that represent the data's geometry—to restrict the algorithm's focus to relevant spatial regions.
  3. Adaptive Hierarchical Region Decomposition (HRD): Instead of a static grid, we employ a tree structure to adaptively partition space, refining regions where data is dense.
  4. Mass Tree MWUA (MTMW): This novel variant of MWUA operates on a dynamic tree of experts. As the tree grows, the "mass" (weight) of parent experts is distributed to children, allowing for continuous refinement of cluster centers without resetting the learning process.

Empirical Results

We evaluated our approach against the common "Follow the Leader" (FTL) heuristic using synthetic and real-world datasets.

Comparison of FTL and FTLMWUA regret on a worst-case synthetic sequence.

As shown in Figure 1, FTL can be forced into linear regret (a "staircase" pattern) on adversarial synthetic sequences. In contrast, the MWUA-based approach (FTLMWUA) maintains sublinear regret. However, FTL often performs well on more "stable" datasets.

FTL regret on various datasets, showing logarithmic growth in non-adversarial cases.

Figure 2 illustrates that on datasets like MNIST and well-separated Gaussian Mixture Models (GMMs), FTL exhibits logarithmic regret, suggesting that its worst-case failures may not manifest in typical real-world scenarios.

Conclusion

Our proposed algorithm achieves an expected $(1+\epsilon)$-regret of $\tilde{O}(\sqrt{T})$ with a runtime near-linear in the number of samples ($T$). While the runtime remains exponential in $k$ and $d$, this represents a significant step toward practical online clustering. Future work may involve integrating dimensionality reduction or exploring stability conditions under which simpler heuristics like FTL are theoretically optimal.

Summary updated

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 $\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, 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\left(T \mathrm{poly}(\log(T),k,d,1/\epsilon)^{O(kd)}\right)$. 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).
BibTeX
@inproceedings{cohenaddad2021online,
  author = {Vincent Cohen-Addad and Benjamin Guedj and Varun Kanade and Guy Rom},
  title = {{Online k-means Clustering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=BnfEK9ucCbq},
}
Figure