Improved Learning-augmented Algorithms for k-means and k-medians Clustering
Authors: Thy Dinh Nguyen
Anamay Chaturvedi
Huy Nguyen
Venue: ICLR 2023 poster (2023)
Keywords: clustering
learning-augmented algorithms

Abstract: We consider the problem of clustering in the learning-augmented setting. We are given a data set in $d$-dimensional Euclidean space, and a label for each data point given by a predictor indicating what subsets of points should be clustered together. This setting captures situations where we have access to some auxiliary information about the data set relevant for our clustering objective, for instance the labels output by a neural network. Following prior work, we assume that there are at most an $\alpha \in (0,c)$ for some $c<1$ fraction of false positives and false negatives in each  predicted cluster, in the absence of which the labels would attain the optimal clustering cost $\mathrm{OPT}$. For a dataset of size $m$, we propose a deterministic $k$-means algorithm that produces centers with an improved bound on the clustering cost compared to the previous randomized state-of-the-art algorithm while preserving the $O( d m \log m)$ runtime. Furthermore, our algorithm works even when the predictions are not very accurate, i.e., our cost bound holds for $\alpha$ up to $1/2$, an improvement from $\alpha$ being at most $1/7$ in previous work. For the $k$-medians problem we again improve upon prior work by achieving a biquadratic improvement in the dependence of the approximation factor on the accuracy parameter $\alpha$ to get a cost of $(1+O(\alpha))\mathrm{OPT}$, while requiring essentially just $O(md \log^3 m/\alpha)$ runtime.

Published as a conference paper at ICLR 2023
IMPROVED LEARNING-AUGMENTER ALGORIHTM FOR K-MEANS AND K-MEDIANS CLUSTERING
Thy Nguyen Anamay Chaturvedi ; Huy Lê Nguyên
Khoury College of Computer Sciences, Northeastern University (nguyen.thy) chaturvedi, .a hu. nguyen |northeastte..ed
ABSTRACT
We consider the problem of clustering in the learning- deaming-augmented setting. We are given data set in d-dimensional Euclidean space, and a label for each data point given by predictor indicating what subsets of points should be clustered together. This setting captures situations where we have access to some auxiliary informa- tion about the data set relevant for our clustering objective, instance the labels output by neural network. Following prior work, assume that there at most an a E (0, c) for some e < I fraction false positives and false negatives each predicted cluster, in the absence of which the labels would attain the optimal clustering cost OPT. For a dataset size m, we propose a deterministic k-means algorithm that produces centers with improved bound on the clustering cost compared to the previous randomized state-of-the-art algorithm while preserv- ing the (dm log m) runtime. Furthermore, our algorithm works even when the predictions are not very accurate, i.c., our cost bound holds for up to 1/2, an im- provement from a being at most 1/7 in previous work. For the k-medians problem we again improve upon prior work by achieving a biquadratic improvement in the dependence of the approximation factor on the accuracy parameter to get a cost (1 + OPP)) while requiring essentially just O(md log m/a) runtime.
INTRODUCTION
In this paper we study k-means and k-medians clustering in the learning- -aggeenee setting. In both these problems we are given an input data set of m points d-dimensional Euclidean space and an associated distance function dist(:.).. The goal is to compute set C of & points in that same space that minimize the following cost function:
cost(P,C)
=E min dist(p.c:)
pEP sE(R]
In words, the cost associated with a singular data point its distance to the closest point in C, and the cost of the whole data set the sum of the costs of its individual points.
In the k-means setting dist(z, y) := || - y||², i.e.. the square of the Euclidean distance, and in the k-medians setting we dist(z; y) : || y|1. although here instead of the norm of o y, we can in principle also use any other distance function. These problem are well-studied in the literature of al- gorithms and machine learning, and are known be hard to solve exactly (Dasgupta) 2008). or even approximate well beyond certain factor (Cohen- Addad & Karthik C. S. 2019). Although approxi- mation al algorithms are known to exist for this problem and are used widely practice, the theoretical approximation factors of practical algorithms & Rajasekaran (2010) and the (In ->paaproxination in Arthur & Vassilvitskii (2006). Mcanwhile, the algorithms with relatively tight approximation factors do not necessarily scale well in practice (Ahmadian et al. 2019).
be quite large, e.g., the 50-approximation in Song
To overcome these computational barriers, Ergun et al. 2002 proposed ting where we have access to some auxiliary information about the input data set. This is motivated
marninggammmeeeteed set-
Eguual contribution. All three authors were supported in part by NSF CAREER grant CCF-175074 and NSF grant CCF-1909314.

---

Published as a conference paper at ICLR 2023
by the fact that in practice expect the dataset of interest to have exploitable structures relevant to the optimal clustering. For instance, a classifier's ' predictions of points in a dataset can help group similar instances together. This notion was formalized in Ergun et al. (002) by assuming that have access to a predictor in the form of a labelling P = P1 .... U Pk (all the points in P, have the same label i [R]), such that there exist an unknown optimal clustering P Pf U... U PE.
an associated set of centers C' = (ci...., .g)) that achieve the optimally low clustering cost OPT (
EieR cost(P:, {c]) = OPT), and a known label error rate a such that:
P. PAOPII (1 a) max (.l.
In simpler terms, the auxiliary partitioning (P1..... Pt)) is close to some optimal clustering: each predicted cluster has at most an a-fraction of points from outside its corresponding optimal cluster, and there are at most an e-fraction of points in the corresponding optimal cluster not included in predicted cluster. The predictor, in other words, has at most a false positive and false negative rate for each label.
Observe that even when the predicted clusters P. are close to a set of true clusters P. in the sense that the label error rate a is very small, computing the means or medians of P/ can lead arbitrarily bad solutions. It is known that for k-means the point that is allocated for an optimal cluster should simply be the average of all points in that cluster (this can be seen by simply differentiating the convex 1-mean objective and solving for the minimizer). However, single false positive located far from the cluster can move this allocated point arbitrarily far from the true points in the cluster and drive the cost up arbitrarily high. This problem requires the clustering algorithms to process the predicted clusters in a way so as to preclude this possibility.
Using tools from the robust statistics literature, the authors of Ergun et al. (2022) proposed ran- domized algorithm that achieves a (1 - 20xx) aapproximmiiioo given a label error rate a < 1/7 and a guarantee that each predicted cluster has 2 ($) points. For the k-medians problem, the authors of Erguun et al. (002)) also proposed an algorithm that achieves (1 + appproxxxintnonnn each predicted cluster contains Ω
( points and label rate most O a4
where the big-Oh
& log +
notation hides some small unspecified constant, and a'
The restrictions for the label error rate to be small in both of the algorithms of Ergun et al. (2022)
lead us investigate the following question:
Is it possible to design a k-means and a k-medians algorithm that achieve (1 + a)-appoxximate clustering when the predictor is not very accurate?
1.1 OUR CONTRIBUTIONS
In this work, not only give affirmative answer to the question above for both the k-means and the k-medians problems, our algorithms also have improved bounds on the clustering cost, while preserving the time complexity of the previous approaches and removing the requirement on a lower bound on the size of each predicted cluster.
For learning- augmented k-means, we modify the main subroutine of the previous randomized algo- rithm to get a deterministic method that works for all a < 1/2, which is the natural breaking point (as explained below). In the regime where the k-means algorithm of Ergun al. (2022) applies, we get improve the approximation factor to 1 + 7.7a. For the larger domain a E [0, 1/2], we derive a more general expression as reproduced in table [ Furthermore, our algorithm has better bound on the clustering cost compared to that of the previous approach, while preserving the O(md log m) runtime and not requiring a lower bound on the size of each predicted cluster.
Our k-medians algorithm improves upon the algorithm in Ergun et al. (2022) by achieving for a < 1/2, thereby improving both the range of a as well as the dependence of the approximation factor on the label error rate from bi-quadratic to near-linear. For success probability 1
(1 + (o(a))-approxmmall
our runtime is 0( O md log m & Alog(k/4) setting 8 1/poly(k (A)). we have just a logarithmic dependence in the cun-time on kt as opposed to a polynomial dependence.
log (1-2ajō log k), ) so we see that by
a
2

---

Published as a conference paper at ICLR 2023
Work, Problem
Approx. Factor
Label Error Range
Time Complexity
Ergun et al. (2022), k- M-Means
+ 20a
10log 1/7)
( log m) ( log m)
V' [0.1/2)
Algorithm
k- Means
+ [1-2a[1-a)
5a 5a-2a²
7.7a
10,1/7)
O m+ poly(k, log m)) md 3 m log
Ergun al. 2022), k-Medians
Ō((kk)(//)
small constant
Algorithm
k- Medians
7+ 1000 10e² 2
[0, 1/2)
[1-a][1-aa)
log
k-means and k-medians algorithms. We recall that m is the data set size, is the ambient dimension, the label error rate, and 6 the failure probability (where applicable). The success probability of the k-medians algorithm of |Ergnn et al. (2022) is - poly(1/k). The Ô notation hides some log factors to simplify the expressions.
Table I: Comparison of
Upper bound on a. Note that if the error label rate a equals 1/2, then even for three clusters there no longer a clear relationship between the predicted clusters and the related optimal clusters for instance given three optimal clusters PT P2. P3 with equally many points, if for all i E [3]. the predicted clusters P. consist of half the points in P. and half the points ((+1) mod 3 then the 1/2 is achieved, but there is no clear relationship between Pt and P.. In other
label error rate words, it is not clear whether the predicted labels give any useful information about an optimal clustering. In this sense, 1/2 is in way natural stopping point for this problem.
1.2 RELATED WORK
This work belongs a growing literature on learning-ann -aggminte algorithms. Machine learning has been used to improve algorithms for a number of classical problems, including data structures
(Kraska al. 2018 Mitzenmacher 2018 Lin et al.
2022). online algorithms (Purohit al.
2018),
graph algorithms (Khalil et al.) 2017 Chen et al.
2022a b). computing frequency estimation (Du
al., (02T), caching (Rohatgil 2020) Weil 2020).
support estimation (Eden al. 202I). We
refer the reader to Mitzenmacher & Vassilvitskii 2020) for an overview and applications of the
framework.
Another relevant line of work is clustering with side information. The works Balcan & Blum (2008); Awasthi et al. (2014); Vikram & Dasgupta (2016) studied an interactive clustering setting where an oracle interactively provides advice about whether not to merge two clusters. Basu et al. (2004) proposed an active learning framework for clustering, where the algorithm has access to a predictor that determines if two points should or should not belong to the same cluster, Ashtiani et al. 2016) introduced a semi-supervised active clustering framework where the algorithm has access to predictor that answers queries whether two particular points belong in optimal clustering. The goal is to produce (1 + a) --aprooxie clustering while minimizing the query complexity to the oracle.
Approximation stability, proposed in Balcan et al. (001)), is another assumption proposed to cir- cumvent the NP-hardness of approximation for k-means clustering. More formally, the concept of (c, a -tt-bbbilytyy requires that every c-approximate clustering is a-close to the optimal solution in terms of the fraction of incorrectly clustered points. This is different from our setting, where at most an fraction of the points are incorrectly clustered and can worsen the clustering cost arbitrarily.
Gamlath et al. (022) studies the problem of k-means clustering in the presence of noisy labels, where the cluster label of each point created by either an adversarial or random perturbation of the optimal solution. Their Balanced Adversarial Noise Model assumes that the size of the symmetric difference between the predicted cluster P. and optimal cluster P is bounded by al P.). The algo- rithm uses a subroutine with runtime exponential in and for fixed a < 1/4. In this work, we have different assumptions the predicted cluster cluster P. and the optimal cluster P. Moreover, our focus is on efficient algorithms practical nearly linear-time algorithms that can scale to very large datasets for k-means and k-medians clustering.
3

---

Published as a conference paper at ICLR 2023
2 k-MEANS
Algorithm Deterministic
k-Means Clustering
Require: Data set P of m points, Partition P P1 U... Ps from predictor, accuracy parameter
for i [k] do
for j [d] do
Let wi, be the collection of all subsets of (1 a)m, contiguous points in Pt,j
Jt, t argmin cost (2, Z) argminzew.. ExEz" 2²
(Ex e²)²
end for Let a = (Tij)sE(4) end for Return (ā }+}
We briefly recall some notation for ease of reference.
Definition 1. We make the following definitions:
1. The given data is denoted as P, and == [P] The output the predictor is partition (P,,... Pk) of P. Further, m, == Pi].
2. There exists an optimal partition (Pr...., PŁ) and centers (ct...., Gx) such that Eie(h cost P of) = OPT, the optimally low clustering cost for the data set P. Further- more, m. == |P.|. I. For each cluster E [K], denote the set of true positives P. n P, = Qi. Recall that |Q:1 (1 a) (a), (P:)), for some 1/2.
3. We denote the average of a set X by X. For the sets X, and P, we denote their projections onto the j-th dimension by Xi, and P.,j, respectively.
Before we describe our algorithm, recall why the naive solution of simply taking the average of each cluster provided by the predictor is insufficient. Consider P., the set of points labeled i by the predictor. Recall that the optimal 1-means solution for this is its mean, P.. Since the predictor not perfect, there might exist a number of points in P. that are not actually in P.. Thus, if the points in P. P.' are significantly far away from P.,. they will increase the clustering cost arbitrary if we simply use P; as the center. The following well-known identity formalizes this observation. Lemma Inaba et al. (1944)) Consider set X C Rd of size and E Rd.
cost X, c) = min cost(X,c')) n ||c - X 1| = cost(X, X, X) + -11
d'ER4
Ideally, we would like to be able to recover the set Qi P. n P and use the average of Qi as the center. We know that IQ, P. I am,.. By lemma it is not hard to show
that cost(P,, Qi) & x (1+ cost(P:, (1+ 1-a approximation for the problem.
[ r-a cost cf), which also implies
Lemma 3. For any purtition J1 J2 of set J of size n, if 2 (1 A)n, then [J - 11 (1-X)m J..
Since we do not have access to Qi, the main technical challenge is to filter out the outlier points in P; and construct a center close to Q. Minimizing the distance the center to Q, implies reducing the distance to ot as well as the clustering cost.
Our algorithm for k--maas,, algorithm [ iterates over all clusters given by the predictor and finds set of contiguous points of size (1 a m) with the smallest clustering cost in each dimension. At the high level, our analysis shows that the average of the chosen points, 4 is not too far away from that the true positives, Qi.-- This also implies that the additive clustering cost of I, would not be too large. Since analyze the clustering cost by bounding the cost in every cluster i and
4

---

Published as a conference paper at ICLR 2023
dimension j, for simplicity will not refer to specific i and j when discussing the intuition of the algorithm. The proofs of the following lemmas and theorem are included in the appendix.
Note that there can be multiple optimal solutions in the optimization step. The algorithm can either be randomized by choosing an arbitrary set, or can also be deterministic by always choosing the first optimal solution. Lemma 4 shows that the optimization step guarantees that J has the smallest clustering cost with respect to all sets of size (1 a m, in P..j-
Lemma 4. For all j E [d], let wh, be the collection of all subsets of a)mm points in P.g. Then
(Ist Teg)
min cost (Z', (',).
2' Z'EW!
Since we know that [Q,y1 2 (1 a ), it can be shown from lemma 4 that the cost of the I is smaller than that of Qi.. More precisely,
(1-a)m, cost((Qi,) Qi.))
cost Tep) S 1Qil
With this fact, are ready to bound the clustering cost by bounding [ Qi.i 2
Tr, Qig1 S Tij Ii,j O Qi,1 + 2TT,, n Qi. - Qi,l²
Using lemma 3 we can bound It,j - I, n 1i, and [4, nQ - 2i, respectively by
cost [i.. Ti.j) and cost(Qi.j. Qi,)). Combining this fact with eq. (1). we can bound, [T.j Qi.
by cost( (ii.) Qi.))-
Lemma 5. The following bound holds:
4xx
cost Qi,5) 1Qi
T
Qi.
2a
Notice that lemma 5 applies any in way with cost smaller than the expected cost of subset of size (1 a amm; drawn uniformly at random from Qi,- Instead of repeatedly sampling different subsets of Qi,, and returning the one with the lowest clustering cost, the optimization step not only simplifies the analysis of the algorithm, but also guarantees that we find such a subset efficiently. This is the main innovation of the algorithm.
In the notations of lemma 2 we can consider -T,,, Pij = X,m; = Thus, we want to
bound P.j Ii. by cost T
mi to achieve a (1 + (0la)))aaproximaatio Recall that we bound
[ Qu,1* 2 by cost(Q., ( lemma
In lemma 6 we relate cost(Qi.,s Qú,) to cost(P P.
Q.
as follows,
1
cost Pi.
m. PP; Qiji cost(Qu.j Qig)
a
cost(
1.3 T
We can then apply lemma to bound IPT Ii.s by Lemma 6. The following bound holds:
mi
T. s cost(Pr. Pi.) ( 1-a (1-20) 20) a)) /m]
4a
P
Applying lemma 6 and lemma 2 to all i [K],] E [d]. we are able to bound the total clustering cost.
Theorem 7. Algorithm I is a deterministic algorithm for k-means clustering such that given a data set P Rixdd and partition (Pı,..., Pk) with error rate < 1/2, outputs
(1+ (1 (1-2a)(1-a) -approximatioo in time O (dm logm).
Corollary 8. For a S 1/7, algorithm aachieves clustering cost of OPT.

---

Published as a conference paper at ICLR 2023
3 K-MEDIANS
In this section we describe our algorithm for ical bound on the clustering cost and the run- run-time. Our algorithm works for ambient spaces equipped with any metric dist((,-) for which it is possible to efficiently compute the geometric median, which the minimizer the 1-medians clustering cost. For instance, is known from prior work (Cohen et al. (016) that the geometric median with respect to the f--metric can be efficiently calculated, and appealing to this result as a subroutine allows us to derive a guarantee for learning-auge -entmneeed k-medians with respect the Eg norm.
k-medians clustering and a theoret-
Theorem 9. (Cohen el al. (2166) There is algorithm that computes a (1 + -)approoximation to the geometric median of a set of size n in d-dimensional Euclidean space with respect to the & distance metric with constant probability Onddlog (n/c)) time.
Looking ahead at the pseudocode of algorithm 2 we see that to eventually derive bound on the time complexity, we would need to account for adjusting the success probability in the many calls theorem g
Corollary 10. It follows from theorem 9 that with probability 1
2k have that for all [R],
cost P1 is a (1 + appprrxmmmiiioonnn to the optimal 1-median cost for P3 \ P/ while taking time Omm,dlog" (m./7) (og(Rk/0) Rk)5)).
We refer the reader to definition I for all notation that is undefined in this section; the only additional notation we introduce is the following definition.
Definition 11. We make the following definitions:
1. We denote the optimal clustering cost of P by OPT, and the optimal 1-medion clustering cost of P. by OPTs with which notation we have that Σie(n) OPT, = OPT.
2. We denote the distance dist(x, y) between two points by || 1 y|1-
We now describe high-level run of our algorithm. Algorithm oppeatess sequentially on each cluster estimate; for the cluster estimate P.. it samples a point x E P. uniformly at random, and removes from P. the [om;]-man points that lie furthest from x. then computes the median of the clipped set, which is where we appeal to an algorithm for the geometric median, for instance theorem 9 when the ambient metric for the input data set the l metric. turns out that this subroutine already gives us a good median for the cluster P." with constant probability (lemma 14); to boost the success probability we repeat this subroutine some R-many times (the exact expression given in the pscudocode and justified in lemma [5], and pick the median with the lowest cost, denoted G Collecting the è across E [k), we get our final solution (c,....,4
Algorithm 2 augnnnnee- k-Medians Clustering
Require: Data set P of m points, Partition P = Pi U... Ps from predictor, accuracy parameter
< 1/2
for i E [k] do
Let R
=
2
24 log
for j
E [ do
Sample
P. u.a.r Let P. be the [ami] points farthest from x
द: median of P, P/.
end for
Let & be the é/ with minimum cost
end for Return (a fa...., }+}
Although algorithm itself is relatively straightforward, the analysis turns out to be more involved. We trace the proof at a high level in this section and mention the main steps, and defer all proofs to the appendix.

---

Published as a conference paper at ICLR 2023
We see that it would suffice to allocate a center that works well for the true cluster P but we only have access to the set P. with the promise that they have a significant overlap (as characterized by a). Fixing an arbitrary true median cf one key insight is that the "false" points, i.c. points in PAP. will only significantly distort the median if they happen to lie far from q. there were a way to identify and remove these false points which lie far from ej. then simply computing the geometric median of the clipped data set should work well.
By direct application of Markov's 's inequality is possible to show that point picked uniformly at random will in fact lie at a distance on the order of the average clustering cost OPT;/n with constant probability, as formalized in lemma 12
Lemma 12.
With probability 2 ||
olll S 20PT:/m..
As we will condition on this good event holding, it will be convenient to introduce the notation E. Definition 13. We let & denote the event that || x <f S 20PT./m4.
Having identified good point z to serve as proxy for where the true median cf lies, we need to figure out good way to clip the data set so as to avoid false points which lie very far from et We observe that since there are guaranteed to be at most [an]] -many false points, if we were to remove the [an] -many points that lie farthest from x (denoted P.), then we either remove false points that lie very far from ef. or true points (P: P.) which are at the same distance from ci as the remaining false points (the points in PAA(P) U P.). In particular, this implies that the impact the remaining false points is roughly dominated by the clustering cost of equal number of true points, and are able to exploit this to show that the clustering cost of P with respect to its own median estimate & is already close to that of the true center P."
Lemma 14. Conditioned on E, (os 2).)) I (1 + 5PPOPT.
Since the event & that the randomly sampled point is close to true median of is true only with constant probability, we boost the success probability by running this subroutine some R times and letting 6₁ be the median estimate with respect which the respective clipped data set had the lowest clustering cost.
( log (2#) many repetitions, with probability at least 1 Lemma 15. For R = 0 (1-20)
22. we
have that cost(P: (P: G), (1 OPPT.
We see from lemma 21 that the set P.P., differs from the true positives P. n P by sets of size most [an]. It follows that as long as the distance between & and of is on the order of OPT, they will not influence the clustering cost by more than O(oOPT,) additive term, which we will be able to absorb into the (1 + O())) multiplicative approximation factor. We formalize this in 166
Lemma 16. If cost(P: G2 < (1 +1+ 5a) then || ct I
2+5a OPT. (I (1-2n)
We finally put everything together to show that the clustering cost of the set of true points P. P with respect to the estimate & is only at most an additive (aOPT,;) more than the cost with respect the true median oi. The key technical point in the analysis is that can only appeal the fact that the cost of PA is close to OPT, and we cannot directly reason about ? apart from appealing lemma 16
Lemma 17. With probability 1 - 5/k, (ost(P, P. cost(P: n P (5a++100 100 P)PPT:
We can now derive our main cost bound stated in lemma for the mislabelled points Pr, which were not accounted for during our clustering. Again, from lemma 16 it suffices to appeal to the fact that the estimate è lies within an O(aOPT,/n) distance of the true median ot
[8 Doing only requires that we account
Lemma 18. With probability 1 8/k, cost(P;; < (1 ca)
7410a 20a (1-a)(1-2a)
We now formalize our main cost bound, success probability and run-time guarantees in theorem 19 Theorem 19. There is algorithm for k-medians clustering such that given data set P and labelling (Pı...., Pk) with error rate a < 1/2, it outputs a set of centers C (Gi 4
7

---

Published as a conference paper at ICLR 2023
such that Eiex cost(P:: .) 1 (1 + ca)OPT, for ++10a-10aa and does in time (1- (1-a)(1-2o))
O (nd log" (m)) log (log(k/0) (I-2ax6
log (3))
Proof. We from lemma 18 that by applying our subroutine for 1-median clustering each labelled partition Ps. we get a center é; with the promise that with probability 1 cost P. G)
(1 + O.,; By the union bound, it follows that with probability 1 - 6, ΣiE(s) cost Pi (2) S
(1 + ca)OPT, (1+ + ca)OPT. Since P Pt U..... Pg. it follows that cost C) (1+.0) (1+o))
The time taken to execute the 1-median clustering subroutine on partition P. is R(m,d + O(m; mo) + (om, (m,/7) (kk/))) + mi,d). This because we have iterations, in each of which we first compute the distances of all my points from the sampled point in time mid, followed by sorting the m, many points by their distances time 0(m; log m2), followed by Olog((M) (Rkkkkk)))))))))))))) many iterations of the median computation for the clipped sets (wherein we appeal to corollary 10). followed by a calculation of the 1-median clustering cost achieved in time m,d. We
recall that we set R O (I- log )) Further, we note that the expression for the upper bound on the time complexity is convex in m,, so if we were to denote the value of this expression on set of size m, by T (m,)), it follows that ΣiE[N] T(m,) - T [{E(A) mi) = T(m). Putting everything to-
gether, we get that the net time complexity is O 1-2a md log (=) log (1122a)0
(log(k//)) log (#) L
EXPERIMENTS
In this section, we evaluate algorithm D and algorithm on real-world datasets. Our experiments were done a 19-12900KF processor with 32GB RAM. For all experiments, we fix the number of points to be allocated & = 10, and report the average and the standard deviation error of the clustering cost over 20 independent runs
Datasets. We test the algorithms on the testing set of the CIFAR-10 dataset (Krizhevsky et al., 2009) (m 10 d 3072), the PHY dataset from KDD Cup 2004 (KDD Cup 2004). and the MNIST dataset (Deng 2012 (m = 1797, d = 64). For the PHY dataset, we take m = I0 random samples to form our dataset (d 50).
Predictor description. For each dataset, we create a predictor by first finding good k-means and k-medians solutions. Specifically, for k-means we initialize by kmeans++ and then Lloyd's algorithm until convergence, For k-medians, we use the "alternating" heuristic (Park & Jun] 2009) of the k-medoids problem to find the center of each cluster. In both settings, we use the label given to each point by the k-means and k-medians solutions to form the optimal partition (Pr..... .......Pi.. Pi.) (recall we set k 10). In order to test the algorithms' performance under different error rates of the predictor, for each cluster i, we change the labels of the om, points closest to the mean (or median) to that of a random center. For every dataset, we generate the set of corrupted labels (PI...., Pio) for a from 0.1 to 0.5. Furthermore, we use the same set of optimal partition (Pi,.... ..... Pro across all instances of the algorithms. By fixing the optimal partition, we can investigate the effects of increasing on the clustering cost.
Guessing the error rate. Note that most situations, we will not have access to the error rate a and must try out different guesses of a then return the clustering with the best cost. For algorithm algorithm 2 and the k-medians algorithm of Ergun et al. (2022), we iterate over 15 possible value of a uniformly spanning the interval (0.1, 0.5). For the k-means algorithm of Ergun et al. (2022). the algorithm is defined for a < 1/5 (not to be confused with the assumption that a < 1/7 for the bound on the clustering cost). Thus, the range |0.1, for the algorithm.
1/5]
Baselines. We report the clustering costs of the initial optimal k-means and k-medians solution (Pi,.., Pio) along with that of the naive approach of taking the average and geometric median of each group returned by the predictor, e.g., returning (Pı,..., Pio) for k-means. The baselines help us see how much the clustering cost increases for different error rate a. The clustering cost
'The repository is hosted atggghhi.ccm//yyyyyyyyelllllCaaa
8

---

Published as a conference paper at ICLR 2023
CPT
OFf
2111
Presider
Piesktor
1A-
Rur durd Sempling
Random Sempling
Ergan, Jon,
Eqgun, Jan,
2.12
2.10
61
Error rade
Exrce 1800
(c) PHY
(a) CIFAR-10
(b) MNIST
Figure Experimental comparison of algorithm with prior work and baselines for k-Means
Eqgin.
Out
0.3
04
03
04
(a) CIFAR-10
(b) MNIST
(c) PHY
Figure 2: Experimental comparison of algorithm 2 with prior work and baselines for k- k-Medians
of the algorithm without corruption can also be seen as a lower bound on the cost of the learning- augmented algorithms. Following [Ergn et al. (2022), use random sampling as another baseline. We first randomly select a g-fraction of points from each cluster for varied from 1% to 50%. Then, we compute the means and the geometric medians of the sampled points calculate the clustering cost. Finally, we return the clustering corresponding to the value of with the best cost.
We use the implementation provided in Ergun al. (2022) for their k-means algorithm. Although both our k-medians algorithm and the algorithm in Ergun et al. (2022) use the approach in Co- hen al. (2016) as the subroutine compute the geometric median in nearly linear time, we use Weiszfeld's algorithm implemented Pillutlla et (2022), well-known method to compute the geometric medians, for the k-medians algorithms. To generate the predictions, we use Pedregosal al. (011);;
C (2021) for the implementations of the k-means and k-medoids algorithms, and the code provided in Ergun et al. (2022) for the implementation of their k-means algorithm.
For algorithm 2 we can treat the number of rounds R as a hyperparameter, We set R = 1; as shown below, this is already enough to achieve good performance compared to the other approaches.
4.1 RESULTS
In Figure I we omit the Sampling and the Prediction approach for the PHY dataset as they have much larger clustering cost than ours and the k-means algorithm Ergun et al. (022).. For the CIFAR-10 10 dataset, we observe that the approach in Ergun et al, (2022) has slightly better clustering costs as a increases. For MNIST dataset, our approach has slightly improved costs across values of a. For the PHY dataset, observe that algorithm is comparable the Ergun et al. (2022).
In summary, the mean clustering cost the two auggeettd algorithms are similar across the datasets. It is important to note that our algorithm achieves similar clustering cost to that of Ergun et al. (2022) without any variance as is a deterministic technique.
Figure 2 shows that our k-medians algorithm has the best clustering cost across all the datasets.
We also observe that the sampling approach outperforms the approach of Ergun et al. (2022) for the CIFAR-10 10 and the MNIST datasets. This is expected since the latter algorithm sample random subset of a fixed size in each cluster while the baseline approach samples subsets of different sizes and uses the with the best cost.

---

Published as a conference paper at ICLR 2023
REFERENCES
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k- means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4): FOCS17-97, 2019.
David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. Advances in neural information processing systems, 29, 2016.
Pranjal Awasthi, Maria Balcan, and Konstantin Voevodski. Local algorithms for interactive cluster- ing. In International Conference Machine Learning, pp. 550-558. PMLR, 2014.
Maria-Florina Balcan and Avrim Blum. Clustering with interactive feedback. In International Conference Algorithmic Learning Theory, pp. 316-328. Springer, 2008.
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Clustering under approximation stability. Journal of the ACM (JACM), 60(2):1-44 2013.
Sugato Basu, Arindam Banerjee, and Raymond J Mooney. Active semi-supervision for pairwise constrained clustering. In Proceedings of the 2004 SIAM international conference on data mining, pp. 133-344. SIAM, 2004.
Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang, Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp. 2022a.
PMLR,
Justin Y Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David Woodruff, and Michael Zhang. Triangle and four cycle count- ing with predictions in graph streams. In International Conference on Learning Reprexentations, 2022b. URL Dettpp:://pperrvvieee neteeeewwwwweeeeeeeeeeeee..eeeee wwttt//ormmmideeeeme
5gN9I0
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. CoRR,
2016. URL aattp://arxiv/
/bs/
1606.05221 05225
Vincent Cohen-Adde and Karthik C. Inapproximability clustering in Ip metrics. In David Zuckerman (ed.), 60th IEEE Annual Symposium Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pp. 519-539. IEEE Computer Society, 2019. doi: 10.1109/FOCS 2019,00040 00040
URL http:pps///.....rr/o/00///////// 111p://....9////..220
Sanjoy Dasgupta. The hardness k-means clustering. Department of Computer Science and Engi- neering, University of California, San Diego, 2008.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 19(6):141-12, 2012.
Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In Marina Meila and Tong Zhang (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pp. 2860-2869. PMLR, 18-24 Jul 2021. URL https:
//proceddings.. mlx www.s/peesslll... http:111///....mmmm...
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning- support estimation sublinear time. arXiv preprint 110.::2006608366 2021.
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou. Learning augmented SkS-means clustering. In International Conference on Learning Representations, 2022. URL
https:://penreviiee net http:///www....ooooooooooooootaa
10

---

Published as a conference paper at ICLR 2023
Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi- Fard, and Ola Svensson. Approximate cluster recovery from noisy labels. In Conference on Learning Theory, pp. 1463-1509. PMLR, 2022.
Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted voronoi diagrams and ran-
domization to variance-based k-clustering. In Proceedings of the tenth annual symposium on Computational geomelry, pp- 332-339, 1994.
KDD Cup 2004. Kdd cup 2004. wts.th/ss/ssmooo...ccococ...uuup 2004. Ac- cessed: 2022-09-28.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. Proceedings of the 2018 international conference on management of data, pp. 489-504 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009.
Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Interna- tional Conference on Machine Learning, pp. 13431-13440, PMLR, 2022.
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. Advances in Neural Information Processing Systems, 31, 2018.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions.
CoRR,
abs/2006.09123 2020. / wttp:///.gggbbbb/......./ wwtpab/.......... 09123
Hae-Sang Park and Chi-Hyuck Jun. simple and fast algorithm for k-medoids clustering. Expert systems with applications, (662):3333-33411 2009.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust Aggregation for Federated Learn- ing. IEEE Transactions on Signal Processing, 70:1142- 154, 2022. doi: 10. 109/TSP.22.... 3153135.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018
Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. Proceed- ings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss, pp. 1834-1845. SIAM, 2020.
Scikit-I eam-Contrib Sciithlam--ommrhhkkkk---aaeeett Seikit-leam contrib estimators, 2021.
Mingjun Song and Sanguthevar Rajasekaran. Fast algorithms for constant approximation k-means clustering. Trans. Mach. Learn. Data Min., 3(2):67-79, 2010.
Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hierarchical clustering, In International Conference on Machine Learning, pp.
PMLR, 2016.
Alexander Wei. Better and simpler deamingg-uugmette online caching. Approximation, Ran- domization, and Combinatorial Optimization. Algorithmss and Techniques (APPROX/RADOM 2020). Schloss Bagstuul-Leibbiz-Zeee für Informatik, 2020.
11

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 MISSING PROOFS FOR k-MRANS
Lemma 3. For any partition J1 U.22 of set c. R of if (1 X)n, then |J J112
(1-A)m J.)
A
Proof. We know =1|=(11 z)n, [J2] on for some S X. follows that
J = (1 JJ + xJ2
| Jıl x|J2 - J1l
and
J - J2l (1 [-))]]]- - J1l
|J - J2l 1 - -
Jıl.
We now observe that we can write
cost(J, J) = cost [1, J) + cost((2z, J)-
and recall the identity
cost(Jb, J] = cost (Jb, Jb) + |bb |J - J
for b {0, 13. It then follows that
(J, 2 | - | - - + J2l [ Jz
(1 - x)m[J - 1 2 + +nn[ Jz22
(1- = - J,
J -, -
x
(1 x)m | 2112
(1 X)n
[ J112
+ JJ J1
cost(J,J)
(1 A)n
Lemma 4. For all i E [k], E [d], let wh, be the collection of all subsets of (1 a)m; points in Pi.. Then
cost Ttg) min cost cost(Z', (Z',Z') Z'EW',
Proof. Suppose Hi argminzee', cost(Z', ".)).. If I1,5 Wij then are done since we know:
cost(Lu, It.)) = min cost Z, Z)
zEw;
If The & Wi.i let and b be the minimum point and maximum points in T'.j- We know there exists a point p Pts (a, b) such that p & 4..5 If [4, 2, then we have contradiction since
cost(l'3; = (b a)² // > - -)) = cost p}. (b,p))
If |4,l 2 3, we know either or b is the furthest point from H, \ {a, b) in the interval [a, bj. Suppose a is such a point, consider Kijj =4,, \a) Up. We have the following identity, cost(Kig \ p, p)
cost(Ki, (p.b).p) + 6|2
cost(Ti, \ (a, 1pppbb bbb2
= cost(1",) \ {a, 6), T,, \ aa b) + 14, \ (a, 1p F,, \ (a, bJ + lp 6/2
< cost(T/) \ {a, b). !/ (a,b)+ I7, \ ba,b)l la-T', (a, 6y12 + la 612
= cost(4i) \ {a, b), + +|a-b/2
= cost(Tk (1/ \ (a).a).
12

---

Published as a conference paper at ICLR 2023
For the inequality, used the fact that is the furthest point from F/ \ (a, dj in the interval (a, b), and i (a,b) b). We have,
Dost(Ks,, Kig))
191 y2l²
(1 a)
V1: Ki
Σ
M v212 + cost(Kis \p,))
(1 aimm
Σ VI.Dee
U1 U2l2 cost( (Tis \. a.
(1 a)mm
y y212 cost(Tly) \ a.a))
(1 a.mm
gI. M.g \a
1/1 122
(1 a.)m V1.
cost((T,,)) T(.))
Hence, (ost( Kis)) ( 11,5) and we have contradiction.
Lemma 5. The following bound holds:
4a
cost (est(Qii,. Qi,s)
1i.3 Qia 2 2
2cx
[Qil
Proof. Consider the set St, {(Qij-9) --²² q Qii Let Vi, be subset of size (1 ai) drawn uniformly at random from Qij. Since the sample mean is an unbiased estimator for the population mean, we know
cost(Qi.jj Qi,i)
Σ gEVE,
(Qis - 9)²
Sig
(1 am
We also know that,
E Σ
Qi,
-)
-E [cost(Vi.. Qi,)) 2 E [coottV (V.., Ve5)) 2 cost( Lig),
nEVis
where we used the fact that I is a subset of size (1 - PP3 with minimum 1-means clustering cost (lemma 4.. Thus, have
cost Ttg) S (1 a)m;;
(Qit(QQi.j Qi.i)-
1Qil
Now, in the notation of lemma 3 we set J = Iij and JI = Iig n P. Since we have that
|T, = (1 a)m; and [T, O Ptyl = [h, n Qiyl = (1 |Ptj | a)m;, we can set
I-m;
| and get that
1-m,
P.. Qi,l cost(Ir.j, In,s)
1 I. 1
((1 a a)m; IP Q1 - a)m;
Pr.j \ Q /o.s/cost((C (oost(Q.,.. Q.,)
((1 a)m; Pr.j \ 1Q,1))
crcost(Qu Qu,))
(1 24)
13

---

Published as a conference paper at ICLR 2023
where we use the fact that [Pt, \ Qiyl am,. Also, by lemma
am, cosst(QQ.. 2u, a cost (C.st(Q..,). Q+)
QQi - Lis n Qiil
(1Qial am.))
(1 - 2a)
We conclude the proof by noting that
[T,3 Qigl S 2/0 I1, nQill + (Qis Qiol.
Lemma 6. The following bound holds:
P Toj & cost(P:.g:: Pig) ( 11-a +
4a
a)) /mg
(1-2a)(1-
Proof. By eq. 12
(1-2)² z²
PP5 - Pio Qi,l
P - Qi. 12
where = 1r.s |Pi.]
< We have
cost(P:.) Pi.j)
cost(P:: \ Qi.j: P.g) + cost(Qii,,,) Pi,))
= cost(P.') Qi.j: Pi, Qis) + +zm; Pm, PT, \ Qisl + cost(Qi,, Qi,)
(1 -2)m; Př, -Qū,]
1 -
mil ijj Qi.i 2 + cost \ /Qis Pij \Qi,) + cost(Qi.j; Qi,
1 a
m; Pi. Qi, cost(QQii Qig).
a
5 Applying lemma
we have
1
1 20
cost Pig)
m. Pij Qigl
(1 a)mi Qu.1?
4a
By Cauchy-Schward
P
Qi. + [T.. - Qi.l
a
4a
+
a
(1-2a)(1 αx)
1-a a
Q2nl + 1- 2a
(1 - a)m?llis Qisi?) /mm
m/l Prrj
4a
4a
cost(P
P.jj)
/m4
a-a (1-2a)(1 - a))
We conclude the proof by the fact that P
Iill 2
Pr.,
Qua
Qi,l) 2
Theorem Algorithm 7 a deterministic algorithum for k-means clustering such that given data set P Roxd and partition (Pı..., Pk) with error rate < 1/2, it outputs
+
2 I-a (1- (1-2a)(1-a) -approximation in time O (dm log m).
14

---

Published as a conference paper at ICLR 2023
Proof. Recall that the k-means clustering cost can be written the sums of the clustering cost in each dimension. For every ė E [ki], we have
E (E(M)
cost (1))))))))
Σ cost(P [E(
cost 1,j1 Cig5)
Te] JEld
Σ
Σ
cost Ps Pri + [c.] P.jl
xe (A) sEld
Σ
Σ
cost P.
P
+ m [in - P
xE[R] JE(d
S ΣΣ
1 a
+
(1 2cx) a)) -a)) cost(Prig.?
4a
1
NE (N) jE(d]
a
21) - a) an)) ))
4a
Σ (ost(P;,c)))
1
1 1
(1-20)
iE(k)
The inequality is due to lemma 6
We analyze the runtime of algorithm Notice for every E [k], j E [d]. computing It, involves sorting the points P.,, iterating from the smallest the largest point, and taking the average of the interval in Wi, with the smallest cost. This takes (m; logm;) m,) time. Note that Σiena] m, = m. Thus, the total time over all E [k] and E [d] is O (dm logm)
Corollary 8. For a S 1/7, algorithm 7 acciivess a clustering cost of (1 + 7.7O)
Proof. We recall that the generic guarantee for a < 1/22ss is
(1 2a) 21) a) )) OPT.
4a
(o 2x)) s 1+
+
1
We see that for a < 1/7, a
Za and 5
I
49-4o 30
so in sum the net approximation
I-a
[1
(1-2a)(1-0)
factor is + 7.7a.
A.2 MISSING PROOFS FOR k-MEDIANS
Lemma 12. With probability 2
1-2a
|| ct S 20PT./m.
Proof.
We observe that cost ( P.nPi.c)) < OPT, It follows that P ||
<
OPT,
<
[P:PT]]
OPT By Markov's inequality.
(1-a)m:
OPT:
1
Pr | - oi'l > (1+c)
P.N:
(1 (1-a) a)mm)
Itc
Pr ||0 cill < (1+r]PPT:
A E P.n.P"'
(1-ajm;
P(x E P.N.
ltc
Pr
||0 cfll <
(1 (1+c)OPT,
2 1tc
'
P(ZE
(1 a-mm
c(1 a)
1tE
To get the stated bound we set 1 - 2a.
Lemma 14. Conditioned on cost PP Pf 2) & (1 + OPP,.
15

---

Published as a conference paper at ICLR 2023
We first define some notation for the sets of false positive and false negative points that occur in proof for lemma 14, and prove a technical lemma relating the sets P, n P. and P, P.Y.P.
Definition 20. We make the following definitions:
1. Let & denote the event that | - - S
20PT,/n.
2. Let A denote the set of false negatives, iee. P C P.-
3. Let B denote the set of false positives, L.e. P.(.)
To bound the clustering cost of P.P.P in terms of the cost of P. P/ we first relate these two sets in terms of the false positives B and the false negatives A.
Lemma 21. We can write P. P ((PA)))) U A (see definition 20 for the definitions of A and B).
Proof. To see this we observe that
PAP = ((PP))
(
=
We also have that
= P ((BAP)NFSSUR( = (PPP)))NP) (P,n () P
Since (P, n P.YP (PAP)) PT we can identify the left hand sides in the last two displays and write
(BPP)) P.P.P ((PPP)NBUUA
wherein use that A = (P.P)))P...
We can now formalize our main argument showing that the clipped data set PA has a clustering cost close to that of the true cluster P.
Proof of lemma 14 By lemma 21 we first observe that
cost P, P.P c cost((P; n P,*,, cost c/) + (o,t(B,c)),
where A and B are defined as in definition 20 Again by lemma 21 P. PV (P.N \ AUB,
C P. n Pr and B (P, n P?) = 0, it follows that
P. - |
Further, we know that P P'l < (1 P; and IP, PTI 2 (1 (1-a) o It follows that [B] < |A| v Therefore, for every false positive p B, we can assign unique corresponding false negative n, E A arbitrarily. We observe that every point in A is farther from x than every point in B, and so we can write
1p
2
Mp - x
|
c
> 1p - 2|| - |
c
Z 1p
ci'l 2 cll
1f'l 4PPT;
Z =lpp
40PT;
+ 11pp-cc c11 <||mp
1t +
16

---

Published as a conference paper at ICLR 2023
It follows that
cost(B,c)) =
Σ
|lp - 4il
PEB
40PT;
1|pp cj +
PEB
I cost (A, of) + 4aOPT,
Returning to expression for cost(P: \ P. m,), get that
cost(P, \ G) = cost ((P; 0 PT) | + cost(B,
cost (P) 0 cf) cost cost(A, o,) + cost(B,
< cost( 0 P,',, + 4aOPT;
I (1+ 4a)
It follows that the optimal clustering cost for the set P: \ P. is at most (1 + 4a)OPT, and hence that cost(P, 122PP Pp, 2)) +1++)))(++))))))) (1+5a)OPT, for suitably small y S I-10
Lemma 15. For R = O [1-2a] log (2t) many repetitions, with probability at least 1 21 we have that cost P3 Pt, G) I (1 OPP
Proof. The probability ε not holding for some Ć is at most (1 - -2a)/ /2. The probability of EN not holding for any of the 2/ is (1-(2 (1 -2a) /2)R.. It follows that for 1-2x In (2k the probability of E not holding for any of the my is at most
(1- (1-2))2)))
22) n exp((-(1 2a)/2)² R
exp (- In (2k/6))
S 2k
follows that with probability 1 1- z6 & holds for some दे and consequently by the union bound cost(P, \ P. a) & (1 + OPP,, holds with probability E.
6
Lemma 16. If cost(P. P. a) < (1 + 5a)OPT, then || cf
2+3a OPT: (1-2a)
Proof. By the reverse triangle inequality we have that for every point p E P." (PP(P || Glll lp 1l Summing up across p. get
| -
pl 2
Σ
1 pl 2 (PP
PDI [ - cf1l
Σ
lp 1p-cll
PEPPN(PAP))
PEPiN(PAP))
(1+ OP) > P X P/I 16 - OPT,
+ (P
1 - -c11 S ((1+ 5a) + 1)OPT,
(2 + 5P)
| dil <
(1 20)m;
10n 100n)
Lemma 17. With probability 1 8/k, cost (P, n ()) I cost(P; n pt,c)) +
1 2a
Proof. From corollary 10 we know that with probability 1 - 5. 2 the following bound holds:
cost P.
P. () < (1 + +)oost( (P P/,c),,
17

---

Published as a conference paper at ICLR 2023
where y I [1+4a) and di is optimal 1-median for P. Also, it follows by definition that cost (P) c) cost(P))P/,c)) cf). Further, from lemma 15 and lemma 16 it follows that with probability 2k
(2 + OP
c o
(1 - 2a)mm
By the union bound, both these events hold simultaneously with probability 1 g- Conditioning this being the case, since P. n P = (P))
A, we can write
cost P. P.O.P G) - cost( n , = (cost P; \ P. Ci) - cost P, P),)))
(cost B, cost B,
+ (cost(A, Q)) cost(A,c;))
I (1+ costt P/,c) cost(PP) c)
[B] ||c, c + |A] |[: all
- 7
[B] - Gill + |A| . |c: ell
(2 - 5a)
< aOPT, + (amm + am.)
20/
a + 2ax(2 + 5a)OPT
(1-2a)
(5a 100a)) OPT;
1-2a
Lemma 18. With probability 1 8/k, cost(P,, 22) $ for
c= 7410a-10c²
(1-a)(1-2a)
Proof.
We have that
cost (f,G) () cost(P, 0 P., + cost(PP
We bound the second summand follows
cost(P, P., G) cost cost(P, 1 (2 OPP,
(1 2a)e;
a(2 + 5 OPT,
(P
(1-a) 2a)
Bounding the first summand cost n (PP G)) using the bound from above, we get
(5a + 10a2) OPT,
cos 23) cost((? 0 PP::) +
1-26 2a
a(2 + 5aP,
cost (ost(
(1 - a) (1 2a)
(5a 10a² 5a² 10a² + 2a 5a?) OPT,
=Psst(P;.
(1 -1- (1 -2x)
(7a + 10a² - 10a OPT;
cost(P:
(1-a) (1-a)(1- 2a)
B EXPERIMENTS ON RUNTIME
In this section, report the runtimes of our k-means and k-mediaas approaches and the methods in Ergun et al. (202).. We sample subsets points from the CIFAR-10 and the PHY datasets, and report the runtime (means and standard deviations) of the algorithms over 20 random runs. The
18

---

Published as a conference paper at ICLR 2023
Jigun,jon,
Bigun,
Runtime in seconds
15
020
666
94
84
6.
Portion of the sataset
Fortion of the dataset
(a) PHY
(h) CIFAR-10
Figure 3: Runtime comparison of algorithm with Ergun et (2022
Ergun, jon, sl. Ours
Brgun, Jon, al.
Cur
Rumtre In 0e:0nd5
Buntere in seconds R
Portion of the datase:
Portion of the dataset
PHY
(b) CIFAR-I0
Figure 4: Runtime comparison of algorithm with Ergun et al. 2022
subset sizes are varied from 20% to 100% of the size of the datasets, le is fixed 10 and o is fixed at .2
For k-means, we observe in fig. 3 that the runtime the two approaches are comparable, except for subset sizes 80% and 100% of CIFAR-I0 where ours is slightly slower. This is expected since finding a subset of size (1 - a)m;; with the best clustering cost in our algorithm and computing the shortest interval containing m, 5a)/2 /2 points in the approach of Ergun al. (2022) both involve sorting the points and takes 0 log m:) time.
We observe similar trends in the k-medians setting in fig. This is also expected given that the runtimes of both algorithms are dominated by calls to compute the 1-median center of the filtered points in each predicted cluster.
19


Reviews:
[{"review_id": "xxHxaCB-2i0", "reviewer": "Reviewer_HcAi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper can be regarded as a follow-up of (Ergun et al. 2021) which is published in ICLR2022. The main contribution of this submission is to answer the question: \"Is it possible to design a $k$-means and a $k$-medians algorithm that achieve (1 + $\\alpha$)-approximate clustering when the predictor is not very accurate?\". Moreover, the proposed two algorithms (Algorithm 1 and Algorithm 2) also have improved bounds on the clustering cost, while preserving the time complexity of the previous approaches and removing the requirement on a lower bound on the size of each predicted cluster.\n\n[Ergun et al. 2021] Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augmented\nk-means clustering.  In: ICLR, 2022.", "summary_of_the_review": "This submission follows the setting in (Ergun et al. 2021), where we are given a data set in $d$-dimensional Euclidean space, and a label for each data point given by a predictor indicating what subsets of points should be clustered together. I am not familiar with the topic of this submission, and I am open to hear opinions from other reviewers.", "strength_and_weaknesses": "Strength:\nThis submission follows the setting in (Ergun et al. 2021), where we are given a data set in $d$-dimensional Euclidean space, and a label for each data point given by a predictor indicating what subsets of points should be clustered together.  The proposed two algorithms (Algorithm 1 and Algorithm 2) have improved bounds on the clustering cost, while preserving the time complexity of the previous approaches and removing the requirement on a lower bound on the size of each predicted cluster.\n\nWeaknesses:\nThe presentation quality can be improved to make it easier to be understood by readers. For example, there is not a conclusion section in this submission. Besides, there are some typos and grammatical problems.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NVVoA3wFS4M", "reviewer": "Reviewer_6m4b", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the $k$-means and $k$-median problem in the learning-augmented setting, where we assumed to access a predictor that provides information about the label of each point with a $(1 - \\alpha)$-precision, and the approximation factor of the algorithm is measured in terms of $\\alpha$. For both problems, the authors propose an algorithm that gets a better approximation. The experiments also demonstrate the advantage of these algorithms.", "summary_of_the_review": "Overall I think it is an interesting paper. However,  the authors should clarify the issues in the time complexity(see strength and weakness).  Also, the comparison of the runtime in the experiment will make this paper more complete. Therefore, my current rating is 6.", "strength_and_weaknesses": "Strength\n\n1. The technical contribution is solid. Both of the algorithms achieve a better guarantee than the previous algorithms.\n2. The experimental results show that the performance of the proposed algorithm is better than the previous ones.\n\nWeakness\n\n1. The paper claims to preserve the time complexity of the previous approaches. However, when referring to the time complexity, the setting of this paper seems to be different than that in Ergun et al. If my understanding is correct, In Ergun et al, the time is including the time to assign each point to the closet center, which is $O(mdk)$ naively, so the authors show that even include this step, the time complexity is still $O(md \\log m)$. However, for this paper, the time seems to not include this step but only output the $k$ centers. One question is that can the technique used in Algorithm 3 of Ergun et al. be applied in this paper? \n2. The paper considers the time complexity of the different algorithms. However, in the experiment section, the authors seems not to list the result of the runtimes of different algorithms.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Mzr6GUbCdL8", "reviewer": "Reviewer_JvjK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies approximation algorithms for k-means and k-median clustering in the presence of \"advice\" in the form of an oracle that approximately provides the optimal clustering. The main assumption is that the algorithm has access to a clustering that agrees with an optimal clustering with parameter \"\\alpha\". The parameter ensures that for every cluster, the provided clustering has a good overlap with the optimal.\n\nUnder this assumption, the authors improve upon prior work in the same model, and show a (1+O(\\alpha)) approximation guarantee. Specifically, they improve prior work in terms of the dependence on \\alpha, as well as the range of \\alpha to which the algorithm applies. \n\nFor k-means, the authors use a \"coordinate wise\" algorithm that keeps track of a good subset of points (the potential \"agreement\" with OPT) in each cluster, and show that this must yield a good approximation ratio. For k-median the high level idea is similar, but the algorithm is randomized and it uses as a subroutine an approximate median algorithm from previous work. Both the algorithms are quite clean and practical. ", "summary_of_the_review": "In summary, the paper presents simple, practical algorithms for k-means and k-median clustering when the algorithm has access to a \"noisy version\" of the optimal clustering. The novelty in terms of algorithm/techniques is somewhat limited though, which is why I rate it as mildly above acceptance threshold.", "strength_and_weaknesses": "The main strengths of the paper are: \n- They analyze simple and practical algorithms for the two problems and show an approximation ratio that improves upon prior works\n- The range of \\alpha is considerably improved compared to prior work.\n\nHowever, the paper has a few weak aspects:\n- The first is wrt the motivation: the model isn't necessarily about \"learning augmented\" algorithms. It is much more closely related to clustering with noisy labels, which has been extensively studied (including in some recent works, e.g., in COLT 22). \n- Secondly, from an algorithmic point of view, the paper is somewhat on the weak side: most of the techniques are relatively standard and it's hard to get excited about. While the overall result is clean, it is not especially surprising. Some matching lower bounds, or surprising trade-offs, or perhaps improved results with the \"errors\" are random, might be interesting to know about.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster