Online Clustering with Nearly Optimal Consistency

The paper gives an algorithm for online $(k,z)$ clustering. The algorithm uses an 'online' coreset and is able to give theoretically best-known consistency bounds for the general $(k,z)$ clustering problem. For an $\alpha$ approximate offline algorithm for clustering, the paper guarantees a $(1 +\epsilon) \alpha^2$ competitive ratio implying that given an optimal offline algorithm, it is theoretically possible to achieve $(1 + \epsilon)$ competitive ratio. Empirical evaluations on 3 datasets and comparison with 2 baselines, one of them being the popular $k$-means++ algorithm show the effectiveness of the algorithm in giving superior consistency.

This paper's considers online (k,z) clustering. Here, z is simply a parameter used as an exponent for the distance function (i.e. z=2 for k-means, and z=1 for k-medians). In this setting, on each subsequent point the learner outputs a set of precisely k points. Algorithms are evaluated with respect to a bicriteria, with 1. their approximation factor being the amount they differ from the optimal clustering over the set of points seen thus far, and 2. their consistency being the total amount of changes they make to their centers.

This paper's contribution is an online algorithm that achieves a $(1+\epsilon)\alpha^2$ approximation factor (where $\alpha$ is the approximation factor of any offline clustering algorithm being taken as input), and $O(\alpha d k poly(\epsilon^{-z}))$ consistency. When $\alpha$ equals $1$, this is the first algorithm to achieve $O(k)$ consistency with a $(1+\epsilon)$ approximation factor.

This paper builds on prior work by using a well-known technique of first maintaining a coreset that approximates the clustering behavior of the dataset, and then applying an offline clustering algorithm to the coreset. However, the key technical challenge is in applying the offline clustering algorithm in a manner that does not change the set of outputted cluster centers by too much. The net result of both of these factors is that because the corset changes less frequently than the dataset, and because the offline clustering algorithm is being cleverly applied, the net amount of center change is small which gives us the linear $O(k)$ consistency.

The key technical innovation of this paper lies within its second step, which proposes an online clustering algorithm (over weighted points) that, under certain conditions achieves $O(m)$ consistency (where $m$ is the number of points). Note that this algorithm will be utilized while substituting $m = O(\log(\Delta n))$ ($\Delta$ is the aspect ratio) and this will achieve the desired results outlined above.

The main idea behind their algorithm is to construct a "robust center sequence," for the online set of points. This sequence essentially picks a sequence of points where each point represents an "appropriate" substitution for an initial point based on exponentially increasing distance scales. Then, from the robust center sequence, they show how to appropriately select $k$ centers, along with how to maintain such a sequence.

The paper studies the online version of the classic k-means clustering problem. Here, points arrive one after another and at every step, the algorithm must decide whether to create a new center or not. The objective they consider is called "consistency", which informally measures the total number of times an algorithms "changes" a cluster center. (At least k changes are required for any online algorithm.) The main result of the paper is an online algorithm for k-means with consistency $O(k polylog(n))$ (times a factor that depends on the aspect ratio of the dataset).

The authors first give an online algorithm that produces a coreset for the points, while having around k * polylog(n) points. They then use the framework of Fichtenberger et al. (2021) to obtain an algorithm that maintains a k means solution. Most of the technical novelty of the paper is in the part of designing an online algorithm for the "bounded input" case.

The paper considers the problem of online $k$-means clustering (and slightly more generally $(k, z)$-clustering. In order to achieve non-trivial results (as is shown to be necessary in prior work), the authors allow the online algorithm to change the centers, but keep track of the recourse cost, called consistency, which is the total number of center changes across the entire online sequence. The present paper shows that an offline algorithm with $\alpha$-optimality can be converted to an online algorithm with $(1 + \epsilon) \alpha^2$ competitive algorithm with consistency bounded by $O(k \mathrm{polylog}(n))$ (this also requires polynomial in $n$ bounded aspect ratio). This makes significant progress over prior work and almost matches the lower bound in the Lattanzi an Vassilvitskii paper which introduced the framework. In terms of techniques, the paper relies on coresets, which is standard in this area, but there are some innovations required to make everything work.

Accept (Poster)