No-substitution k-means Clustering with Adversarial Order
This work is significant for researchers and practitioners dealing with online k-means clustering, particularly when data arrival order cannot be assumed to be random or when data does not fit restrictive aspect ratio assumptions, by providing a method that works under adversarial order.
The paper addresses online no-substitution k-means clustering where input arrives in arbitrary order, a setting where previous methods fail without strong assumptions. The authors introduce a new complexity measure 'd' for datasets and propose a randomized algorithm that achieves an O(k^3)-approximation while using O(d log(n) k log(k)) centers. For data from natural distributions like Gaussian mixtures, this translates to poly(k log(n)) centers.
We investigate $k$-means clustering in the online no-substitution setting when the input arrives in \emph{arbitrary} order. In this setting, points arrive one after another, and the algorithm is required to instantly decide whether to take the current point as a center before observing the next point. Decisions are irrevocable. The goal is to minimize both the number of centers and the $k$-means cost. Previous works in this setting assume that the input's order is random, or that the input's aspect ratio is bounded. It is known that if the order is arbitrary and there is no assumption on the input, then any algorithm must take all points as centers. Moreover, assuming a bounded aspect ratio is too restrictive -- it does not include natural input generated from mixture models. We introduce a new complexity measure that quantifies the difficulty of clustering a dataset arriving in arbitrary order. We design a new random algorithm and prove that if applied on data with complexity $d$, the algorithm takes $O(d\log(n) k\log(k))$ centers and is an $O(k^3)$-approximation. We also prove that if the data is sampled from a ``natural" distribution, such as a mixture of $k$ Gaussians, then the new complexity measure is equal to $O(k^2\log(n))$. This implies that for data generated from those distributions, our new algorithm takes only $\text{poly}(k\log(n))$ centers and is a $\text{poly}(k)$-approximation. In terms of negative results, we prove that the number of centers needed to achieve an $α$-approximation is at least $Ω\left(\frac{d}{k\log(nα)}\right)$.