Online Clustering with Nearly Optimal Consistency
Authors: T-H. Hubert Chan
Shaofeng H.-C. Jiang
Tianyi Wu
Mengshi Zhao
Venue: ICLR 2025 Poster (2025)
Keywords: clustering
online
consistency
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: (1 + eps)-competitive online clustering algorithms with O(k polylog n) consistency

Abstract: We give online algorithms for $k$-Means(more generally, $(k, z)$-Clustering) with nearly optimal consistency (a notion suggested by Lattanzi & Vassilvitskii (2017)). 
Our result turns any $\alpha$-approximate offline algorithm for clustering into an $(1+\epsilon)\alpha^2$-competitive online algorithm for clustering with $O(k \text{poly} \log n)$ consistency. 
This consistency bound is optimal up to $\text{poly} \log(n)$ factors. 
Plugging in the offline algorithm that returns the exact optimal solution, 
we obtain the first
$(1 + \epsilon)$-competitive online algorithm for clustering that achieves a linear in $k$ consistency.
This simultaneously improves several previous results (Lattanzi & Vassilvitskii, 2017; Fichtenberger et al., 2021). 
We validate the performance of our algorithm on real datasets by plugging in the practically efficient $k$-Means++ algorithm. 
Our online algorithm makes $k$-Means++ achieve good consistency with little overhead to the quality of solutions.

Published as a conference paper at ICLR 2025
ONLINE CLUSTERING WITH NEARLY OPTIMAL CON- SISTENCY
T-H. Hubert Chan
Shaofeng H.-C. Jiang
The University of Hong Kong hubert hku. hk
Peking University shaofeng. j jian@ppu edu.cn
Tianyi Wu
Mengshi Zhao
Peking University wuty@stu. pku.edu.ee edu. en
The University of Hong Kong zmsxs connect........ooooooo .ku. hk
ABSTRACT
We give online algorithms for k-MMAAN (more generally, (k. CLUSTERING) with nearly optimal consistency (a notion suggested by Lattanzi & Vassilvitskii (2017)). Our result turms any a-approximate offline algorithm for clustering into (1 + +++e)a--ooo >cmpppttei online algorithm for clustering with poly log n)) con- sistency. This consistency bound optimal up to poly log(n) factors. Plugging in the offline algorithm that returns the exact optimal solution, (1+ (--e--compttiii online algorithm for clustering that achieves a linear con- sistency. This simultaneously improves several previous results (Lattanzi & Vas- silvitskii, 2017; Fichtenberger et al., 2021). We validate the performance of our algorithm on real datasets by plugging in the practically efficient k-MEANS++ algorithm. Our online algorithm makes k-MEANS+ achieve good consistency with little overhead to the quality of solutions.
obtain the first
INTRODUCTION
The well-known k- MEANS clustering algorithm has been employed extensively in machine learning applictions. The input set of points P in I2d and parameter l: 2 1. The goal is to find set of k centers C' C Idd such that the cost function cost((. C) = Exer (dist(x C))² is minimized, where dist(z, C) ;= mingeo dist(z; (z, c) and dist(z, c) == || ell2. k-MEANS is tightly related to k-MEDIAN, and the only difference is that the cost function of M-MEDIAN takes sum of distances without squaring.
We focus online versions of M-MEANS. The online setting captures the practical scenario of evolving datasets and the requirement of making prompt decisions. In typical online setting, data points arrive in an arbitrary order, and the algorithm must decide immediately, without knowing the entire input, whether and where to define new center (and the data points are automatically assigned the nearest center). As usual, the performance an online clustering algorithm is measured by the competitive ratio, which is the ratio between the algorithm's 's K-MEANS cost and the optimal k-MEANS cost (with full information). The central challenge in the setting that the decision must be made without knowing the information of the entire dataset, and the competitive ratio exactly captures this difficulty.
Unfortunately, online clustering is very sensitive to incomplete information, and it has been shown to admit strong lower bounds (L.bberty et al., 2016) so that relaxations must be made allow any finite competitive ratio. One natural relaxation is allow recourse of decisions, and this has been formulated by Lattanzi Vissilvi (2017). Specifically, let C, be the center set after the algo- rithm processes the i-th input point, then the total recourse of the algorithm is Σ, IC \ C.-1l- This quantity is called the consistency of the algorithm (Lattanzi & Vassilvitskii, 2017).
As shown by Lattanzi & Vassilvitskii (2017), there exists O(k2 poly(logg))-coonisse competitive algorithms for k-MEANS and k-MEDIAN. They also show a lower bound that any ((1)-comeeiitive algorithm must be 2(k poly coosssnnitttett. In recent work by Fichten-
O(1)-

---

Published as a conference paper at ICLR 2025
berger et al. (2021), coompettte algorithm with improved consistency O(k poly log(n)) for M-MEDIAN is given. All these results also work for general metric spaces.
Despite the progress, there is still gap in the consistency competitive ratio tradcoff. In particular, it is unclear if k-MEANS also admits ((1) ccompetteeii ratio with O poly (og(n))-connister)) (as in A-MEDIAN (Fichtenberger al., 2021)). Moreover, the lower bound in Lattanzi & Vassilvitskii () does not rule out (1++) competitive ratio (although this might require an exponential running in general). Lastly, existing consistent algorithms are specially designed optimize the ratio and might not be as efficient as practical algorithms such as K-MEANS++ (Arthur & Vassilvitskii, 2007), so it would be useful turn 6-MEANS++, or more generally any offline clustering algorithm, into an online algorithm with good consistency.
1.1 OUR RESULTS
Our main result, stated in Theorem 1.1, systematically addresses these challenges. Our algorithm turns any a-approximate offfine algorithm (a 2 1) into an online algorithm with (1 + e)a² com- petitive ratio, with little overhead in time complexity. Moreover, no matter what offline algorithm used, it always achieves the nearly-optimal O(k poly log consistency. Importantly, this con- sistency bound is nearly optimal up to poly log n factors, as is complemented by a lower bound of Lattanzi Vassilvitskii (2017).
Theorem 1.1 (Informal; see Theorem 3.1). Given an offline a-approximate algorithm for k-MEANS compettiivee algorithm for online
that runs in T(n) time, there exists an (<co)-ccon (1 + e))² k-MEANS, and the running time is (nk + k-. (T(((())))
We notice that the formal statement of this result more generally works for (k, -LUUSESENG (see Definition 2.1, which particularly contains k-MEDIAN), in addition to k-MEANS. Moreover, although we state our results in Euclidean IR which is typical case for clustering, our results also apply to general metrics. Our bound actually has a dependency on poly ploy(log A) factor, where A is the aspect ratio of the dataset. This is necessary (for any constant ratio) as mentioned Fichtenberger et al. (2021), and that one can typically assume A = poly(n) so that poly(log A) translates to poly(log n)).
As an important corollary, if one plugs in the brute-force exact offline algorithm (which may run in exponential time), Theorem 1.1 leads to a (1 + cooppetiiiee O(k poly log -)-consistent algorithm for k-MEANS (and for general (k:, =)-CSTETER, This is the first (1 + e)cometttiiive algorithm for any clustering problem with nontrivial consistency, while simultaneously achieving a nearly optimal consistency bound, hence fundamentally improves all relevant previous works (Lattanzi & Vassilvitskii, 2017; Fichtenberger et al., 2021) in ratio and/or consistency. Note that this + e ratio is nontrivial even allowing infinite computational power.
Experiments. While the mentioned 1 + c bound is powerful, it is mostly of theoretical value because of the exponential running time. Thanks to the generality of Theorem 1.1, we are able to plug in widely-used efficient algorithm, K-MEANS++ (Arthur & Vassilvitskii, 2007), to obtain an efficient consistent online clustering algorithm. We validate (in Section 5) the performance for this new consistent k- 6-MEANS++ on 3 real datasets, and compare with the vanilla 4-MEANS+ as well as a previous algorithm (Lattanzi & Vassilvitskii, 2017), as baselines. Our experiments show that with cost similar to A-MEANS++ and the algorithm in Lattanzi & Vassilvitskii (2017), our algorithm achieves much lower consistency.
1.2 TECHNICAL OVERVIEW
At a high level, our algorithm starts with maintaining a consistent e-coreset. Roughly speaking, a coreset (Har-Peled & Mazumdar, 2004) is small proxy of the dataset, such that for every center set, the cost on the coreset is within + e to that of the original dataset. Our coreset is of size (k),, and that the consistency is bounded by Ō.(k). We build such a coresct by a modified ring sampling technique (Chen, 2009; Cohen-Addad et al., 2021), and very similar construction was also introduced in Woodruff et al. (2023). We remark that similar steps are also employed in various
'O2 hides poly(e log(n)) factor.
2

---

Published as a conference paper at ICLR 2025
previous works (Lattanzi & Vassilvitskii,, 2017; Fichtenberger al., 2021), but they do not give e-coresets and hence it only leads to -apppxppxxiatttonn
With such a small e-coreset, are able to reduce the problem to the case with size-bounded input. In particular, we can work with inputs with length (k), and it suffices to have O2 (k) total recourse. This is simpler than the original problem, since it only requires amortized (1) recourse, instead of o(1).
Our algorithm for this size- bounded input case is based the framework of Fichtenberger et al. (2021), but our implementation differs because the original framework only works for M-MEDIAN and achieves only an (1)) approximation ratio. Roughly speaking, the algorithm processes input points in batches (which we also call phases in our proof), using the following steps for each batch. Suppose the algorithm starts with a set of exactly k centers Co as the current solution. Before processing any input point in the batch, it deletes the maximum number of centers from Co such that the cost of the resultant center set still good enough; denoting the number of deleted centers as l and the new center set as C. Then for every input point p. the algorithm directly include to the current center set C, provided that |C| is still less than k. When |C] reaches k again, the algorithm "forgets" C' and operates Co to conclude the batch and build the initial solution for the next batch. Specifically, it chooses Ó,()) (f) centers in Co. and then swaps them with the same number of centers in the candidate center set.
Clearly, this procedure has amortized recourse (1). so the consistency follows immediately. How- ever, obtaining the claimed ratio is nontrivial, and particularly requires very careful choice of discuss how the deletion and swap is done in more detail. We focus
swapping centers. Next, on the case where we have the access to the optimal k-MEANS solutions, and the goal is to achieve (1 + comppttiiee We discuss at the end how our algorithm works with general a-approximate (offline) algorithm.
Procedure for deletion and swap. For the deletion step, the E is defined as the maximum number of centers that can be removed from Co such that the resultant center set is (1 + +(()))-apprpoonn apprrxxaaa The procedure for swap is more complicated and depends on the structure of "well separated pairs", which was also used in Fichtenberger et al. (2021) but only defined for constant approximation. Given two center sets U and V. we define (u, v) as e-well separated pair for some E U and V E V. if dist(u, u,, v) is e times between the nearest neighbors in their respective center sets, namely, dist(e, V \ {u}) and dist(u, U {u)). In our swapping procedure, we let U == Co and V be the optimal solution at the end of the phase (which is the time step when the swapping happens), and identify the points in Co that do not belong to a well separated pair.
Now, recall that in our algorithm outline say the number of swapped points needs be Ó.) in order to bound the consistency. To show this, we need our first key lemma (Lemma C.13): given a point set P and two center sets U' and V, suppose U and V form & e-well separated pairs, then Q(k t) centers can be removed from U to form U", such that cost U') S (os U) + (cost((, U) + cost(P, V)). Applying this key lemma with U == Co and V being the optimal solution to the point set at the end of the batch, it implies that 2 (k: - 1) (since we can assume at any time step the optimal solution is within (1 + c) factor to each other). Observe that h - t is precisely the number of swaps, and this is at most Óe)..
We remark that Fichtenberger et al. (2021) proves a weaker version of this lemma whose error guarantee is only O(cost(P, U) + cost(P, V)). whereas ours is times of this. This is inherently caused by the linear programming method used in their proof. In particular, due to the integrality gap of linear programming which is a constant, this method cannot achieve a + c ratio like ours. Furthermore, their linear programming analysis seems to only apply to M-MEDIAN, whereas our general technique is suitable for general (k, 2)- -LLUSEEEEI (in particular k-MEANS). Our proof cannot use linear programming, and it is inspired by the analysis of local search algorithms for the clustering problem (Cohen-Adiee Addad et al., 2016; Friggstad al., 2019).
Bounding the cost of swaps. We next describe how we bound the cost of the swap step. We use similar strategy in Fichtenberger al. (2021), where the key idea is to use "robust centers". Roughly speaking, a "robust center" is a center such that is approximately locally optimal - any other center that is close enough to it cannot c significantly improve the approximation ratio. It enables
3

---

Published as a conference paper at ICLR 2025
our algorithm to build cluster centers that remain effective even data evolves over time, without requiring knowledge of future changes. This is useful in the analysis, since in a near-optimal solution with robust centers, even moving the centers bit does not improve the cost (significantly), which may not otherwise hold in an arbitrary approximate solution. Thus, we need to add extra steps of making centers robust in various places in the algorithm. While the robust centers possess good properties, making centers robust may introduce additional error. Nonetheless, we manage to bound the cost of the swap step in our second key lemma (Lemma C.2), based on which we inductively show if the centers are robust at the start of a batch and that the center is (1 + O(c)) O(c))-approximate then after the batch the (new) centers are still robust and has the same ratio. Again, similar lemmas and notions of robust centers were first introduced in Fichtenberger et al. (2021), but they only considered the (apaprxxxiiitooon version. Our technical contribution to modify the definition of robust centers so that it is (1 + -appproxiamte, as well as to strengthen the inductive guarantee to be (1 + e) in our key lemma. The analysis uses several new steps and observations compared with that in Fichtenberger et al. (2021).
General o-approximation. Now we show how the above generalizes to work with any given a- approximate offline algorithm. Recall that Co is the center set at the beginning of batch. In the deletion step, instead of removing maximal number of centers such that the resultant center still + ( -pproxxatt solution, the algorithm calls the a-approximate offline algorithm with candidate center set as Co and k- = l' for every 1 S L < k. Then it picks the maximum E' such that the cost is less than (1 + O(e))a cost(P', Co), where Po the point set at the beginning of batch. Similarly, in the swap step, we replace the optimal solution V for the point set at the end of the batch with an a-approximate one, and then perform the swaps before (i.e., swapping out from Co points that do not belong to well separated pair between Co and V). We also adopted the two key lemmas to work with these new steps.
1.3 RELATED WORK
Data points in the online setting that we consider is insertion-only. Recent works also study the more general dynamic setting for consistent online clustering, such that data points can also be deleted. Cohen-Addad et al. (2019) gives O(1) compettiieee poly log(m))-cnsisttet algorithm for dynamic facility location with uniform opening cost in general metrics, and Bhattacharya et al. (2022) gives a similar bound for the more general case of non-uniform opening cost. Lacki et al. (2024) provides an (n) (oonsissstt algorithm that achieves O(1) ratio for dynamic k- E-CENTER in general metrics, and they also show (2()) consistency lower bound (for any finite ratio). Recently, Bhattacharya al. (2024) provided uniform framework for consistent (k:, 2))CLU)TERRNG achieving an O(1/c) ratio Ölk*)) consistency.
While much research focuses on optimizing resource efficiency, there are other studies aiming to minimize the number of centers in online (ks, -J-CLLUSTRIING without recourse while retaining a constant approximation ratio. For example, studies have explored scenarios such as (i) using an estimate of the optimal clustering cost as an input parameter, (ii) knowing the total number of points n in advance, or (iii) processing points in random order Moshkovitz (2021); Bhaskara & Ruwanpathirana (2020); Bhattacharjee & Moshkovitz (2021); Hess et al. (2021). These studies, along with many online clustering algorithms, do not allow for recourse and require opening more than Q2 ((klog())) log(n)) centers. leading to bi-criteria approximation.
2 PRELIMINARIES
Although we focus on IRd, we assume the dataset is a subset of [ for some integer A, which is supposed be the aspect ratio. This is without loss of generality since one can always rescale the dataset provided the knowledge of A. Let C C Rd be the candidate center set. Given a point g E R and a radius r E R4. a ball is defined as ball(q. r) {p E Rd dist(p, q) S r]. Moreover, a ball with respect to a point set P is defined as ball (g. r) == ball(q, r) P.
Definition 2.1 ((k, -LCCLSSTTRI Given P C Rdd for any center C C with |C| S k, define the cost for (ks, 3)-CLLSSTRRIGG as
cost, cost,(P, (P,C)
Σ (di C xEP
4

---

Published as a conference paper at ICLR 2025
We define OPT(P) the optimal cost of (k, 2) CLUSTERING. Specifically,
(PT; min cost.(P.C). cgc.jelsk
Definition 2.2 (Online 2k CLUUSTERIN)) In online (k, 2)- -CUUSTERING, the imput datasct P presented as sequence (PI....,Pr) and upon the arrival of p: (for every E [πt),, the online algorithm must output a center set C₁ S C such that |C,| S k. We say an online algorithm is p-competitive if c (P, p. (P.,(P.) for every i, where P. is the first points in P. Definition 2.3 (Consistency). We say a sequence of center sets CI...., Cn r-consistent, Dia(n C \ C--1l= & I' (Co = 0). An online algorithm is I'--------- I'-consistent if its output center sets CI..... C₁ is I-consistent.
Weighted point set. A weighted point set is an (ordinary) point set equipped with positive weight function. Specifically, we identify weighted point by vector P E R[A]" with support P. Then for P, the weight of point p P denoted as P(p). and for subset S S P. define P(S) := Epes P(p). We also use |P| to represent P(P) as the total weight of the point set. We treat unweighted point sets as weighted point sets with unit weight.
The relation P. S P2 is defined as P S P2 with respect to coordinate- wise comparison. The operation Pl U P2 is the coordinate-wise maximum of the two vectors, and P1 Pg is the coordinate-wise minimum. The set subtraction Pi \ P2 sets every negative value in P, P to zero. The function for CLLSSCCLIT c (P,C) = Epep (dist(p, O))². The ball with respect to a weighted point set gen- eralized as (lg = tō P dist(p, q) r).
weighted point set is generalized as
Definition 2.4. For 0 < e < and weighted set P,, a weighted set Š such that S S P is an c-coreset for (k, CLUSSTEERN
AC CCC (1 cost, (P, C) cost c C) (1 c) cost, (P,C)
Definition 2.5 (Cluster of a point). Let P be weighted point set, C C C be center set and E C be center. The cluster of e with respect to P is defined (where ties are broken arbitrarily and consistently)
P(C,c] == (ō P dist(p, C) = dist(p, c)}.
Lemma 2.6 (Cohen-Addad et al. (2021)). Let a, b, be any points in [A]d, be any positive stant. Then for any > 0,
dist(a, 6)t s (1 + e) dist(a, c) (iss))-ddss( + (1te)
2-1
dist(b, c)²,
22 1 =-1 (2
[dsttaa, c)² dist(b, c) dist
das b)2.
3 FRAMEWORK AND PROOF OF MAIN THEOREM
In this section, we present the high-level framework and explain how it proves Theorem 3.1 which our main theorem. All results stated in this section are without the actual dependence in z, since the most interesting case is E (1,2) anyway. However, we do try to figure out the detailed dependence in the proof (Section 4).
Theorem 3.1. Suppose for some a 2 1 there is an a-approximate (randomized) offline algorithm for (k, 2) J--C.USTTRRIG that runs in T(n) time. Then there exists algorithm for online (k, z)- CLUSTERING such that for every n-point dataset in [A] (A 2 is integer), 0) < 1 and integers k, 2 (1 + =) comppetiteee and O(adk poly(E -consist))nonsisseeen with probability poly(ny' provided that all invocations of the offline algorithm succeed. The algorithm runs in Okkn log(nA) )++ + 20oly(e"") dk3 (e log(nA)) (dk (o log(nA)))) time.
Notice that the factor d may be turned into Ollog n) by using dimension reduction (Makarychev et al., 2019).
5

---

Published as a conference paper at ICLR 2025
Our proof idea consists of two steps. First, we reduce the number of points be considered by leveraging a coreset structure, which contains significantly fewer points than the original set, with each point assigned a positive weight. This coreset structure satisfies two key properties: it is always a coreset for any prefix of the stream, and points sampled into the data structure are never deleted from the incremental coreset. We note that with slight modifications, the so-called "online coreset" proposed in Woodruff' et al. (2023) meets our requirements. Although their definition of an online coreset seems require the algorithm to access the entire dataset, their main procedure can indeed be executed in an online/incremental manner. We summarize our coreset guarantee in the following lemma.
Lemma 3.2 (Consistent coreset (Woodruff et al., 2023)). There exists an algorithm that given as imput 0 < integers k, 2 Z 1 and an online point sequence (Pt....,Pal in [A] outputs weighted point set sequence Di,..., _D, such that
1. There is m Ollog(nA) numbers 61 S i S m-1, OPT. (1)41-1) S 22PPT,(De) and for every e, S S c 10 1, D, S Dj+1.
S 6m
such that for every
2. With probability 1 poly(n)* for all 1 S i n, D; is an c-coreset for P. := {pi....: Pi) and
|ō:| O(dk poly(e-+oog(nA))) log(n
The algorithm runs Ok (o)(n))) time.
In the second step, we solve the consistent (k, C)LUSTERRIN with weighted points as the input. Specifically, algorithm (in Lemma 3.3) achieves Ô(1) amortized consistency. The proof of this lemma is our main technical contribution and is postponed to Section
Lemma 3.3 (Algorithm for bounded input). Suppose for some 2 there is approximate (randomized) offline algorithm for (k: -LLUSTRRRI that runs in T(n) time. Then there exists algorithm for online (k:, CI.USTTRRIN such that for every weighted point set Po and weighted m-point sequence "mi,...,'') in [A]d, provided that O U (Fr.....Phh & 2OPT, competitive and O(am poly(c- poly(c=log((A)) (og((A)))-onmsl dkm? (lmm22oly(c")) lo) time.
-OPT=(Pr (Po). and all invocations of the offline algorithm succeed, it is (1 + c)a²- The algorithm runs in Omm +
Finally, we combine these two steps to form Algorithm 1. The bound on cost and consistency follows from the composition of Lemma 3.2 and Lemma 3.3. The formal proof Theorem 3.1 is presented in Section A.
Algorithm 1: Consistent online algorithm for (k, 2) -LLUSTEEIIN
denote the algorithms Lemma 3.2 and Lemma 3.3 as Acoreset Abound respectively
for i 1, ..,.. n, suppose x; is inserted do
feed r; to Acoreset and let D; be the coreset returned by Acoreset
if then
L C. - U.-1U /* let Co - 0
else
if Di-1 C D, then
feed D, D, Abound
else
start hound over and feed it D
let C2 be the output of Abound
return C1....,Co
4 ALGORITHMS FOR BOUNDED INPUT: PROOF OF LEMMA 3.3
In this section, we give the algorithm for inputs of bounded length, denoting the length as m. Our algorithm is (1 competttee with consistency proportional to m, which proves Lemma 3.3.

---

Published as a conference paper at ICLR 2025
We start with several definitions used in our algorithm in Section 4.1. This includes key notion called "robust sequence" in Section 4.1, where a similar version has been proposed in Fichtenberger et al. (2021). Moreover, a procedure for identifying robust sequence (in Algorithm 3) is crucially used our algorithm. We state our main algorithm in Section 4.2. The analysis of the algorithm can be found in Section C, and combining these immediately conclude Lemma 3.3.
4.1 ROBUST (CENTER) SEQUENCES
In this section (and in Section B), we give the definition of robust sequence in Definition 4.1 along with many other related properties and definitions. All these essentially follow similar ones in Ficht- enberger et al. (2021), whereas the key difference is that ours works for (1 + appppooximttioon and general (A; C)LUSEERRN Because of this, we need re-prove properties so that they comply with our stronger definition.
Definition 4.1 (Robust (center) sequence). Let t 2 and P be a weighted point set. A robust center sequence (co, C1 ...,Cr Ce) can be constructed by the following procedure. Start with any center op. For from to I, we pick Ci-1 as follows.
C-11 - C, when at least one of the following holds: 2²
+)),, 2 g=2z (1+ ;)';or, (i) avgcost, (balll,,,, (1
(ii) avgcost, (ball (1 + c)) I [1 (1++) mim (balls (1 c)+),
Otherwise, C--1 is any center e E C such that:
avgcost_ (baltttbballlaaaaa (1+ +c))),)) S (1 + mincre (balls p(c, (1 ))
Given a sequence (Cn, 61, 02,02, ,,,,..,, ..) and S to S t, the lo-prefix of the sequence defined as the prefix (co, ,,,...,,tpp Given a center sequence with length t + 1, it is called fo-prefix robust if to S and its fo-prefix is robust. is immediate that (i) any prefix of a robust center sequence is automatically robust and (ii) given number to and sequence (co, .I,...,.y Ct), the sequence is not to-prefix robust if either to > or the prefix (co, Cl. C.,.) is not robust.
The concept of a robust center sequence is pivotal in ensuring stability and adaptability in clustering, particularly when dealing with dynamic evolving data. Intuitively, this sequence starts from some arbitrary center c, then identifies for every distance scale (up to some threshold) good center to replace From this point, the definition can be viewed as backward induction algorithm with input t and an initial center cz. The output is the sequence (co, cI,...,cy ce) computed by the definition.
From a high-level point, robust center sequence embodies local optimality across multiple scales, ensuring each center is resilient to minor cluster perturbations. This backward construction ensures that cy is robust the finest scale, having been refined through progressively larger neighborhoods. This definition enforces that each center is either inherently stable or replaced by a locally near- optimal alternative, balancing current performance with adaptability to future changes. By iterating over exponentially growing radii, the sequence accounts for uncertainty in cluster scales, as clusters may develop, merge, or split over time.
A similar version of the following definition is also originally proposed in Fichtenberger et al. (2021), and we generalize it to achieve (1 + -ppappooxintiion as well as to handle general (k, z)- CLUSTERING.
Definition 4.2 (Bounded robust). A witness of center C is defined as finite sequence of points in C that starts at e. Let C C C be a center set. A witness mapping wite maps each e E C to witness (c) Given a weighted point set P, (C, witc) is called bounded robust w.r.t. 15 if for every c E C. (i) is to (c)-prixix robust with respect to P., where tc(c) denotes the smallest integer I' such that (1 + f > dist(c, C \ (ct)/10. If CC {c} = 0, we define dist(c, 0) = vda (which is the largest possible distance of the data).
We define an algorithm MAKEROBUST (Algorithm 3) make a center set with a witness mapping bounded robust, by iteratively calling subroutine in Algorithm 2. In Algorithm 2, if wit is center point equipped with
not (c)-prrxx robust, then ROBUSTIFY(P). C, generates witness that is (c(c--rreixx robust. Again, these two procedures are also based on similar ones in Fichtenberger al. (2021) but our version is generalized to work for (1 + -)appoooxiinaoon.

---

Published as a conference paper at ICLR 2025
Algorithm 2: Robustify, on weighted point set P. center set C' and a center point E C
let t be the smallest integer such that (1 + e) 2 dist(c, C' {cH)/5 compute a robust sequence (Cp, C1,...,) such that Ct = c by Definition 4.1
f- (Co, C1)
return (Co, v)
Algorithm 3: MakeRobust, on weighted point set P and center set C' with witness mapping wite
while There is center c C' such that (i) not (c))f-rrexxx robust with respect to P do Arbitrarily pick a center e such that the while condition holds
(Co, 2) + ROBUSTIFY(P, C. C C fcJ (cot, wit +
return (C, witc)
4.2 CONSISTENT CLUSTERING ALGORITHM
Now ready introduce the consistent algorithm. The algorithm runs in phases. The input of each phase weighted point set Po and a center set with witness mapping (Uo, wite.). The algorithm guarantees that (Uo, witu,) is bounded robust (see Definition 4.2) with respect to Po and Uo is a (1 + a-aprroiptt solution for Po- Our analysis mostly focuses on an (arbitrarily) fixed phase. Let P. be the point set after the i-th insertion of the phase. The algorithm executes the following steps in each phase.
1. Deleting centers. The algorithm enumerates / [k] and runs the a-approximate algorithm for (k- (x-E)-a -)ccuutruriiin with point set Po and candidate center set Ug. Then picks the maximum to such that the cost output by the a-approximate algorithm is less than (1 + 12c) a (P%, Uo). Let Ü be the center set with & fu centers that the a-approximate algorithm outputs. Handling insertions. As long as the center set U consists of less than & points, if a point is inserted a position with center (in U), the algorithm includes the new point in U. Otherwise, does nothing. The center set is the reported center set of the online algorithm.
Swapping centers. Suppose after some 2 to insertions from the start the phase, the size of the center set U achieves k. Now, for the next input point (which is the & + 1-th insertion from the start), the algorithm starts with changing O ( (22 ( centers in Uo to produce (1 + 5e)a- approximate solution W for Pe+1, whose detail is given immediately after the description of the algorithm. Let witw (c) (c, c) for every e e W Ug. (This W is not the output of the é + 1-th round yet.)
4. Robustifying centers. Let (U2+1, witven1) == MAKEROBUST(PeHI (W, witw)) (defined in Algorithm 3) and it is both the output of the + 1-th insertion and the input for the next phase. Define the length of the phase as f+ 1.
The detailed implementation step 3 requires the following notion of e-well separated pairs, which identifies close center pairs from two different center sets. In general, this is a standard notion in geometric approximation algorithms (see Har-Peled (201 1)), and similar notions have been used in local search algorithms for clustering Friggstad al. (2019). Fichtenberger al. (2021) also em- ploys this notion, but only for (I1-approxiiaation whereas ours can work for ---r)-aaproximmttion.
Definition 4.3 (Well separated pairs). Suppose U and V are points sets, pair (u, v) E V is a e-well separated pair if both of the following hold:
dist(u, v) & e dist(U \ (u),u) u), dist(u, v) s dist(V \ (v).
(1)
Implementation details of step 3. We formalize the step as follows. At the (6 + 1)-st input point from the start of the phase, the algorithm runs the offline a-approximate algorithm for the
8

---

Published as a conference paper at ICLR 2025
consistency for SKIN, km:10
ronsistency for SHUTTLE km10
53020
rarve
talve
1927
I937
1917
42030
curafathlll
sursil thiul
cura-a trful
ourshou is66
sur-hou st:
30030
50000
20020
3002
10030
2502
20000
50
100
150
209
250
20
30
60
100 200
300
500
600
number marrtions Ix10))
limmentiona (x110%)
numberal reartinn (4309
Figure 1: The consistency curve over the insertions of points, for all datasets and l = 10.
cost skin, k=10
cost for shuttle, k=10
cost for covertype, k=10
1.75
nalue
naive
IV17
LV17
WV17
fabifu bursheunttii:
cared ad vuul
carsdetndul
aursheuuissic
3.0
oursheuristic
1.0
0.75
0.5
300
Figure 2: The cost curve over the insertions points, for all datasets and 10. We plot the curve after applying a moving average with a window size equal to 1% of the dataset size.
current point set, denote the approximate solution as V. Let a be some integer such that for every ب welll separated pair, and P [V, Ui] C Po. Then the algorithm swaps centers U. Ug into Un forming a new center W W Un and witw = wity, (c) for others. We would relate this with in Lemma C.8, and would be useful for bounding the consistency.
e [s]. (u, 1.) forms a 2005
{up, Us Us+1s.... Jg Let
witw (c) = (c) for every
This finishes the description of our main algorithm. To finish the proof of Lemma 3.3, it remains to show that the algorithm has the claimed time complexity, competitive ratio and consistency. We prove these in Lemmas C. C.3 and C.6, to be presented in Section C.
5 EXPERIMENTS
In this section, present experimental results evaluating the performance of our algorithms. We provide two implementations: one that faithfully implements Algorithm 1 and heuristic variant (implementation details of which are described shortly). We evaluate both the computational cost and consistency of our two implementations against two baseline approaches using three real-world datasets.
Datasets. Our experiment is conducted on the SKIN (Bhatt & Dhall, 2009), SHUTTLE (Catlett), and COVERTYPE (Blackard, 1998) datasets from the publicly available UCI repository, which were also used in the experiments of previous works such as (Lattanzi & Vassilvitskii, 2017). The SKIN dataset consists of 245,057 points with features, where each point represents an RGB pixel. The SHUTTLE dataset contains 58,000 points with 7 features. The COVERTYPE dataset consists of 581,012 points with 54 features.
Implementation details Now we detail our two implementations of the algorithm, both of which share a common online coresct construction phase followed by different downstream clustering approaches.
Common Component: Online Coreset Construction. Both implementations begin with the con- struction of online coreset. For this step, rather than using the worst-case coreset size bound specified in Lemma 3.2, we directly set a target size. Our experiments employ coreset sizes rang- ing from 1000 to 2000 elements, calibrated according to the dataset size. As our subsequent

---

Published as a conference paper at ICLR 2025
experimental results demonstrate, these sizes provide sufficient accuracy while maintaining com- putational efficiency.
Implementation 1: Consistent k-MEANS++. Our first implementation faithfully executes the downstream component of Algorithm 1. This algorithm incorporates a subroutine that imple- ments consistent clustering approach for bounded input, which requires offline clustering algorithm. In our experiments, we integrate k-MEANS++ (Arthur & Vassilvitskii, 2007) into this framework. This implementation performs the complete robustify-delete-swap process spec- ified in the theoretical algorithm. We refer to this implementation as "ours-faithful" throughout our experimental evaluation.
Implementation 2: Heuristic Single-Swap Approach. Our second implementation employs a sim- plified heuristic for the downstream component while using the same coreset construction algo- rithm Implementation 1. This heuristic employs a simple single-swap algorithm that operates as follows: whenever new point added to the coreset, the algorithm evaluates whether re- placing any current center point with this new point would reduce the clustering cost. If such cost-reducing swaps exist, the algorithm executes only the single swap that yields the greatest im- provement. The primary advantage of the single swap approach is its small consistency and fast running time. Specifically, given a sequence (æI,..., Im as the bounded-size input, the single swap algorithm has consistency at most m and achieves O(km) running time. We refer this heuristic implementation as "ours- bourshheuristic in our experiments.
Baselines. We compare our two implementations with two baseline algorithms. Note that both of our two implementations are combining the consistent coreset (Lemma 3.2) and a downstream consistent algorithm for bounded input (Lemma 3.3 and single swap algorithm). Hence, a natural naive baseline is directly running k-MEANS++ on the consistent coreset instead of running any ad- ditional algorithm. Specifically, whenever the consistent coresct updates, the algorithm computes a new center set, and we note that this algorithm is Ō(k²) -consssttt in the worst case. Another base- line algorithm is the consistent k-MEANS algorithm proposed in Lattanzi & Vassilvitskii (2017)², which is the state-of-the-ee for consistent k-MEANS before our work. This algorithm constant competitive and O(k² (n))))))onnsstentt These two baselines are called "naive" and "LV17", respectively.
Experiment results. We depict the consistency and cost curves in Figures and 2 for k: 10, comparing the performance of the algorithms "naive", "LV17", "ours- faithfla,, and "ours-hcuristic", described carlier. Interestingly, the heuristic algorithm "ours-heuristie" outperforms all other al- gorithms in both cost and consistency, particularly hundreds times better in consistency. The strong performance of our heuristic may be attributed to the characteristic of the datasets used in our eval- uation. However, it is important to note that our heuristic approach lacks worst-case approximation guarantees, it may perform poorly on more complex datasets, for example, datasets with over- lapping groups, significant outliers, or highly imbalanced cluster sizes sizes-would likely challenge our heuristic approach more severely.
For algorithm "ours-faithful"" from Figure 1, it achieves much better consistency compared to base- lines, with times better to naive and roughly times better than Lattanzi Vassilvitskii (2017). Moreover, achieving such a better consistency bound does not incur must overhead to the cost, as can be seen from Figure
Finally, we observe that the cost has some sudden fluctuations in Figure 2. This is mainly caused by the consistent coreset, on which baselines and our algorithm are based, since the coreset needs to recompute from scratch for (ppoly(log n:) times, and each recomputation introduces a big difference in cost. In addition, algorithm pour-ffithhul" further uses the subroutine in Lemma 3.3, which introduces another source of re-computation during phase transition (and hence one can an even bigger "spike" in this algorithm). Luckily, these fluctuations are not significant and are averaged out the entire
Thee algorithm in Lattanzi & Vassilvitskii (2017) is also generic one like ours, and we plug in k- MEANS+ we do for our algorithm.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
Shaofeng H.-C. Jiang was supported in part by national key R&D program of China No. YFA 1000900 and startup fund from Peking University. T-H. Hubert Chan was partially sup- ported by the Hong Kong RGC grant 17203122.
REFERENCES
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein (eds.), Proceedings of the Eighteenth Anmual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pp. 1027-1035. SIAM, 2007. URL http:/ /dl acm. www.coooo.......e...ooooee.e.ooo wttg/iittttiooooooo///ooo//o cmm? 1283383 1283494.
Aditya Bhaskara and Aravinda Kanchana Ruwanpathirana, Robust algorithms for online k-means clustering. In Aryeh Kontorovich and Gergely Neu (eds.). Algorithmic Learning Theory, ALT 2020, 8-11 February 2020, San Diego CA, USA, volume 117 of Proceedings of Machine Learning Research, pp. 148-173. PMLR, 2020. URL pttt:://proceedingg mlr, press/v117/ bhaskara20a. html.
Rajen Bhatt and Abhinav Dhall. Skin Segmentation. UCI Machine Learning Repository, 2009. DOI: http://doi.rr/11022443///33
Robi Bhattacharjee and Michal Moshkovitz. No-substitution k-means clustering with adversarial order. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), Algorithmic Learning The- ory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pp. 345-366. PMLR, 2021. URLittp::/proceedinn .mlr.press/ v132 http//haatthhaaaaaee jee2la 2a html.
Sayan Bhattacharya, Silvio Lattanzi, and Nikos Parotsidis. Efficient and stable fully dynamic facil- ity location. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 De- cember 9, 2022, 2022. URL http: /ttp:///aappeeeee nips ee / laapp__affafeeeee files pttpeesspppp/200/0 2002// ot
html.
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering with fast update time and small recourse. In 65th IEEE Annual Sym- posium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27- 30, 2024, pp. 217.227. IEEE, 2024. doi: (0L1099FFCS0112222224000000 //doi org/ 10. 21109/0C66125555551101111 2024. 00023.
URL https:
Jock Blackard.
Covertype.
UCI Machine
Learning
Repository, 1998.
DOI:
Jason Catlett. https://0o.orr/1044444////333
Statlog (Shuttle).
UCI
Machine
Learning
Repository.
DOI:
Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923-941) 2009. doi: 10.1 10/173777706990077 URL
https://doi. org/ 10. 1111111100000 1137/070699007.
Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metries. In Irit Dinur (ed.), IEEE
57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 353-364. IEEE Computer Society, 2016. doi: 10. F..1109/FCSS.001.
URL https: doi. org/ 10 1 1 wwc.s.2216..
Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in

---

Published as a conference paper at ICLR 2025
Neural Information Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pp. 3250-3260, 2019. URL /tttpss//proceeddngg.eeeeee httpp//......aee//////aaaaa #face8385abbe 2
html.
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams (eds.), STOC '21: 53rd An- nual ACM SIGACT Symposium on Theory of Computing. Virtual Event, Italy, June 21-25, 2021, pp. 169-182. ACM, 2021. doi: 10. 10.11457340032533451022 URL https: 1145/340633 3451022.
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Consistent k- clustering for general metries. In Dániel Marx (ed.), Proceedings of the 2021 ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pp. SIAM, 2021. doi: 10.1137/1 711137/.97811111176665.118 URL https: / /oii .rg/
10.1137/1. 1...1.998111 978161197645..
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields PTAS for k-means in doubling metrics. SIAM J. Comput., 48(2):452 480, 2019. doi: 10.1137/17M1 127181.
URL https:tpp/// wtt.:i...ggg..goo// wtt.oo/g//...../....... 11..11117/111121111111 127188
S. Har-Peled. Geometric Approximation Algoritiuns. Mathematical surveys and monographs. Amer- ican Mathematical Society, 2011. ISBN 9780821849118 URL ttttps://bool google.
com/booken hww.ssiddydyyyyAA...A..
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In László Babai (ed.), Proceedings of the 36th Annual ACM Symposium Theory of Computing, Chicago, I1, USA, June 13,16, 2004, pp. 291 291-300. ACM, 2004. doi: 10.1145/10073352200074444 URL
https: / /ttp///o../a htt//ii.oggg//// org/10ggg/00 . 11..::..111111111 011.5/511035..211 10074400...
Tom Hess, Michal Moshkovitz, and Sivan Sabato. constant approximation algorithm for se- quential random-order no-substitution k-median clustering. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang and Jennifer Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems 34: Annual Conference
Neural In- formation Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp- 3298-3308 2021. URL https: http://ppoceeeinseee/ee/e https::/pproroeedii 1aa057313c2 htt.:///.eBBaaaaaaccco0000e11... 6 atssstttttttttbaaattttt.....a...
new.eeedddnn...nnn.....e........ newrips. htt..eriss...ppppeeee/////..
Abstract. .tml.
Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, and Václav Rozhon. Fully dynamic consistent k-center clustering. In David P. Woodruff (ed.), Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7- 10, 2024, pp. 1463-3484, SIAM, 2024. doi: 10.1137/1.97 181719999911111999211111 URL https: //doi. /rg/ 10. 1137/11 9w1.997881199911 124.
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In Doina Precup and Yee Whye Tch (eds.), Proceedings of the 34th International Conference on Machine Learning. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Re- search, pp. 1975-1984. PMLR, 2017. URL httt::/pprcceee: ngs. ml prr.s/s/s// lattanzi 7 html.
Edo Liberty, Ram Sriharsha, and Maxim Sviridenko. An algorithm for online k-means clustering, In Michael T. Goodrich and Michael Mitzenmacher (eds.), Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January URL httpp:://at /doi.
10, 2016, pp. 81-89. SIAM, 2016. doi: 10. 0tg/10.1137/11 000137/1..77.11 9781611974317.71
Konstantin Makarychev, Yury Makarychev, and llya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Moses Charikar and Edith Cohen (eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Com- puting, STOC 2019, Phoenix, AZ, USA. June 23-26, 2019, pp. 1027-1038, ACM, 2019. doi: 10.1145/3313276.333333 URL https: http://ddo.ooooo..o./o //tp://.............13////3333.0
12

---

Published as a conference paper at ICLR 2025
Michal Moshkovitz. Unexpected effects of online no-substitution k-means clustering. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), Algorithmic Learning Theory. 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Re- search, pp. 892-930. PMLR, 2021. URL http:/ pprocerooeeeeeeeeeoooooooc ngs.mlr. wtw.m/.......//vl......mm. prwss/vi3222 moshkovitz21a a.mmmml........... html.
David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k-clustering in the sliding window model. In Alice Oh. Tristan Naumann, Amir Globerson, Kate Neural Informa- Neural Information Processing
Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances
tion Processing Systems 36: Annual Conference Systems 2023, NeurIPS 2023, New Orleans, LA, USA. December 10 16, 2023, 2023. URL http:/ http://papers.r. nips. ctcpppee.pppperraeeeeeepp fillsffillsleeeeeeeeeeeee /ttlee/paper/2223//aaat 4 htt.://00.......aaaaaaoaa---aaa.
html.
13

---

Published as a conference paper at ICLR 2025
Appendices
A PROOF OF THEOREM 3.1
Theorem 3.1. Suppose for some a 2 1 there is an a-approximate (randomized) offline algorithm for (k, J-CLUSTERING that runs in T(n) time. Then there exists an algorithm for online (k, 2)- CLUSTERING such that for every n-point dataset in [A] (A 2 1 is integer). 0 E < 1 and integers with probability
k 2 2 I, (1 + c))=2-coppe -competitive and Ocodkk poly(e - (og((n)))--cossstee)) 1 poly(n)' provided that all invocations of the offline algorithm succeed. The algorithm runs in Okk (ng(n))+ 2poly(e d)k3 poly(c (ooo=log(nn))))))) (dllo)o(( poly(c=+og((nn)) time.
Proof of Theorem 3.1. Equipped with Lemmas 3.2 and 3.3, our main algorithm is listed in Algo- into m == ((lg((nA) parts. We use 61 == C,,,,...,,C == n + to represent the times such that De.-1 & De,- Now for a fixed part (Pei (Pes-Pettl, Pe.tl, ..... PP 1), we have 1i..--1 De.l S O(dk poly(e log(n))))
rithm By Lemma 3.2, A Acoreset partitions the point stream (pI .pi.P......
P..) .p.)
Let le, - \D,ll Note that for every 1 S m we have OPT(D s 2 OPT(DD.. So feed De, as Po and Dectr-1 De, as the point stream to Abound we get center set sequence (c) claa) "..,,,,,,,, such that for each 0 S S Ci+1 - 1, cf is (1 + c) -pprrxxxma solution for point set Dest> and thus a + 3c)a approximaaee solution for Pertj. Since this is true for all e; we finish the proof of the approximation ratio.
For the consistency, we directly compute it as
m
m [aaaee poly(e llo(A))) poly(e=Logg())) +
IC
\ cf + 1 dleesss)
S
O(a poly log(A)) log(((
Le,) + km O(adk poly(e- log(()))))))))
Finally, provided that all invocations the offline algorithm succeed, the randomness only comes from the construction of the coreset. Thus, the failure probability inherits from Lemma 3.2, which
is poly(n)
For the running time, note that constructing the consistency coreset takes O(kn log( (n))) time. Also. observing that each time feed Ahound at most 2 (-=(=) poly(e -a log(n (n)) points, Summiing over all restarts of Abound, the time complexity 2poly(e dik''s (o (dk poly(E -1 log(nA)))). Thus we finish the proof.
O(kn log(nd) +
B PROPERTIES OF ROBUST (CENTER) SEQUENCES
Fact B.1. If a sequence (co, c.) c.) is robust, then it is to-prefix robust for every 0 S to S
Fact B.2. Given point set P, robust sequence (co,-..,Cc) .e) with respect to P and integer (1 + +c) c3) S (bgeost,(ball (1 c) c.))
1 S i t, for every j <
The properties of Definition 4.1 are mostly used in Lemma B.3. In other words, Definition 4.1 directly used in most of other parts of the proof, instead, they use Lemma B.3.
Lemma B.3. (Co, ,..,..,,)) is robust, then
For every 1 < i < t, dist(c;-1,, (:) <
2c²
(1+c) ()
92
For every 1 < < t, (c (1+e) +e) C ball (1)
'Notice that the factor d may be turned into (logg by using dimension reduction (Makarychev et al., 2019).
14

---

Published as a conference paper at ICLR 2025
Vi E [n]. dist(cu, q) $ 1: + c)
Proof. For every 2 < < t, if 1:- = ai then d) 0. If ci-1 * then
avgoost, (ball, p (2, (1 (1+c)i),c)) ()) - क (1 +)). By letting j = i- in Fact B.2, we have
2²x
22
2² (1 e) g=
(1 1++0 +c)* 2 avgoost, (ball (1 + e))), + (balll (1+c)
Σ
(P(p) dist (p, c--1) + P(p) dist (p, ci)
bbll (1+))
peball
1 (2-1 P(p) dist (c-1;())_,,))) 2 dist (c-1,
Σ
bct (1 + +)))
2
p(
So we have dist dist(c;-1, S 20 (1+c):. For the second part, it suffices to show that (ist(c:1,, Gi s (1 + e) (1 e)+ And this can be obtained from the first part. For the third part, we have dist(coo ci) S E dist dist(c)-1.,;)
2. (1+e) 9=
(1 E)
Lemma B.4. Let (co, c....., 0a) be robust sequence with respect to P. and Po S P be subset of P such that pal (1 + c)} b (c., (1 c))+ for all E [t). Then vi [t]
cost (Po, co) S (1 2c) cost (Po. ct).
Proof. For every S t- -, let D. == b, (cH+1, (1 + E) )) ball p. (c, (1 + +)) Let D. == Po ball p(a, (1 +)) By the third property of Lemma B.3, we have V1 < i is 4, Vp E D. dist(c;, co) S 5o + e) < fo dist(ci, p). So
dist(p, co)² < (1+c) dist (p. c)+(( 2z 'y-- dist diist((s, co) S (1+c+ (22+ dist (p. S (1+26) dist dist" (32)²
By Definition 4.1, in the point set ball ballp(ca, (1 + )) we have
cost. (ball R2 (c. (1 + ++) 2 (ball, (cs, (1 + c))).
Now combine the above inequalities to bound the cost of po by the following inequalities:
cost, (Po. c;) cost, (ball p (c., (1 )) cost, (y.
2 cost:(ball,,, (cs, (1 + c-1) + 1 + 2e
cost, Bost=(U/))) (U.2:
(by Fact B.2)
1
cost, f. (-- (1 ) .-1 + cost (D, 1 C-11 1 2e
cost, (Ugz;
2 cost (ball (G-1, ),G-1)+ + 1 (cost, (cost + cost. (U) co))
1
cost (ball fo (c1, (1 + ()+
cost, (1 13,
1+
1
cost (Po, co)-
1 20
Lemma B.5. Given a weighted point set P and a center set C with witness mapping witc, during the whole process of MAKEROBUST(F? (C, wite)), the size of center set C remains the same the input C.
To prove the lemma, first show the following technical lemma.
15

---

Published as a conference paper at ICLR 2025
Lemma B.6. Let P be weighted point set, (C, witc) be center set with witness mapping. Suppose there is C. such that witcle) is not preci-prefix robust with respect to P. and let
co :- ROBUSTIFY C,c). Then for every è C. {ch, dist(co, c) < <(1++) dist(c, é). Further- more dist(cn, 2) S (1 +
15x
<(I+)] dist(e, ().
15=
Proof. Let d' be the closest point in C \\ {c}. By line 1 of ROBUSTIFY, witc( is t-prefix robust such that
5(1 + E) 1 = v dist(c, C {c} = dist(c,, c').
By Lemma B.3, we have dist c) v 32 (1 + c) combining the two inequalities we have for <(+c) dist(c, ê). By triangular inequality 15s
every è E C. {c], dist(co. s <(l+c) 152
dist(c, d') S
we have
dist(co, 8) z dist(co, c) + dist(c, 8) s (1+ c(1 + +)
dist(c,
15:
Now we are ready to prove Lemma B.5.
Proof of Lemma B.5. We prove this by induction. Let the size of the input center set be n. Our induction hypothesis is for every round of the while loop, the size of the center set C in line is n. The base case in the first round is naturally true by definition. For the inductive step, suppose at the i-th round for i 2, the beginning of the loop |C| = n. If ROBUSTIFY C, is called for a center e E C, let (Co, v) == ROBUSTIFY(P, c). Recall that by Lemma B.6, dist e) s <(I+e)
15z dist(c, C \ {ct), so can not coincide with any center in C' \ {c}. Then at the end of the loop, the size of the center set is still n.
Next argue that during the execution of MAKEROBUST, once center swapped out, it can never be swapped back again.
Lemma B.7. Suppose MAKEROBUST is some point set P and center with wimess map- ping (C, wi During the execution of MAKEROBUST, if (Ca, v) RORUSTIFY C, e) for center e C and e replaced by co, then MAKEROBUST does not call ROBUSTIFY(P,C. C,c) until the end of the algorithm.
Proof. To clearly track the changing during the algorithm, we construct & queues (Q1, Q2....,Q Qk). The elements in the queues are points from the candidate center set with witness. At first, each queue Qi contains one element in C' with the witness. During the execution, if (Co, v) ROBUSTIFY(e) is called, we find the unique queue Q where is the end of the queue. And add element co to that queue with the witness w.
We first point out the above procedure is well-defined. This means that any time, the end elements of these queues correspond to the center set. This can be concluded by Lemma B.5 because the size of the center set does not change and any center point must be at the end of one queue.
By our queue construction, for each round, the union of the end element for all queues is exactly the center set. Moreover, the elements in a queue totally capture how a center in the original center set is transferred. Leveraging these queues it suffices to show that none of the & queues has length more than 2.
Suppose for contradiction, there exists queue Q with length of least 3 during the exccution of MAKEROBUST. We consider the first queue such that this case happens. Suppose the algorithm runs rounds and denote the immediate output set ((C₂ C, wit ), (C2, witc;). ... (C., witc, ))- Let j be the minimum number such that at the j + 1-th round, there a queue with a length 3.
Moreover, let i be the minimum number such that at + 1-th round, cu is in Q. Then by the property that each end element of queue is in the center set for any round, co keeps staying in the center set from i 1-th round to j-th round.
16

---

Published as a conference paper at ICLR 2025
Let c' be the closest point in C₁ \ {c) to We note that c' is also the closest point in C++1 \ feu). Recall that from the definition, v(co) is tc..., (co)-prefix robust with respect to P. where tc (co) is the value defined in line 1 of Algorithn 2. We discuss the following two cases separately.
1. is in the center set Cj+1. By Lemma B.6, we have
<(1 + c) dist(c,
dist(co, d') & dist(co, c) + dist(c, ('), s (1+ By the definition of 1c,41 (co) again we have
15z
(1 + (1+))((1100) dist(c,
dist(co: d)
dist(co,
dist(co. Cj+1 {co)
5
5(1
<(1+c)
10
10
162
Recall that EC (Co) is the smallest integer such that (1 +) 2 dist(co, Cj+1 \ fcol)/10.
Then we have CC4. (co) 2 115++ (co) thus w((o) is still (Cz+, (co)-prefix robust. This contradicts our assumption that v(co) not (
2. Otherwise, c' is not in Cj+1. Let Q' be the queue such that when calling ROBUSTIFY(P, C), is at the end of Q'. If is not in Cj+1, we know that there must be a center with witness (ch, 2/)) being added Q' before ên being in Q. On the other hand, c' is at the end of Q' at the i + 1-th round, so o has to in Q' after the + 1-th round. Suppose for a number i < r < j. +++1 is the minimum round such that d is in Q'- Recall that co is at the end of Q from the
i i 1-th round to the r-th round, so must be at the end of Q at the r-th round thus co is in the center set Cr.
As at the r-th round, ROBUSTIFY(C)) is called, so by Lemma B.6 dist(c', .cc'.c)) c6) S e(1+e) dist(co, d') < [( ((( (=(I+e) dist(c, c'). Thus we have 132
15z
dist(co, 66) I dist(cco d') + (c, (6) S (1 e(1 + e) dist(c. 152
Recall that by our selection, Q is the first queue with 3 elements. So at the j + 1-th round, Q' has have only elements: c' and c.- So d the center set Cz+1- As co is (ecot((roobue we have
dist(c,c))
dist(Co, %6
dist(co. d6) dist(co, Cj+1 \ (cul)
(1 + () ( (co)
31t 5(1+ +
10
10
15s
This also contradicts our assumption that v(co) is not to (co)-prefix robust.
Lemma B.8. Let P and Pr be two weighted point sets, (co, 01 ..,,,....) cz) be a robust sequence with respect to points set P. If ball (1 + )1 + e) = ball pa (Co, (1 + (1 +) then (Co.C1... C1 c.) is also robust with respect to point set pr.
Proof. By Lemma B.3, for every siga t 1, (al,, (1 + +) S ballp(c++, (1+ (1) So if ball plee, (1 + +)) = pall (1 + +)) then (co...., (.) is l-robust sequence with respect to points set 8r For every point 5f pall (1 + e)) by Lemma B.3 we have
dist(co.P) = dist(co. dist(cr, S (1 3: (1+)))
So ball s(e,, (1 + +)+) C ball p(co: (1 + ) + +)) And this suffices to prove the lemma.
C ANALYSIS OF MAIN ALGORITHM IN SECTION 4.2
Below we first define some notations used in the proof for the convenience of presentation. For each phase e, suppose the length of the phase is l + 1, we write (5(e) and (5(e) end as the points set at the beginning and the end of the phase, and (T/6)) U(e)) "ite,,..,ur U(()) Ule) = Utee (++1) as the intermediate
center set during phase e. The intermediate center after swapping is denoted ((e).
17

---

Published as a conference paper at ICLR 2025
C.I TIME COMPLEXITY
The running time of the algorithm is summarized in the following lemma.
Lemma C.1. The consistent (K,SS)-CLUSERIIGG algorithm for bounded input runs in O(K2mi((m) + dkm22pply(e ') log(A)) time.
Proof. We first analyze the time complexity for a fixed phase. Recall that each phase consists of four steps and we give the time complexity for each step.
Deleting centers. In this step, the algorithm enumerate all possible number 0 k and then call the a-approximate algorithm on the candidate center set Un with center set size less than The time complexity is kT(m).
Handling insertions. The time complexity is O(Ekd), wince we need to check the current center belongs the current center set which has at most & points.
Swapping centers. this step, following the proof of Lemma C.2, suffices to consider the time to compute a-approximate solution and then find all valid well separated pairs. The time complexity is O + T(m)) where the term comes from computing the pair-wise distance between two center sets.
Robustifying centers. In this step, the algorithm runs subroutine MAT 3), which runs subroutine ROBUSTIFY(Algoribn) 2) if center is not bounded robust. Since checking if a center with witness is bounded robust takes the same order of time as computing a robust sequence, it suffices to analyze the running time of ROBUSTIFY.
When computing the robust sequence in line 2 of ROBUSTIFY, the algorithm needs to compute a near-optimal center for ball ((;; (1 + +) for some Definition 4.1, which can be done in O(dm2Poly(c=*) time by Chen (2009). As the length robust sequence can be most (loog(A)/e) and ROBUSTIFY is called at most & times by Lemma B.7, the running time for k calls of ROBUSTIFY O (km2polly 1> log(A)).
Finally, since the number of phases is upper bounded by the total number inputs which we de- noted as m, the time complexity is (m)²mT(m) + dkm d 22poly(e 1) log( A)) in total for all phases combined.
C.2 COST ANALYSIS
We analyze the competitive ratio in this section. Recall that the algorithm runs in phases. and in each phase e, the algorithm starts from some center set Ufe), Hence, our plan to inductively show that v/()) is (1 +1+00 ((e)) a-ppprxximae.. Notice that this alone is not enough, since for all but the last input point during a phase, the output center set is derived from (:(0) (by first deleting some centers from it and then adding some input points), so also need to analyze the ratio for these intermediate steps, and we show it is (1 + (()))a"-approximg the last step of a phase which particularly has swapping procedure (and hence the induction is to analyze this last step only).
We also notice that UT(e) is changed only in
Now, observe that to show Uf()) is (1 + O(e))a-approximate, it suffices to bound the approximation ratio after swapping centers, since if we can show the center set W(() resulted from the swap is (1+0(e))-approiimaa) apprrxiiie then by Lemma B.4, the center set (1(e) still a solution. To this end, recall that in the algorithm Section 4.2, W(e) is obtained by swapping out + -eel separated pair with a a-approximate solution for P/+1. or serve points p(e) \ ( In the following technical lemma, we show that this swapping and
centers in (e) that either do not form a 2002
rule indeed guarantees (1 be)ao-pproximate ratio.
18

---

Published as a conference paper at ICLR 2025
Lemma C.2. Let U and V be two center sets, and P, P' be two weighted point sets such that P P P'. Suppose U is equipped with witness mapping witg and (U, wite)) is bounded robust with respect P. Given E (0, 1), let 2 1 be any integer such that the following hold:
1. (1), (u2, U2) (ua, Us) are 2005
wwell separated pairs.
[[V, _ P for E [s].
Let C = {ui, 02 May 1s J, then
cost, (P,C) S (1+ cost, V).
Assume this lemma is true (and the proof appears after this part of argument), we can conclude the competitive ratio analysis follows. Lemma C.3. The consistent algorithm for bounded input is (1 233e)a2 -cmpettitie..
Proof. We first prove for every phase e, (U%+5) wit ((0) bounded robust with respect to (5(e)
and U is a (1 + 17cja-approximate solution for e This is done by induction on the phase, the base case is the first phase, where the algorithm runs the a-approxiamte algorithm and then calls MAKEROBUST for the output obtain Ug. By Lemma B.4, Ug a (1 + approxxmmae solution. The bounded robust property naturally holds since Un is the output of MAKEROBUST. For the inductive step, suppose for phase e, the induction hypothesis true. Let be an a-approximate solution for end- By letting (()) and pie)
end be the corresponding P and P', Ui(e) V and W()) be the corresponding U, V and C' in Lemma C.2, we know W(() is (1 + -e)a-aaprooimate solution end" By Lemma B.4, calling MAKEROBUST(Pre.) end (W(+), wil increases the cost by factor of 1 + 2c, U(e) is (1 -apprrxiite solution. Moreover, U(+), is naturally bounded robust because it is the output of MAKEROBUST. Thus we finish the induction.
for pls)
Now prove the competitive ratio for the algorithm. For every phase e, we know 0/ is (1 + 17 a--aprooximaee solution. Suppose phase e consists lg insertions for some 2 For S
fe, we have
cost, (P (P()) & (1 12c)a cost, ,
< (1 17)) + 12e)a² (
< (7)) 12e)a² OPT(?. (1+ 233e)a OPT(P!
where the first inequality comes from the fact that cost, (p!le) F(ee u(())= = and the definition of the algorithm. The second inequality follows from (/() is (1 + 17c)a-approximate solution for p(())
Now we give the proof of our key lemma Lemma C.2.
Proof of Lemma C.2. As the second condition (VVV, vs] S P is equivalent to P'[V, v.] = PLV, v.).
write
(P' Σ cost. u.),
(P'(C, e)
$ cost. (P'V,
Σ cost. (V VV
The inequality holds because it's optimal to assign every point in / to the closest center in C.
We will show that for a well separated pair (u,, vz), i < s, cost, cost.(P u:], u.) S (1 +
2r) (o us), vz) and this suffices.
19

---

Published as a conference paper at ICLR 2025
Suppose (u, is a well separated pair, wity (u) (u, c1, (2,...,(((()))) then have
et
dist(u, v) -
dist(u, U fuf) I
(1 + +
tim
400z
40x
which follows by the Definition 4.3 and Definition 4.2.
So there exists a t" 2 t(u) such that 21 + e) =²= S (u, v) S a
402 (1+
Claim C.4. ball (1 + (1++)) S ulV.
Proof. q bul, (1 + 3c) c) ) then we have
c (1+c)* + ét
é (1+c) s (1+))
dist(q. v) I dist(g, Pr- ) + ( dist(uu, v) s (1+ (1+e) +
32
32
402
where the second term of the second inequality follows by Lemma B.3. On the other hand, for any C such that s' # v, we have
400z dist(u,,)) dist(g. v) 2 dist(q, u),
dist(g, r') 2 dist(u', u) dist(r, 2 c²
where the final inequality follows by fuz (1+ dist(u, v) and dist(q, v) (1 (1+)) So is the nearest center to in V. This finishes the proof of Claim C.4.
As (u, v) is close enough, for the points outside the ball ball (1+ se (1++)) the cost induced by u is naturally a good approximation for the optimal cost. As long as the average cost in the small
ball ball suu, (1 (1+}) )1++)) " around e is large enough, then cost. (ball (1 + se (1++e) : u)
is good approximation for cost. (ball (u, (1 + á. (1++)) ),) Summing the two parts together achieves our goal.
To formalize the above discussion, we handle two situations ct -1 and Ct * cr separately.
ct. = Cc-11 this means crglost(ball,, p. (ce., (1 + e) ..))) 2 2
2= (92)
(1 + e) : We first
show that the average cost of in ball R (u, (1 + c) can not be too small.
Claim C.5. avgcost, (egcost,,bballp(( (1+ 6))
2-(153y (1 (e)
2x+1
Proof. If u Ct- then we naturally have
2x
avgcost, (ball, (1+ S (1) u) (balostt,(ball((c) (1+c)) 2
(92)= (1+c)*.
3z
So from now on we assume # c.. Suppose ct- = Ct- = Then by definition we have
* cv-1 for some t' > 0.
2=
avgcost, Cobcost,bbalppae (cte, (1 + ()) ),,)) )) <
(9z)z (1 + t)²
Let Sy be the points set ((er, (1 e) \ berr, (1 c) 3) Sz be the points set
ball p(ce,, (1 ) and Q be the points set ball (1 + & + )) (S1 52). Then we have
w(S,) (S1,, + w(5)) avgcost (S avgeost, prgcost,(ball (1+e)*)), ),))) (92)z (I+e)* w(S)) + w w(22)
22
20

---

Published as a conference paper at ICLR 2025
Thus w(Si) cost= (5),,( w((i) + wS2)
22 (9=)z (1+e3" 22 (1 +6)²
(9z)s (1+e)* avgoost -
(1+)*(1+()
On the other hand, for every point pi in $1, we have
2 dist." (p, + +2- dist. dist"(ce,, (cr,u) S 2 + e²
dist. (p, (x) dist.
(p, (p,t"(p,
dist (p, u) S 2 dist (p,
(32)²
(2)
Finally we have
(u 1 6 ) 32
(1 ) =
w(Si) (v + w/ avgcost u) + w(() avgcost(Q, u)
w(1) + (S2) + wQ))
w(S) avgoost($1, + w avgcost @ u)
w(1))+ + (w)))(((())))) + (Q)
w(Si) avgeost(Si, u)
w(Si) + w(2))
w(S)) avgcost( (S) C1-)
2 (11 w0 w(2))
20+1
(182)<(1 (1 e)r
2++1
2 (18z)= (1 (1+c)*
where the second inequality follows by avgcost
(Q. u) 2 avgcost(S1, u), the third inequality fol- lows by Equation (2). This finished the proof of Claim C.5.
Now we divide cost., (PIV, v)), v) into two parts: the small ball ball (1+ +1) and the points outside the ball. Namely,
cost:(P|V, e], v) cost., (ball (1+ (((+)) v) coost, toott (1+ { (1+c))),,))
32
32
We bound the two terms separately, for the first part.
(bsl:(ball (1 +
3 (1 + +))= =)
32"
P(p) dist (p.u)
Σ
(i)) dist (p, w)] Z
Σ
P(p) dist dist"(u, v)
2--1
))
FEball
p(u,(1+ FEball
+))
= =Iball p (u, (1 + (1 + c) - )[( (ball (1 + + (1 + ) ),u)
dist=(u, v)
32
2--1
2 ball p (u, (1 +
E
(1 + e) _ )[((1 - <) puy (1+ E
(1 (1 + +)) u))
3z
3
(1 c) cost. (ball (1+ 32 c)
where the second inequality follows by Claim C.5 and dist(u, v) S - =)
Next we deal with the other part. For any p E PIV, u] \ bull (1 + - : (1 1 = ). we have
dist (p. v) 2 dist (p. u) dist 2 (u, v) 2 (1 - c) dist (p. u):
2--1
21

---

Published as a conference paper at ICLR 2025
thus cost
(1+ E ) (1++) (1+e)=) 2 (0st) (PV, 32
(1++)))
32
Now we add the two parts:
cost, (P(V. 2 (1 cost. (PVV
So in this case cr- = -1- we have
cost, (P(, u], - --c cost,, cost S (1 + 26) cost (PIV, v),
1
If ct- # C1- this means ct- is near-optimal center for ball (1 + )) thus we have
cost: u) cost, (aat + c) m) cost = (PIV, \ ball Po (c--1, (1 + x)")),,)
(ball $ (1 + 2e) cost (ball p(ce-- (1 + +) -) Ct- --- + (1 + +) cost (PIV, o) ball (c---1, (1 + v)
< (1 + (e + E) costs (ball 1
+ (1 + cost (PIV, e) \ ball p (Cr- (1 + e) + v)
$ (1 + 5e) cost. (PIV, v)
where the first term of the first incquality follows by Lemma B.4, and the second term follows by dist v) 2 (1 e) dist" u) for 5 E PIV, v] \, ball (1 + )) The second inequality
follows by Ct--1 a (1 + e)-approximation of the optimal (1, =-clusterinng problem for the ball.
This finishes the proof of Lemma C.2.
C.3 CONSISTENCY ANALYSIS
In this section we prove the consistency of our algorithm, summarized as the following lemma. Lemma C.6. Given an input stream of m weighted points, the total consistency of the algorithm is O 22 log(e)) m log" (A)
By the definition of the algorithm, the consistency is upper bounded by E. Eigige, (LU!))
U.Si)) + (U(e) \ U(()), which accounts for the changes of the center set both within phases and across phases. We first deal with the easy part: the consistency contributed by Eisise. (0,S0) ( which the consistency within phases. In this part, it straightforward that the consistency is fa- Note that a phase contains le + insertions, so the amortized consistency during a phase is O(1). Summing up all phases, the total consistency contributed by this part is O(m).
Next we bound the consistency contributed by end U,(e), which is the consistency across phases.
First we have (Tte) U < (r(e)) \ ( + fa- So it suffices to consider the term ((tle) \ Ufee),
Based on this observation, We partition Uree into two parts.
1. Updated centers. We define the updated center set as Up(e) which consist of (1) centers in ((e) Ule) (W()) nuf()) and (2) obtained by calling ROBUSTIFY end: W(e), c) where c E W(e) ul Centers in Up(e) are called updated centers.
Fresh centers. We define the fresh center set as F((), which consists of the remaining centers, specifically, (1) the centers in U(e) O (W(e) \ Uife)) and (2) centers that are obtained by calling end
ROBUSTIFY centers in ((e) Uffe) Centers in Fle) are called fresh centers.
Based on the partition strategy, ((() \ (:(e) C F(e) U (UP(*) (U)) so (ole) \ (/(0) < [ + end (UP()) (Uo. So we can split the consistency across the whole phases E. (U(e)) end \ Up(e) into two
parts:
Σ (r
100o x Σ | + \o
(UP())
(3)
22

---

Published as a conference paper at ICLR 2025
So it suffices to bound the two terms on the right hand side. For the fresh centers, the following lemma provides the bound.
Lemma C.7. E. |F(0| S O
c
Proof. Fix a phase e, note that the number of fresh centers in e is upper bounded by the num- ber of centers in W(e) \ U/d0) This is because for every W(e) \ Ugd), either E U or ROBUSTIRY(PIL) (Pie)
(nnd end W(e), c) E U(e) end'
Let V be an a-approximate solution for end be the number such that for every i [s], (u,, Us) end [us] C Po- Recall that the consistency algorithm for
, -well separated pair and plle
forms a 100% bounded size in Section 4.2 swap co Up into Uo to produce W. So |W(ee) \ U/41 = k - 8. e²
On the other hand, suppose the number of 1u0s well-separated pairs between Uo and V is f, then is larger than f - le - because at most Le + 1 centers serve the le - -1 new points. Thus [W(e] |/ < k- t le +1.
The following technical lemma gives the lower bound for t, whose proof is provided in the next subsetion.
Lemma C.8. Un and V have at least (0020(2zog()))))))))))(0)))))))) e well separated pairs.
100z
Proof. The proof can be found in Section C.3.1.
By Lemma C,8, [W 0 < 0/
So we also have [F(e)]
S
O( ((220 lox(s)) fe). Now summing over all phases, we get the number of new centers is at most the total number of O oz (o m)). This finishes the proof of Lemma C.7.
Next we consider the number of updated centers. Recall that we are in fact considering points in the difference of sets: Up(*) (u(()) for each phase e. We should point out that for a center u, there can be several phases such that E UP(c) (u("). In this case, it means that u is moved out from the center set and swapped back several times, and every time u is counted independently.
Now we fix phase e. Let u be a center point in Up(e) (which is also in U with witness v(u) such that ROBUSTIFY of u is called during the execution of MAKEROBUST (W, witw)). Suppose v(u)= = (u, P2. ... . .P(.)) is the witness for some t(u) E N.
Note that duing the process of MAKEROBUST, the center keeps changing. Let Ć' be the center set immediately before calling ROBUSTIFY for u. Then v(u) not (u((u-ppeftt robust with respect to
end- By Definition 4.1, there are two cases:
1. ((u) < ((( regardless of whether v(u) is robust or not. In this case, we say u is violated by centers update.
ple) t(u) 2 tz) but u(u) is not fp-rffx robust with respect to end In this case, we say u is violated by points insertion.
For the second case, as u E U/ee and U/()) is bounded robust, we know that vu) is f(u) robust with respect to points set p(c) By the contradictory proposition of Lemma B.8, there must be point p E p(e) end \ F(e)) such that
dist(p, 51+ S )1 [c) S 51+ (((+c) 3z
(a(w)
cc) d6
(4)
3z
Given center point Up(e) and a point F E ple) P(o) if dist(u, p) S (1+ (1(
then we say ğ violates u. Note that if a center u is violated by points insertion then there must be at least one point that violates However, if point violates u, may not be violated by points insertion.
We have the following bound for the two cases.
23

---

Published as a conference paper at ICLR 2025
Lemma C.9. For every e, every point p E Fied \ ( violates most (Ioo((A) centers in Up(e),
end F for a phase e. Let s be the number of centers in Up(e) that are violated by pi during the phase e, and denote those centers {ui, .W,) For each 1 s
Proof. Suppose y E F(t)
i S 8, let e be the minimum phase such that u, E Use') for every e e S e. We define the arrival order as follows. For any u, and Uj. if e, < Ej, we say u, arrives earlier than ej. If e, = e let ((C₁ == W(ea), witc; ), (C2, witc:).... ...., (C,-1, witc..,), (C, ;= Uled witc,)) be the intermediate center set sequence during the execution of MAKEROBUST( (W(a), witw())) (which also MAKEROBUST (P (W(e), wegg)) Let G = min(t u4 E C.} and oj = min(t: : Uz E CtJ. By the algorithm MAKEROBUST, C + cj. If c; < ej we say u, arrives earlier than ug- Without loss of generality write the centers as (u1: U2 ........... Ug) such that u, arrives earlier than új for any j.
For each S i 8, suppose (ui, v(u))) is the output of ROBUSTIFY for center un E Ug Let C be the center set immediately before calling ROBUSTIFY to u4. Let ((w)) be the smallest positive integer such that (1 + s(ma)) 2 diistuu,, CV (u4))/5. Then by line of Algorithm v(u:) is ((ue)- prefix robust with respect to Flad) Moreover, by the order of the sequence, Wi+1 must also be in C. Because of the minimum property of t(u4) we have dist(u u441) 2 5(1 + c) (w;))1 On the other
hand, by Lemma B.3 we have dist(1,, u:) S 35 (1 + dea
Combining these together.
5
[un]
5 - 6
dist(u; 4;+1) 2 dist(u4,
2; 2;- distuuu u;) 2
(1+c)
(1+e)
2
(1+E)
(1 + ee)
3z
(1 + E)
As p violates u, for every 1 S i S 8, we have
(p, u.) S (1
(e) siss. 8.
32
So it follows that for all 0 0 siss-L
b- (1+c)
(1+ (1+c)
dis Ui+1)
dist(u; (wi, Ui+1) 1) dist(p, us)
alm))
(1++)
2 2(1+e)
c 1
1 32
1 32
32
So the sequence ((1 c) 1((2)) This finishes the proof Lemma C.9.
Jisis grows exponentially. Thus can only be at most O(log( ())).
Since there are at most m insertions we immediately have the following corollary. Corollary C.10. There are al most 0(m log( log(A)) centers that are violated by points insertion.
Now we deal with the second case: centers that are violated by centers update.
Lemma C.11. There are at most O aa22 log(s)) mog' lo)) centers that are violated by centers up- date.
(81-2
Proof. We construct collection of queues and a mapping from the center points to those queues to prove the lemma. The elements of every queue in the collection belong to the candidate center set. And the collection is constructed as follows. Recall that a center is in F(e) if either in (r(e) n (W(e) \ (r(e)) or is obtained by calling ROBUSTIFY to centers in W(e) \ U For every fresh center e F(e), we construct a new queue instance Q (c) with single element c, labeling the element "fresh center". Moreover, we assign the center c to the queue: o(c) := Q. Given a e is replaced by a center d' by calling ROBUSTIFY(C) and c, suppose
phase e, if a center ((c) = Q, we add an element in Q. Then we let Φ(d') = Q and label the element e by either "violated by points insertion" or "violated by centers update" based on which case e belongs to.
24

---

Published as a conference paper at ICLR 2025
We first show that this procedure is well-defined. Specifically, we show that for every phase e, each center in U/+e) is assigned to a unique queue. This done by induction on the phase e. At the beginning, all vertices are considered as the fresh centers. So each center is assigned to a unique queue. For a phase e, suppose every center point c E U67) is assigned to a unique queue. Consider the next phase e + 1 and centers in U(++1), If, C F(e). Then the center will be assigned to new queue thus it is unique. Otherwise, if e UP(e), either e E Ui(e) or E Uf(+1) \ Uife). For the first case such that t/ it is assigned to a unique queue by the induction hypothesis. For the second case, there must be a center E e such that c = ROBUSTIFY(PIt), w((), ,d). In this case, by the induction hypothesis, c' is assigned to unique queue.
Based on the construction, for each queue in this collection, the first element is labeled by "fresh center" and the labels of other elements are consecutive "violated by centers update" and "violated by points insertion" alternatively. We claim that for any queue in the collection, there is no sub- queue with a length more than O ( such that every element is labeled by "violated by centers update". This is because every time a center violated by centers update, by the definition, means the witness sequence is too short. And the length of the witness after calling ROBUSTIFY increases by at least 1. This implies (1 ( increases exponentially where / denotes the length of the witness.
Secondly, Lemma C.7 implies that there are at most O 22 lox(=))
elements labeled by "fresh centers" and Lemma C.9 implies that there are at most O(log((A) (A) elements labeled by "vio- lated by points insertion" among all queues in the collection. So in the collection, there are most O( 9:2 g
(=))(())))) m + (moo((A)) -( a =
O a2 lox(=)) m (o) elements labeled by "violated ca2-2
by centers update". Thus we finish the proof of Lemma C.11.
Finally we combine everything to conclude the proof of Lemma C.6.
Proof of Lemma C.6. Combining Lemma C.7, Lemma C.9 and Lemma C.11 shows that
Σ
(0 \ + p / |
S Ee + 11ted \. 1 ee)
50(m) +
(((e) + |Up(() [
220(=
0= m log 1og + O(mlog(A)) + +0 (by Lemma C.7, Corollary 1. and Lemma C.11)
s (mm) + 0( 83
O a2 a20(= log(=))]
m log (A)
2
C.3.1
THE NUMBER OF WELL SEPARATED PAIRS IS LOWER BOUNDED: PROOF OF LEMMA C.8
In this section we prove that the number of well separated pairs between the center set maintained by the algorithm at step 2 and an a-approximate solution at the end of the phase is k - 2(6)), where to the number of centers the algorithm deletes. Our key lemma Lemma C.13 shows that given a point set P and two center sets U and V, suppose U and V form t c-well separated pairs, then l2k - t) centers can be removed from U to form U", such that cost(P, U') < cost(P, (P, U) cost(P, V)). This is an improvement compared with Fichtenberger et al. (2021) where they only provide an upperbound cost(P,U' U') < cost(P, U) +
U)+
+ cost V)). We first provide the cost increase bound for re-assigning points to other centers in Lemma C. Base on that, we show how to pick a subset with size large enough to delete while the cost is upper bounded in Lemma 1. Combining the algorithm and Lemma C. we conclude our goal in Lemma C.8.
25

---

Published as a conference paper at ICLR 2025
Lemma C.12. Suppose U and V two center sets, |U| |
k, and P is point set. Also suppose t is some integer such that and V form e-well separated pairs. Then there exists a subset DCU U with [D] 2 (k- 2 and mapping D U. such that
1. Vu E D, + u
vp E P. suppose u is the nearest neighbor of p in U and v is the nearest neighbor of p in V, then
4 (10z)=-1 (dist (p. u) + dist (p. v))
dist (p, p(u)) dist u) S 22
Proof. Construction of D and di For center U that is not in well separated pair, we consider the following case:
Let be the point in V that the closest point ur
1. If the cloesest point to from U is not u, denote it as u'. Then we include D and let
Φ(u) := :=
Otherwise, the cloesest point from U is u. Let u' be the second closest point in U. And it satisfies dist(u, v) 2 dist(u, v²), then include u E D and let Φ(u) == u' If the above does not hold, then the closest point to u from U is u and dist(u, v) S edist w²). Let v' be the closest point to from V. Then dist u, v) 2 (e, v²). If there is a u" E U such that dist(u", e²) S dist (u, v)), then include u E and ((u) == n..
Next, we show that |D] 2 (k- - t)/ We construct bipartite graph H. whose vertices consist of points in U LUV. V. For all points u E U, let v be the point in V that is closest to u. And we put an edge pointing to e from u. similar edges construction is done for V.
Let Ö be the center set containing centers that do not form a well separated pair with any center in V. We first prove for each u in D, the in-degree is at least and the out-degree 1. For any Ü \ D. suppose u points to and v' E V is the closest point to By our selection of we have that v points to u and for all u' E U \ {u), dist(u', v') & dist(u, v). On the other hand, dist(v', v) < dist(u, u, v). So dist(u', v)) 2 dist(u/, v') - dist(v', v) 2 1 dist(u, v) 2 dist(u, v). So v' also points points some u E U \ D. Then we have IQ] 2 2n.
Suppose I0 \ DI n. Let Q be the subset of V such that each of its vertex
Consider the points set D. The out-degree of the set is k - t We claim that there are at least points D such that one of the following is true:
1. points to some Q. 2. points to some in V 'QQ And does not point to this
Suppase in D. there are m points pointing to some v in Q. If m 2 n then we are done. So we assume m < n. Then the number of points D that do not point to some in Q is t n m. However, V Q has only at most k 2n points. There are most
2n points u pointing
t E V\Q and v pointing to , so there will be at least (k - t- n - m) - (k - - 2n) = n - m points in D satisfying the second condition. Those u's satisfy the first condition of points in D. So we have found least points in D. This shows ls t DD] - DI < 2| therefore [D] 2 (k - 1)/2.
Finally, we prove that the cost increase is bounded. For any
D, consider the following case:
26

---

Published as a conference paper at ICLR 2025
1. If this satisfies the first condition. Then Vp PIU, u), let vo V that p is assigned to. We have
dist (p, v(u)) - dist." (p, u) S e dist (p: u) + e + (==22)=-1 dist (u, (())
I edist $ up + 2(c + 22)
y { (u, u) + dist (v, o(u))]
e
2(c 22)
I edist $ (p, + 2
)s- dist (u, t)
2( + 2z)
S dist * (p,u) + 2(
y dist (u, un)
4(c + 22)
S edist (p, u) + 2(
y [dist (p, u) + dist vp))
102 5 -((-))=- ) (p. u) + dist un)].
2. If this u satisfies the second condition. Then Vp PlU, u]. let up E V that p is assigned to. We have
dist (p.t"(p,((u)) dist (p. u) S edist (p. u) + c+ 2z -== dist (u, p(u)) ( 2-1
e
+ 2z ---1
S cdist u)
dist dist"(u, u)
c
I dist (p, u) + c + 22
dist dist"(u, vo)
6²
< dist (p, u) + 2(e + 2z)
)=-1 (pist"(p, u) dist"(p, m))
2- (52)=-1 [dist. (p, u) dist. dist vo)
62a-1
3. If this u satisfies the third condition. Then Vp E PIU, u]. let vo E V that is assigned to. We have
dist (p, dist (p, u) s eddst u) + <=
2z 2=)= dist (u, d(u))
<d (p, (e+ 22)
> [42-1 dist (u, v) 4 dist (v,'') + 2- dist dist d()))]
c
A(c + 2x)
2
edist (p,
)=-1(1 +
dist $ (u.
A(c + 2x)
2 dist (u, vo)
dist" (p,u) +
> +
4 (10z)=-1
[dist (p. u) + dist (p, vo)]-
2
Lemma C.13. Let P be weighted point set, (0,1) and U and V be two center sets. Let t be
(10x)=-1 some integer such that U and V have t e-well separated pairs. Then for any a < 2 1 there
exists a subset S C U with size at least (k-1) such that 6(102)=-1"
(P,t U S) < cost.
(P,U) co + 4a(cost,, cost, (P, V)).
(5)
Proof. First we apply Lemma C.12. It says that we can find set D S U with size k-t containing only those points that do not form a e-well separated pair. There exists a mapping Φ : D + such that reassigning the cluster in to (DD will lead to the cost increment less than --102))-1(008 (P, U) + co V)).
Consider the abstract graph H where the nodes are the elements of U and there is a directed are from D dDD). More formally, H (U, (()) u E D)). Notice that every node of H has
27

---

Published as a conference paper at ICLR 2025
outdegree at most 1. Thus, there exists a coloring of the nodes of H with three colors, such that all ares dichromatic. Let $ denote the color set with the largest number of nodes of D. We have that S contains at least /D/3 nodes of D.
(102) (2s-1 we can arbitrarily partition S into ac parts, each of cardinality at least 3(10=)=-1- Given vertex with outdegree 1, we define the reassignment operation as follows. For all p [u], let d(u) be the center serving it. Note that deleting increases cost at most 4-(10=) -- (cost, (P,U) + co V)). By an averaging argument, there exists set such that reassigning each cluster in this set increases the cost by most da(cost,,P,, U) + cost, (P, V)). Denote this set as S and it is what we want to obtain. Thus deleting the centers in S will increase the cost by at most (c(ssst (P, U) cost, V)). Since the arcs of Hf are dichromatic, if u E S then ((u) @ So the reassignment is well-defined.
(10x)=-1
By <
Now we fix a phase in our algorithm. Let V be an a-approximate solution at the end of the phase We show that if one can delete at most centers from ui(e) such that the cost increases by factor of (1 + 12e)a, then the number of well separated pairs between sets e++) and is lower bounded.
weell separated pairs between Uo and V. By in Lemma C.13, we know that there is set S with |S| 2 i == O (2o))))()))) ), and cost. (Po, Uo \ () < cost, (Po. Uo) + 1 (cost, (Po. Uo) + cost (Po, V)). This is upper bounded by cost, (Po, Up) 12c cost. (Po. Un), because cost, (Po, V) I cost, (Pr-1. V) S OPT, s 2x cost. (Po Uo). Furthermore, there exists a set 5" with |S 2 S1/2 = 2/2 such that the cost after deleting S' from Up is upper bounded by costz(Po. Up) + 6e cost (Po. Uo). Therefore, if the minimal cost after deleting center for some E < k is larger than cost, (Po, Uo) + 6e cost, (Po, Uo), we must have 2 8/2.
Proof of Lemma C.8. Let t be the number of 2008
letting
For our algorithm, if é 0 then it does not delete any center. In this case we must have & < 1. So t z k - 211). From now on we assume & >> 0. For every < k, suppose the algorithm outputs the center set D; C Up with D2 = k- - i. If there is some < k such that
a(1 + Ge) cost. (Po. Uo) I cost (Po, Uo \ D.) S a(1 + 12c) cost, UP) U).
Denote OPT(() the minimal cost by deleting centers from Un- Then we know OPT(1 Z (1 + Ge) cost (Po, Uo) so have i > ~/2.
Otherwise, if for any < l either co, Un D:) S a01 + Ge) cost. (Po. Uo), or a(1 + 12c) cost, / (Po, U) I cost, (Po. Uo! \ D.). In this case, the algorithm picks the largest i such that the first inequality holds. And this exactly E.
Based on the above discussion, we always have 2 Ł/2 2 (a220(a log(s)) ((o())))
Ω (
). Thus t 2 k
agots (oR()))
8/c This finishes the proof of Lemma C.8.
D EXPERIMENT FOR k 5 AND k 20
In this section we give the cost and consistency curves in Figures 3 and 5 for k = 5 and l = 20. Both "ours-faithful" and "ours-heuristic" have significant lower consistency compared with the base- lines, especially for larger i and larger dataset. We also list the accumulative running time for the algorithms.
outperforms all other algorithms. As can be seen from the figure, "ours-faithful" has a comparable running time (within 150%) to all baselines, except for the case of COVERTYPE (k- = 20) where our algorithm may perform no more than times worse; Nonetheless, even for this relatively bad case of COVERTYPE with & 20, "ours-faithful" still runs in about 0.02 seconds per insertion on average, which is fast in an absolute sense. This is a reasonable per- formance given that our algorithm uses much more involved steps to maintain consistency. Indeed,
28

---

Published as a conference paper at ICLR 2025
cost for skin, k-5
cost for shuttle. km5
cost. for covertype. k=
naive
natre
halve
5.0
IV17
outs fa Entuu
3.0
6.0
IV17
ours fainnul
hurs-heuristic
hounstic
harshauniiic
4.0
6.0
1.0
2.0
0.0
250
200
400
(191)
cost for shuttle, k=20
cost for skin, k=
cost for covertype, K=
10.0
14.0
12.0
CUS neuttat
our- thiul
IV17
ve
5.0
6.0-
7.0
ours hourstic
1917
natre
oun-lattihul
25.
20.0
0475 faimiful
0475 he reuuttiiic
1917
have
8.0
6.0
3.0-
4.0
2.0
2.0-
1.0
5.0-
0.0
0.0
0.24
100
150
200
10
20
30
40
50
120
250
300
400
500
800
number of Insertione (100)
number of irsertionn (207)
number of resertons (197)
Figure 3: The cost curve over the insertions of points, for all datasets and different choices of k. We plot the curve after applying a moving average with a window size equal to 1% of the dataset size.
consistency for
consistency for SHUTTLE, kwS
consistency for COVERTYPE, ko
IV17
naive
navve
1X37
12000
12520
4000
eurs hourssc
eurs (athial
20000
3000
7530
2536
5000
50
100
150
260
250
0
10
20
30
30
60
200
360
450
500
603
number of ins.eianss (x1PP)
number of Insert ons 1=107)
number mertons (x107)
consistancy for SKIN, k-20
consistency for SHUTTLE, k-20
consistency for COVERTYPE, k--0
150000
IV37
salve
250300
nabe
turt-ftthful
125000
suroheuradi
200000
120000
30003
150200
75000
100000
30000
25000
10002
50500
52
100
150
200
30
62
120
200
200
400
500
600
numbeerot inserture
Insentors (x1.7)
insertoons (K101)
Figure 4: The consistency curve over the insertions of points, for all datasets and different choices of k.
the mentioned behavior of the running time also matches our (theoretical) running time bound. To see this, since we plug in k- 6-MEANS++, our total running time is O(nk + k.). However, the "LV17" baseline runs in roughly Ö(k + k²)) time. When k = 20, the 1.5 term starts to dominate our running time, and hence our running time curve starts to deviate from that of 1IV'
29

---

Published as a conference paper at ICLR 2025
cumulative running time for SKIN, k-5
cummulative running time for SHUTTLE, km5
COVERTYPE,
naive
nake
ours fa sursheurttt::
IV17
-0
IV17
oum-heunttte
300
500
cus-tall futhf
U117
(US i661
20
10
25
30
40
50
120
200
300
400
500
500
Inseriins (x207)
number of (x10
cumuulltivv running SKIN, km10
currilltive running time for SHUTTLF, ke
oumulstivve running time for COVERTYPE k-10
cuming Gane
CLTTLA wpw. nurerTo Sime Lun0o
U337
rake
2030
IX17
make
0ut hou--euu
1000
100
50
300
200
250
23
50
200
300
400
500
620
number maerian (x30))
number of Insertoon (x127)
sumber Insetions (430")
cumu/stive running time for SKIN, k-20
cumulative running time for SHUTTLE, k=20
cumulativv running time for COVERITPE, k-
I912
rakee
300
taies
zurs-utthhuu
10300
aurshsurattc
210
220
9000
250
0320
6050
200
160
Inserions
Figure 5: The cumulative running time over the insertions of points, for all datasets and different choices of k. æ-axis corresponds to the number of insertions and y-axis corresponds to the cumulated running.
30


Reviews:
[{"review_id": "k5CLn81OJL", "reviewer": "Reviewer_7dtW", "summary": "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).\n\nThe 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.", "questions": "If the authors can address the weaknesses described above (motivate the novelty of the results a bit more) it would help the paper.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- k-means clustering is a classic problem in ML and online algorithms for it and other variants of clustering have been an extensive topic of research.\n- It is nice that the algorithm nearly matches the lower bounds from the work of Lattanzi and Vassilvitskii.", "weaknesses": "- The paper's contributions feel a bit incremental. While there are some novel ideas required in, e.g., Algorithms 2 and 3 and their analysis, the overall framework follows that of prior work on k-median, as well as standard ideas in the literature.\n\n- The paper misses comparison to some prior work. E.g., see:\nhttps://proceedings.mlr.press/v201/bhattacharjee23b.html\nhttp://proceedings.mlr.press/v132/moshkovitz21a/moshkovitz21a.pdf\nhttps://proceedings.mlr.press/v117/bhaskara20a.html\n\nAs far as I can tell, these works do not study recourse/consistency explicitly, but they have very similar reasons for requiring to depend on \\log \\Delta, etc.\n\n- The experiments do not seem to add much value to the paper (and seem disconnected); are there simplifications that are made there that perhaps would make the algorithms easier to implement in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lZJ15xmID9", "reviewer": "Reviewer_d1TJ", "summary": "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. \n\nThis 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. \n\nThis 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. \n\nThe 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. \n\nThe 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.", "questions": "Can you confirm (to check my understanding) that main strength of the result shown in lemma 3.3. is that the consistency does not depend on k? If i understood the setting correctly, obtaining a consistency of $O(mk)$ would always be trivial (just pick $k$ new centers on each point).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper achieves a very exciting overall result -- $(1+\\epsilon)$-approximation with $O(k)$-consistency is more or less the best we can reasonably expect for this problem -- all other improvemenets would only be in shaving down constants. Furthermore, the algorithm is reasonably efficient -- it is polynomial in all aspects except for $\\epsilon$ (which can always be set to even a reasonably large value and still achieve interesting results).", "weaknesses": "I think the paper could use improvement on its presentation. I'd suggest moving the discussion of Lemma 3.3 further up in the paper and ensuring that the reader can easily grasp the intuition and definition behind robust sequences. I also think that it might help to simply choose a value of z for the main body and defer details of the general proof to the appendix. \n\nFinally, I found the constant references to Fichtenberger et. al. in section 4 cumbersome. I understand that many of the main ideas are taken from that paper, but this can simply be addressed in the related works section. The way this section is currently written gives the reader the impression that they should read Fichtenberger first, and I don't think this should be necessary if the intuitions behind the definitions are explained properly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0mwqCbmqUO", "reviewer": "Reviewer_aeE5", "summary": "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.", "questions": "1) In the coreset definition 2.4 it is given that $\\overrightarrow{S} \\subseteq \\overrightarrow{P}$. However, points in a coreset can have higher weights than original data points. Am I missing something? Please clarify.\n\n2) In the experiments in your method, is the cost calculated over the coreset, or centers are selected using coreset and then cost is calculated on original data?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) Online clustering is a practically more important problem and the idea of 'consistency', which loosely tries to address the problem with not allowing an algorithm to change decision in an online setting, has gained significant attention in the recent past. As such the paper will be of considerable interest and significance.\n2) The paper generalizes and improves the theoretical results for online clustering problem. The paper does a good job of describing the high-level algorithm and also the technical challenges faced in extending as well as improving the results. Although many ideas/definitions are borrowed from existing works the paper does a good job of combining these to address the challenges. I could not go through all the proofs, but the paper overall appears technically solid.\n3) Experimental results show the algorithm achieves much better 'consistency' than the baselines while incurring comparable costs.", "weaknesses": "1) The paper is not easy to follow. The notations are dense. Also, it requires some familiarity with existing work to understand the paper as it relies heavily on ideas from the related work. Moreover, there are many typos throughout the paper. \nFor e.g.:\nLine 86 bonded instead of bounded\nLine 144 and 145 approximation and approximate are spelt incorrectly\n\n2) Experiments could have used other baselines for online k -means clustering. Also, what is the time required empirically to make updates at every step of the online algorithm could be included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)