Near-optimal Coresets for Robust Clustering
Authors: Lingxiao Huang
Shaofeng H.-C. Jiang
Jianing Lou
Xuan Wu
Venue: ICLR 2023 notable top 5% (2023)
Keywords: clustering
outlier
robustness
coreset

Abstract: We consider robust clustering problems in $\mathbb{R}^d$, specifically $k$-clustering problems (e.g., $k$-Median and $k$-Means) with $m$ \emph{outliers}, where the cost for a given center set $C \subset \mathbb{R}^d$ aggregates the distances from $C$ to all but the furthest $m$ data points, instead of all points as in classical clustering. We focus on the $\epsilon$-coreset for robust clustering, a small proxy of the dataset that preserves the clustering cost within $\epsilon$-relative error for all center sets. Our main result is an $\epsilon$-coreset of size $O(m + \mathrm{poly}(k \epsilon^{-1}))$ that can be constructed in near-linear time. This significantly improves previous results, which either suffers an exponential dependence on $(m + k)$ [Feldman and Schulman, SODA'12], or has a weaker bi-criteria guarantee [Huang et al., FOCS'18]. Furthermore, we show this dependence in $m$ is nearly-optimal, and the fact that it is isolated from other factors may be crucial for dealing with large number of outliers. We construct our coresets by adapting to the outlier setting a recent framework [Braverman et al., FOCS'22] which was designed for capacity-constrained clustering, overcoming a new challenge that the participating terms in the cost, particularly the excluded $m$ outlier points, are dependent on the center set $C$. We validate our coresets on various datasets, and we observe a superior size-accuracy tradeoff compared with popular baselines including uniform sampling and sensitivity sampling. We also achieve a significant speedup of existing approximation algorithms for robust clustering using our coresets.

Published as a conference paper at ICLR 2023
NEAR-OPTIMAL CORESETS FOR ROBUST CLUSTERING
Lingxiao Huang
Shaofeng H.-C. Jiang
State Key Laboratory of Novel Software Technology,
Peking University Email: shaofeng. farlng.jiangee lrangppku.edu.. cn
Nanjing University
Email: www.ggiigg.ail1900000000 http:/iaaal99111... com
Jianing Lou
Xuan Wu
Peking University
Huawei TCS Lab
Email: Loujn@pku. edu. cn
Email: wu341 211127900gmg 00 com
ABSTRACT
We consider robust clustering problems in R specifically k-clustering problems (e.g., k-MEDIAN and k-MEANS) with outliers, where the cost for given cen- ter set C. C IR aggregates the distances from C' to all but the furthest m data points, instead of all points as in classical clustering. We focus on the e-coreset for robust clustering, small proxy of the dataset that preserves the clustering cost within e-relative error for all center sets. Our main result is an e-coreset of size 0m + poly(ke ))) that can be constructed in near-linear time. This significantly improves previous results, which either suffers an exponential de- pendence on (m + k) (Feldman & Schulman 2012). or has a weaker bi-criteria guarantee (Huang et al. 2018). Furthermore, we show this dependence m is nearly-optimal, and the fact that is isolated from other factors may be crucial for dealing with large number outliers. We construct our coresets by adapting to the outlier setting recent framework (Braverman et al., 2022) which was designed clustering, overcoming a new challenge that the partici-
for rapacity-constraing pating terms in the cost, particularly the excluded m outlier points, dependent on the center set C. We validate our coresets on various datasets, and we observe superior size-accuracy tradeoff compared with popular baselines including uni- form sampling and sensitivity sampling. We also achieve a significant speedup of existing approximation algorithms for robust clustering using our coresets.
INTRODUCTION
give near-optimal e-coresets for k-MEDIAN and k-MEANS (and more generally, (k, z)- CLUSTERING) with outliers in Euclidean spaces. Clustering is a central task in data analysis, and popular center-based clustering methods, such as k-MEDIAN and k- b-MEANS, have been widely ap- plied. In the vanilla version of these clustering problems, given a center set of k points C, the objective is usually defined by the sum of (squared) distances from each data point to C.
This formulation, while quite intuitive and simple use, has severe robustness issues when dealing with noisy/adversarial data; for instance, an adversary may add few noisy outlier points that are far from the center to "fool" the clustering algorithm wrongly put centers towards those points in order to minimize the cost. Indeed, such robustness issue introduced by outliers has become major challenge in data science and machine learning, and it attracted extensive algorithmic research on the topic (Charikar et al.] 2001 Chen 2008; Candès et al.] 2011 Chawla & Gionis 2013 Mount al. Gupta et 2017 Statman
2020 Ding Wang 2020). Moreover, similar issues have also been studied from the angle of statistics (Huber & Ronchetti 2009).
Robust Clutering We consider robust versions of these clustering problems, particularly a natural and popular variant, called clustering with outliers (Charikar et al., (001). Specifically, given a dataset X Rdd the (k, z, 2, ROBUST CLUSTERING problem to find center set C C Rd of

---

Published as a conference paper at ICLR 2023
points (repetitions allowed), that minimizes the objective function
cost (m) (X,C)
min
Σ (dist(a, C))².
(I)
I.X:I DEXIL
Here, L denotes the set of outliers, dist denotes the Euclidean distance, and dist C) = min,ge dist(x,,)) c). Intuitively, the outliers capture the furthest points in cluster which are "not well-clustered" and are most likely to be the noise. Notice that the parameter z captures various (robust) clustering problems, including (k. ---OBUUS MEDIAN (where
1). (k, -RBBUST MEANS (where = 2). On the other hand, if the number of outliers m = 0 then the robust clus- tering problem falls back to the non-robust version. The (k, 2, m ROBUST CLUSTERING problem has been widely studied in the literature (Chen, [2008] Gupta et al. 2017 Krishnaswamy et al., 2018 Friggstad et al. 2019; Statmann et al. 2020). Moreover, the idea of removing outliers has been also considered in other machine learning tasks, e.g., robust PCA (Bhaskara & Kumar 2018 and robust
regression Rousseeuw & Leroy 1987 Mount et al. (2014).
Computational Challenges However, the presence of outliers introduces significant computa- tional challenges, and it inspires a series of research to design efficient algorithms for robust clus- tering. On one hand, approximation algorithms with strict accuracy guarantee has been obtained (Charikar et al.
Gupta et al., 2017] Krishnaswamy et al. [2018] [ et al., [2019] 2019 Zhang et al. 2021) but their running time is high-degree polynomial which On the other hand, more scalable algorithms were also proposed (Bhaskara et al.) 2019 Deshpande er al., 2020), however, the approximation ratio worse, and a more severe limi- tation is that their guarantee usually violates the required number of outliers. Moreover, to the best of our knowledge, we are not aware of works that design algorithms in sublinear models, such as streaming and distributed computing.
2001
Friggstad et al.
impractical.
Coresets In order to tackle the computational challenges, we consider coresets for robust clus- tering. Roughly, an 6-coreset tiny proxy of the massive input dataset, on which the clustering objective is preserved within c-error for every potential center set. Existing algorithms may benefit significant speedup if running on top of a coreset, and more importantly, coresets can be used to derive sublinear algorithms, including streaming algorithms (Har-Peled & Mazumdar) 2004), dis- tributed algorithms (Balcan et al. 2013) and dynamic algorithms (Henzinger Kale 2020), which highly useful to deal with massive datasets.
Stemming from Peled Mazumdar (2004), the study of coresets for the non-robust version of clustering, i.c.. 2 --LU-TEUUUNIGGGG has been very fruitful (Feldman & Langberg 2011
Feld-
man et al. 2020 Sohler & Woodruff 2018 Huang & Vishnoi] 2020) Braverman et al. 2021
Cohen-Addad al. [2021b] Braverman al.] 2022), and the state-of-the-ar coreset achieves size
poly(ke independent of and n. However, coresets for robust clustering were much less under- stood. Existing results either suffers an exponential (k++ m=)+*mm factor in the coreset size (Feldman)
& Schulman 2012), or needs to violate the required number of outliers (Huang et al. 2018). This gap leads the following question: can we efficiently construct an e-coreset of size poly(m, for (k, 2, 2.2,,,m)RRBUS CLUSTERING (without violating the number of outliers)?
1.1 OUR CONTRIBUTIONS
Our main contribution, stated in Theorem 1.1 is a near-optimal coreset for robust clustering, affir- matively answering the above question. In fact, we not only achieve poly (m)). but also linear in m and is isolated from other factors. This can be very useful when the number of outliers m is large.
Theorem 1.1 (Informal; see Theorem 3.I There exists a near-linear time algorithm that given data set X C Rd 2 1, E (0, 0.3) and integers m 1, computes an e-coresel of X for (k, 2, m)- ROBUST CLUSTERING of size O(m) + 20(a log log=) -3z-2), with constant probability.
Our coreset improves over previous results in several aspects. Notably, compared with Feldman & Schulman (002)). our result avoids their exponential (k (+++ m)) factor in the coreset size which is likely to be impractical since typical values of k and/or m may be Ollog n)) In fact, observed in our experiments, the value of m can be as large as 1500 in real datasets, so the dependence in Feldd man & Schulman (2012) is prohibitively large which leads to inferior practical performance
2

---

Published as a conference paper at ICLR 2023
(see Section Moreover, coreset has strict guarantee for outliers instead of a bi-criteria guarantee as in Huang et al. 2018) that needs to allow more or fewer outliers in the objective for the coreset. We also note that our coresct is composable (Remark B.2). Furthermore,
show that the linear dependence in m is necessary (Theorem 1.2). Hence, combining this with a recent size lower bound of (2(ke-2) (Cohen-Addad et al. 2022) for vanilla clustering (i.e., = 0), conclude that the dependence of every parameter (i.c., m, k, E) is nearly tight.
Theorem 1.2. For every integer m 2 1, there exists a dataset X C. I. of 2 m points, such that for every 0 < 0.5, any c-coreset for (1) ROBBUST MEDIAN must have size (1()).
For the lower bound, we observe that when m = 1, the clustering cost for m1, (.mm)-RRBBSS MEDIAN reduces to the distance to the nearest-neighbor from the center c. This is easily shown to require (1)) ((m) points in the coreset, in order to achieve any finite approximation. The formal proof can be found in Section
Experiments We evaluate the empirical performance of our coreset on various datasets (in Sec- tion 4 We validate the size-accuracy tradeoff' of our coreset compared with popular coreset con- struction methods. particularly uniform sampling (which pling (Feldman & Schulman 2012), and we observe that our coreset consistently outperforms these baselines in accuracy by sigmificant margin for every experimented coreset size ranging from 500 to 5000. We also run existing approximation algorithms on top of our coreset, and we achieve about 100x speedup for both a) a Lloyd heuristic adopted to the outlier setting (Chawla & Gionis) 2013) that is seeded by an vetsier-vession of k- K-MEANS++ (Bhaskara et al., 2019), and b) a natural local search algorithm (Friggstad et al. 2019). These numbers show that our coreset is not only near-optimal in theory, but also demonstrates the potential to be used in practice.
natural heuristic) and sensitivity sam-
1.2 TECHNICAL OVERVIEW
Similar to many previous coreset constructions, we first compute near-optimal solution, an (a, appproxxmaai (see Definition 2.2p C* := {cr I i E [ák]], obtained using known ap-
proximation algorithms (see the discussion in Section (A). Then with respect to C*, we identify the outliers 1a C X of C' and partition the remaining inlier points X LL into |
clusters {Xi}.
We start with including L' into our coreset, and we also include weighted subset of the remaining inlier points X \ L by using a method built upon a recent framework Braverman et al. 2022 which was originally designed for clustering with capacity constraints. The step of including L' in the coreset is natural, since otherwise one may miss the remote outlier points which can incur huge error; furthermore, the necessity of this step is also justified by our Q(m) lower bound (Theorem T.2p. Similar to |Braverman et al. (2022). for each cluster X; among the remaining inliers points X Lt, we identify a subset of X; that consists of poly(ke-)) rings, and merge the remaining part into poly(ke-) groups of rings such that each group G has a tiny cost (Theorem 3.3). We use general strategy that is similar to Braverman et al. (0022 to handle separately the rings (Lemma (36) and groups (Lemma 3.7). but the actual details differ significantly due to the presence of outliers.
Handling Rings Similar to Braverman et al. 2022). ). for a ring data subset It = ring(e,, rr, 2r) C
X,, i.e., a subset such that every point is similar distance (up to factor of 2) to the center c,, we apply a uniform sampling on it to construct a coreset (with additive error, Definition 3.5) In Braverman et al. (2022). for any center set C C Rd, the error incurred by uniform sampling is bounded by e-cost, RR, C) which is times the total cost without outliers from R to C' (ignoring some neglectable additive term). However, in the presence of outliers, their error bound e cost,, (R, C') can (R, hardly be charged to cost (man) (R. C"), where m is the number of outliers in R with respect to C.
This is because cost (ma) (omt, (R, C') can be very small and even close to 0 when ma R RR. Moreover, the number of outliers ma is not known priori and can be any number between 0 and Hence, we provide a stronger guarantee (Lemma 3.6) where we give an alternative upper bound which eventually charges the error to E cost! (m)) (R, C') and e opt.. We use the fact that cost! (m)) (R2 C') is "small enough" compared to opt for large mgg while for small ma, we rewrite the robust clustering cost as integration of ball ranges (Fact F.II) and use fact that uniform sampling approximately estimates all ball ranges (Lemma F.3). Similar idea of writing the cost as an integration has also been used in previous works, e.g.. Huang al. (2018); Braverman et al. (0022..
3

---

Published as a conference paper at ICLR 2023
Handling Groups The main technical difficulty is to handle groups (Lemma 3.7 We still con- struct a two-point coreset (Definition 3.4) for every group G C X,, as in Braverman et al. (2022). To analyze the error of this two-point coreset for an arbitrary center set C R we partition the groups into colored and uncolored groups with respect to C' (Lemma G. in a way similar to Braverman al. (2022). Let us call a group G "bad" if the error incurred by the two-point coreset is much larger than E cost. (ma) (G, C"), which is E times the contribution of G. We focus our discussion on bounding the error of bad groups. We first show even with outliers (in Lemma G.I), the error for each bad group is at most 6 cost, (G, C*). Hence, it remains to bound the number of bad groups. In Braverman et al. (2022). only colored group can be bad, and the number of them is bounded by
Ok (olog E). However, in the outlier setting a key difference to Braverman et al. (0022 is that, un-
colored groups can also be bad (due to a reason similar to that for rings: cost. !T (G, C*) may be too small when the number of outliers mg in G is large), and we call them "special uncolored groups" (22). To bound the number of them, in Lemma G.5 we make a crucial geometric observation: even though special uncolored groups may significantly change for varying C"s, invariant is that they must always be consecutive uncolored groups, due to the way we decompose X;, and apart from the two groups that partially intersect the outliers, every other group within the consecutive sequence consists of outliers only. This key geometric observation implies the number of such groups is ((1) (Lemma G.5). and consequently. the total number of bad groups most O log e) with respect to any C.
Finally, in addition to the above new steps, we remark that it is also necessary to make these bounds for rings/groups work for all numbers of outliers 0 S t S m "simultaneously", since one does not know advance how many outliers reside each ring/group due to the arbitrarily chosen C.
1.3 OTHER RELATED WORKS
Robust Clustering in Rd Robust clustering, first proposed by Charikar et al. (2001). }. has been studied for two decades. For (k, RO-RUUSST MEDIAN, Charikar et al. (2001) designed a bi-criteria approximate algorithm with violations k. Chen (2008) first showed pure constant approximate algorithm, whose approximate ratio was improved to 7.081 + c (Krishnaswamy et al. 2018). When MEDIAN. For (k: m)- ROBUST MEANS, Gupta et all (2017) designed bi-criteria approximate algorithm with violations on m. Krishnaswamy
k = O(1), Feng et al. (2019) also proposed a PTAS for
(2018) first proposed constant approximate algorithm, and the approx- imate ratio was improved to 6+4 Feng et al. (211)). For general (k, 2, m)-ROBUST CLUSTERING, Friggstad et al. (2019) achieved an O(z)) approximate solution with (1 + e)k centers. Due to the wide applications, scalable algorithms have been designed for (k, ROBUST MEANS Bhaskara jt al. (2019); Deshpande et al. (2020) besides theoretical study, which may have a worse provable guarantee but are more efficient in practice.
Coresets for Clustering There is large body of work that studies coreset construction for vanilla (k, CLCUSTRRNG in I2 Har-Peled & Mazumdar (004)); Feldman & Langberg (2011); Braverman et al. (016);; Huang et al. (2018;; Cohen-Addad et al. (202Tb) Ib; 2022). The state-of- art result for general (k, CLLUSTERIN is by Cohen-Addad et al. (2022). where the coreset size is (()) -2, min (k) This bound nearly matches a lower bound of Ωike- + I min {d, 22/20/))) (Cohen-Addad et al. 2022 Huang & Vishnoi 2020). In addition, coresets for constrained clustering in Euchdean spaces has also been considered, such as capacitated clustering and the tightly related fair clustering (Schmidt et al., 2019 Huang et al., 2019:; Braverman et al.) 2022], and ordered weighted clustering (Braverman et al. 2019). Going beyond Euclidean spaces, coresets of size poly(ke were known for (k, CCLUSTERIG in doubling metrics (Huang al.
2018), shortest-path metrics of graphs with bounded treewidth (Baker et al. 2020) and graphs that exclude a fixed minor (Braverman al. 2021
2 PRELIMINARIES
For point Rd. and positive real numbers r' 0, define Ball(a, r) {o E IR,, dist(r, a) < r) and ring(a, r, r') = Ball(a, Ball(a, For a set of points A C Rd, Balls(A, A) Une ra.
Balls and Rings
4

---

Published as a conference paper at ICLR 2023
Weighted Outliers Since our coreset uses weighted points, need to define the notion of weighted sets and weighted outliers. We call a set S with an associated weight function ws : S + Ry0 weighted set. Given two weighted sets (X, wx) and (Y, such that Y S X and wy (z) S (x) for any I E Y, let X - Y denote a weighted set (Z, wz) such that wz wx wy and Z is the support of wz. Moreover, for weighted set X, we denote c(m) as the collection of all possible sets of weighted outliers (Y, wy) satisfying that Y S X, Evey (x) = m and that Vz X, Wy (z) S wx(x). In this definition, since X is a weighted point set, we need to pick outliers of total weight m in the objective cost." (mm) (X, C*), instead of m distinct points which may have a much larger weights than m.
Weighted Cost Functions For m = O, we write cost, for cost." (m)) We extend the definition of the cost function to that on a weighted set X c Rdd. For m = 0, we define cost.2 (xst,((,CC (X,C) == Exex (x(x)) (1, C))². For general m 2 1, the cost is defined using the notion of weighted outliers and aggregating using the cost, function which is the m = case.
cost! (X,
min {cost (X L, C)]. (L,3)))22)))
One can check that this definition a generalization of the unweighted case ① For a weighted set X C Rdd let the optimal solution be opt! (m)) (X) == mingeR', |C|== cost." (m)) ()
Definition 2.1 (Coreset). Given point set X Rd and E (0, 1), c-coreset for (k: 2, m)- ROBUST CLUSTERING is a weighted subset (S, wg) of X such that
AC c TRdd |C| = k,
cost (mm) (S, C) E (1 +) cost! ((m) (X; C)
Even though Definition 2.1 naturally extends the definition of coresets for vanilla clustering (Har- Peled & Mazumdar 2004 Feldman & Langberg 2011 Fellman et al.. 2020). it is surprising that this exact definition did not seem to appear in the literature. A closely related definition (Huang et al.) 2018) considers relaxed "bi-criteria" (with respect to the number of outliers) guarantee of the cost,
i.e. (1 - c) cost!" ! (1-8)mmmm-)))))0) (S.C) S cost." (1m) (X, C) < (1 + c) cost 11-8)mm (S, C), for 3 E [0. 1),
and their coreset size depends B-1 Another definition was considered in Feldman & Schulman (0122). which considers a more general problem called weighted clustering (so their coreset implies our Definition 2.1 Unfortunately, this generality leads an exponential-size coreset (in k; m).
Definition 2.2 ((a, 8, (..7))AAppooxinn .pproxxxiiit,,nn Given dataset X C Rd and real numbers a, B, > 1, an (a, B, apprrxxmmee solution for (k,, 2, m) -)-ROBUST CLUSTERING on X is a center set C* C
Rdd with |C*| x ,3k such that cost, (7m) (X, C*) I a opt (mm) (X).
3 CORESETS FOR (k, z, m) RROUUST CLUSTERING
We present our main theorem in Theorem 3.1 As mentioned, the proof of Theorem 3.1 is based on the framework in Braverman et al. (2022). and we review the necessary ingredients in Section 3.1 The statement of our algorithm and the proof of Theorem 3.1 can be found in Section 3.2
Theorem 3.1. Given input dataset P C. Rd with [P| n, integers k. m 2 L, and real number = and assume there exists an algorithm that computes an (a, 3, (3,7)))) appproximmaioon of P for (k, 2, m)- ROBUST CLUSTERING in time A(n, k, d, 2), then Algorithm| I uses time A(n, k. 2) + O(kkd) to construct a weighted subset (S, ws) with size |S| = -ym+22 20 (l0g)))) 3. (k33 1-33--3--22 -3:-2), such that with probability at least 0.9.for every integer 0 S t < m, S is ac-coreset S of P for (k, 2,, ROBUST CLUSTERING.
Remark 3.2. By rescaling to e/a in the input of Algorithm 1 obtain an e-coreset of size ymm + 20(zlog=), . 3=+22 (--(0---33-2) 32-2). We discuss how to obtain (a, 3, -pprroooxiiaas in Section A We also note that Theorem 3.1 actually yields an e-coreset for (k, ROBUST CLUSTERING si-
multaneously for every integer < t < m, which implies that our coreset is composable. Specifi- cally, if for every integer 0 < t < m, Sx is an e-coreset of X for (k, 2, t)- ROBUST CLUSTERING and Sy is an e-coreset of Y for (k:, z, ROBUST CLUSTERING, then for every integer 0 S 1 S m, Sx U Sy is an e-coreset of X U for (k, =, 1)- ROBUST CLUSTERING.
Here, if a & Y, we let wy (x)
5

---

Published as a conference paper at ICLR 2023
RG E R
R4 G2 EG
Ra
G1 Eg
Ra
Ri E ER
points
Figure 1: Illustration of Theorem 3.3
(plotted distance is the logarithm of the real distance).
3.1 THE FRAMEWORK OF BRAVERMAN ET AL. (2022)
Theorem
3.3 is general geometric decomposition theorem for coresets which crucially. It partitions an arbitrary cluster into poly(k/e) rings and merge the remaining rings into pkly(k/e) groups with low contribution cost (Xi; cf) (See Figure I for illustration.)
Theorem 3.3 (Decomposition into rings and groups (Braverman et al. 2022 Theorem 3.2)). Let
X C. Rd be a set and с E g be a center point. There exists an O(nkd)-tinn algorithm that computes a partition of X into two disjoint collections of sets R and G, such that X = (URERR) U (UGegG), where R is collection of disjoint rings satisfying
1. VR E R, R is a ring of the form = R&(XX c) for some integer i ZZU where R. (x( = --xXxring Krringle, 22-1,,,, 22) for Z and cx X {c)
2. R S 20 Ō(k==)
and G is collection of disjoint groups satisfying
1. VG G. G the union of consecutive rings of (X,c). Formally, VG G, there exists two integers -00 S la S TG such that G = U.e R, (X,,)) and the intervals [ll, G e
g} are disjoint for different G EEB E
2. 9 < 20(slogz), 30(kke))) and VG e G. costz S S (
co,t.((.e) 2210((222/e)
Rings and groups are inherently different geometric objects, hence they require different coreset construction methods As in Braverman et al. (2022), uniform sampling is applied on rings, but swe-point coreset, whose construction is defined in Definition 3.4 applied for each group. Our main algorithm (Algorithm!) I
also follows this general strategy.
Definition 3.4 (Construction of two-point coreset (Braverman et al. 2022)). For a group C Rd and center point E Rdd let pf: and p denote the furthest and closest point to in G. For every p E G, compute the unique Xo E [0, such that dist (p, c) Ap dist. (pC c) + Ap) dist. (pfa c). Let DG = {pf p p }. WD (pE
EpEc Xp. and WDo (pe Epec (1x))).
DG is called the two-point coreset of G with respect to c.
By definition, useful for upper bounding the error induced by such two-point coresets.
verify that Wpy (De) |G| and cost (Da,c) costz(G,c)) which
In Braverman et 2022). they mark some of the rings (which they heavy rings), then group remaining (unmarked) rings into groups. Our notion of ring corresponds to their "marked ring". and our group is the same theirs. However, we do not need the concept of unmarked rings explicitly, since we only need to deal with the groups that are formed from them (and the construction of groups follows from black box in Braverman et al. (2022)..

---

Published as a conference paper at ICLR 2023
3.2 PROOF OF THEOREM 3.1
Coreset Construction Algorithm We present our main algorithm in Algorithm [ In Line and Line the set L* of outliers of C* is the set of ym furthest points C* and L is directly added into the coreset S. In Line 3 and Line 4 the inliers P L are decomposed into Sl clusters with respect C** and the linear time dccomposition algorithm of Theorem applied each cluster. In and Line
similar to Braverman et al. (2022), uniform sampling and two-point coreset (see Definition 3.4) are applied in constructing coresets for rings and groups, respectively.
and
Algorithm Coreset Construction for (k: 2, (22.m))RoBBS ROBUST CLUSTERING
Input: dataset P C Rd 1, integer k. m 2 1, an (a, 5, approxximati C* {cp [
1: let L + arg min L/ c P L, C*) denote the set of ym outliers
2: add L into S and set VI E L" Wg +
3: partition P I," into 3K clusters P1 .i...., Pęk: such that P; is the subset of P ) I." closest to of
4: for each i E [S8c], apply the decomposition of Theorem 3.3 to (Pi,ct) and obtain a collection
R. of disjoint rings and a collection 9; of disjoint groups
5: for E [3k] and every ring R E R,, take uniform sample QR of size 20(2log=) Ō şमकन
from R. set Vx E QR. wQn (z) t [Qxl' and add (Qn, wQn) into S
6: for i E [3k] and every group G E Gi center cf construct a two-point coreset (Do, WDa) of G
as in Definition 3.4 and add (Da, WDe) into S
7: return (S, ws)
Error Analysis Recall that P is decomposed into 3 parts, the outliers I,,, the collection of rings, and the collection of groups. We prove the coreset property for each of the parts and claim the union yields an e-coreset of P for (k, z, m)-ROUUST CLUSTERING. As L is identical in the data set P and the coreset S, we only have to put effort in the rings and groups. We first introduce the following relaxed coreset definition which allows additive error.
Definition 3.5. Let P C Rd, 0 < < 1 and A 2 0, weighted set (8, ws) is an (e, A)-coreset of X for (k, z, RO-RUT CLUSTERING if for every c R2, [ =
(
! (S, (S, C)I < cost (1) (P.C)+
This allowance of additive error turns out to be crucial in our analysis, and eventually we are able to charge the total additive error to the (hear-)optima cost, which enables us to obtain the coreset (without additive error).
where we analyze the guarantee of the uniform-sampling coresets for rings (Lemma 3.6) and the two-point coresets (Lemma 3.7
The following two are the key lemmas for the proof of Theorem 3.1
Lemma 3.6 (Coresets for rings). Let Q = Usejan) (ow) URER, QR denote the coreset of the rings Rall =
Useteny URER. R, constructed by uniform sampling as in Line Algorihhm) then Vt, 0 < t <
Q is an (c, cost. C²)) -coreset of Ran (k: z, t)- -ROBUST CLUSTERING.
Proof. The proof can be found in Section
Lemma 3.7 (Two-point coresets for groups). Let D = Uiejon) Useg, DG denote the two-point coresets of the groups Gall Uieton UGeg, G, as in Line 6 Algorithm!! 7 then for every t,0 s t < m, D is an (c, cost. (P) L,", (*)) -coreset of Ganfor (k, 2, 2,,2,,)RRooE ROBUST CLUSTERING.
Proof. The proof can be found in Section
G
Proof of Theorem
3.1 Fix a center C C Rd, |C| = k and fix a E [0, m), we first prove that
cost (ost() < (1 + e) cost (t) (P. + cost. (P ('))).
To this end, assume I. C P is the set of outliers for C with [. = t.

---

Published as a conference paper at ICLR 2023
Ours
14
Empirical error (%)
Empirical error
900 1000 1500 2000 2500 3000 3500 4000 4500 5000 Size of coreset
300 1000 1500 2000 2500 3000 3500 4000 4500 5000 Size of coreset
Adult dataset
Bank dataset
Ours
Ours
Empirical error (8%)
Empirical error (9%
800 1300 1800 2300 2600 3300 J000 4J00 4600 5300 Size of coreset
fooo 2300 2800 3300 3800 4300 4800 5J00 5800 63000 Size of coreset
Twitter dataset
Census 1990 dataset
Figure The tradeoff between the coreset size the empirical error.
Let = =In Ra lo = Ganl- By Lemma 3.6 and Lemma 3.7 there exists weighted subset To C Q,TD C D such that, WT, (TQ)= R.. WTp (Tp) =c.
cQ To, C) s (1 + c) cost. (Rall (L Rau), C) c. cost: C*)
(3)
and
cost, (D C) S (1 + c) cost. cost;((a.l (Ln Gau); C) cost
(4)
Define weighted subset (T, wT) of S, such that T = (Ln UTU Then WT (T) = and
cost (O.t!
s cost. (S TCC)
cost, [L* (0 To. C) cost, Tn. C)
cost.
S cost,(L' (L (1 cost. (Ral) (L Rau)) C) cost, (Gall (G.ll (L Gau). C)
6. costs (R)
+ e cost, C*)
< (1 cost, (P L, C)) cost L L*)
< (1 O(a ))) cost (P,C).
Similarly, also obtain that cost. (t) (P, C) & (1 O(a c)) cost (4) (S,C) for any 0 S t
remains to scale by a universal constant.
We analyze the time complexity. Clearly, the running time of Algorithm i dominated by the first four lines, each of which takes (Akkd) time. Apart from the steps of building the coresets, the time for the initial tri-criteria approximation discussed in Section I.3 and Section A
4 EXPERIMENTS
We implement our coreset construction algorithm and evaluate its empirical performance various real datasets. We compare with several baselines and demonstrate the superior performance of our coreset. In addition, we show that our coresets can significantly speed up approximation algorithms for both (k, m) ROBUST MEDIAN and (k, R)-BOU MEANS problems.
Experiment Setup Our experiments conducted on publicly available clustering datasets. Table for a summary of specifications and choice of parameters. For all datasets, we select nu- merical features to form vector in RRd for each record. For larger dataset, particularly Census199p
8

---

Published as a conference paper at ICLR 2023
Table Specifications of datasets and the choice of the parameters.
dataset
size
subsample
dim.
# of outliers m
Adult
Dua & Graff 2017)
48842
6
200
Bank (Moro et al. 2014)
41188
10
200
Twitter (Chan et 2018
21040936
10
2 500
Census 1990 (Meek et al. 1990
2458285
10
68
1500
and Twitter, we subsample it to 10 points so that inefficient baselines can still finish in a reason- able amount of time. Unless otherwise specified, we typically set A: = 5 for the number of centers. The number outliers m is determined by a per-dataset basis, via observing the distance distribu- tion of points on a PC with Intel Core i7 CPU and 16 GB memory, and algorithms are implemented using C++ 11. We implement our coreset following Algorithm 1 except for few modifications. The detailed modifications are described in Section C
near-optimal center (see Section for details). All experiments are conducted
Empirical Error We evaluates the tradeoff between the coreset size and empirical error under the (k, --RBUST MEDIAN objective. In general, for (At, =, R)-BUUSST CLUSTERING, given coreset S, define its empirical error, denoted as E(S, C.), for specific center C R.d |C| =
as ((S,)) == (o.)
Since it is difficult to exactly verify whether coreset
cost (X.C)
preserves the objective for all centers (as required by the definition), we evaluate the empirical error, denoted as É(S), for the coreset S as the maximum empirical eтror over C, which is collection of 500 randomly-chosen center sets, i.e., E(S) maxcee é(S, C). Note that E(S) is defined in way similar to the worst-case error parameter as in Definition 2.1
Baselines We compare our coreset with the following baselines: a) uniform sampling (US), where we draw N independent uniform samples from X and set the weight LX] aware uniform sampling (OAUS), where we follow Line Line Algorithm to add m outliers L" to the coreset and sample N- m data points from X L as in US baseline, and c) sensitivity sampling (SS), the previous coreset construction algorithm of Feldman & Schulman (2012).
N for each sample, b) outlier-
run it construct coresets of varying target sizes N, ranging from m + 300 to m + 4800, with a step size of 500. We evaluate the empirical error ε(-) and we plot the size-error curves in Figure] 2 for each baseline and dataset. To make the measurement stable, the coreset construction and evaluations are run 100 times indepen- dently and the average is reported. As be seen from Figure 2 our coreset admits a similar error curve regardless of the dataset, and it achieves about 2.5% error using a coreset of size m + 800 (within 2.3% 2.5% of data size), which is perfectly justified by our theory that the coreset size only depends on (m ((m++pp poly(ke ")). Our coresets outperform all three baselines by a significant margin in every dataset and every target coreset size. Interestingly, the two baselines SS and US seem to perform similarly, even though the construction of SS (Feldman & Schulman 2012) is way more costly since its running time has an exponential dependence on k + m, which is already impractical in our setting of parameters. Another interesting finding is that, OAUS performs no better than US overall, and both are much worse than ours. This indicates that it is not the added initial outliers L (as in Algorithm [T) that leads to the superior performance of our coreset. Finally, we also ob- serve that our coreset has a smaller variance in the empirical error ( 10 10-6), compared with other baselines (%s 10-1).
Experiment: Size-error Tradeoff For each coreset algorithm,
Impact of The Number of Outliers We also examine the impact of the number of outliers m on the empirical error. The details of this experiment can be found in Section D
Experiment:
Speeding Up Existing Approximation Algorithms We validate the ability of our coresets for speeding up existing approximation algorithms for robust clustering. Due to space limit, the details and results can be found in Section t
Experiment:

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Research is partially supported by a national key R&D program of China No. 2021YFA 1009900, startup fund from Peking University, and the Advanced Institute of Information Technology, Peking University.
REFERENCES
Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth. In ICML, volume 119 of Proceedings of Machine Learning Research, pp. 569-579. PMLR, 2020.
Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clus- tering on general communication topologies. In NIPS, pp. 1995-2003 2013.
Aditya Bhaskara and Srivatsan Kumar. Low rank approximation in the presence of outliers. In OPPROX-RANDOR, volume 116 of LIPles, pp. 4:1-4:16. Schloss Dagstuhl Leibniz-Zentrum für Informatik. 2018.
Aditya Bhaskara, Sharvaree Vadgama, and Hong Xu. Greedy sampling for approximate clustering in the presence of outliers. In NeurlPS, pp. 11146-11155, 2019.
Vladimir Braverman, Dan Feldman, and Harry Lang, New frameworks for offline and streaming coreset constructions. CoRR, abs/1612.00889, 2016.
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for or- dered weighted clustering. In ICML, volume 97 Proceedings of Machine Learning Research, pp. 744-753. PMLR, 2019.
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clus- tering in excluded-ming graphs and beyond. In SODA, pp. 2679-2696. SIAM, 2021.
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwicgelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In FOCS, pp. 462-473. IEEE, 2022.
Emmanuel J. Candès, Xiaodong Li, Ma, and John Wright. Robust principal component analysis? J. ACM, 58:11:1-11:37, 2011.
T-H. Hubert Chan, Arnaud Guerquin, and Mauro Sozio. Twitter data set, 2018. https:
Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In SODA, pp. 642-651. ACM/SIAM, 2001.
Sanjay Chawla and Aristides Gionis. k-means-- A unified approach to clustering and outlier detec- tion. In SDM, pp. 189-197. SIAM, 2013.
Ke Chen. A constant factor approximation algorithm for k-median clustering with outliers. SODA, pp. 826-835, SIAM, 2008.
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. In NeurlPS, pp. 21085-21098, 2021a.
Vincent Cohen-Addad, David Saulpie, and Chris Schwiegelshohn. A new coreset framework for clustering. In STOC, pp. 169-182. ACM, 2021b.
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-meaan coresets. In STOC, pp. 1038-1051. ACM, 2022.
Amit Deshpande, Praneeth Kacham, and Rameshwar Pratap. Robust k-means++. UAI, volume 124 of Proceedings of Machine Learning Research, pp. 799-808. AUAI Press, 2020.
10

---

Published as a conference paper at ICLR 2023
Hu Ding and Zixiu Wang. Layered sampling for robust optimization problems. In ICML, volume 119 of Proceedings of Machine Learning Research, pp. 2556-2566. PMLR, 2020.
Dheeru Dua and Casey Graff. Uci machine learning repository, 2017. uci pcw. wtt.ee/m///aaattts//e/e/e//////e
ics.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In STOC, pp. 669-578, ACM, 2011. [ttpss//aaxx....orr///////1111//
Dan Feldman and Leonard J. Schulman, Data reduction for weighted and outlier-resistant clustering. In SODA, pp. 1343-1354. SIAM, 2012.
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM J. Comput., 49(3):601-657, 2020.
Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. Improved algorithms for clustering with outliers. In ISAAC, volume 149 of L/Ples, pp. 61:1-61:12. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour. Ap- proximation schemes for clustering with outliers. ACM Trans. Algorithms, 15(2):26:1-26:26, 2019.
Shalmoli Gupta, Ravi Kumar, Kefu Lu, Benjamin Moseley, and Sergei Vassilvitskii. Local search methods for k-means with outliers. Proc. VLDB Endow., 10(7):757-768, 2017.
Sariel Har-peled. Geometric Approximation Algorithms. American Mathematical Society, USA, 2011. ISBN 0821849115.
Sariel HeleP and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC, pp. 291-300. ACM, 2004. /tttp:://axxxv.or///bb...
12826
Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In ESA, volume 173 of L/Ples, pp- 57:1-57:21. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020.
Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. In STOC, pp. 1416 1429. ACM, 2020.
Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In FOCS, pp- 814-825. IEEE Computer Society, 2018.
Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. Coresets for clustering with fairness constraints. In NeurIPS, pp. 7587-7598, 2019.
Peter Huber and Elvezio Ronchetti. Robust Statistics. Wiley, 2009.
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In STOC, pp. 646-659. ACM, 2018.
Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. J. Comput. Syst. Sci., 62(3):516-527, 2001.
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In STOC, pp. 1027-1038. ACM, 2019.
Chris Meek, Bo Thiesson, and David Heckerman. Uci machine learning repository. 1990. http: ics uci. wtt.p/..c//....aaaaaaaaa//aaaaaa
(1990)
S. Moro, P. Cortez, and P. Rita. Uci machine learning repository, 2014, https://archive, ccs. uci edu /m //////////aaa htw.///aattsttssseeeess ttt.tttttsttttttaareeett
David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. On the least trimmed squares estimator. Algorithmica, 6981):148-183, 2014.

---

Published as a conference paper at ICLR 2023
Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in euclidean space. In STOC, pp. 1064-1069. ACM, 2019.
Peter J. Rousseeuw and Annick Leroy. Robust Regression and Outlier Detection. Wiley Series in Probability and Statistics. Wiley, 1987.
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algo- rithms for fair k-means. In WAOA, volume 11926 of Lecture Notes in Computer Science, pp- 232-251. Springer, 2019.
Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In FOCS, pp. 802-813. IEEE Computer Society, 2018.
Adiel Statman, Liat Rozenberg, and Dan Feldman. k-means: Outliers-resistant clustering++++ Al- gorithms, 13(12)3311 2020.
Zhen Zhang, Qilong Feng, Junyu Huang, Yutian Guo, Jinhui Xu, and Jianxin Wang. A local search algorithm for k-means with outliers. Neurocomputing 450:230-241, 2021.
12

---

Published as a conference paper at ICLR 2023
Appendices
A ALGORITHMS FOR TRI-CRITERIA APPROXIMATION
Various known algorithms that offer different tradeoffs may be used for the required (a, 3, 7)- approximation. In particular, Friggstad et al. (2019) designed a polymomial-time A(n, k. d, 2) (1)) algorithm with a = ( 0(1), A(n, ki d, 2) = Ō(nke) algorithm with a = 0(20(=)), B = 0(1), = Q(1) (which implies the statement in Theorem 1.1 Finally, true approximation algorithms, i.e., 3 = . = 1, are known for both (k, m) ROBUST MEDIAN and -K)BUSS MEANS, and they run in polynomial-time
1: Bhaskara et al. (2019) gave a near-linear time
A(n, k. d, 2) = n (1) and achieves a = O(1) (Chen 2008 Krishnaswamy et al. 2018
B TECHNICAL LEMMAS
Lemma B.1 (Generalized triangle inequalities). Let a, 2 0 and 8 E (0, 1), for 2 1,
1. (Lemma A. of Makarychev et al. 2019)) (a + b)* (1 5)a-1 1 a² (1+ + 2))-11 B=
2. (Claim 5 Sohler & Woodrufi 2018)) (a + b)* s (1 + 8) a (3))=-1, b²*
The following lemma a simple but useful way to bound the error between coresets and data sets and the proof idea is similar Lemma 3.5 of Braverman et al. (022) which relies coupling the mass and applying generalized triangle inequality LemmalB: B.1 This technical lemma is used in many places in our entire proof.
Lemma B.2. Let B C P. be either ring a group. Assume (U, wy) and (V, wv) are two weighted subsets of B such that (U) = (V) = N, then for every C Rd |C| = we have
|cost, (U, - cost,, (V,C) S 6. , + 62 E (cost, (t) + cost, (V, ())))) (5)
Proof. Since wo (U) wy (V), there must exist matching M U x V + Ryo between the mass of and V. So Yu E U. Evsy M (u, v) = (w) and Vo E V, V.E.eu M(u,v) v) = wy (v). By generalized triangle inequality Lemma B.I we have,
cost, (U, C) cost. (V,
Σ (M, r) dist(u, C) C)11
ueU DEV
(e-ddss(uu Σ Σ M(, (c dist(u, C)²² + ( (22)==1 (dist(u, C) dist(v,
32
NeU veV
Σ WEU
wu)(u) dist(u, C)2 + +--)) )=2)-11 Σ
32
M v) (dist(u, cf) + dist(u,
NEU VEV
3z )2-1 6 cost (U,T=((U,)+)))) +
Σ
(w) - 2 (u, (1, + Σ (v) (-) dist(u, ef))
DEU
vEV
< 6 cost, (U,C) + 2 )=1=-|
(0:3-1((ostt (cost: + cost= costx(V,c)))
C MORE DETAILS OF THE EXPERIMENT
Determining The Number of Outliers To determine the number of outliers m for each (subsam- pled) dataset in our experiment, we run vanilla h-MEANS clustering (without outliers) algorithm,
Bhaskara et al. 2019) only showed the case of 2, but we check that it also generalizes other 2's.
13

---

Published as a conference paper at ICLR 2023
1.0
Dist nearest center
1.0
0.8
0.8
0.6
0.6
0.4
0.4
Dist.
0.9
200
10000
20000
30000
40000
0.0
200
10000
20000
30000
Point ID
Point ID
Adult dataset
Bank dataset
1.0
1.0
0.8
0.8)
nearest
0.6
0.6
0.4
0.4
Dist.
0.2
0.9
500
10000
20000
0.0
1500
10000
20000
Point ID
Point ID
Twitter dataset
Census dataset
Figure 3: Distances to the found near-optimal center (using vanilla clustering algorithm) for each point, sorted decreasingly and rescaled to [0, 1].
and plot the distribution of distances from data points to the found near-optimal centers. As shown in Figure every dataset admits a clear breaking point that defines the outliers, and we pick m accordingly.
Implementation Details Our coreset implementation mostly follows Algorithm except for few modifications. For efficiency, we use near-linear time algorithm by Bhaskara et al. (2019) to compute an (O(1), (1), (()))-apprximmation (as required by Algorithm 1. but still add m outliers to coreset (in Line ! instead of adding all the found ones. Moreover, since it is more the target coreset size N (instead of solving for N from e), modify the algorithm so that the generated coreset has exactly N points. Specifically, the coreset size is affected used determine how the rings and groups
practical directly
by two key parameters, one a threshold, denoted are formed in the construction of Theorem 3.3 (whose details can be found in |Braverman et al.) 20222), ) and the other, denoted as 8, the size of each uniform sample (used in Line 5) Here, we heuristically set i = 0( N-m and solve for such that the total size equals to N.
D EXPERIMENT: IMPACT OF THE NUMBER OF OUTLIERS
We examine the impact of the number of outliers m on empirical error. Specifically, we experiment with varying but fixed N m., which is the number of "samples" besides the included outliers L in our algorithm. We pick a typical value of - m 800 based on the curves Figure 2 We plot this outlicr-error curve in Figure 4 and observe that while some of our baselines have fluctuating empirical error, the error curve of our coreset is relatively stable. This suggests that the empirical error of our coreset is mainly determined by the number of additional samples N m, and is mostly independent of the number of outliers m itself.
E EXPERIMENT: SPEEDING UP EXISTING APPROXIMATION ALGORITHMS
We validate the ability of our coresets for speeding up existing approximation algorithms for robust clustering. We consider two natural algorithms and run them on top of our coreset for speedup: Lloyd-style algorithm tailored (k, ROBBUS MEANS (Chawla & Gionis 2013) seeded by
14

---

Published as a conference paper at ICLR 2023
Table 2: Running time and costs for LL and LS with/without coresets. Tx and I's the running time with- out/with the coreset, respectively. Similarly, cost cost' are clustering costs without/with the coreset. Te is coreset construction time. This entire experiment is repeated 10 times and the average is reported.
dataset
algorithm
cost'
Te
Tss (s)
Tx (s)
LL
3.790 x 10
3.922 10
0.4657
0.06385
16.51
Adult
LS
1.100 x 10
1.107 x 10
0.5300
1.147
204.8
LL
4.444 x 10
4.652 10
0.4399
0.05900
11.40
Bank
LS
4.717 10"
4.721 10"
0.4953
1.220
186.6
LL
3.218 10?
3.236
10?
0.9493
0.08289
11.27
Twitter
LS
1.476 x 10"
1.451 x 10
1.064
2.135
460.2
LL
1.189 x 10?
1.208
10?
3.673
0.4809
40.54
Census1990
LS
1.165 10"
1.163
10
4.079
24.83
2405
26
Ours
26
Ours
Emplrical error (%6)
Empirical error (%)
144
900 400 600 800 1000 1200 1400 1600 1800 2000 Number of outliers
900 400 600 800 1000 1200 1400 1600 1800 2000 Number of outliers
Adult dataset
Bank dataset
Ourr
Ours
Empirical error (85)
.US
Empirical error (9))
foo0 1200 1400 1600 1800 2000 2200 2400 2600 2800 Number of outliers
f000 1400 140006000600 1800 2000 2200 2400 2600 2800 Number of outilers
Twitter datasct
Census 1990 dataset
Figure 4: The impact the number outliers m on empirical error
modified 4-MEANS+ for robust clustering Bhaskara et al. 2019 which call "LL", and local search algorithm for (k: m)-BBBUST MEDIAN (Friggstad et al. 2019), which we call "LS"". We note that for LS, uniformly sample 100 points from the dataset and use them the only potential centers, since otherwise it takes too long to run on the original dataset (without coresets). We a coreset of size vn 500 for each dataset (recalling that m is picked per dataset according to Figure 3 to speed up the algorithms. To make consistent comparison, we measure the clustering costs on the original dataset for all runs (instead of on the coreset).
We report in Table2itha running time and the cost achieved by LL and LS, with and without coresets. The results show that the error incurred by using coreset is tiny (< 5% error), but the speedup is significant 80x-250x for LL., and 100x-200x for L.S. Even taking the coreset construction time into consideration, it still achieves 1 10-300x speedup to LL and 80x- 60x-140x speedup L.S. We conclude that our coreset drastically improves the running time for existing approximation algorithms, while only suffering a neglectable error.
F PROOF OF LEMMA 3.6) ERROR ANALYSIS OF UNIFORM SAMPLING
As with recent works in Euclidean coresets (Cohen- et al. 202
2022
Braverman et al,
2022), make of iterative size reduction Braverman et al. 2021 and terminal ia embedding
15

---

approximation of the k-Balls range space on Published as a conference paper at ICLR 2023
technique Narayanan & Nelson bound with factor of O( (og Hence, suffices to prove that uniform sample of size 0 kd yields the desired coreset.
2019), which allows to trade the factor ((d) in coreset size
g2
The following simple formula can obtained via integration by parts.
Fact F.1. Let (Y, wy) denote a weighted dataset and C' S R4 |C| k then for every S t s wy (Y)
cost (1) (P,C) = //00 2 z.u=-1 (wy (wy - m m-wyy -wy (By(Bals(C,,u)) du.
The following notion of e-approximation for k-balls range space is well-studied in PAC learning and computational geometry communities (see e.g. Har-peled (201T))
Definition F.2 (e-Approximation for k-balls range space), Let Balls, = [Balls(C, u) C C R.,IC|- k, u > 0} denote the set of unions of l balls with the same radius. For dataset P C R2, the k-Balls range space on P is denoted by (P,Ps) where Pa := {P n Balls: (C, u) Balls, (C, u) E Balls;). A subset Y C called an c-approximation of the k-Balls range space (P, Pk) if for every Balls(C, u) E Balls;.
P Balls(C,,))
TiBllsssCC u))
S.
PP]
The following lemma reduces the construction of an e-approximation to uniform sampling.
Lemma F.3 (Li et al. 2001)). Assume Q is uniform sample of size Ö ((b))) from P, then with probability least
(oly( is an e-approximation of the k-Balls range space on P.
The following Lemma R4 shows ( apappoxxmmaiion yields 20(zlogz), c-coreset for robust ( -OBBUST CLUSTERING for every t.
Lemma F.4. Assume R = P. n ring(c), r, 2r) is ring in the cluster P.. Let QR be an (1Tz)² )- approximation of the k-balls range space R. Suppose every element of QR is re-weighted by [R]] then every C C Rd |C1 = and every t, 0 < t S min {R).m m).
[Qal
cost (t) (R, C) - cost (QR, C)I < cost (R, C) + |
(6)
Proof. Fix a C C Rdd | = k. As Qn an 12x R, know that for every u 0,
[w (BallallssCCu) n Rt)) WQn (Balls(C,
[R].
12:
Let Telose minze n (1s cr C) and Tiar maxzendist(ar C). Since R ring(c, r, 2r), the diameter of R is at most 4r and this implies Ter - Teloss I 4r. Since QR is a subset of R, we know that for every & [Telose, Tiss].
w (Balls(CC, u) R)) = ua (Balls(C,u) nQQR)
(8)
To prove (6. we do the following case analysis. the number of outliers /. 2 (1
Thm )) RR let La C R and Lg C Qn denote the outliers of R
and Q with respect to C. Using Lemma B.2 know that
cost." =
(9) (R, C*) cost (1) (Qn. CYI
cost (1) (R) + 62 )--==11,, (cost,(R - LL, + cost,(QR= LQ, 07))
6z )=
(o + (--)
12"
cost (R,C) +er R
16

---

Published as a conference paper at ICLR 2023
I (1- 122 )) | using 7 (8) Fact F.1
and the generalized triangle inequality Lemma B.1
we have,
cost (1) (P.C) cost (1) (QR. C)]
Tiu
zu zu²-1 1-
| (Balls(C, Rt) wQn (Balls(C, n QR) du
Telane
R| (Thr Telose)
122
32
R (c.Taomm + ((2) )-))-11(44))
W4
12z
)² |R] Taose + err [R]]
12z
cost (4) (R, C) + +er [
where for the last inequality, we have used the fact that
cost (2) (R,C) [
T close
11 |
T
close
We are ready to prove Lemma
3.6
Proof of Lemma 3.6 Fix center C C RR [0/ k. By Lemma F.3 the sample size in Line 5 of
Algorithm iimlies that Qn is (22 ( a--apprxximation of the k-balls range space R for every R E [pk] R₂ By lemma F.4 and the union bound, with probability at least 0.9, for every E [8].
for every ring R E Ri, and for every E [R]]
cost (e) (R, C) - cost (c) (QR. O)I S e cost!") (ost(")(A C) + cost, (R, c().
(9)
Let L denote the set of outliers of Ral with respect C. By for every R E UiE[sn R4, there exists a weighted subset TR C QR such that WTR (TR) = wr R) and
cost (Q Tn, C*) < (1+ cost, (R (L R), C) + c cost, (o,st,RR,o) cf).
Summing over all Uie(ak) R5 we know that, cost!") (Q, C)
Σ cost: -ORT,(QR-TR,C)))
SE[BA] IER,
Σ Σ
((1 c)) cost, (R - (L) + cost, (R, ci)
SE[BA] RER,
(1 + e) cost. (Ral L, + cost, (Rall; C*)
= (1 (1+c) cost (t) (Rall C*) + e cost, (Rall, C*).
On the same way, we can show that
cost Ralll C) s (1+c) cost (0 (Q. c coost, (Ran, C*)).
Thus we finish the proof.
G PROOF OF LEMMA 3.7 ERROR ANALYSIS OF TWO-POINT CORESETS
Throughout this section, we fix center set C C C = and prove the coreset property of D with respect to C.. To analyze the error of two-point coreset for Gall. we further decomposes all groups into colored groups and uncolored groups based on the position of C' in the following Lemma G.I which was also considered in Braverman al. (2022). Furthermore, inside proof, we also consider a more refined type of groups called special groups. An overview illustration of these groups and other relevant notions can be found in Figure
17

---

Published as a conference paper at ICLR 2023
data points
uncolored groups
colored groups
centers in Cle
special groups
ocntonns in Caow
x outliers
Figure 5: An illustration of the decomposition into colored, uncolored and special groups with respect Cear Celoees where radii of balls are taken the logarithm.
Lemma G.1 (Colored groups and uncolored groups [Braverman et al. 2022 For center set
C TRd |C| = k; a collection of groups 9s can be further divided into colored groups and uncolored groups with respect to C such that
1. there are at most O(k ?) colored groups and
2. for every uncolored group G E Go for every E C, either Vp E G, dist(u, (esst(u,,)) cf) < 95 dist(p, ct) or Up G, dist(u, ct) > 24s dist(p, e().
Let G E Gú be an uncolored group with respect to C, Lemma G. iipliis that the center set C' can be decomposed into "close" portion and a "far" portion to G. the following Definition G.2
Definition G.2 BBavvrman et al. ). For center set C, assume G E Gs is an uncolored group with respect to C. Define
24s Chu = C G, dist(u, c) > dist(p, cf),,
and
GG Co = E Vp E G, dist(u, cf) < dist(p, c))
9z
Remark that C = CG UCG by the property of uncolored group.
close
The following Lemma G.3 shows the difference of cost to any center C C Rd |C| k between group G and its two-point coreset DG can always be bounded by a small additive error, via general- ized triangle inequality Lemma B.1
By combining Lemma B.2 and the fact that cost. (Gi, o7) S ( following inequality.
(Pt.e. Te (20g(2) we can obtain
Lemma G.3 (Robust variant of (Braverman al. 2022 Lemma 3.5)). For a group G Gv, assume (U, we) and (V, wv) are two weighted subsets of G such that (U) wv(V). Then for every C R
[C| = k.
cost, cost,
cost (U,C) cost, (V.C) (U,
(10)
2 log(z/e)
Lemma G.4. Let G denote uncolored group with respect to C. Suppose (U, wo) and (V, wy) are two weighted subsets of G such that one of the following items hold,
1. either Co # 1 and cU, c,) cost, (V,c))
2. or CG
close and wy (U) wy (V).
Then we have
costx(U,C) E (V, C).
(11)
18

---

Published as a conference paper at ICLR 2023
Proof. If C
* 0. by the property of uncolored group in Lemma G.1 know that Va
clase
G, dist(z, C) E
(1 ) dist(z, ) So we have
cost: (U, C) (1 c) cUst <t) and cost, C) (1 (
By combining the above two inequalities and scaling
obtain
In the other case, if Closse 0, Lemma G.1 implies Vx E G. dist(z, C) > Rs dist(x, c?). By triangle inequality, we know that dist(2, (z, CJ (1 ) dist(c) C). So we have,
c
CU, о) E (1 -U)(U) co C) and cost, (V, E (1+c) wv(V) cost, (4,, C)2 moreover since wy (U) = wy we conclude by scaling c.
We ready prove Lemma 3.7
Proof of Lemma
3.7 It suffices to prove the following two directions separately.
cost (D, (1 + c) cost!" (Gall, C) ee cost, ( ,,, ,²",,,
(12)
cost (Gall: C) - (1 + e) cost!! (D, C) + c cost. (P) LP'""C")
(13)
and scale c.
Proof of 122 Let (I,, w denote the outliers of Gall with respect to C. Namely, I C G, (T.)(T t and
cost: L, C) cost (Gall, C).
It suffices to find weighted subset (T, wr) of D such that wT (T) L and cost, T, C) S (1 +) cost, (Gall L, C) 2 (P C²,
(14)
We define T as the following. Recall that
G U G. kE(DR] GEG,
For every G E Gs, we add {ooo p into T and set
WT (Pelose)
Σ >e,
WT (
Σ Aa)
#ELnG
zeLnG
where we recall that Ae is the unique number in [0, 1] such that dist dist"(x, G)) = A dist (p G2 )
(1 1--Aa >a) dist (pfa. ).).
If G is an colored group, we apply Lemma G.3 to obtain
costz
cost., - (T (T S + cost, (L.G),
(15)
2k logg((2/()
Now suppose G is an uncolored group, observe that by construction, orr(TDD) = ww(LnG) and cost_(Tn De, ct) cost. (LnG, ct). Applying Lemma G.4 De (Tn and (LNG), we obtain that,
cost_ (DG (T C) & (1 c) cost. (G (LLG),
(16)
By Lemma G.
there are most & log(z/e) many colored groups in each cluster P, combining
with 15 and (16). we have
cost D T,C)
Σ
Σ
cost (DG -T (D)
rE[Ak] GEG:
cost: ct) 2k log(z/e)
Σ
Σ
(1 +
log(z/e)
Σ e.
vE[SA] GEG;
(E|A
(1 + <) cost.z(Gatl (Gall C, + cost (P) T,, T²,CO))
which is
19

---

Published as a conference paper at ICLR 2023
Proof of 13 Let (T, wr) denote the set of (total weight wy((T t) outliers of D with respect to C. Namely,
cost cost!"(D,,C) = -D
suffices to find a weighted subset wr) of G such that wr, (L. = and
cost (Gall L, C) S (1 cost! (D C) + cost.; (P (P\L,C
(17)
We construct L the following. For every i [k], for every G 9. let me wT (T n DG) and let (La, w()))) denote a weighted subset of such that
cost! (G,C) cost ( LG,
In other words, LG is the subset of furthest mg weights of points C' in G. Add Lg into and set (z)x) = (z)a) (z) for every I E Lg-
We prove satisfies
17.. We do the following case study.
If G' a colored group, we simply apply Lemma G.3 to obtain
cost, (P.,
cost. LG, C) & (1 + e) cost: (Tn CG)
(18)
2h (xlc)(2/c)
If G an uncolored group, and Cl by Lemma G.4 we know that
(1+ + cost: (Dc - (Ti Da), C)-. cost.; Lo; C) S (1
(19)
If G' is uncolored group, C.G. * 0, and me {0, [G]}, note that in this case LG G or LG = 0. So we have
cost,(G - LG, cost. (D (T Da).
(20)
by the fact that De the two-point coreset of G, satisfying Definition 3.4 So this case, the conditions of Lemma G.4 satisfied. So we have,
(G LG. C) < c) cost, (TnDs),C).
(21)
If G an uncolored group, C.G + 0, and mg & {0, [G],, we call such group special uncolored group and prove in Lemma G.5 that there at most 2 special groups in every Gi- (See Figure 5 for an illustration.) Then we use Lemma G.3 to obtain
cost. cT)
cost.(G LGg C) S (1 + cost, (T Da), +
(22)
2h 2olog(2/c)
Combining 18
21 [22). and the fact that there are at most k log(z/e) colored groups and 2
special groups in each G, we have
cost. (Gall C,
= Σ
cost. (G LG,C)
iE(SA] GEO
cost of) 2k log((22/))
< (1++) Σ cost, (D (k (olo 2).
Σ
FEiBR] GEG.
*E(AR]
<
cost, (1st) (D-T,C) + c (ost,(P)L',.C)) C").
Lemma G.5. For center set C' C R.d, |C| = k. in every Gi, there are at most 2 special uncolored groups with respect to C.
Proof. For the sake contradiction, assume there are special uncolored groups G1, G2, and G3 in cluster P, Assume w.l.o.g. that G₃ is the furthest to center of and G3 is the closest one. Since G2 is special uncolored group, know that CG
cluse + 0, Var G1, dist(ar, C) (1 +e) dist c))
20

---

Published as a conference paper at ICLR 2023
In particular, there exists inlier y/1 E Da, such that (ist(y1, there exists an outlier ys E G3 such that dist(ys, C) I (1+ c) dist(y3, o.).
C) (1- dist((1, of). Similarly,
However, G1, G2 and G3 are disjoint groups which are union of consecutive rings. So dist(y1, of) 2 2 (Ys, of) and this implies
dist(y1, C)
c) dist(y1. cf)
M 2(1 c) dist ct)
(1 + <) dist o7) dist(ys, C)
where we have used that e < 0.3. However, this contradicts to the fact that y1 is an inlier but ya is an outlier.
H LOWER BOUNDS
We show in Theorem H.l that the factor m necessary in the coreset size, even for the very simple case of k = 1 and one dimension, for (k, m)-ROUUST MEDIAN.
Theorem H.1. For every integer m 2 1, there exists a dataset X C I. of 2 m points, such that for every
< 0.5, any e-coreset for (1. ROBUST MEDIAN must have size (2(m).
Imm C R! of size n m + 1, where 2g 0 and H; = for i E [m]. Suppose (S, ws) is an c-coreset for (k; m)- ROBUST MEDIAN.
Proof. Fix 0 < c < 0.5. Consider the following instance X {ro, ... Jm
We first claim that ws((S) 2 m + 1 e. This can be verified by letting center e > +00, and we have
cost (m) (m)) (S,c) ws(() El
cost (m)) (X.c)
Next, c Fi-rt for some i E [m++1] 1]. which implies that cost the distance to the nearest-neighbor of in X. Suppose both -;-1 and x; are not in S and have
(m²) (m)) (()))()()))))))))))) (X,c)
= |z cc = 0.5, i.e..
cost (m²) (S,c)
VVIVI IV M
(ws(S) (S) m)) min d(x,c)
(1 E) min d(I,,)
(ws(S) 2 m +.6)
#ES
(1 - c) 1.5
(Ii-1, $ S)
0.75
(e 0.5)
(1+ cost (1m) (X, (X,
(e < 0.5)
which is a contradiction. Hence, either æ;-1 or 24 must be contained S. is not hard to conclude that |S| > "2 which completes the proof.
21


Reviews:
[{"review_id": "c8JENUxaX1x", "reviewer": "Reviewer_A4Ec", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents coresets for a robust version of the $k$-clustering problem where the cost of clustering is taken over the dataset after removing $m$ outliers. The coreset size is polynomial in $k$ the number of clusters and linear in $m$, the number of outliers. The paper also shows a lower bound on the coreset size implying that the linear dependence on $m$ is necessary. The theoretical results are validated with experiments on real-world datasets.", "summary_of_the_review": "Overall, I believe that the results of this paper will be of interest to the community. However, the paper needs to highlight its contributions in terms of novelty more clearly and also improve the writing to include few concepts for the sake of completeness. I believe if these changes are made the paper will present a better case for acceptance.", "strength_and_weaknesses": "Strengths: \n1. The problem of robust clustering is well studied and important one while at the same time being computationally expensive. Using coresets for such computationally expensive problems is a justified and popular approach.  This paper improves the size of coreset for the problem significantly and also provides a lower bound for the same. \n2. A good set of experiments is performed to validate theoretical claims and the code is provided. \n\nWeaknesses: \n1. The paper appears to rely heavily on the paper by Braverman et al. 2022 for the coreset construction idea and the proof techniques. In that regard seems to be lacking in novelty. The novelty section needs to be highlighted better as to what are the technical challenges faced in comparison to the Braverman et al. paper. Do mention clearly the subtleties when adopting the technique to incorporate outliers. \n2. While the paper is written nicely in terms of language and notations, there are a few points which I believe will enhance the completeness aspect. I list them below in the section on clarity.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SzxDU3bCw1_", "reviewer": "Reviewer_1Ghq", "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": "", "summary_of_the_paper": "This paper studies coresets for robust clustering. A coreset is a small proxy of the dataset, which is yet sufficient to perform the task at hand while not significantly compromising the quality of the solution. The goal of the robust clustering task is to cluster a set of data points that contains a number of adversarial outliers. Concretely, given a clustering objective $cost$ (e.g. $k$-means) and a set of points $P$, the robust clustering objective with $m$ outliers is defined as the minimum cost achievable by a clustering that is allowed to remove up to $m$ datapoints: $\\min_{\\text{clustering }C} \\min_{M\\subseteq P, |M|\\leq m} cost(P \\backslash M, C)$.\n\nThe main result of this paper is a coreset for the robust clustering problem with a range of clustering cost objectives that includes $k$-means and $k$-median. Specifically, the coreset has size $O(m) + \\mathrm{poly}(k \\epsilon^{-1})$, where $k$ is the desired number of clusters and $\\epsilon$ is an error tolerance. This is quite satsifying since previous work shows that $\\mathrm{poly}(k \\epsilon^{-1})$ is tight for the non-robust case (even though the polynomial dependency doesn't quite match the lower bound). The runtime is O(|P| k d), where d is the dimension of the data.\n\nThe idea is to first run an approximate but fast robust clustering algorithm from previous work (Bhaskara et al), and then define the coreset as the set of worst fitted points wrt this clustering plus a random sample. The most technical part is this sampling process, which builds on previous work of Braverman et al.", "summary_of_the_review": "In summary, I find this paper interesting and I think it makes significant theoretical progress in a fundamental ML problem, and is also promising for practical applications. I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n- The robust clustering problem is important in practice. Coresets are very relevant in large scale and dynamic applications where going maintaining and processing all the data points is impractical.\n- The algorithm is simple and intuitive.\n- The experimental results on four public datasets are promising. In particular, the authors' coresets have significantly better quality than trivial ones, e.g. uniform sampling. In addition, the coreset generation time seems to be >10x faster than the time if one were to run robust clustering without a coreset. This shows that coreset generation can be used as a preprocessing step to significantly speed up robust clustering.\n\nWeaknesses:\n- I would like to have seen a comparison with the algorithm of Bhaskara et al. In theory it gives a $O(1)$-approximation, but how does it do in practice compared to the coreset approach? Also, there are other, simpler heuristics for coreset generation that would be nice to be considered. For example, what happens if I just perform uniform sampling on the clusters of Bhaskara (plus the outliers)?\n- There is some confusion with symbols in various places: $P$ vs $X$, $n$ not defined, what is $c^*$ in Lemma F.1, etc.", "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": "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": "9XYe5Rxtj6", "reviewer": "Reviewer_7BQh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents near-optimal coresets for robust Euclidean clustering. Given k, z, m, and a set of n points P in R^d, we look for a k-clustering of P excluding a set of outliers L of size at most m, minimizing the sum of (power z of) distances of points to their centers. This gives k-median and k-means objectives for z = 1, 2.\n\nThe authors present a coreset of size O(m + poly(k/epsilon)), which adds error epsilon to the approximation.\n- Best coresets for non-robust problem have size poly(k / epsilon).\n- Linear dependence on m is necessary (the paper gives a simple example).\n- Dependence of k^3 and epsilon^5 (k-median) or epsilon^8 (k-means) sound too big, but the experiments show that one can use much smaller dependence and beat prior work.\n- Omega(k/epsilon^2) is a lower bound for the non-robust case.\n- Prior work for robust algorithms either had exponential dependence on m or bicriteria for the number of outliers.\n\nThis work heavily builds on the techniques from the recent Braverman et al. [FOCS 2022], though certain pieces need to be adapted to the outlier setting.", "summary_of_the_review": "Significant improvement of the state of the art for an important problem, and very good practical performance.", "strength_and_weaknesses": "S1: Strong results and significant improvement of the state of the art.\nS2: Timely contribution as the non-robust version has been only recently settled and having robust algorithms is a hot topic.\nS3: Great practical performance despite the large dependence on k and epsilon.\n\nW1: There is still some gap between upper and lower bounds.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "00ZL5R-tTpg", "reviewer": "Reviewer_qzTd", "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": "", "summary_of_the_paper": "The paper shows constructs coreset for (k,z,m)-robust clustering problem, where k is the number of clusters over the distance measure between two points are || - ||_2^z and m is the number of outlier points. The coreset size linearly depends on m, poly(k,eps^(-1)) and exponentially depends on z. The running time of the algorithm is yime taken to get a constant factor aprooximation of the problem plus O(nkd).", "summary_of_the_review": "The paper tackles a very important problem called robust clustering, which has many common applications. It improves the coreset size by exponential factor. It also shows emperical results on real datasets to back its theoretical claims and to show its benifits in improving scalability. ", "strength_and_weaknesses": "strength:\n- the result improves the coreset size by expotential factor in k abd m, by bringing it down to nearly optimal (m + ply(n,eps^(-1))).\n- it presents extensive experimental results on real world datasets.\n\nweakness/suggestions:\n- a comparative discussion about its coreset vs exponential size coreset will be useful to motivate towards the probem\n- are the groups consist of rings with at most 1 point? The discussion about groups could be further improved.\n- a proof sketch of lemma 3.6 and 3.7 in the main paper could be useful. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%