Learning-Augmented $k$-means Clustering
Authors: Jon C. Ergun
Zhili Feng
Sandeep Silwal
David Woodruff
Samson Zhou
Venue: ICLR 2022 Spotlight (2022)
Keywords: clustering
learning-augmented algorithms

Abstract: $k$-means clustering is a well-studied problem due to its wide applicability. Unfortunately, there exist strong theoretical limits on the performance of any algorithm for the $k$-means problem on worst-case inputs. To overcome this barrier, we consider a scenario where ``advice'' is provided to help perform clustering. Specifically, we consider the $k$-means problem augmented with a predictor that, given any point, returns its cluster label in an approximately optimal clustering up to some, possibly adversarial, error. We present an algorithm whose performance improves along with the accuracy of the predictor, even though na\"{i}vely following the accurate predictor can still lead to a high clustering cost. Thus if the predictor is sufficiently accurate, we can retrieve a close to optimal clustering with nearly optimal runtime, breaking known computational barriers for algorithms that do not have access to such advice. We evaluate our algorithms on real datasets and show significant improvements in the quality of clustering.

Published as a conference paper at ICLR 2022
LEARNING-AUGMENTI k-MEANS CLUSTERING
Jon C. Ergun
Zhili Feng Carnegie Mellon University
Sandeep Silwal MIT
Georgetown Day School jergun228gds. org
cmu edu
s silwall Millwa@@m 10mit edd
David P. Woodruff
Samson Zhou
Carnegie Mellon University dwoodruf6 andrew. cmu. edu
Carnegie Mellon University
gansoonzhou@gmaaae com
ABSTRACT
k-means clustering is a well-studied problem due to its wide applicability. Unfor- tunately, there exist strong theoretical limits on the performance of any algorithm for the k-means problem on worst-case inputs. To overcome this barrier, we con- sider a scenario where "advice" is provided to help perform clustering. Specif- ically, we consider the k-means problem augmented with predictor that, given any point, returns its cluster label in an approximately optimal clustering up some, possibly adversarial, error. We present an algorithm whose performance improves along with the accuracy the predictor, even though naïvely following the accurate predictor can still lead to high clustering cost. Thus if the predictor is sufficiently accurate, we can retrieve a close to optimal clustering with nearly optimal runtime, breaking known computational barriers for algorithms that do not have access to such advice. We evaluate our algorithms on real datasets and show significant improvements in the quality of clustering.
INTRODUCTION
Clustering is a fundamental task in data analysis that is typically one of the first methods used to understand the structure of large datasets. The most common formulation of clustering is the k- means problem where given a set C Rdd of n points, the goal is to find a set of centers C' C B& of k points to minimize the objective cost (ost(P.) Eper min.ec |p cll2 (1)
Despite decades of work, there exist strong theoretical limitations about the performance of any al- gorithm for the k-mmaas problem. Finding the optimal set is NP-hard even for the case of (Dasgupta, 2008) and even finding an approximate solution with objective value that is within factor 1.07 of the optimal solution is NP-hard (Cohen-Addad & S., 2019; Lee et al., 2017). Fur- thermore, the best-known practical polynomial time algorithms constant factor approximation to the optimal clustering, c.g., the 50-approximation in Song & Ra- jasekaran (2010), or use techniques such as linear programming that do not scale, e.g., the 6.357- approximation in Ahmadian et al. (2020).
only provably achieve large
natural approach to overcome these computational barriers is leverage the fact that in many applications, the input is often not arbitrary and contains auxiliary information that can be used to construct a good clustering, e.g., many applications, the input can be similar to past instances. Thus, it is reasonable to create (possibly erroneous) predictor by using auxiliary information or through clusterings of similar datasets, which can inform the proper label of an item in our current dataset. Indeed, inspired by the developments in machine learning, many recent papers have stud- ied algorithms augmented with predictions (Mitzenmacher & Vassilvitskii, 2020). Such algorithms utilize predictor that, when invoked, provides (imperfect) prediction for future inputs. The predictions are then used by the algorithm to improve performance (see references Section 1.3).
Hence, consider the problem of k-means clustering given additional access to predictor that outputs advice for which points should be clustered together, by outputting label for each point. The goal is find & centers that minimize objective (1) and assign each point one of these centers.

---

Published as a conference paper at ICLR 2022
The question is then whether one can utilize such predictions to boost the accuracy and runtime of clustering of new datasets. Our results demonstrate the answer in the affirmative.
Formal learning-augmented problem definition. Given set P S R of n points, the goal is to find a set of k points C' (called centers) to minimize objective (I). In the learning- seaming-augmenter setting, we assume we have access to predictor IT that provides information about the label of each point consistent with a (1 + +a)))aa -aa--apooiiimaey optimal clustering C. We say that a predictor has label error rate À S a if for each label i [k] := {L..... k). in cluster i in C, and II errs on at most a À I a fraction of all points given label i by II. In other words, II has at least (1 X) precision and recall for each label.
II errs at most a A S fraction of all points
Our predictor model subsumes both random and adversarial errors by the predictor. For example the cluster sizes are somewhat well-balanced then special case of our model is when [[pp) outputs the correct label of point p E P with some probability - X and otherwise outputs a random label in [k] with probability X. The example where the predictor outputs adversarial label instead of random label with probability X also falls under our model. For more detail, see Theorems 1 and 3.4. We also adjust our algorithm to have better performance when the errors are random rather than adversarial in the supplementary material.
1.1 MOTIVATION FOR OUR WORK
We first motivate studying k-means clustering under the learning- algorithms framework.
Overcoming theoretical barriers. As stated above, polynomial time algorithm can achieve better than a constant factor approximation to the optimal clustering. In addition, the best provable approximation guarantees by polynomial time algorithms have a large constant factor (for example the 50 approximation in Song & Rajasekaran (2010)), or use methods which do not scale (such as the linear programming based algorithm in Ahmadian et al. (2020) which gives a 6.357- 337-approximation). Therefore, it is of interest to study whether a natural assumption can overcome these complexity barriers. In work, we show that knowing the true labels up to some possibly adversarial noise can give us arbitrarily good clusterings, depending on the noise level, which breaks these computational barriers. Furthermore, we present an algorithm that runs in nearly linear time, rather than just polynomial time. Lastly, we introduce tools from the robust statistics literature to study k-means clustering rather than the distance-based sampling procedure that is commonly analyzed (this the basis of kmeans++), This new toolkit and connection could have further applications in other learning-augmented clustering problems.
Practical considerations. In practice, good predictors can be learned for datasets with auxiliary information. For concrete example, we can take any dataset that has a train/test split and use a clus- tering on the training dataset to help us cluster the testing portion of the dataset. Therefore, datasets do not have to be specifically curated to fit our modelling assumption, which other modelling formulations that leverage extra information such as the SSAC model discussed in Section 1.3. A predictor can also be created from the natural class of datasets that vary over time, such as Census data or spectral clustering for temporal graphs (graphs slowly varying over time). For this class of datasets, a clustering from an earlier time step can function as a predictor for later time steps. Lastly, we can simply use the labels given by another clustering algorithm (such as kmeans+ +) or heuristic as a predictor. Therefore, predictors are readily and easily available for a wide class of natural datasets.
requirement in
Following the predictor alone is insufficient. Given a predictor that outputs noisy labels, it is conceivable that its output alone can give us a good clustering relative optimal. However, this is not the case and naively using the label provided by the predictor for each point can result in an arbitrarily bad solution, even when the predictor errs with low probability. For example, consider a cluster of points at the origin and a cluster of 2 points at x = 1. Then for A = 2, choosing centers at the origin and at æ = 1 induces a k-means clustering cost of zero. However, even for a predictor that errs with probability 4. some point will be mislabeled with constant probability, which results in a positive k-means clustering cost, and so does not provide relative error approximation. Thus, using the provided labels by the predictor can induce an arbitrarily bad clustering, even as the label error rate of the predictor tends to zero. This subtlety makes the model rich and interesting, and requires us create non-trivial clustering algorithms.
2

---

Published as a conference paper at ICLR 2022
Predictors with adversarial errors. Since the predictor is separate from the clustering algorithm, interference with the output of the predictor following the clustering algorithm's query can be a source of non-random noise. Thus any scenario in which communication is performed over noisy channel (for example, if the predictor is hosted at one server and the algorithm is hosted at another server) is susceptible to such errors. Another source of adversarial failure by the predictor is when the predictor is trained on a dataset that can be generated by an adversary, such as in the context of adversarial machine learning. Moreover, our algorithms have better guarantees when the predictor does not fail adversarially, e.g., see the supplementary material).
1.2 OUR RESULTS
In this paper we study searminngauggentedd methods for efficient k-means clustering. Our con- tributions are both theoretical and empirical. On the theoretical side, we introduce an algorithm that provably solves the k-means problem almost optimally, given access to a predictor that out- puts label for each point p E P according to (1 + ox) -)aapproximmatel optimal clustering, up to some noise. Specifically, suppose we have access to a predictor II with label error rate À upper bounded by a parameter a. Then, Algorithm outputs a set of centers C in (knd) time', such that cost( P. C) < (1 + ((a)) cost( P, Copt), where Copp is an optimal set of centers. We improve the runtime in Section by introducing Algorithm 3, which has the same error guarantees, but uses (nd) runtime, which is nearly optimal since one needs at least nd time to read the points for dense inputs (Theorem 3.4, and Remark A.1
To output labels for all points, Algorithm 3 requires n queries to the predictor. However, if the goal is to just output centers for each cluster, then we only require Ökk/a) queries. This is essentially optimal; we show in Theorem 3.5 that any polynomial time algorithm must perform approximately ((k/a) queries to output + a-approximate solution assuming the Exponential Time Hypothesis, well known complexity-thooee -thhorttcc assumption (Impagliazzo & Paturi, 2001). Note that one could ignore the oracle entirely, but then one is limited by the constant factor hardness for polynomial time algorithms, which we bypass with a small number of queries.
Surprisingly, we do not require assumptions that the input is well-separated or approximation-stan stable (Braverman et al., 2011; Balcan et al., 2013), which are assumed in other works. Finally in the supplementary material, we also give a maaming-augmenter algorithm for the related problem of k-median clustering, which has less algebraic structure than that of k-means clustering. We also consider a deletion predictor, which either outputs a correct label or a failure symbol 1 and give a (1 + a:) approximation algorithm even when the "deletion rate" is 1 - 1/ poly
On the empirical side, we evaluate our algorithms on real and synthetic datasets. We experimentally show that good predictors can be learned for all of our varied datasets, which can aid in clustering. We also show our methodology is more robust than other heuristics such as random sampling.
1.3 RELATED WORK
saarning-augmented algorithms. Our paper adds to the growing body of work on learning- augmented algorithms. In this framework, additional "advice" from a possibly erroneous predic- tor is used to improve performance of classical algorithms. For example, common predictor is "heaviness" predictor that outputs how "important" a given input point is. It has been shown that such predictors can be learned using modern machine learning techniques other methods on train- ing datasets and can be successfully applied to similar testing datasets. This methodology has found applications in improving data structures (Kraska al., 2018: Mitzenmacher, 2018), streaming al- gorithms (Hsu et al., 2019; Jiang et al., 2020), online algorithms (Lykouris & Vassilvtiskii, 2018; Purohit et al., 2018). graph algorithms (Dai et al., 2017), and many other domains (Mousavi al., 2015; Wang et al., 2016; Bora et al., 2017: Sablayrolles et al.. 2019; Dong et al., 2020; Sanchez et al., 2020; Eden et al., 2021). See Mitzenmacher Vassilvitskii (2020) for an overview and applications.
Clustering with additional information. There have been numerous works that study clustering in a semi- supervisd setting where extra information is given. Basu al. (2004) gave an active learning framework of clustering with "aai--iinnnmcannttiiiinn constraints, where algorithm is allowed
'The notation Ô hides logarithmic factors.
3

---

Published as a conference paper at ICLR 2022
to interact with a predictor that determines if two points must cannot belong to the same cluster. Their objective function is different than that of k-means and they do not give theoretical bounds on the quality of their solution. Balcan & Blum (2008) and Awasthi et al. (2017) studied interactive framework for clustering, where a predictor interactively provides feedback about whether or not to split current cluster merge two clusters. Vikram & Dasgupta (2016) also worked with an interactive oracle but for the Bayesian hierarchical clustering problem. These works differ from ours in their assumptions since their predictors must answer different questions about partitions of the input points. In contrast, Howe (2017) used logistic regression to aid k-means clustering but do not give any theoretical guarantees.
The framework closest in spirit to ours is the semi semi-supervised active clustering framework (SSAC) introduced by Ashtiani et al. (2016) and further studied by Kim & Ghosh (2017); Mazumdar & Saha (2017); Gamlath et al. (2018); Ailon et al. (2018); Chien et al. (2018); Huleihel et al. (2019). The goal of this framework also to produce (1 + a -approoxiat clustering while minimizing the number of queries to a predictor that instead answers queries of the form "same-cluster(u, vt"", which returns 1 points u, v E P are in the same cluster in a particular optimal clustering and otherwise. Our work differs from the SSAC framework in terms of both runtime guarantees, techniques used, and model assumptions, as detailed below.
We briefly compare to the most relevant works in the SSAC framework, which are Ailon et al. (2018) and Mazumdar & Saha (2017). First, the runtime of Ailon et al. (2018) is O(ndk / even for a perfectly accurate predictor, while the algorithm of Mazumdar & Saha (2017) uses O(nk²) queries and runtime (ndk3². By comparison, we use significantly fewer queries, with near linear rumtime (nd) even for an erroneous predictor. Moreover, predictor of Mazumdar & Saha (2017) independently fails each query with probability p so that repeating with pairs containing the same point can determine the correct label of a point whereas our oracle will always repeatedly fail with the same query, so that repeated queries do not help.
The SSAC framework uses the predictor to perform importance sampling to obtain a sufficient num- ber of points from each cluster whereas we use techniques from robust mean estimation, dimension- ality reduction, and approximate nearest neighbor data structures. Moreover, it is unclear how the SSAC predictor can be implemented in practice to handle adversarial corruptions. One may consider simulating the SSAC predictor using information from individual points by simply checking if the labels of the two input points are the same. However, if particular input is mislabeled, then all of the pairs containing this input can also be reported incorrectly, which violates their independent noise assumption. Finally, the noisy predictor algorithm in Ailon al. (2018) invokes step of recovering a hidden clique in a stochastic block model, making it prohibitively costly to implement.
Lastly, in the SSAC framework, datasets need to be specifically created to fit into their model since one requires pairwise information. In contrast, our predictor requires information about individual points, which can be learned from either a training dataset, from past similar datasets, or from another approximate or heuristic clustering and is able to handle adversarial corruptions. Thus, we obtain significantly faster algorithms while using an arguably more realistic predictor.
Approximation stability. Another approach to overcome the NP-hardness of approximation for k-means clustering is the assumption that the underlying dataset follows certain distributional prop- erties. Introduced by Balcan et al. (2013), the notion of (c, ax) a-)-appoxximaee stability (Agarwal et al., 2015; Awasthi et al., 2019; Balcan et al., 2020) requires that every c-approximation is a-close to the optimal solution in terms of the fraction of incorrectly clustered points. In contrast, allow inputs so that an arbitrarily small fraction of incorrectly clustered points can induce arbitrarily bad approximations, previously discussed, e.g., in Section 1.1.
LEARNING-AUGMENTER k-MEANS ALGORITHM
n2. Preliminaries. We use [n]] to denote the set f1. Given the set of cluster centers C, we can partition the input points P into ls clusters (C1,... C₂) according to the closest center to each point. If point is grouped in C₁ in the clustering, be arbitrarily permuted as long as the labeling across the points of each cluster is consistent. is well- well-known that in k-means clustering, the i-th center is given by the coordinate-wise mean of the
refer to its label i. Note that labels can
4

---

Published as a conference paper at ICLR 2022
aaggenntge k-means clustering Input: A point set X with labels given by predictor
Algorithm 1
Algorithm 2 Coordinate-wise estimation CRDEST
II with label error rate
Output: (1 + (a):))approxiinn k-means clustering
Input: Points ;1,...,,2m E R. corrup- tion level À S a
of X
1: for i = 1 to = k do
1: Randomly partition the points into Iwo groups X1, X2 of size m.
2: Let Y; be the set of points with label i.
3: Run CRDEST for each of the d coordinates of Y,
2: Let I= [a, bj be the shortest interval containing m 5a) points of X1.
4: Let C₁ be the coordinate-win wise outputs of CRDEST.
3: Z t X2 I
4: +- T2T Σzez 2
5: end for
5: Return 2
6: Return clustering with centers C,...,, Cj
points in C. Given x E Idd and a set C' C IRd, we define d(x, C*) = min.ec || - cll2. Note that there may be many approximately optimal clusterings but we consider fixed one for our analysis.
2.1 OUR ALGORITHM
Our main result is an algorithm for outputting a clustering that achieves a (1 + 20a) approximation 2 to the optimal objective cost when given access to approximations of the correct labeling of the points in P. We first present suboptimal algorithm in Algorithm 1 for intuition and then optimize the runtime in Algorithm 3, which is provided in Section 3.
The intuition for Algorithm is follows. We first address the problem of identifying an approxi- mate center for each cluster. Let C ..... Cht be optimal grouping of the points and consider all the points labeled by our predictor for some fixed 1 S S k. Since our predictor can err, a large number of points that are not in C.pe may also be labeled i. This is especially problematic when points that are "significantly far" from cluster C are given the label i, which may increase the objective function arbitrarily if we simply take the mean of the points labeled i by the predictor.
To filter out such outliers, we consider a two step view from the robust statistics literature, e.g., Prasad al. (2019); these two steps can respectively be interpreted as a "training" phase and a "testing" phase that removes "bad" outliers. We first randomly partition the points that are given label into two groups, Xi and X2. of equal size. We then estimate the mean of C using a coordinate-wise approach through Algorithm 2 (CRDEST), decomposing the total cost as the sum of the costs in each dimension.
For each coordinate, we find the smallest interval that contains (1 4a) fraction of the points in X1. We show that for label error rate À S a, this "training" phase removes any outliers and thus provides rough estimation to the location of the "true" points that are labeled i. To remove dependency issues, we then "test" X2 on 7 by computing the mean of X₂ n T. This allows us to get empirical centers that are a sufficiently good approximation to the coordinates of the true center for each coordinate. We then repeat the other labels. The key insight is that the error from mean- estimation can be directly charged to the approximation error due to the special structure of the k-means problem. Our main theoretical result considers predictors that err on at most X-fraction of all cluster labels. Note that all omitted proofs appear in the supplementary material.
Theorem 2.1. Let a E (10logn/ Vn. 1/7), II be a predictor with label error rate À < a, and y 2 1 sufficiently large constant. If each cluster in the (1 a) approximmatly optimal k-means clustering of the predictor has at least ynk/ a points, then Algorithm can be used to output a (1 + 20a) -pproximation to the k-means objective with prob. 1 1-1 1/n, using Okgnlogg)) runtime.
We improve the running time to Ond n + poly(k, log n)) in Theorem 3.4 in Section 3. Our al- gorithms can also tolerate similar error rates when failures correspond to random labels, adversarial labels, or special failure symbol.
Note that we have not attempted to optimize the constant 20.
5

---

the accuracy Published as a conference paper at ICLR 2022
Error rate À vs. accuracy parameter a. We emphasize that À is the error rate of the predictor and a is only some loose upper bound on A. It is reasonable that some algorithms can provide lossy guarantees their outputs, which translates to the desired loose upper bound of the predictor. Even if is not known, multiple instances of the algorithm can be run in parallel with separate exponentially decreasing "guesses" for the value a. We can simply return the best clustering among these algorithms, which will provide the same theoretical guarantees as if we set 1.011, for example. Thus a does not need to be known in advance and does not need to be tuned as hyperparameter.
3 NEARLY OPTIMAL RUNTIME ALGORITHM
We now describe Algorithm 3, which is an optimized runtime version of Algorithm and whose guarantees present in Theorem 3.4. The bottleneck for Algorithm is that after selecting k empirical centers, it must still assign each of the n points to the closest empirical center. The main intuition for Algorithm 3 is that although reading all points uses ((nd) time, we do not need to spend (dk) time per point to find its closest empirical center, if we set up the correct data structures. In fact, as long as we assign each point to a 'relatively good" center, the assigned clustering is still a "good" approximation to the optimal solution. Thus we proceed in similar manner as before to sample a number of input points and find the optimal centers for the sampled points.
We use dimensionality reduction and an approximate nearest neighbor (ANN) data structure to ef- ficiently assign each point to a "sufficiently close" center. Namely if a point p E P should be assigned to its closest empirical C; then p must be assigned to some empirical center Cj such that I S 21[p- 2- Hence, points that are not assigned to their optimal centers only ineur a "small" penalty due to the ANN data structure and so the cost of the clustering does not increase "too much" in expectation. Formally, we need the following definitions.
Theorem 3.1 (JL transform). Johnson & Lindenstrauss ( (1984) Let d(.:.) be the standard Euclidean
norm. There exists a family of linear maps A Rdd TR and absolute constant C > O such that for any I. E Rd Pr (Ø E A, d(((z), o(y)) E (1 + a (x, y)] 2 1 -Cakk
Definition 3.2 (Terminal dimension reduction). Given a set of points called terminals C C CRd,, we call a map f : Idd + I terminal dimension reduction with distortion D if for every terminal c E C and poins p E &Rd,, we have d(p, c) S d(f(p), f()) I D d(p,c).
Definition 3.3 (Approximate nearest neighbor search). Given a set P of points in metric space (X, d), a aapp--ppoo nearest neighbor search (ANN) data structure takes any query point q e X with non-empty (p E P 0 < d(p, 4) S r and outputs a point in {p E P 0 < d q) - cr).
To justify the guarantees of Algorithm 3, we need runtime guarantees creating a suitable dimen- sionality reduction map and an ANN data structure. These are from Makarychev et al. (2019) and Indyk& & Motwani (1998); Har-Peled et al. (2012); Andoni et al. (2018) respectively, and are stated in Theorems 1.12 and A.13 in the supplementary section. They ensure that each point is mapped to "good" center. Thus, we obtain our main result describing the guarantees of Algorithm 3.
110logn n/ /n, 1/7), 11 be a predictor with label error rate S a, and 2 be a sufficiently large constant. If each cluster in the optimal k-means clustering of the predictor has at least 7/k log k/j points, then Algorithm outputs a (1 + 20aa) approximiannnnnnn to the k-means objective with probability at least 3/ /4. using Ond log n + poly (k, log n.)) total time.
Theorem 3.4. Let
Note that if we wish to only output the & centers rather than labeling all of the input points, then the query complexity of Algorithm 3 is Ō(kaa) (see Step 1 of Algorithm 3) with high probability. We show in the supplementary material that this is nearly optimal.
queries to the predictor with label error rate a cannot output a (1 + apprrxxittnnt to the optimal k-means clustering cost in time 20(2--)) time, assuming the Exponential Time Hypothesis.
Theorem 3.5. For any d E (0, 1], any algorithm that makes O log
6

---

Published as a conference paper at ICLR 2022
Algorithm 3 Fast karninggauggentte algorithm for k-means clustering.
Input: A point set X, a predictor II with label error rate À at, and tradeoff parameter Ç Output: A (1 + appppooxie k-means clustering of X
1: Form 5 by sampling each point of X with probability 100 where A₂ is the set of points A=A.
with the same label as z according to II.
2: Let Cl....,Cz be the output of Algorithm 1 on S.
3: Let d2 be random JI. linear map with distortion 5 3. i.e., dimension O(log n).
4: Let Φ1 be terminal dimension reduction with distortion $
5: Let Φ = Φ1 o Ø2 be the composition map.
6: Let A be (2, data structure on the points (C (Ckk)
7: for x E X do
8: Let l be the label of a from IT.
9: g e Ct.)
d(x,Co
Query to find the closest center c(Cp.) ) to æ with r
11:
if' d(x,, Cp.) ) < 2d(2r Ct,) then
Assign label pz
13: else
14:
Assign label l to x.
15:
end if
16:
end for
4 EXPERIMENTS
In this section we evaluate Algorithm empirically on real datasets. We choose to implement Algorithm 1, as opposed to the runtime optimal Algorithm 3, for simplicity and because the goal of our experiments is to highlight the error guarantees of our methodology, which both algorithms share. Further, we will see that Algorithm is already very fast compared alternatives. Thus, we implement the simpler of the two algorithms. We primarily fix the number of clusters to be readily
k = 10 and k = 25 throughout our experiments for all datasets. Note that predictors generalize to other values of k but we focus on these two values for clarity. All of our experiments were done on CPU with i5 2.7 GHz dual core and 8 GB RAM. Furthermore, all our experimental results are averaged over 20 independent trials and + one standard deviation error is shaded when applicable. We give the full details of our datasets below.
1) Oregon: Dataset of 9 graph snapshots sampled across 3 months from an internet router commu- nication network (Leskovec al., 2005). We then use the top two eigenvectors of the normalized Laplacian matrix to give us node embeddings into R² for each graph which gives us 9 datasets, one for each graph. Each dataset has roughly n 10 points. This is an instance of spectral clustering. 2) PHY: Dataset from KDD cup 2004 (kdd, 2004). We take 1 random samples to form our dataset.
3) CIFARIO: Testing portion of CIFAR-10 (n 10a, dimension 3072) (Krizhevsky, 2009).
Baselines. We compare against the following algorithms. Additional experimental results on Lloyd's heuristic are given in Section E.3 in the supplementary material.
1) kmeans++: We measure the performance of our algorithm in comparison to the kmeans++ seeding algorithm. Since kmeans++ a randomized algorithm, we take the average clustering cost after running kmeans++ seeding on 20 independent trials. We then standardize this value to have cost 1.0 and report all other costs terms of this normalization. For example, the cost 2.0 means that the clustering cost is twice that of the average kmeans++ clustering cost. We also use the labels of kmeans++ as the predictor in the input for Algorithm (denoted as "Alg kmeans + ++") which serves to highlight the fact that one can use any heuristic or approximate clustering algorithm as predictor.
2) Random sampling: For this algorithm, we subsample the predictor labels with probability ranging from 1% to 50%. We then construct the k-means centers using the labels of the sampled points and measure the clustering cost using the whole dataset. We use the best value of q in our range every time to give this baseline as much power as possible. We emphasize that random sampling cannot have theoretical guarantees since the random sample can be corrupted (similarly
7

---

Published as a conference paper at ICLR 2022
as in the example in Section 1.1). Thus some outlier detection steps (such as algorithms) are required.
Predictor Description.
We use the following predictors in our experiments.
1) Nearest neighbor: We use this predictor for the Oregon dataset. We find the best clustering of the node embeddings in Graph #1. In practice, this means running many steps of Lloyd's algorithm until convergence after initial seeding by kmeans+ Our predictor takes as input point in R² representing a node embedding of any of the later 8 graphs and outputs the label of the closest node in Graph #1.
2) Noisy predictor. This is the main predictor for PHY. We form this predictor by first finding the best k-means solution on our datasets. This again means initial seeding by kmeans++ and then many steps of Lloyd's algorithm until convergence. We then randomly corrupt the resulting labels by changing them to uniformly random label independently with emror probability ranging from O to 1. We report the cost of clustering using only these noisy labels versus processing these labels using Algorithm 1.
3) Neural network. We use a standard neural network architecture (ResNet18) trained on the train- ing portion of the CIFAR- 10 dataset the oracle for the testing portion which we use in our periments. We used pretrained model obtained from Huy (2020). Note that the neural network predicting the class of the input image. However, the class value is highly correlated with the optimal k-means cluster group.
Summary of results. Our experiments show that our algorithm can leverage predictors to signifi- cantly improve the cost of k-means clustering and that good predictors can be easily tailored to the data at hand. The cost of k-means clustering reduces significantly after applying our algorithm com- pared to just using the predictor labels for two of our predictors. Lastly, the quality of the predictor remains high for the Oregon dataset even though the later graphs have changed and "moved away" from Graph #1.
Selecting a in Algorithm 2. In practice, the choice of a to in our algorithm depends on the given predictor whose properties may be unknown. Since our goal is to minimize the k-means clustering objective (I), we can simply pick the 'best' value. To do so, we iterate over a small range of possible a from .01 to .15 in Algorithm 2 with a step size of 0.01 and select the clustering that results in the lowest objective cost. The range is fixed for all of our experiments. (See Paragraph 2.1
4.1 RESULTS
Dataset Orepon Spectal Clustein. km
Datasen: Oregon Special Clusterigg k=25
Donaset Oregon Spectral Custering Groph 45, k=10
0.5
2.6
my Sampling
3.4
12
Cyeweng.oo
0.3
3.0
5.8
5.6
0.1
Grash
Grap
Comustin 9o
(a)
1: 10
(b) A: 25
(c) k 25
Figure 1: Performance of Algorithm 1 on later graph embeddings using Graph #1 as predictor.
Oregon. We first compare our algorithm with Graph #1 as the predictor against various base- lines. This is shown Figures I(a) and Figure 1(b). In the k = 10 case, Figure 1(a) shows that the predictor returns a clustering better than using just the kmeans + seeding, which is normalized to have cost 1.0. This is to be expected since the subsequent graphs represent a similar network as Graph #1, just sampled later in time. However, the clustering improves significantly after using our algorithm on the predictor labels as the average cost drops by 55%. We also see that using our algorithm after kmeans++ is also sufficient give significant decrease in clustering cost. Lastly,
8

---

Published as a conference paper at ICLR 2022
Daloast: PHY. J-10
Delaeet: OFAR-10, I-110
Ag m No Predicoor
Purent inc recuaaee Classeting Dast
12
smeonsee
Randim Sampling
2.0
Noley Fred
1.0
0.
10
20
30
40
50
Fraction Queted
(a) PHY, 10
(b) CIFAR-10, l: 10
Figure 2: Our algorithm able to recover a good clustering even for very high levels of noise.
random sampling also gives comparable results. This can be explained because we are iterating over a large range of subsampling probabilities for random sampling.
In the h = 25 case, Figure 1(b) shows that the oracle performance degrades and is worse than the baseline in of the graphs. However our algorithm again improves the quality the clustering over the oracle across all graphs. Using kmeans++ as the predictor in our algorithm also improves cost of clustering. The performance of random sampling also worse. For example in Graph #3 for k = 25, it performed the worst out of all the tested algorithms.
Our algorithm also remains competitive with kmeans++ seeding even if the predictor for the Ore- gon dataset is highly corrupted. We consider later graph, Graph #5, and corrupt the labels of the predictor randomly with probability q ranging from 1% to 25% for the & = case Figure I(c). While the cost of clustering using just the predictor labels become increasingly worse, algorithm is able to sufficiently "clean" " the predictions. In addition, the cost random sampling also gets worse as the corruptions increase, implying that it is much more sensitive noise than algorithm. The qualitatively similar plot for k = 25 is given in the supplementary section. Note that in spectral clustering, translate to those settings as well since having higher order spectral information only results in stronger predictor. We continue the discussion the PHY and CIFAR-10 datasets in Section E.
may wish to get mapping Rd for d >> 2. We envision that our results
Comparison to Lloyd's Heuristic. Section E.3, we provide additional results on experiments using Lloyd's heuristic. In summary, give both theoretical and empirical justifications for why our algorithms are superior to blindly following predictor and then running Lloyd's heuristic.
ACKNOWLEDGEMENTS
Zhili Feng. David Woodruf, and Samson Zhou would like to thank partial support from NSF grant No. CCF- 181584, Office of Naval Research (ONR) grant 100014-18-1-256 and a Simons Investigator Award. Sandeep Silwal was supported in part by NSF Graduate Research Fellowship Program.
REFERENCES
Kdd cup. http:://ssmet cs wtt.s/mmttt.....oellll..cm httpp//l..eet//ddddd////ttteeee htmll 2004.
Manu Agarwal, Ragesh Jaiswal, and Arindam Pal. k-means++ under approximation stability. Theor. Comput. Sci., 588:37-51, 2015.
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k- means and euclidean k-median by primal-dual algorithms. SIAM J. Comput., 49(4), 2020.
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate Clustering with Same-Cluster Queries. In 9th Innovations in Theoretical Computer Science Conference (ITCS), pp. 40:1-40:21, 2018.

---

Published as a conference paper at ICLR 2022
Alexandr Andoni, Piotr Indyk, and Ilya P. Razenshteyn. Approximate nearest neighbor search in high dimensions. CoRR, abs/1 2ts//8806.08223 2018.
Martin Anthony and Peter L. Bartlett. Neural Nenwork Learning: Theoretical Foundations. Cam- bridge University Press, 1999. doi: 01177//CB077001166624
David Arthur and Sergei Vassilvitskii. How slow is the k-means method? In SCG '06, 2006.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Pro- ceedings of the Eighteenth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp- 1027-1035, 2007.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In Advances in Neural Information Processing Systems 29, pp. 3-16-3224, 2016.
Pranjal Awasthi, Maria Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive clustering. Journal of Machine Learning Research, 18(3):1-35, 2017.
Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, and David Woodruff. Robust communication-opine distributed clustering algorithms. In 46th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 18:1-18:16, 2019.
Maria-Florine Balcan and Avrim Blum. Clustering with interactive feedback. In Proceedings of the 19th International Conference on Algorithmic Learning Theory, pp. 316-328, 2008.
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Clustering under approximation stability. ACM, 60(2):8:1-8:34 2013.
Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-center clustering under perturbation resilience. ACM Trans. Algorithms, 16(2):22:1 1-2::99, 2020.
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 Min- ing (SDM-04), April 2004.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G. Dimakis. Compressed sensing using gener- ative models. In Proceedings of the 34th International Conference on Machine Learning, ICML, pp. 537-546, 2017.
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku. Streaming k-means on well-clusterable data. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 26 SIAM, 2011.
I Chien, Chao Pan, and Olgica Milenkovic. Query k-means clustering and the double dixie cup problem. In Advances in Neural Information Processing Systems 31, pp. 6649-6663 6658. 2018.
Miroslav Chiebik and Janka Chlebiková. Complexity of approximating bounded variants of opti- mization problems. Theor Comput. Sci., 354(3):320-338, 2006.
Michael Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 9-21, 2016.
Vincent Cohen-Addad and Karthik C. S. Inapproximability of clustering in Ip metrics. 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pp. 539, 2019.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp.
2017.
Sanjoy Dasgupta. How fast is k-means? In Computational Learning Theory and Kernel Ma- chines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop. COLT/Kernel, Proceedings, pp. 735, 2003.
Sanjoy Dasgupta. The hardness of k-means clustering. 2008
10

---

Published as a conference paper at ICLR 2022
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems, 2021. URL
atttss://arxiie org/ abs 0977077977...
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2020.
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-based support estimation in sublinear time. In International Conference on Learning Representations, 2021.
Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based on weak coresets, In Proceedings of the 23rd ACM Symposium on Computational Geometry, pp- 11-18, 2007.
Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential approximation schemes for esps: From dense to almost sparse. 33rd Symposium on Theoretical Aspects of Computer Science, STACS, pp. 37:1-37:14, 2016.
Buddhima Gamlath, Sangxia Huang, and Ola Svensson. Semi-Supprrised Algorithms for Approx- imately Optimal and Accurate Clustering. In 45th International Colloquium on Automata, Lan- guages, and Programming (ICALP), pp. 57:1-57:14, 2018.
Sariel Har-Peled and Bardia Sadri. How fast is the k-means method? Algorithmica, 41:185-202, 2005.
Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards re- moving the curse of dimensionality. Theory Comput., 8(1):321-350, 2012.
Johan Hástad. Some optimal inapproximability results. J. ACM, 48(4):798 2001.
J. A. Howe. Improved clustering with augmented k-means. arXiv: Machine Learning, 2017.
Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019.
Wasim Huleihel, Arya Mazumdar, Muriel Medard, and Soumyabrata Pal. Same-cluster querying for overlapping clusters. In Advances in Neural Information Processing Systems 32, pp. 10485- 10495. 2019.
Phan Huy. 2020.
Pytorchcifar10.
0,
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62 (2):367-377) 2001.
Mary Inaba. Naoki Katoh, and Hiroshi Imai. Applications of weighted voronoi diagrams and ran- domization to variance-baae based k-clustering (extended abstract). In Proceedings of the Tenth Annual Symposium on Computational Geometry, pp. 332-339, 1994.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pp. 604-613, 1998.
Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for wasserstein barycenter. In Advances in Neural Information Processing Systems, 2021.
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. aaurmnne- data
stream algorithms. In International Conference Learning Representations, 2020.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space, 1984.
Taewan Kim and Joydeep Ghosh. Relaxed oracles for semi-supervised clustering. CoRR, abs/1711.072 1,0433,, 2017.
11

---

Published as a conference paper at ICLR 2022
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pp. 489-504, 2018.
Robert Krauthgamer. Randomized algorithms course notes. weizmann. ac. at.i//................ att///b/////....... tebi/ttechinggg. Baaiiing//oaaaaaaan lecture8 pdÉ, 2019. Lecture 8.
http:/ www. wi sdom. 102019a-Raae wew.dmoriindlgggiitnnmi..
Alex Krizhevsky, Learning multiple layers of features from tiny images. Technical report, 2009,
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. simple linear time (1 + <)-approximation algorithm for k-means clustering in any dimensions. pp. 454-462, 2004.
Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 3662-3671, 2019.
Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Inf. Process. Lett., 120:40-43,200
Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 177-187, 2005.
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. Journal of Machine Learning Research, 18(160):1-25, 2018, URL http: // / /tmmmmmr.rrrrr/ wwwp:o.rggppppppappoa wwtpsvvvvvi/////a
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. vol- ume 80 Proceedings of Machine Learning Research, pp. 3296-3305. PMLR, 2018.
Konstamtin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1027-1038, 2019.
Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems. pp. 5788- 5799, 2017.
Michael Mitzenmacher. A model for learned bloom filters, and optimizing by sandwiching. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 462-471, 2018.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions, 2020.
Ali Mousavi, Ankit B. Patel, and Richard G. Baraniuk. A deep learning approach to structured sig- nal recovery. In 53rd Annual Allerton Conference on Communication. Control, and Computing, Allerion, pp. 1336-1343, 2015.
Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A unified approach to robust mean estimation. CoRR, hts/1907.000 907.00927, 2019.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems 31, pp. 9661-9670. 2018.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou. Spreading vectors for similarity search. In International Conference on Learning Representations, 2019.
Thomas Sanchez, Baran Gözcü, Ruud B. van Heeswijk, Armin Eftekhari, Efe llicak, Tolga Çukur, and Volkan Cevher. Scalable learning-based sampling optimization for compressive dynamic MRI. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, pp. $584, 2020.
Mingjun Song and S. Rajasekaran. Fast algorithms for constant approximation k-means clustering. Trans. Mach. Learn. Data Min., 3:67-79, 2010.
12

---

Published as a conference paper at ICLR 2022
Andrea Vattani. k-means requires exponentially many iterations in the plane. Discrete & Computational Geometry, 45:596-616 616, 2011.
Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hierarchical clustering, volume 48 of Proceedings of Machine Learning Research, pp. 2081-2090. PMLR, 2016.
Wang, W. Liu, S. Kumar, and S. Chang. Learning hash for indexing big data a survey. Proceedings of the IEEE, 104(1):34-55) 2016.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
Theorem A.1 (Chernoff Bounds). Let Xi...., Xu be independent random variables taking values in {0, 1}. Let X = Di=1 X; denote their sum and let μ = [[ denote the sum't 's expected value. Then for any E (0, 1) and t 0,
Pr 8) Se
For any 8 8>0 O,
Pr (1+ se -
Furthermore,
Pr| μ t S #
A. PROOF OF THEOREM 2.
We first prove Theorem 2.1, which shows that Algorithm provides a (1 + appapppoxiniaooon the optimal k-means clustering, but uses suboptimal time compared to faster algorithm we present in Section 3. All omitted proofs of lemmas appear in Section A.2.
We first show that for each coordinate, the empirical center for any (1 a fraction of the input points provides good approximation to the optimal k-means clustering cost.
Lemma A.2. Let P.Q C be sets of points on the real line such that IPI Z (1 a) and [QI S Let X = PUQ Cp be the mean of P and Cx be the mean of X. Then cost Cp) S
(1+ - cost(X,
We now show that conceptual interval I" R with "small" length contains significant fraction of the true points. Ultimately, we will show that the interval computed in the "training" phase in CRDEST has smaller length than /" with high probability and yet I also contains significant fraction the true points. The main purpose of I" (and eventually I) is to filter out extreme outliers because the "testing" phase only considers points in I N22
Lemma A.3. For a fixed set X C R, let C' be the mean of X and 0² 21IT Exex C) be the
C+ variance. Then the interval I CC Va points X.
contains at least (1 - 4a) fraction of the
Using Lemma A.3, we show that the interval / that computed in the "training" phase contains significant fraction of the true points.
Lemma A.4. Let m be sufficiently large consatnt. We have that 1 := [a, b) contains at least 6o fraction of points of X2 and b b- S 2a/ ya, with high probability, i.e., 1 1 poly(m).
We next show that the optimal clustering on a subset obtained by independently sampling each input point provides rough approximation of the optimal clustering. That is, the optimal center is well-approximated by the empirical center the sampled points.
Lemma A.5. Let be a set of points obtained by independemtly sampling each point of C Rd with probability p 1/2 Let C' be the optimal center of these points and Cs be the empirical center of these points. Conditioned on |S] 2 1, then E [[ = x and there exists a constant n such that for
7 2 1 and [X]
1ik
E [[[Cs x S
Σ | x13 x
X
Pr [cost(X, Cs) > (1 + a) cX, C?] < 1/(m)).
Using Lemma A.2, Lemma A.4, and Lemma A.S, we justify the correctness of the subroutine CRDEST.
14

---

Published as a conference paper at ICLR 2022
Lemma A.6. Let B.0logn//rii. P be of points the real line such that [P] 2 (1 am2 and [Q] & 2am, and = PUQ. Let be the center of P. Then CRDEST on impur set X outputs point C' such that with probability at least 1 - (nk),, cost(P, C*) - (1+ 18a) a [1- cost(P.C).
Let
Using CRDEST subroutine for each coordinate, prove Theorem 2.1, justifying the correctness of Algorithm by generalizing to all coordinates and centers and analyzing the runtime of Algorithm
Proof of Theorem 2.1. Since II has label error rate À I a, then by definition of label error rate, least a (1 - a)) fraction of the points each cluster are correctly labeled. Note that the k- means clustering cost can be decomposed into the sum of the costs induced by the centers in each dimension. Specifically, for set {CI...., C&} of optimal centers,
cost (x,t(x))) = Σ d(x, C)
Σ
Σ d(s, C.)² #ES.
where S is the set points in X that are assigned to center C.. For particular E [kt, we have
Σ d(,, ZES.
Σ Σ daz (C:),))
J=
where zy and (C.), are the j-th coordinate of æ and C₁, respectively.
By Lemma A.6, the cost induced by CRDEST for each dimension in each center C₁2 is (1 + a)- approximation of the total clustering cost for the optimal center C, in that dimension with probability 1- 1/(k). That is,
Σ Eds,, (C),) S + 18a)(1 + a1 + a/(1 - a)?) E d(x,;(()))) ZES,
#ES.
for each j E [d]. Thus, taking a sum over all dimensions j E [d] and union bounding over all centers i E [k:]. we have that the total cost induced by Algorithm is (1 apprroxiiooiiiiooon to the optimal k--maans clustering cost with probability at least - 1/1
To analyze the time complexity of Algorithm first consider the subroutine CRDEST. It takes O(kdn) time to first split each of the points in each cluster and dimension into two disjoint groups. Finding the smallest interval that contains certain number of points the points and then iterating from the smallest point to the largest point and taking the smallest interval that contains enough points. This requires O(n log n) time for each dimension and each center, which results in O(kd log r2) total time. Once each of the intervals is found, computing the approximate center then takes (kdn) total time. Hence, the total running time of Algorithm O(kdn n).
be done by first sorting
L
A.2 PROOF OF AUXILIARY LEMMAS
Lemma A.2. Let P.Q C be sets of points on the real line such that |P| 2 (1 a)n and [QI < an. Let X = PUQ, Cp be the mean of P and Cx be the mean of X. Then cost(XX, Cp) s
1 cost(X,
Proof. Suppose without loss of generality, that Cx = 0 and C'p < 0, so that Co 2 0, where Co is the mean of Q. Then it is well-known, e.g., see Inaba et al. (1994), that
cost(X, Cr) = cost (X, Cx) + X
CCr 2
Hence, it suffices to show that | |Cp Cx प- cost Cx).
15

---

Published as a conference paper at ICLR 2022
Since Cx 0 we have PPICPp -IQ .Q. with PP 2 (1-a)n and [Q] an. Let [P| = (1-2)m p)m
and [Q] en for some @ S Thus, Co =-1- I-e Cr. By convexity, thus have that
cOst(Q,, (ost(Q(()) |Q] (1 0)²
|rrl2
g²
n(1 - 2) Cppl
0
n( - a} |ppp.
Therefore, we have
CCp - -xx1x n(1 a)²
cost(Q. (x) n(1 a)? cost(X,CC Cx).
Thus,
| -xx
a
cost X, Cx),
(1 a)=
as desired.
Lemma A.3. For a fixed set X C R, let C be the mean of X and 0² 2|x| Ez (x Cyp be the variance. Then the interval I [C- C+ contains least 4a) fraction of the points in X.
Proof. Note that any point E X \ I' satisfies |r - C > (4a)) Thus, if more than a 4a fraction of the points of X are outside of I*, then the total variance is larger than o², which is contradiction.
For ease of presentation, we analyze = 1/ and we note that the analysis extends easily to general A. We now prove the technical lemma that we will use the proof of Lemma A.8.
Lemma A.7. We have
Σ
θ
2
m
Proof. Let m sufficiently large. A Chernoff bound implies that for sufficiently large constant C,
Σ
S
2
m
Ij 1/-m/2/2Cv/
Furthermore,
Σ
-
Σ
m
m20'm 2.
2m
=
J21
so the upper bound the desired relation holds. A similar analysis provides lower bound.
Lemma A.4. Let be sufficiently large consatnt. We have that 1 := [a, b] contains least 1 6ox fraction of points of X₂ and b S 20/ Vo, with high probability, i.e., 1/ poly(m).
Proof. By Lemma A.3, 1 contains least 2m - 4a) of the points in X. Hence, by applying an additive Chernoff bound for t O( log m) and for sufficiently large m, have that the number of points in /* n X, is at least m(1 5a) with high probability. Since of minimal length with least m(1 5a) points, then the length of I is most the length of I". Moreover, again applying Chernoff bounds, we have that the number of points in I n X₂ is at least m(1 6o).
the interval
More formally, suppose we have set of 2m points that we randomly partition into two sets X1 and X2. Consider any fixed interval J that has at least 2em total points for 2 1 5a (note there
16

---

Published as a conference paper at ICLR 2022
most ((m²) intervals in total since our points are in dimension). Let J1 and J2 denote the number points in J that are in X1 and X2 respectively. By a Chernoff bound, we have that both J1 and J2 are at least me(1 a) with high probability. In particular, |Ji - J2l I amc with high probability. Thus by using a union bound, all intervals with at least cm total points satisfy the property that the number of points partitioned X2 differ by at most ame with high probability. Conditioning on this event, must also contain m(1 6a) points in X2 since it contains least m(1 5a) points in X1, desired.
X1 and the number of points partitioned to
Lemma A.8. Let be a set of points obtained by independently sampling each point of X S R with probability 2, and let Cs be the centroid of S. Let be the centroid of X. Conditioned |S| 2 1, we have E(Cs] = x, and there exists constant ry such that
E [[CCs - =12 S
Σ ZE
| -
X
Proof. We first prove that [C(ss] Note that by the law of iterated expectations,
[[Cs] BiCs [.
Let be random permutation of the elements in S, so that for each S [S], have E[rr,]] = J. Now conditioning the size of S, we can write
Cs Ti, + Pijst
S
Therefore,
F | E|Cs |S|]]
S
and it follows that [[Css = x.
To prove that
E [| =||o| S X
Σ ZE
|| |
we again condition on |S]. Suppose that |S| = j. Then,
Cs - F (Igs F) (2 x)
Now let yi, Fi, x for all < S..j. Therefore,
E =
||Css z||
E I1
+ Vi 112]
j2
Bills, 1 + j -
E ElyT, Veal
j
Note that o4 is uniform over elements in X, so follows that
x =1
X
zEX
Now if j 2 2, we have that
Eaco yb
E 11 2- E,
||
Ely T yi,1
S 50
(IXI)
|X1(X
since E, /4 = by definition. Hence,
E 2
||Cs-- - 1 < x
Σ 11-2
ZEX
17

---

Published as a conference paper at ICLR 2022
Now the probability that |S| for j 2 is precisely ///xx, have
Pr |S| 2 2]
E |
[[CCs
x1 |1
X
1
Σ
||
I1?
X
2|
JE X
From Lemma A.7, we have that
|X|
(1XI)
S |
21X
for some constant e so it follows that
d'
C|
x112
S
Σ
1130 - z01??
X
TEE
for some constant d' For j = 1, note that
E [|Css 1
|| 1 =11.
|S|=j=1
X
aEX
Moreover, we have Pr [|S] = 1] = 2 expectation, we have
X
and
Pr
[|S| = 0]
= 2|xT-
1
Thus from the law of total
E
C|
Pr [|S]
2|
E
[[|Cs "
[
Pr
||S|
>
2
[[|ss
[||
|S|22
X
[1x - ক1
2
X
ZEX
d
Σ
| - x/|
X
ZEX
K
Σ D X
|| 3/2
X
for some constant 7, as desired.
Lemma A.9. Let S be a set of points obtained by independently sampling each point of X C R with probability p 2- Let C be the optimal center of X and Cs be the empirical center of S. Let y 2 be the constant from Lemma A.8. Then 1j 2 1 and [X| > gik
Pr (cost(X,,C Cs) > (1 + a) cost(X C)] < 1/mk))
Proof. By Lemma A.8 and Markov's 's inequality, have
nyk
Pr
[Cs C11 >
2
2
X
We have
Σ
|| Csll3 Σ
|| - C11 +
|
||C
Csl12.
x
zEX
so that by Lemma A.8
1ykk
Σ - Cs <
1+
Σ
C
|
ZEX
zex
77kk
1
cost(X,C),
X
18

---

Published as a conference paper at ICLR 2022
with probability least - Hence for |X] 2 12 the approximate centroid of each cluster induces (1 + a apprrooxxittao the cost the corresponding cluster.
Lemma A.S. Let S be sel of points obtained by independently sampling each point of X C Rd with probability p = z.2 Lel C be the optimal center of these points and Cg be the empirical center
of these points. Conditioned on |8| 1, then E[Cs] T and there exists constant y such that for
n 1 and [X]
2ik
E [||ss
1 I x
Σ
|2 =1
Pr [cost (X, Cs) > + a) cost X, C)] 1/(m)).
Proof. Lemma A.5 follows immediately from Lemma A.8 and Lemma A.9.
Lemma A.6. Let a E (o0logn/ /u,1/7 (1,
Lei P.Q C be seis of points on the real line such that [P] 2 (1 a2)2m and [Q] S 20m, and X = PUQ Q. Let C be the center of P. Then CRDEST on input set outputs point C' such that with probability at least 1 - (nnk), cost(P, (P,C") s (1 + (++18))1++ + a (1+T-ajz) cost(P.C),
Proof. Let a (10log n/ /n, 1/7). Then from Lemma A.4, we have that n X contains least (1 6a:m points of P n X2 and most 2am points of Q in an interval of length 20 /a, where
0²
Σ pEp
(p c)
cost P,C).
P|P
Pl
From Lemma A.2, we have that
cost Most(P,CC) (P, S 1 (1 (1-a) a}²
cost C1),
where Co is the center of / /nnPr PnP, and C is the center of P X2.
For sufficiently large and from Lemma A.9, have that
cost(P, C1) $ (1 + a.) cost(P,
with probability at least 1 1/(nk). Thus, it remains to show that cost(P,,C") s (1 O(a)) cost(P,Co)
Since Co is the center of / n Pn X2 and C" is the center of 0 22, then we have
Pn
Σ
q 9= 1-
@eIn@nX2
2g Since has length 20/ Va, then q Co Va Co +
2g
Because
InPiX 2 (1 1-6a)m
Va
and [Q| 2am, then for sufficiently small a, we have that
C - Cul S 6/ao.
Note that we have cost (P, C*) cost (P, Co) IP| ICo C² P, so that
cost (P, C²) S cost (P, Co) + |P| 36072
Finally, 0²
cost((P. C) and cost P.C) < cost Cu) due to the optimality of C. This
P
implies
Dost(P,C') < cost (P. Co) + PP 36002
s cost(P, Co) + P| 36a
cost(P. (PCC)
2|P
cost(P. Co) + 18a cost Co)
(1 + 18a) cost (esst(..h)))) Co).
as desired, Thus putting things together, we have
cost(P, (,,C')) < (1+ (1 [+
a
cost(P, (C.)..
(1 a)²
19

---

Published as a conference paper at ICLR 2022
A.3 PROOF OF THEOREM 3.4
We now give the proofs for optimal query complexity and runtime. We first require the following analogue to Lemma A.5:
Lemma A.10. Let S be set of points obtained by independently sampling each point of S R with probability min (1, 1 Let C' be the optimal center of these points and Cs be the
empirical center of these points. Conditioned on [S| 2 1, then E[Css] = I and for [X] a
E [l|ss - 212
Σ LEX
| =
x|
for some constant 7/-
Lemma A.11. For a E Lo vn.1/7) let II be predictor with error rate X S. a/2. If each cluster has at least yk log k/a points, then Algorithm 3 outputs a (1 + -0paaxappxonnnaioon to the k-means objective value with probability at least 3/4.
Proof. Since S samples each points independently with probability proportional cluster sizes given by II, for fixed i E [k] at least 90 points with label are sampled, with probability at g from Chernoff bounds. Let 7.....p 7he be the empirical means corresponding to each of the sampled points with labels 1, .... k. respectively, and let To {71..... 7. Let CI,..., be centers of a (1 + ar) approximaeee optimal solution C with corresponding clusters X X By Lemma A.10, we have that
least 1 - +
E
[[[C - -111.
Σ wr
1
0:
x|
where p = min (1,
100 log k a|S|
By Markov's inequality, we have that
Σ kE[k]
|c 7 < 100
Σ
Σ
|
x|
kE[k]
LEEX
with probability at least 0.99. Similar to the proof of Lemma A.9, we use the identity
Σ x
|1 1-12112---
Σ
| C.I.3 + + |1C, - 7x112.
zEX;
Hence, we have that
cost(X, S (1+ cost(X, C),,
with probability at least 0.99.
Suppose II has error rate À < and each error chooses label uniformly at random from the k possible labels. Then by definition of eπror rate, at most a:22 fraction the points are erroneously labeled for each cluster. Each cluster in the optimal k-means clustering of the predictor II has at least n/ nÇk:)) points, so that at least (1 a) fraction of the points each cluster are correctly labeled. Thuss by the same argument in the proof of Lemma A.6, we have that Algorithm outputs set of centers Ci,..., Cs such that for (CI,...,Ch, we have
(1--o)) a cost(XX
cost(X,1) S (1+ 18a)
(1 a)z a}-
with sufficiently large probability.
Let E' be the event that cost(XX I)) < (1+ (1 (1-
-1- cost((XC), so that Pr[E] 2 - 1/ poly(k). Conditioned on E, let X, be the subset of X that is assigned the correct label by II, and let X₂ be the subset of X assigned the incorrect label. For each point X, assigned the
20

---

Published as a conference paper at ICLR 2022
correct label la by II, the closest center to in I is Ce., Algorithm will always label with lx- Thus,
cost(X,, I cost((,,)) & +1+ 18a) (1- (1-a)²
cost(X, (),
(1-11-1
conditioned on &. On the other hand, if x E X2 is assigned an incorrect label & by II, then the -apprroxiii nearest neighbor data assigns the label Ps, to 2. where (CCp, is the closest center to ((x) in the projected space. Recall that ø is the composition map @1 o Φ2, where Φ1 has a terminal dimension reduction with distortion 5/4, and Φ2 a random JL linear map with distortion 5/4. Thus the distance between and Cp- is a 2-approximation between and its closest center C.. Hence, by assigning all points to their respective centers Cp., we have d(x, Cp.) S cost D). Since each point E X is assigned the incorrect label with probability À S oz/2, the expected cost of the labels assigned to X2 is a cost(X, (X,,)) I).. By Markov's inequality, the cost of the labels assigned to X2 is at most
10a cost(X, () < 10a(1 + a) cost(tX,)) with probability at least y. conditioned on E.
Therefore by union bound, the total cost is at most (1 (1+20a)) cost(x, C), with probability least 3/4.
We need the following theorems on the quality of the data structures utilized in Algorithm 3. Theorem A.12. Makarychev et al. (2019) For every set C Rd of size k, a parameter < a < and the standard Euclidean norm d(-, -), there exists terminal dimension reduction f :C R
with distortion (1 + at), where d' 0 logk The dimension reduction can be computed in polynomial time.
Theorem A.13. Indyk & Motwani (1998); Har-Peled et al. (2012); Andoni et al. (2018) For >> O, there exists a (1+ az r) r-ANN data structure over equipped with the standard Euclidean norm that achieves query time O (d log a²
and space := O (+ log + d(n 4)), where q == logn a² The
runtime of building the data structure is O(S ndg).
We now prove Theorem 3.4.
Theorem 3.4. Let a E (10logn/:) n/..///.///// Il a predictor with label error rate S a, and y 2 be sufficiently large constant. If each cluster in the optimal k-means clustering of the predictor has at least "/k log k//o points, then Algorithm ousputs a (1 + 20xx) -pprrxxppronimaion to the k-means objective with probability least 3/4 4, using Ond log n + poly log total time.
Proof. The approximation guarantee of the algorithm follows from Lemma A.11. To analyze the running time, we first note that we apply a JL matrix with dimension O(log n) each of the n points in Rd, which uses O log n) time. As result of the JI. embedding, each of the points has dimen- sion (log n). Thus, by Theorem A., constructing the terminal embedding uses poly (k, log n) time. As a result of the terminal embedding, each of the k possible centers has dimension Olog k). Hence, by Theorem A.13, constructing the (2, r)-NN data structure for the & possible centers uses O(k log" k) time. Subsequently, each query to the data structure uses O(log" k) time. Therefore, the overall runtime is O(nd + poly log n)).
A.4 REMARK ON TRULY-POLYNOMIA TIME ALGORITIMS VS. PTAS/PRAS.
Remark A.14, We emphasize that the runtime of our algorithm in Theorem 2.1 is truly polynomial in all input parameters n. d, Ao and 1/a (and even near-linear in the input size nd). Although there exist polynomial-time randomized approximation schemes for k-means clustering, e.g., Inaba et al. (1994); Feldman et al. (2007); Kumar al. (2004), their runtimes all have exponential dependency on h and 1/a, i.e., 200 However, this does not suffice for many applications, since k and 1 1/a should be treated as input parameters rather than constants. For example, it is undesirable to pay exponential amount of time to linearly improve the accuracy of the algorithm. Similarly, if the number of desired clusters Olog' n),, then the runtime would be exponential. Thus believe the exponential improvement of Theorem 2.1 over existing PRAS in terms of l and 1/a is significant.
21

---

Published as a conference paper at ICLR 2022
A.5 REMARK ON POSSIBLE INSTANTIATIONS OF PREDICTOR
Remark A.15. We can instantiate Theorem 2.1 with various versions of the predictor. Assume each cluster in the (1 a)-approximately optimal k-means clustering of the predictor has size least n (Çk) for some tradeoff parameter Ç E [1, (/n)/(8k))) log 1)]..). Then the clustering quality and runtime guarantees of Theorem 2.1 hold if the predictor II is such that
1. II outputs the right label for each point independently with probability 1 - X and otherwise outputs a random label for À I ((a/S),
2. II outputs the right label for each point independently with probability À and otherwise outputs an adversarial label for O(a/(k()).
In addition, if the predictor outputs a failure symbol when fails, then for constant ( >> O, there exists an algorithm (see supplementary material) that outputs a (1 aaproxxmaaiiiiio to the k-means objective with probability least 2/3, even when II has failure rate À = 1- 1/ poly(k). Note that this remark (but not Theorem 2.1) assumes that each of the & clusters in the (1 a apprrooxxialel optimal clustering has at least u Çk points. This a natural assumption that the clusters are "roughly balanced" which often holds in practice, e.g., for Zipfian distributions.
B DELETION PREDICTOR
In this section, we present a fast and simple algorithm for k-means clustering, given access to a label predictor II with deletion rate That is, for each point, the predictor II either outputs label for the point consistent with an optimal k-means clustering algorithm with probability X, or outputs nothing all (or a failure symbol 1) with probability X. Since the deletion predictor fails explicitly, we can actually achieve a (1 + o:) -approximation even when À = poly(k)
Our algorithm first queries all points in the input X. Although the predictor does not output the label for each point, for each cluster C; with a sufficiently large number of points, with high probability, the predictor assigns at least 2 [Cll points of C, to the correct label. We show that if |Cil 22 then with high probability, the empirical center is a good estimator for the true center. That is, the k- means objective using the centroid of the points labeled i is (1 + -approxmaatiio the k-means objective using the true center of C.. We give the full details in Algorithm 4.
To show that the empirical center is good estimator for the approach for mean estimation is to sample roughly an O (+)) number of points uniformly at random with replacement. The argument follows from observing that each sample is an unbiased estimator of the true mean, and repeating O (.:2) times sufficiently upper bounds the variance.
center, recall that common
Observe that the predictor can be viewed sampling the points from each cluster without replace- ment. Thus, for sufficiently large cluster sizes, we actually have huge number of samples, which intuitively should sufficiently upper bound the variance. Moreover, the empirical mean again an unbiased estimator of the true mean. Thus, although the above analysis does not quite hold due to dependencies between the number of samples and the resulting averaging term, we show that the above intuition does hold.
Algorithm 4 Linear time h-means algorithm with access label predictor II with deletion rate X.
Input: A point set X with labels given by label predictor II with deletion rate X. Output: A (1 + a)) appproxxiee k-means clustering of X.
1: for each label
[k] do
2: Let S, be the set of points labeled i.
3: C: +- [ST
Σ.es,
4: end for
5:
for all points E X do
6: if x unlabeled then
7: Lu + arg min d(z, ci)
8: Assign label l, to x.
9: end if
10: end for
22

---

Published as a conference paper at ICLR 2022
We first show that independently sampling points uniformly random from sufficiently large point set guarantees a (1 + a) approximation to the objective cost. Inaba et al. (1994); Ailon et al. (2018) proved a similar statement for sampling with replacement.
remains to justify the correctness of Algorithm by arguing that with high probability, the overall k-means cost is preserved up to (1 (1+a) by the empirical means. We also analyze the running time of Algorithm+ 4.
Theorem B.1. If each cluster the optimal k-means clustering of the predictor 11 has at least points, then Algorithm 4 outputs (1 + a apprroxximatin to the k-means objective with probability at least 2 using (kdd) total time. 3.
Proof. We first justify the correctness of Algorithm 4. Suppose each cluster in the optimal k-means clustering of the predictor II has least 3 points. Let C {ci, {ci,..., ,..,,, C& be the optimal centers be the empirical centers chosen by Algorithm 4. For each i E [k), let C, be the points of X that are assigned to C, by the predictor II. By Lemma A.9 with = 3, the approximate centroid of cluster induces (1 + approxxixatto to the cost of the corresponding cluster that
selected by II and let Cs (c...... ( }
cost c) S (1 (1+0g ax) cost ci),
with probability at least 1 - 36' Taking a union bound over all & clusters, we have that
Σ
cost(C,, c) S Σ
cost)coosCG..ca))
iE(A]
with probability at least 3. Equivalently, cost((X,)) C) S a1) cost(X,Css Cs).
To analyze the running time of Algorithm 4, observe that the estimated centroids for all labels can be computed in O(dn) time. Subsequently, assigning each unlabeled point to the closest estimated centroid uses (kd) time for each unlabeled point. Thus, the total running time is O(kdn).
C k-MEDIAN CLUSTERING
We first recall that well-known result states that the geometric median that results from uniformly sampling a number of points from the input is a "good" approximation to the actual geometric median for the 1-median problem.
Theorem C.1. Krauthgamer (2019) Given set P of points in RR,, the geometric median of sample of O ( a log 2) points of P provides a (1 + appproxxxmitioon to the 1-median clustering problem with probability at least 1 1/ 1/loy(dd).
Note that we can first apply Theorem A.12 to project all points to space with dimension O (2zz log {) before applying Theorem C.I. Instead of computing the geometric median, we re- call the following procedure that produces (1 + appapooxxiitoo to the geometric median.
Theorem C.2. Cohen et al. (2016) There exists an algorithm that outputs a (1 + aapproxxxiittionn to the geometric median in O log 2) time.
We give our algorithm in full in Algorithm 5.
Theorem C.3. For a E (0, 1). let II a predictor with error rate X O klog 8 log log If each
cluster in the optimal k-median clustering of the predictor has at least n/ n((Ck) points, then there exists algorithm that outputs (1 + appproxximaai to the k-median objective with probability least 1/ poly(k), using O(ndlogg n + poly (k, log n)) total time.
Proof. Observe that Algorithm 5 samples O ( log k) points for each of the clusters labeled i, a à log log loc
with i E [k]. Thus Algorithm 5 samples O ( log" &) points in total. For À = O with a sufficiently small constant, the expected number of incorrectly labeled points sampled by Algorithm 5 is less than Thus, by Markov's inequality, the probability that no incorrectly labeled
23

---

Published as a conference paper at ICLR 2022
Algorithm 5 [Leannng-Augmentte k-median Clustering
Input: A point set x E X with labels given by predictor II with error rate A. Output: A (1 + apprroxmia k-median clustering of X.
1: Use terminal embedding to project all points into a space with dimension (2zz log m).
2: for i = 1 to
& do
3: Let E be the most common remaining label.
4: Sample O (Tt log" &) points with label 4,
5: Let C be a (1 + a -approximation to the geometric median of the sampled points.
6: end for
7:
Return Cy,.,,,,,
points are sampled by Algorithm 5 is at least 3. Conditioned on the event that no incorrectly labeled points are sampled by Algorithm 5, then by Theorem C.1, the empirical geometric median for each cluster induces (1 + [) apprroximmtioon to the optimal geometric median in the projected space.
Hence the set of k empirical geometric medians induces (1 + ] -approximation to the optimal k-median clustering cost in the projected space. Since the projected space is the result of a terminal embedding, the set of i empirical geometric medians for the sampled points in the projected space induces a k-median clustering cost that is a (1 + 7 -approximmation to the k-median clustering cost induced by the set of k empirical geometric medians for the sampled points in the original space. Taking the set of k empirical geometric medians for the sampled points in the original space induces
(1+ + ))² -approximation each of the geometric medians. Thus for sufficiently small a, Algorithm 5 outputs (1 + a)- approximation to the h-median clustering problem.
the k-median clustering cost. We take (1 + [) -aprrxximation to
To embed the points into the space of dimension O ( log )), Algorithm 5 spends O(nd log n) total time. By Theorem C.2, takes O(nd n) total time to compute the approximate geometric medians.
D LOWER BOUNDS
MAX-E3-LIN-2 is the optimization problem of maximizing the number of equations satisfied by system of linear equations of Zn with exactly 3 distinct variables in each equation. EK-MAX-E3- LIN-2 is the problem of MAX-E3-LIN-2 when each variable appears in exactly i equations. Fotakis et al. (2016) showed that assuming the exponential time hypothesis (ETH) (Impagliazzo & Paturi, 2001), there exists an absolute constant C such that MAX k-SAT (and thus MAX k-CSP) instances with fewer than OI) clauses cannot be approximated within a factor of C₁ in time 20(n'") for any 8 > 0. As consequence, the reduction by Håstad (2001) shows that there exist absolute constants C2, C33 such that E.K-MAX-E3-LINS
with k 2 C2 cannot be approximated within factor of C3 in time 20(n for any 5 > 0. Hence, the reduction by Chlebík & Chlebíková (2006) shows that there exists constant C₁ such that approximating the minimum vertex cover of 4-regular graphs within a factor of C4 cannot be done in time 20(n²=)) for any > 0. Thus the reduction by Lee al. (2017) shows that there exists constant C, such that approximating k-means within factor of C3 cannot be done in time 20(n' for any 8 > assuming ETH. Namely, the reduction of Lee et al. (2017) shows that an algorithm that provides C3 ap-rpoxximtaoon to the optimal k-means clustering can be used to compute a C4 ap-approximation to the minimum vertex cover.
n'-6 Theorem D.1. If ETH is true, then there does not exist an algorithm A that takes set S of Togn vertices and finds Ca-approximation the minimum vertex cover that contains S on 4-regular graph G, using 20(n) 1-)) time for some constant 8 E (0, 1].
Proof. Suppose by way of contradiction that there exists an algorithm A that takes set of logn vertices and finds a Ca-approximation to the minimum vertex cover that contains S on a 4-regular graph G, using 20(nt=)) time for some constant 5 E (0, 1]. We claim that we can use A to cre- ate an overall algorithm that violates ETH. Indeed, suppose we guess each subset of n 1-a
log
24

---

Published as a conference paper at ICLR 2022
tices and which vertices of the subset are in the cover. There are (n 2 2m1-6/10 log S (en" logn)" (n)"""///on) //ogg log 22 log such combinations of vertices. For each guess, we then run the purported algorithm A that uses 20'n' ") time. Thus we can identify Ca-approximation to the minimum vertex cover in time
(en" logn)" momnn""/"n ""lo"ooooo llgg 2n/ logn, 20(nn 20(n'"), (00m")))000"79) =000==)=2=0"77 =00(''
which would contradict ETH.
Finally, we show the query complexity of Algorithm is nearly optimal. Lee al. (2017) con- structed an instance of k-means that cannot be approximated within a factor of 1.0013 in polynomial time. The reduction of Lee et al. (2017) creates 4n points in g that must be clustered by O(n) centers and an algorithm that provides C3-approximation to the optimal h-means clustering can be used to compute a C1- Ca-approximation to the minimum vertex cover. Thus, there exists a constant
Css such that approximating k- k-means within factor of C5 cannot be done in time 20(n'²) for any 8 > 0, assuming ETH.
Theorem 3.5. For any d E 1], any algorithm that makes (d queries to the predictor with label error rate a cannot output a (1 + Ca)-apppoximation to the optimal k-means clustering cost in time 20(""=> time, assuming the Exponential Time Hypothesis.
Proof. Let a be a fixed constant such that a < Cg.- Given an instance of a k-means clustering con- structed from the reduction of Lee al. (2017), the optimal clustering cost is (2(n) and kı (n)).
We embed this instance into a k-means clustering by adding an additional (2(1) points arbitrarily far from I, that the additional points contribute Q(n/ox)) cost upon partitioning into k 22)) clusters. We set k = k1 + k2.
In summary, the resulting instance has ((n) points and k M(x). The optimal solution has cost O(n/a) cost so that contributes an ((a) fraction of the cost. By querying O
1 points with
a log
sufficiently small constant, most O construction of I. Each center corresponds to selected vertex in the corresponding vertex cover in the reduction from minimum vertex cover on 4-regular graphs Hence, in the corresponding vertex
A1-6 of the cluster centers in I will be revealed by the log
61-6 (a lo
cover instance, most O
vertices revealed. Thus by Theorem D.I, any algorithm
running in 20(x-=) time cannot determine a Ca-approximation to the optimal k-means clustering cost on as it would correspond Since I induces an (ax) fraction of the total clustering cost, it follows that any algorithm that makes O
Cy-approximation the optimal vertex cover, assuming ETH.
3--6
queries cannot output a (1 + Car) approximatin to the optimal k-means clustering cost
log
in time (-") time, assuming ETH.
ADDITIONAL. EXPERIMENTAL. RESULTS E
E. OMITTED DISCUSSION
In this section we continue the discussion from the experimental section of the main body. In Figure 3(a), we show the qualitatively similar version of Figure 2(c) of the main body for the case of 25. In Figure 3(b), we display the qualitatively similar version Figure 3(a) of the main body for the k- = 25 case of dataset PHY.
PHY. We use the noisy predictor for this dataset. We see Figure 2(a) that as the corruption percentage rises, the clustering given by just the predictor labels can have increasingly large cost. Nevertheless, even the clustering cost of the corrupted labels is rising, the cost decreases signifi- cantly after applying Algorithm 1 by roughly factor of 3x. Indeed, we see that algorithm can beat the kmeans++ + seeding baseline for q as high as 50%. Just as in Figure 1(c), random sampling is sensitive to noise. Lastly, also remain competitive with the purple line which uses the labels output by kmeans+ as the predictor in our algorithm (no corrupiinss added). The qualitatively similar plot for 25 is given in the supplementary material.
25

---

Published as a conference paper at ICLR 2022
CIFAR-10. The cost of clustering CIFAR-10 using only the predictor, the predictor with algorithm, random sampling, and kmeans+ ++ as the predictor for our algorithm were 0.733, 0.697, 0.721, and 0.640, respectively, where 1.0 represents the cost of kmeans+*, The neural network was very accurate (~ 93%) in predicting the class of the input points which is highly correlated with the optimal k-means clusters. Nevertheless, algorithm improved upon this highly precise predictor.
Note that using kmeans++ the predictor for our algorithm resulted in a clustering that was 13% better than the one given by the neural network predictor. This highlights the fact that an approxi- mate clustering combined with our algorithm can be competitive against highly precise predictor, such as neural network, even though creating the highly accurate predictor can be expensive. In- deed, obtaining a neural network predictor requires prior training data and also the time to train the network. On the other hand, using a heuristic clustering as a predictor is extremely flexible and can be applied to any dataset even no prior training dataset is available (50, 000 test images were required to train the neural network predictor but kmeanst+ + as predictor requires no test images), in addition to considerable savings in computation.
For example, the time taken to train the particular neural network we used was approximately 18 minutes using the optimized Py PyTorch library (see training details under the "Details Report" section in Huy (2020)). In general, the time can be much longer for more complicated datasets. On the other hand, our unoptimized algorithm implementation which used the labels of a sample run of *means++ still able to achieve better clustering than the neural network predictor with a 0.01 in Algorithm 2 in 4.4 seconds. In conclusion, we can achieve a better clustering by combining much weaker predictor with our algorithm with the additional benefit of using more flexible and computationally inexpensive methodology.
We also conducted an experiment where we only use a small fraction of the predictor labels in our algorithm. We select p fraction of the images, query their labels, and run our algorithm on only these points. We then report the cost of clustering on the entire dataset as p ranges from 1% to 100%. Figure 2(b) shows the percentage increase in clustering cost relative to querying the whole dataset is quite low for moderate values of p but increasingly worse as p becomes smaller. This suggests that the quality of our algorithm does not suffer drastically by querying smaller fraction of the dataset.
Dataset: Oregon Spectral Clustering, Graph #5, k=25
Dataset: PHY, k-25
80
Alg Noisy Predictor
Random Sampling
1.4
1.2
Alg k-means++
Randem Sampling
Noisy Predictor
kmeans++ ++
Clustering Cost
60
Predictor
Cluttering Cost
1.0
kmeans++
Noisy Predictor
40
0.6
0.4
20
0.2
0
5
10
Corruption %
155
20
25
0
10
20
Corruption %
30
40
50
(a) Oregon Graph #5, l = 25
(b) PHY, & 25
Figure 3: Our algorithm is able to recover a good clustering even for very high levels of noise.
E.2 SYNTHETIC DATASET
We use a dataset of 10010 points in RRd for d 10x created using the kmeans+* ++ lower bound construction presented in Arthur & Vassilvitskii (2007). The dataset consists of 10 well separated clusters in Rd. let e; denote the basis vectors. Our dataset is {1000e;} } U (1000e, + eÿ} for all 1 5 i 10. 1 < j < 1000.
From the description of the dataset, we can explicitly calculate the optimal clustering and its cost. Our predictor for this dataset to take the optimal clustering and randomly change each label
26

---

Published as a conference paper at ICLR 2022
with probability 1/2 to another uniformly random label. Empirically, kmeans++ seeding returned a clustering that had cost at least 1,9x the optimal clustering. Furthermore, using just the predictor labels naively resulted in a clustering with cost up to five orders of magnitude larger than the op- timal clustering. In contrast, our algorithm was able to precisely recover the true clustering after processing the predictor outputs. In addition, applying our algorithm using the labels of sample run of kmeans + was also able to precisely recover the true clustering.
E.3 COMPARISON TO LLOYD'S HEURISTIC
We give both theoretical and empiricial justifications for why our algorithms could be superior to blindly following predictor and then running Lloyd's 's heuristic.
PAY
0.00
"redictor Layyt
0.65
Liytts
0.63
Linyds
0.:4
0.65
0.02
0.62
0.81
0.60
of Loyd fttestions
beracions
(a)
(b)
(c)
Figure 4: Additional experimental results for comparison to Lloyd's heuristic.
Empirical Comparison. We first compared Lloyd's algorithm on kmeans+ seeding to our al- gorithm with the predictor on the PHY dataset. The predictor is a noisy predictor that has corruption level 50% as described in Section 4 so that outputting the clustering from the predictor alone has cost 1.9x the average kmeans+- cost. Hence, it is clear that the predictor is much worse than kmeans++, yet our algorithm using the predictor (horizontal line in Figure 4(a)) much better than kmeans++ and Lloyd's algorithm (orange line in Figure 4(a)).
Next, we took the noisy predictor for the PHY dataset with corruption level 50% and repeatedly applied Lloyd's algorithm. We observe that even with 5 Lloyd's iterations (Figure 4(b)), the clustering cost does not seem to improve upon kmeans++, much less the clustering output by simply applying our algorithm to the noisy predictions (Figure 4(a)).
Finally, we compared Lloyd's algorithm on kmeans++ + sceding to Lloyd's algorithm on the seed- ing output by our algorithm (with kmeans++ as the predictor) on the CIFAR-10 dataset, similar to the experiments you suggested by Lattanzi & Sohler (2019). Lloyd's algorithm on the seeding out- put by our algorithm exhibits superior performance than Lloyd's algorithm on kmeans+ (Figure 4(c)), which is consistent with our previous experiments showing that our algorithm improves upon kmeans+ This further strengthens our claim that our algorithm and methodology with provable worst-case guarantees can be applied in conjunction with heuristics such as Lloyd's that do not have provable worst-case guarantees. Moreover, Figure 4(c) indicates that our approach may be more advantageous than just running kmeans++ + + with heuristics. Note that naïve implementation of Lloyd's algorithm O(dkk) time while our algorithm can be implemented in nearly linear time.
We emphasize that all of our above experiments use noisy predictor with corruption level 50% as input to our algorithm. Our experiments exhibit even better behavior when clustering produced by kmeans++ + is used for predictor as input to our algorithm. Combined with our other experiments in Section 4, this gives empirical evidence that there exist many scenarios in which running our algorithm with an erroneous predictor is ad advantageous.
Theoretical Comparison. We now provide an example that demonstrates why blindly following the predictor and then running Lloyd's Is heuristic would run into issues. We emphasize that it is well- known e.g., see Dasgupta (2003); Har-Peled & Sadri (2005); Arthur & Vassilvitskii (2006); Vattani (2011), that Lloyd's 's algorithm can take large number of steps converge. In particular, Vattani (2011) shows that an exponential number of Lloyd iterations can be required for the algorithm to converge to the optimal solution. Nevertheless, we offer the following concrete answer:
27

---

Published as a conference paper at ICLR 2022
We describe simple set of points that guarantees Lloyd's algorithm will fail. This is based on the example given in Har-Peled & Sadri (2005) and is also conceptually similar to the example given in 1.1. Consider 4n points on the real line I1...., F2n, 22n. V...... 92n so that y1 ... S V2n S A < B S 21 & S F2a where B - A is large. Suppose k = 2 in which case the optimal clustering groups all the Yt points together and all the I2 points together as two separate clusters. Suppose the predictor initially gives label "1" to points yi,...., In and gives label "2" to points gn+1..... II,............................. .... 22n, so that the predictor has corruption level uses this predictor will get a constant-facte approximation in only one iteration. However, since B A can be arbitrarily large without affecting the optimal clustering cost, blindly listening to the predictor will give a worse clustering. Furthermore, Theorem 2.1 in Har-Peled & Sadri (2005) implies that Lloyd's will take (n)) iterations to converge if initialized using this predictor. Note that even a single (naïve) iteration of Lloyd's algorithm already uses ((ddk) time while our algorithm only uses (nd) + poly(k: (k: 1/a) time. Note that there are also more complex examples in higher- dimensional spaces in the literature which provably have even worse convergence rates for Lloyd's method.
1/2. Then our algorithm that
E,4 CONCLUSION
Although .07-appprxximationn for k-means clustering in polynomial time is NP-hard and clustering consistent with the labels of any predictor with nonzero eπror can be arbitrarily bad, we give a (1 + -pprooxxiiitoo algorithm that uses the labels output by the predictor as "advice" and runs in nearly linear time. We use linear number of queries to the predictor, which can be improved to nearly optimal under natural assumptions about the cluster sizes. Our results are well-supported by empirical evaluations and are an important step in demonstrating the power of algorithms beyond the limitations of classical algorithms for clustering-bast applications.
F LEARNABILITY RESULTS
In this section, we present formal learning bounds for learning a good predictor for the learning- augmented k-means problem. Namely, we show that a good predictor can be learned efficiently if the problem instances are drawn from a particular distribution. Our result is inspired by derived from data-driven algorithm design and utilizes the PAC learning framework. Formally, our setting is the following.
Suppose there exists an underlying distribution D that generates independent k-means clustering instances, representing the case where similar instances of the k-means clustering problem are being solved. Note that this setting also mirrors some of our experiments in Section 4, specifically in the case of our spectral clustering datasets which are derived from snapshots of a dynamic graph across time.
Our goal is to efficiently learn a good predictor f among some family of functions F. The input to each predictor f is clustering instance C and the output the each input instance C is encoded as a vector in Ran, that is, we think of nd as the size of the description of the input. We also assume that the output of f is in n dimensions, which represents the prediction of the oracle. For example in the case of k-means clustering, the output can be an integer in [k] for each point in C.
feature vector. We assume that
To select the "best" f. we need to formally define what we mean by best. In most learning settings, a loss function is used to measure the quality of a solution. Indeed, suppose we have loss function L : x C > R which represents how well a predictor f performs on some input C. For example, f can represent the cluster labels of a points in C and outputs the cost of the clustering. Alternatively, L can represent an algorithm which uses the hints given by I and performs clustering algorithm such as some number of steps of Lloyd's ' heuristic.
Our goal is to learn the best function f E F that minimizes the following objective:
(2) We define fo to be optimal function f E F, that f = arg min Ecn We also assume that for each clustering instance C' and each f E ((C) and L(f, C.) can be computed in time T(n, d) that should be interpreted (small) polynomial in and d.
Ec-D|L(f.O)]
28

---

Published as a conference paper at ICLR 2022
Our main result is the following.
Theorem F.1. There exists an algorithm that uses poly(T(n,,)) 1/e) samples and returns a that satisfies
Ec-DlL(f, CJ EC_D
with probability at least 9/19
The above theorem is a PAC-style bound that shows only a small number of samples are needed in order to have good probability of learning approximately-opiina function f. The algorithm to compute is the following: samples are drawn, i.c., we perform empirical risk minimization. This result is proven by Theorem F.3. Before introducing it, need to define the concept of pseudo-dimension for function class, which is the more familiar VC dimension, generalized to real functions.
simply minimize the empirical loss after an appropriate number of
Definition F22
DimenssoD e.g., Definition 9 Lucic et al. (2018)). Let X be a ground set and JF be a set of functions from X to the interval [0, 1]. Fix set S = {II, .In) C X, set of reals numbers R (ri,... [Tn] with r; E [0. 1] and a function
F. The set S = {rx E f(x)) 2 r is called the induced subset of S formed by f and R. The set S with associated values R is shattered by F K largest shattered subset of X (or oo).
FHH = 2". The pseudo-dimension of F is the cardinality of the
The following theorem relates the performance of empirical risk minimization and the number of samples needed, ppeudo-dimession We specialize the theorem statement situation hand. For notational simplicity, we define G be the class of functions in F composed with
= (L o f F).
Furthermore, by normalizing,
assume that the range of L. is equal [0, 1).
Theorem F3 (Anthony & Bartlett (1999)). Lel 'D be distribution over problem instances C and be a class of functions g C [0, with pseudo-dimension dg. Consider i.i.d. samples C1, C2....,Cr, C. D. There is a universal constant co, such that for any = > 0, if 2 dg/s?, then we have
Σ (C.) (C-Dg(() SE
i=1
for all g E 9 with probability least 9/10.
The following corollary follows from the triangle inequality.
Corollary F.4. Consider set of independent samples Cı...., from 'D and 9 be a function G that minimizes & Et=1 1 (C..). If the number of samples is chosen as Theorem F.3, then Ec~ple(C)) S EE-Dlg (C)) +
holds with probability at least 9/10.
Therefore, the main challenge at hand is to bound the pseudo-dimension our given function class G. To do so, first relate the neeudo-dimension to the VC dimension of a related class of threshold functions. This relationship has been fruitful in obtaining learning bounds in variety of works such Lucic et al. (2018); Izzo et al. (2021).
Lemma F,5 (Pseudo-dimension to VC dimension, Lemma 10 in Lucic et al. (2018)). For any E G, let Bg be the indicator function of the region on or below the graph of g. i.e. By y)
sgn(g) x)) - y). The pseudo-dimensia of G is equivalent to the VC-dimension of the subgraph class
Bg { Bg g).
Finally, the following theorem relates the VC dimension of a given function class to its computa- tional complexity, i.e., the time complexity of computing function the class.
Lemma E6 (Theorem 8.14 in Anthony & Bartlett (1999)). Let h Ra x R2 + {0, 1}, determining the class
= - h(0,z) R*).
Suppose that any h can be computed by an algorithm that takes as input the pair (0,z) E R x R and returns h(0,zz)) x) after more than of the following operations:
29

---

Published as a conference paper at ICLR 2022
arithmetic operations +, - x, and / real numbers,
jumps conditioned on 7, 2, S =, and comparisons of real numbers, and
output 0,
then the VC dimension of H. is + +faloga).
Combining the previous results allows us prove Theorem F.1. At high level, we are instantiating Lemma F.6 with the complexity of computing any function in the function class G.
Proof of Theorem F.I. First by Theorem F.3 and Corollary F.4, it suffices to bound the pseudo- dimension of the class = F. Then from Lemmas F.5, the pseudo-dimension of G is the VC dimension of threshold functions defined by G. Finally from Lemma F.6, the VC dimension of the appropriate class of threshold functions polynomial in the complexity of computing a member of the function class. other words, Lemma F.6 tells that the VC dimension of Bg defined in Lemma F,5 is polynomial in the number of arithmetic operations needed to compute the threshold function associated to some g By our definition, this quantity is polynomial in T(n, d). Hence, the pseudo-dimensio dimension of g is also polynomial in T(n, d) and our desired result follows.
Note that we can consider initializing Theorem F. with specific predictions. If each function in the family of oracles
interested can be computed efficiently, which is the case of the predictors we employ in our experiments, then Theorem F. assures us that we only require polynomially many samples to be able to learn nearly optimal oracle.
Note that our result is in similar in spirit to the recent paper Dinitz et al. (2021). They derive sample complexity learning bounds for different algorithmic problem of computing matchings in graph. Since they specialize their analysis to specific function class and loss function, their bounds are possibly tighter rather than the possibly loose polynomial bounds we have stated. However, our analysis above is more general as it allows for a variety of predictors, as we employ in our experiments, and loss functions to measure the quality of the predictions.
30


Reviews:
[{"review_id": "zlHGdoMXSf2", "reviewer": "Reviewer_4io3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths: \n\n1. The problem is interesting. Given the fact that hard clustering is generally NP-hard in the worst-case, it make sense to try and mimic/find scenarios where this discouraging fact can be bypassed, e.g., by introducing reasonable side information. As the authors mentioned, perhaps the first attempt for introducing such side information is the SSAC framework. This paper introduce another possible approach.\n\n2. The paper is well-written and motivated.\n\n3. The numerical part is thorough.\n\nWeaknesses:\n\n1. Similarly to the SSAC framework, it is unclear to me if such a predicator(s) exist in practice. I appreciate that, at least, based on the way things are presented the current framework seems to be more \"practical\" than the SSAC framework. In particular, I am not completely sure what is required by the predictor; unless I am missing something trivial, we need the \\alpha to be less than 1/7, which to me seems completely not easy to obtain. How you managed to do that in your experiments? \n\n2. I am not sure if it is a real weakness, but I find both the algorithm and (especially) the analysis quite standard or at least not surprising. Perhaps the authors could elaborate a bit more on the technical novelty in their proofs.", "summary_of_the_paper": "This paper considers the problem of k-means clustering with the aid of a predictor which supplies a proxy to the optimal clustering subject to some possible errors. The motivation for this setting is the inherent computational issues with solving the vanilla k-means clustering problem. For this model, the authors propose and analyze an efficient algorithm whose approximation factor scales gracefully with the predictor error guarantees. ", "summary_of_the_review": "See above. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tChLFBOyviZ", "reviewer": "Reviewer_Ftwn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "I’d like to point out that this setting/algorithm is conceptually different (and weaker) from many previous papers on learning-augmented algorithms (cf. [Competitive Caching with Machine Learned Advice, Lykouris and Vassilvitskii, J. ACM]), in the sense that this algorithm does not have strong guarantee when the prediction is very inaccurate (for instance, Theorem 2.1 requires \\alpha to be at most 1/ 7). Instead, the focus of this algorithm seems to be “de-noising” an already good but slightly noisy predictor. This could be a limitation of the work, since “good” predictors themselves may not be easily obtained, and it could be that the major issue of using predictions is not to be “misled”. Nonetheless, I can still see that this “de-noising” setting make sense, and it is relevant in dealing with adversarial data set. But I’d still like to see how your algorithm performs, when the predictor is inaccurate (e.g., it is only 10 approximation?)\n\nI also have other concerns about some proof details and the experiment results. The major ones are listed as follows.\n1.\tLemma A.4. In the proof, one of the step is to use Chernoff bound to argue |I \\cap X_2| >= m(1 – 6 \\alpha). Can you elaborate how Chernoff bound is applied? Note that I and X_2 are not independent and both of them are random (recalling that X_2 is the complement of X_1, and I is defined w.r.t. X_1, so they both depend on the random set X_1). \n2.\tIn Figure 1 (a), it seems Alg+Predictor and Alg+k-means++ are highly correlated, but the performance of predictor and k-means++ are shown to be quite different in some of the graphs. Can you explain why this happens? Also, this correlation is not observed in Figure 1 (b). Can you also explain why is the difference?\n3.\tIn your experiments, it seems k-means++ baseline only runs the random seeding step, without any iteration of Lloyd heuristic. I suggest to run at least one round of Lloyd’s heuristic after your seeding as another baseline, since your Algorithm 1 is essentially Lloyd if in Algorithm 2 no bad point is eliminated.\n\nOverall, this is an interesting paper, and it is somewhat the first of its kind, in the sense that it studies how machine-learned advice could help to improve the *time complexity* of k-clustering, instead of looking at the competitive ratio as in the commonly studied online setting. I would be glad to accept the paper if the authors could properly address my major concerns in the follow-up discussions.\n\nMinor comments:\n\n1.\tLemma A.9, please specify what “these points” refer to, in the second line of the statement.\n2.\tIn the proof of Lemma A.11, could you remind the definition of p, in the displaymath?\n3.\tAlso in the proof of A.11, 2. The equation below ‘By Markov’s Inequality, …’, should be ‘\\sum_{i \\in [k]} |X_i|*||C_i-\\gamma_i||_2^2’ instead of ‘\\sum_{i \\in [k]} ||C_i-\\gamma_i||_2^2’ ?\n4.\tPage 9, the paragraph about CIFAR-10. You mentioned that your algorithm “could improve upon this highly precise predictor” – I think the claim is a bit weird, because the neural network predictor is for the purpose of classification, while your task is clustering. The objectives might be related, but I don’t see a strong correlation, and it’s possible that this neural network baseline has a bad clustering cost. Hence, your improvement over the neural network one is not clearly convincing to me. I suggest to also show the clustering cost of the neural network predictor.\n5.\tI don’t get why your Theorem 2.1 needs O(kdn) time – it seems to be Algorithm 1 + Algorithm 2 only takes O(nd) time, because each iteration of the for-loop in Algorithm 1 takes O(|Y_i|) time/accesses to the predictor, and \\sum_i |Y_i| = n? This also confuses me about the necessity/improvement of Theorem 3.4.\n", "summary_of_the_paper": "The paper studies k-means problem in a learning-augmented setting. Recall that in k-means, a point set $P \\subset \\mathbb{R}^d$ is given and the goal is to find a set $C$ of $k$ centers, such that $\\mathrm{cost}(P,C) = \\sum_{p \\in P} \\min_{c \\in C} \\|p-c\\|_2^2$ is minimized. In addition to the input point set, a predicted solution, which is an approximately optimal clustering of $P$, is also provided in the proposed learning-augmented setting. The algorithm can access this solution by querying the predictor the cluster that a point $x$ belongs to. \n\nThe main result is an algorithm that can leverage the predictions. For $\\alpha \\in (10 \\log n / \\sqrt{n}, 1/7)$, given access to a predictor with label error rate $\\lambda \\leq \\alpha$, and let $\\gamma \\geq 1$ be a sufficiently large constant, if the predicted solution satisfies all clusters has at least $\\gamma k \\log k / \\alpha$ points, then the algorithm outputs a $(1+20\\alpha)$-approximate solution with probability at least $3/4$, using $O(nd \\log n + \\mathrm{poly}(k, \\log n))$ total time.  Furthermore, the algorithm only uses $\\tilde{O}(k / \\alpha)$ queries to the predictor for outputting the centers. The authors claim that for any $\\delta \\in (0,1]$, any algorithm makes $O(k^(1-\\delta)/(\\alpha \\log n))$ queries to the predictor with label rate $\\alpha$ cannot output a $(1+C \\alpha)$-approximate solution for k-means problem in $2^{O(n^(1-\\delta))}$ time, assuming ETH.  The authors also experimented with their algorithm on three datasets, along with three different predictors. The experiment result shows that their algorithm significantly improves the performance when using with predictor or k-means++, and has a stable accuracy against corrupted predictors. \n\nTechnically, since it is guaranteed that the predicted solution is a $(1+\\alpha)$ approximately optimal solution, with some of the labels corrupted, Algorithm 1 aims to reconstruct centers of each cluster $X$ in $(1+\\alpha)$-approximately optimal solution, i.e. find point $c$ such that $\\mathrm{cost}(X, c) \\leq (1+O(\\alpha)) \\mathrm{cost}(X, C_X)$. Notice that $d$ dimensions are independent of each other in k-means objective. Hence Algorithm 1 can estimate each coordinate of $c$ independently, which is implemented by Algorithm 2.  Then Algorithm 2 (randomly) divides the input (1D) data points into two parts, and one part is used for the computation of interval $I$, an estimation of the value range of the uncorrupted data points. Then the points outside $I$ are filtered out and the mean of the remaining coordinates are returned as the final estimation.  \n", "summary_of_the_review": "This is an interesting paper that has both conceptual and technical novelties. However, I also see some technical issues in the paper, and I'd like to accept the paper if those issues are addressed properly.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "oEwfwPs_AZw", "reviewer": "Reviewer_dm82", "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": "The paper is nicely written, with the motivation clearly stated. The $k$-means clustering is a fundamental, yet important problem. The authors consider a setting in which some prior knowledge about the clustering is available, and derive a statistical method to recover the solution with some provable guarantees. \n\nWeakness\n\n• The theorem applies when the label error is small, less than 1/7. However, it might be non-trivial to obtain a predictor with that quality in the first place. For example, in the experiments, the initial solution are derived from $k$-means (Lloyd's) algorithm, which might require many initial seeds to attain a good solution. Are there any guarantees can be made when the initial label error is larger? \n\n• When $k$ gets larger, the $k$-means algorithm (even with $k$-means++) solution can be stuck at local minima, with arbitrarily worse objective [1]. How would algo+$k$-means++/predictor behave compare with $k$-means++ (with multiple seeds)? Can the algorithm help escape the local minima and attain a much better solution? There is a collection of synthetic datasets [1] for k-means to understand the performance of the algorithm. I suggest the authors take these benchmark datasets into consideration for the experiments for evaluation. In the current experiment, only $k=10$ and $k=25$ are tested, and it is hard to see the comparison of algorithms when $k$ gets larger, which is a more challenging case for the $k$-means problem. \n\n• Minor suggestion: the average of $k$-means objectives with multiple seeds are used as a baseline, I think the minimal $k$-means objective over multiple seeds is more reasonable. \n\n\n[1] Jin, Chi, et al. \"Local maxima in the likelihood of gaussian mixture models: Structural results and algorithmic consequences.\" Advances in neural information processing systems 29 (2016): 4116-4124.\n[2] Fränti, Pasi, and Sami Sieranoja. \"K-means properties on six clustering benchmark datasets.\" Applied Intelligence 48.12 (2018): 4743-4759.", "summary_of_the_paper": "This work aims to find a solution of the k-means clustering problem based on (prior) predicted labels. Here the predicted labels could be obtained from some clustering algorithms or some supervised models, with additional noise. A polynomial time procedure (Algorithm 1) is proposed as follows: for each fitted component from the predicted labels, a robust mean is computed (in a coordinate wise way). These robust means are output as the final clustering solution. The running time is $O(knd\\log n)$. The paper rigorously establishes a theoretical guarantee on the approximation ratio of the solution assuming the predictor label has a bounded label error. To further improve the running time, the authors utilize dimension reduction technique to cluster $O(k/\\alpha)$ points in dimension $O(\\log n)$ and then obtain the label for original data points with approximate nearest neighbor data structure. This modified approach (Algorithm 3) has running time $O(nd\\log n+\\text{poly}(k,\\log n))$ and attains a solution with a similar theoretical guarantee. To empirically evaluate the proposed method, the authors perform experiments on synthetic data and a few real datasets. The experiments demonstrate that the proposed method with $k$-means++ initialization achieves better performance than $k$-means++; moreover, the performance is competitive and robust even when the predictor labels are corrupted. ", "summary_of_the_review": "The paper provides a simple and practical approach to obtain a clustering solution from some predictor labels. A rigorous analysis of the algorithm has been provided. I would recommend the paper to be accepted. For further improvement, the authors need to address, at least empirically, if not theoretically (1) robustness of the algorithm to different level of label error, i.e., the performance of the algorithm when the assumption fails (2) robustness of the algorithm to different $k$, the number of components. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: One might assume that the k-means problem has already been beaten to
death, but this paper shows there are still remaining questions. And
rather interesting ones at that, with a novel angle of having
additional help from a prediction algorithm of cluster
memberships. This connects to learning-augmented algorithms research.

The reviewers agreed that the problem is interesting and gives a novel
angle, and the interestingness stems from novelty, and the ability to
"escape" from NP-hardness.

The reviewers and authors had nice discussions about details and
conclusions, on how limiting is it that the authors focus on
reasonably accurate predictors, for instance, and where could the
predictors come from. This is a good paper, and hopefully the
discussion helped make it even better.
Decision: Accept (Spotlight)