Improved Coresets for Euclidean $k$-Means
Authors: Vincent Cohen-Addad
Kasper Green Larsen
David Saulpic
Chris Schwiegelshohn
Omar Ali Sheikh-Omar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Clustering
coresets
k-means
Euclidean

Abstract: Given a set of $n$ points in $d$ dimensions, the Euclidean $k$-means problem (resp. Euclidean $k$-median) consists of finding $k$ centers such that the sum of squared distances (resp. sum of distances) from every point to its closest center is minimized. The arguably most popular way of dealing with this problem in the big data setting is to first compress the data by computing a weighted subset known as a coreset and then run any algorithm on this subset. The guarantee of the coreset is that for any candidate solution, the ratio between coreset cost and the cost of the original instance is less than a $(1\pm \varepsilon)$ factor. The current state of the art coreset size is $\tilde O(\min(k^{2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-4}))$ for Euclidean $k$-means and $\tilde O(\min(k^{2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-3}))$ for Euclidean $k$-median. The best known lower bound for both problems is $\Omega(k\varepsilon^{-2})$. In this paper, we improve these bounds to $\tilde O(\min(k^{3/2} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-4}))$ for Euclidean $k$-means and $\tilde O(\min(k^{4/3} \cdot \varepsilon^{-2},k\cdot \varepsilon^{-3}))$ for Euclidean $k$-median. In particular, ours is the first provable bound that breaks through the $k^2$ barrier while retaining an optimal dependency on $\varepsilon$.

Improved Coresets for Euclidean k-Means
Vincent Cohen-Addad Google Research
Kasper Green Larsen Aarhus University
David Saulpic University of Vienna
Chris Schwiegelshohn Aarhus University
Omar Ali Sheikh-Omar
Aarhus University
Abstract
Given a set of n points in d dimensions, the Euclidean k-means (resp. Euclidean k- median) problem consists of finding centers such that the sum of squared distances (resp. sum of distances) from every point to its closest center is minimized. The arguably most popular way of dealing with this problem in the big data setting is first compress the data by computing weighted subset known and then run any algorithm on this subset. The guarantee of the coreset that for any candidate solution, the ratio between coreset cost and the cost of the original instance is less than a (1 + E) factor. The current state of the art coreset size is Ō (minnk?2. - k for Euclidean k-means and Ommin(k2 2 -
coreset
k- ()) for Euclidean k-median. The best known lower bound for both problems is (2KE 3). In this paper, we improve these bounds O(min(k33/ .2.3/2. g- I----)) for Euclidean k-means and (minnA44/2 e-2, e e))) for Euclidean k-median. In particular, ours is the first provable bound that breaks through the x barrier while retaining an optimal dependency on E.
4)) 4))
Introduction
Coresets have become staple in the design of algorithms for large data sets. In the most general setting, coreset compresses the data set in such way that for any set of previously specified candidate queries, the cost evaluating the query and the cost of the coreset are similar, up to an arbitrary small distortion.
A popular subject in coreset literature is the Euclidean k--maan problem. Here, points P d dimensions and our task is to find a set of k points C called centers minimizing
given
cost(P,C)) := Eper min.ec l|p- cll2, where |pp cll VE (p: c;)² denotes the Euclidean distance. In this case, coreset is weighted subset of the input such that difference between the cost for any set of centers C' on the coreset and the cost on the original point set at most cost( P, C). Since its initial study by Har-Peled and Mazumdar (2044), the Euclidean k-means problem has received arguably the most attention out of any coreset problem. The current state the art by Cohen-Addai et al. 2022) yields coresets of size Ōkk minnk, = =²))), where Ö(x) hides multiplicative factors that polylogarithmic in Unfortunately, there is still gap towards the best known lower bound of (kk -2 by Cohen-Addad et al. 2022
We thus have the option obtaining either an optimal dependency on k. at the cost of suboptimal dependency c-1, or optimal dependency on c- the cost of suboptimal dependency k. While these bounds suggest that the lower bound is the correct answer, things are not as clear on closer inspection. Quadratic dependencies & become necessary for many forms of analysis and so far, it is unknown how to avoid this loss while retaining an optimal dependency on the remaining
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

parameters Moreover, the trade-off between the dependency on & and the dependency on = is natural. Specifically, if k ~ E-2 the two previous alternatives 0(k2/=²) and (kk/s*) are equal.
In this paper we break through this barrier. Specifically, we show that coresets of size 0
exist. Furthermore, for the Fuclidean k-median problem where we minimize cost P, C) = Epep min.ec lp cll, we also improve the known bounds from Ō(ke2 min(k:// "-)) In view, this is further and arguably stronger evidence that the ke-2
(k, E =-1) to bound will be the correct answer. Another contribution exists on a technical level. Previously, most coreset constructions for high dimensions heavily relied on terminal embeddings to facilitate the analysis. In this paper, we present a novel method that avoids terminal embeddings. We expect that our technique may have further applications for coreset constructions in Euclidean spaces.
1.1 Techniques
Starting point of our work the framework introduced by Cohen- et al. [202Ta] and specifically
Cohen-Addad et al.] [202]_ Prior to Cohen-Addad et al. [2022], all coreset analyses required
dependency at least k d e-2 To illustrate why, suppose we are sampling points from some distribution and wish to use the sampled points as an estimator for the true cost of any candidate solution. The analysis then consists of (1) a bound on the variance o² of the estimator and (2) a bound on the number of solutions |N| to be approximated. This typically results in coresets of size O( 2 o² log [N). When enumerating all (discretized) candidate solutions (henceforth called a net) in d dimensions, virtually all known techniques result in [N] x exp (s d). The dependency d may be reduced to log(k/E)) uusin dimension reduction techniques.
To bypass this, Cohen-Addat et al. [2022) used chaining- thaseing-based analysis to define sequence of discretized candidate solutions. Specifically, they showed that there exist discretizations Na of size exp(ka 2) such that for any point p and any solution S, there exists a solution Sa with
[cost(p, Sa) - cost(p, S) S cost(p, S)
where cost(p, Sa) minges. l|p - a|12 and cost 8) minges ||v s|I?. The idea of the analysis is then to write cost(p, S) as a telescoping sum
cost(p, S) cost(p, S2 (.115) - cost(p, S2-1)
and show that the sampled points achieve concentration for each summand. The number of candidate exp(k 2 but the difference in cost is 2 "cost(p, This directly leads to a variance of the order 2 2-2h where o² is the variance of the basic estimator: Thus, the increase in net size countered by the decrease and variance. Using this technique, Cohen-Addad ct al. (2022) obtained coreset of size roughly : =k=
solutions is now [Ng-(++)]] [N--1|
To obtain a bound on o², the framework by Cohen-AAdad et al. [2021a] proposed an algorithm that first computes solution A with strong structural properties and then samples any point p proportionate cost(p, A). To simplify the exposition, we assume that A is the optimum, every cluster has identical cost and every point has identical cost. For this special case, the distribution of Cohen Addad et al. [021a] turns out to be equivalent to uniform sampling. For any given solution S. let k; be the number of clusters of A whose points served at cost 2' times their cost in A for i > + i.c. 2
S.st(p.S)
Cohen-
2021a showed that their sampling distribution leads variance
co)t(p.A))
of the order ²²
k= 22
min 2,2', k), which yields the Ö(kE ( ?)) bound.
To improve either the variance or the net size has to reduced. Unfortunately, is unlikely that reducing x² will be possible the bounds o² obtained by Cohen-Addad et al. (0022 are tight up to constant factors. Our main goal is to find a net with an finer error of
|cost(p, S.) cost(p, S) < 2 h /cost(p, 8), cost(p, A).
'Coresets of size Ō(kd/e²) are also known Aodhen-Addadaa et al. 2021a)). This offers improvements in low dimensions, but generally dependency on d considered worse than a dependency on - "Observe that if one points of a cluster C of A costs 2' times more for i > 3, then all points from C₁ do likewise (up constant factors).

---

In the case of min(2',e [k] = 2", this leads to a reduced variance for the h-th summand of the order 2 24 (v (eeos(p.Secouppp..
To find such net, we now have two options. First, we can essentially use the previous nets and rescale 2 by a factor 2-1/2, Unfortunately, this leads to nets of size exp(k: 22h any gain in reducing the variance is countered by an increase in the net size.
)² S 2 2h
1= (++4,
co)t(p.A)²
The novelty in our approach now lies in showing that a net of size exp(k K, 22h) exists. Com- bining the two net sizes with the improved variance bound results a coreset size roughly e- log (exp(k- min(k;, 29) -22h)) 2- 2h. be of the order =l)
). which after some calculation is shown to (R+R;22T)))
R-
For the remainder of this section we will illustrate how these improved nets can be obtained. The key idea already appears in the case of a single center. Suppose that is candidate center. Then can show that there always exists a subspace with orthogonal basis U spanned by a set T of at most O(a 2) points of P such that
1pt - (U>)) Sa IIII- I1(I )0?))
We can then write
|pp 1p-s| =|2 (| 3)11 + + |1(I UU= )pl 110- -2= )
The error for the terms ||Up - s|1² and | Us*) can be made negligibly small using net of size exp(a Thus the main loss in error comes from the p" - -UU") )s term. The key insight is that when adding the center 6; of point p in solution A, we have |( UU yrl2
cost(p,, A). Thus, when adding all the k; centers of clusters that cost 2' more in S than in A to T the net size becomes exp(a 2 k)). By composing these nets for l candidate centers, we then obtain our desired bound.
1.2 Related Work
There has been tremendous amount of work on coresets for Euclidean k-means following the
work in Bachem et al. [201 b). Baker et al. [2020] , Bandyapadhyay et al. (202T), Becchetti
et al. [019)] Braverman et al. [2022] 2021b), Chen [2099] Cohen-Addad and Li [2099] Cohen
Addad et al. 2021a b). Feldman and Langberg [2011). Feldman et al. [[020]] Feng et al.
[2021]
Fichtenberger et al. 2013
Peled and Kushal Har-Peeddd and Mazumdar [2004]. J. Huang
and Vishnoi (2020) , Huang et al. 22018 2019]. Langberg and Schulman
Schhmid et al. 2019
Schwiegelshohn and Sheikh-Omar 2022]. Sohller and Woodrufi 2018). Almost as prolitic is the
catalogue of work on dimension reduction for clustering problems in Euclidean spaces, see Boutsidis
ct al. [2009] 2010, 2015). Charikar and Waingarten (2022a]r bj. Cohen et al. (2015). Cohen-Addad
and Schwiegelshohn [211]] |.. Drineas et al. (2004), Feng et al. [2019] Makarychev et al. [019]].
The arguably most important dimension reduction technique for coresets are terminal embeddings. see Cherapanamjer and Nelson 2021], Elkin et al. [201]]. Mahabadi et al. [2018), Narayanan and
Nelson [2019]. [ Subsequently to publication, Huang et al. [2022] obtained similar bounds to result. Specifically, they showed a 22//
coreset bound for (k, clustering, which recovers our result for k-means and k-median and extends it to higher powers.
Further work on coresets considering objects other than points centers Braverman et al. [22 la], Feldman et al. (2010), Huang et al. [202T) or other objectives all together Boutsidis et al. [2013),
Huang et al. [2020). , Jiang al. [2021], J. Karnin and Liberty [2019] 1. Mai et al. [202] IJ. Molina et al.
2018), Munteanu et al. 2018 8 Phillips and Tai [2020). Tukan et al. 20200 For further reading, we refer the interested reader to recent surveys Feldman 2020
Munteanu and Schwiegelshohn 2018
2 Preliminaries and Setup
First, we require the following basic notions. For point p Rd, we denote ||p||2 V VE of to
be the Euclidean norm of p and ||p|| = Σ [pa]. The distinct number of points in a point set is denoted by ||lol Note that the true number of points [P| may be larger than ||o as different points may lie on the same coordinates. Given solution S consisting of at most centers, and any subset P' P we use cost(P", ;= Epep cost(p, = =x Epe min wp.oot(p, s), where
3

---

cost(p,s) s) = lpp s|? for Euclidean k-means and up is a non-negative weight (in the basic case this simply whereas for the coreset it can be any non-negative number). We also denote by v E IR the cost vector associated with the point set P and solution S, that is 2p := w,cost(p. s). Note that ||o0 = S. The classic coreset guarantee is to show that for any solution S the designated coreset satisfies
[cost(S2, S) cost(P, S)l < = cost(P,
We will later introduce an equivalent statement that uses cost vectors. It will also be convenient to consider coresets with additive error E. which satisfy
cost((2, S) cost( S)I cost(P, +.
Coden-Addad et al. 2022 showed that any coreset algorithm that works for instances with the following assumptions be extended to general instances:
Assumption 1: |Pllo E poly(k,
Assumption 2: d E 0(log(k/e).E--
Assumption 3: w 1, for all p E P. Note that this only applies to the weights of the original points; the coreset points will have different weights.
Assumption 4: There exists a solution A such that
1. |AA| O(k)-
For any two clusters C,, Cj induced by A. cost(C;, S cost(C,,,
3. For any cluster Cj induced by A and any two points p.p' E Cj, cost(p, A) S 2 cost(p', .A)
To keep this paper self contained, we will later detail the validity of these assumptions.
The sampling procedure is now very simple. Given that these aforementioned assumptions hold, sample points p E Cj with probability P, C2 coreset Ω2 Furthermore, p receives the weight wp
custl C.,A) and add it to the designated P.A)
Overall, our basic cost estimator for any candidate solution S is therefore cost(S2 == [ Σ pen cost(p, S) upp It is routine to check that E[cost(S2, cost( P, 8). The remainder of this section will be devoted showing that Ω satisfies for all S
(oo S) co, <
(cost(P, (P cost(P:
log
Using the framework from Cohen-Addad et al. 2021a this implies an O(e) coreset in general.
2.1 Justification of the Assumptions
To obtain the first assumption, we compute any coreset of size poly(k,=-1) in preprocessing. Con- structions of these coresets are abundant in literature and any one would serve our needs.
To obtain the second assumption, we apply a terminal embedding on the coreset. A terminal embedding guarantees that for any point p P and any point q IR", where d is the dimension of the points of P, we have mapping f s.t.
|p 2 = (1 e)( f())
Narayanan and Nelson 2019 showed that for any n-point a terminal embedding of target dimension (( 1(f-21ogg log n) exists, which, combined with the first assumption, yields the desired target
dimension.
To obtain the third assumption, merely have to ensure that the weights of the coreset points are integers. A number of constructions satisfy this but a simple way of always enforcing this is to scale and round the weights (see Corollary 2 of Coheen-ddda et al. [2021a])
The fourth assumption follows from the preprocessing ('Cohen-Addan et al. 2021 see Sections 3.3 and 4.1 of that reference. Similarly, the same preprocessing. given that A is an O(1) ((1)-approximation also shows that Eq immplee that the overall construction will be a coreset (subject rescaling & by constant factors), see Section 4.2 of the aforementioned reference. We must point out that a point set

---

cannot always be decomposed into only sets that satisfy the aforementioned assumption. Nevertheless Cohen-Addad et al. [2022] showed that every other case require only (kk/=²) many sampled points (compared Lemmas and 17 of that reference.)
Finally, we remark that these steps and assumptions immediately also apply to the k-median problem.
3 Analysis
In this section we prove the following theorem.
Theorem 1. For any set of points in d dimensional Euclidean space, there exists a coreset for k-means clustering of size O(k..5g-2).
For the k-median case, we also obtain an improved bound as follows. Details will mainly consider the result for k-means. The analysis for k-median is given in the supplementary material.
Theorem 2. For any set of points in d dimensional Euclidean space, there exists a coreset for k-means clustering of size 0(k4/3g-3)
We first describe the random process used show concentration of the estimator.
3.1 Setting up the Chaining Analysis
First, we observe that Eq is equivalent to showing
[cost(S2, S) ||l||a|
E log e-1
sup s
(cost S) cost(P, A))
Our goal is to show that
(c)s((2, |||||||
6
Eg
sup
(cost(P, + cost(P,,A))
log 2og2=-1'
where En is meant to denote the expectation over the randomness of Ω. This implies that the desired guarantee holds with constant probability.
We now apply a standard symmetrization argument.
Lemma (Appendix B.3 of Rudra and Wootters 2014 ). Let 9p be independent standard Gaussian
random variables. Then.
Epen cost(p, up - ||2|| (cosi(P, 8) cost A))
1 Epen cost(p, Wp 9p
Ensup
S v Bx
(P,s cost(P,A))
s
is therefore sufficient to show
[T Epen cost(p, up 9p
E E sup
sup
(2)
(cost(P, (PS) cost(P,.A) AP)
v 2t log
We partition the clusters of any solution by type. We consider cluster Cj of type T, if
min |p - cll < min min || - a|| < 2 min || - c|l2. cEA
PEC; sES
cEA
The number of clusters Cj E Ti are denoted by k, If Cj is of type < 3. we say C3 is of type Tsmall and if C2 is of type 2 logne- -2 for a sufficiently large absolute constant 7, we say that Cj is of type Tharge- Then, we show
P2 EcGeT Epec,nn cost(p, S)up In (cost(P, S) + cost( P. P.))
E v 2T log g-1
Eg y
sup
(3)
[33 EcSer. Epec,nn cost(p, S)p
E
EgE. y
sup
(4)
(cost(P, + cost P, P,A))
v 2n log
e-1
[0 Ec Epec,no cost(p, (p, S) S)ip
EgE, sup
(5)
(cost(P, S) cost( P. A))
/ 2m log g--
S
5

---

Note that if Equation 4 holds for i f log 1/E), , this also implies Equation 2 as the enror from each type can only sum up the worst case and there are most Olog !) many types.
The small and large types are comparatively simple to handle.
Lemma (Lemmas 15 and 16 Cohen-Adddd al. (2022). Let [S2] absolute constant K. Then Equations and hold.
k polyloogkk)/ for some
Our main objective will be to prove the following lemma.
Lemma 3. Let [2]] 2 k/.3
2² polylog(k/e) for some absolute constants Then Equation 4 holds.
Combining Lemma and Lemma then implies Theorem 2
3.2 Sketch of the Proof of Lemma
The proof of Lemma mainly consists of defining nested sequence of nets cost vectors over which we apply union bound. Roughly speaking, for any cost vector SS, we aim to find an approximating cost vector v' such that
cost(p, S) = op 1/2 S e V cost(p, S) cost(p, A). This analysis differs from the which aimed for an error of the order ε cost(p, S).
based one used in Cohen et al. 2022]
Suppose we have, for every E, suitable collection of approximating cost vectors Nog 1/e with this guarantee for any candidate c Let SSS be the vector approximating oS in the net Nogg 1/2 Then we can write
(a-1)
S,2
p
A=0
with u. O. Our goal now bound
Σcyer, Epec, na cost(p, SWup 9r
Eg g
sup S
|S2| (cost( P)S) + cost(P.A) P.A))
En-o ECEE, 20 (1
)ep Ip
= EgE.
sup
[2I (cost(P,S) + cost( P. P,A))
Ec,e,, Epec (1 8, 11 (0+1) 11 2
00
)ecp
<
B Rg
sup 15.11 MRE (h+1) xN
| (cos(cos P,5) ) + cost( P.A))
A=0
EcSer; Epec,na S22 up-9m 9n |0 (cost(P,S) cost( P.
= EqE.
sup E.
(6)
loge"
ΣcYeT, Epeci (1S
(n (,,52-1441 (1+11)
u 'eep"" Ip
+
EnllE g
sup 1. p U.N XN
(7)
|0] (cost( (oost(P,,))
P, ) cost( P, A))
4=1
EoSer, (usc
-Up S1 ") In
jepp
+
Eql. g
sup ENNN XN
(8)
| (cost( Moost(P,ST) P,S) + cost( P. P.)
loge
We will bound Equations 6 and directly. For the O(log equations in term we prove a bound on each. Thus, aim for bound of the order O ( ); the overall bound then follows by summing up the errors and rescaling by constant factors. Technically, bounding each of the terms in Equations 6. 7 and g requires somewhat different arguments. For the sake of illustrating the key new ideas we focus on Eq. A full proof is contained in the supplementary material.
The next section presents the nets for the cost vectors. The subsequent section bounds the variance. The final section combines these results and completes the proof of Lemma 3
'The reason for indexing the net by Nog 1/c and not by N, is to conveniently sum over Di log [Na], rather than D log NN =l.

---

Cost Vector Nets
Definition 1. Let be a metric space, Pa set of points, k a positive integer, and let 0 be precision parameters and let A be some solution with at most centers. Let C I be a (potentially infinite) set of candidate k-clusterings. We say that set of cost vectors N C PI is an (a, k)-means clustering net for every S E C there exists vector o' E N such that the following condition holds. For all p P.
2/y S a (V S)osst(p, A) cost(p,
These nets have a substantially smaller error than those proposed in Cohen-Addad et al. 2022 which had an error of the order a (cost(p, S) + cost(p, A)).
Given a set of points X in Euclidean space, an E-net is a subset S C XX such that for every p E X there exists 9 in S with lpp all S E. Throughout this section, will frequently use the fact that in d dimensions, there exists an e-net of cardinality (1 + 2/e)* (see for example Pisier (1999] Our main goal in this section is to prove the following lemma.
Lemma 4. Let P be a set of points in dimensional Euclidean space, k positive integer, A be candidate solution with k; clusters and r an absolute constant. Define C be the set of possible candidate centers such that a subset A₃ the clusters induced by A are of type i, with 3 I &i= S log 1/E². For all a S 1/2. there exists an (a, -)-maans clustering net N. of C with
N S exp ( log || min(k; h + a= a,a -2 2) (0).ilogg. ilg ))
Proof (Sketch). We first show that given a set of vectors P and any vector 8, there always exists small subset U of P such that all inner products between p P and s are preserved by the span of U.
Lemma 5. Pet = {p1,... .... pad S Rd and let Rd. Then there exists U C P. with [U] 0(= and orthogonal basis Hy such that
Vp E P. Pp 1)) S <el((1 - 11 min |p - s|l
(9)
pEP
Proof. Start with Ug prgminpperly s||, and proceed in rounds. Note that || Ilu, 1y ]s| 1 |pp =|| for all p P.
In each round denote the current set of vectors U, with orthogonal basis Nu,, We add a vector p; the following equation holds
1p Iy 17, 2 =|[(1 - Il, (7, )ll II(I (T.
We observe that if this equation holds for all p E P. then Equation 9 must also hold. Note that (I - Me, L p is orthogonal to the span of U, of all previously added vectors. Thus, due to the Pythagorean theorem, we have
-1- 17, .)s)
Σ
21
I(T -II- m,, (.,,,)/) )pll 11(I UoU )s|
Therefore, after & = e-2 many rounds (I - 11 = 0, which implies that after at most e-2 rounds Eq. has to hold.
With this lemma, we can prove our net bound. Our objective to generate small set of cost vectors that satisfy the desired guarantee. We first define the cost vectors. For each subset U of + k;), we consider the the subspace 1ly spanned by U. In this subspace we consider (a/2)) /cost(p, A)-nets of every ball centered around Hp with radius 60 2 / /cost(p, A) for all E P. Such net has size exp(r rank(U)) log a)), for some constant and there exist at most ||Pllo exp(y [U log a)) many such nets. Furthermore, there are at most such subsets.
size O(min(a (a -22¹, ,2,,0 a
[0] |
Now, for every point p. define an exponential sequence a² + a/2' for j E (0, log 10 29). There exist at most [Poo such sequences and every such sequence consists of at most O(a 2 .))
7

---

many values. We combine every net point in ever ball of every subspace with all values in the exponential sequence obtain the evaluation for a single candidate center. The overall number of candidate centers is therefore of the order ||Pl exp(? |Uli log a), for sufficiently large 7, The overall number of candidate cost vectors is now the number of k subsets of candidate centers, i.e. (41 exp(1 [ log or). Combined with the bounds on U, this yields the desired size. What remains to be shown is that the thus constructed cost vectors are (ax, -clusttenin net.
||P|1o
Here, we use that for any center s in some candidate solution S
Ipp - =|I2 = ||ا| - )) + II( 11 )ll + (11 - 11 - (1 -1
The nets for the span of Hy are so fine that the distance ||TT - s'11 is essentially negligible,
where s' is the point in the span of Hy closest to Hy and the same holds for the exponential
sequence approximating the term [[ He 1T )11² Thus, the error is dominated by 2p" (I
Iss: Now, we can assume that the input point closest to is included in U. Then mingeP P ||p
a|l - / /ostt(p, S) - 0(1) 2//² (cost(p, and [I I1 pll S (cost(p,S) I 0(1)
2//2 V cost(p, (p. A). a 2'= k; + a a² we have
(I- s| S a ||(I - I1
S)cost(p, (cost(p.)ccost/2 A) min Ip - s|| I 0(1) a /cost(p, PEP
otherwise have ||(T TT IT) |ll| S /cost(p, A) which implies
(I- 111-11011 )a| < ||(I 11 )lll min ||v a|l S a v cost(p, S)cost(p,,)
PEP
Rescaling a by constant factors yields the claim.
Corollary 3. Let P be a set of points in d dimensional Euclidean space, k positive integer. A be a candidate solution with (k) clusters and 7 an absolute constant. Then there exists an (ax, k) clustering net of size Define C to be the set of possible candidate centers. such that a subset A; the clusters induced by A are of type with 3 S S 1og1/6". For all a S 1/2, there exists an (or, k)-means clustering net N of C with
N S exp (- log |Pl|| mi: + a a==20 -2--, -2.2) 222) ilog )
Bounding the Variance
We now use the cost vectors to obtain an improved variance for the estimator Eo,er, Epec, na (A-1) (A-1) -1 Jap
9p- The bounds on variance for any random variable Σ Eap9p with standard Gaussians Ip is Gaussian distributed with mean 0 and variance Σ az.
[coni
Before we do this, we require additional notion. Let & denote the event that (oj Epec,na Wp (1+ |C5]. The following lemma bounds the probability of & occurring.
Lemma 6. /Compare Lemma 19 of Cohen-Addad et al. [2022)] If Assumption 4 holds, then event &
holds with probability k i
> K Ke "log k. for a sufficiently high absolute constant k.
Lemma 7. Given Assumption 4, the variance of Eo,er, Epce,na(t S.2 -op S.8 pw, Ap
(h+1)
is at most
[0] (Ccom((P.)))) P (PA))
2 2h
k. k; 2
conditioned on event
|2
(k: ki 20)2
2
2h
k
k. k 2
7
[2
(I: Rig 2
conditioned event E
for an absolute constant
Proof. We first observe that since the Ip are standard normal Gaussians, the entire estimator is Gaussian distributed with variance
(u (1522-(0t)) ug " Jup (cost(P, cost(P,AA) AA)
Σ
PECyn
8

---

We have (1g-2 (2 u2
(u S22-21
cost(p, + cost(p, S) - u 11 S 2 2-
/cost(p, A)cost(p, S) due to Lemma Furthermore, by definition wip = coat C
Finally, by
cost(C,
definition of type i, we have cost(p, S]-
C 0(1) cost(Cj, and by Assumption 4 we have cost(p, A) ||y] = ((1) cost(Cj, A) for all E Cj.
(ups (vS.2 " )up (cost(P, + cost( (P.A))
E CyET, DECynA
[2/
2-hh 3=hh/or cost((p A)cost(p, S) cost(P;
< 0(1) Σ
cost(C), A) (cost( P. S) cost(
CJET peC,nn
2- cost(CC CCC, A)²
s 0(1) Σ
cost(Cj. A)2 2 (cost( P, cost( (,,tt,,,,00 A)))
CJER, PEC,nN
Now, let K; be the number of clusters of type i. Then due to Assumption 4 cos h; < ((1)costt) S), , for all Cj of type Finally, note that cast PP.A) S (1) k, also due to Assumption Combining this, we then have
coall C,,)
(10 (18:2-(0 ( (h-1) -1/522 )e0p
Σ
Σ
(cost(P. - cost( Poost(P..A. P.A))
CJET, pEC,nR
2-2h. cost( P, P,Ssst P, A)
$ 0(1) Σ
k 122/2 1 (cost(P, S) cost( (P, (P,)))
CJET; pEC,rs
2 2-2hh
k ki 2
s 0(1) Σ CYET, pEC,
Σ
h; 1222
(I: + kū 26)2
Assuming event E, this may now be bounded by O(1) we may bound the term by
24
2
If evennt does not hold,
[o] 264
2h 2
2 2h
kk
k.100
(
(6+6.2.)
Completing the Proof (for Eq. 7
Throughout this section, we use the bound on the expected maximum of independent Gaussians.
Lemma (Lemma 2.3 of Massart 2007 ). Let yi ~ ((,, [m] be Gaussian random variables and suppose o, S a for all i. Then E[max|gi gg]l] < 2o /nnnn.
*E[n]
We construct nets for all cost vectors constrained to the entries associated with points of clusters of type in some solution, i.e. we only consider points p Cj E Ti and the entries vi
For every fixed set of clusters of size k; of type T;, the number of cost vectors in Nx+1 x N₂, is most exp (7 k log ||P|o min(k; 22h 22h 2 - It)) for some absolute constant y due
Lemma We split the vectors in the nets by k; S Vk or by k; > Vk. both cases, we have 2 217z I Vk. With the bound the variance (Lemmal 7 and conditioned on event E),
min k2, 2'
then have
logs 22
ΣcSer, Epec,na (h+1) S,8 )ep 9p (cost(P, + cost(P,A))
En
sup E X
E
8,,4
1=1

---

log
Ec,en, Epec,nalus (1 (1+1)
(1
- -1p
Dwp 9p
Eeilig
sup -
(cost( P.S) + costsos..
Ing
Ecee (ug
-17 - )up 9p
Σ h=1
EgglEg
sup 08.111 AN,
(cost(P, (P..)) cost(P.A)))
logg
2-2h
< 2
y. k. log |Pll 22h /k .i. h.
[22]
h=1
< //r y. kVk log Pllo -i- log c-1
(10)
[S2]
If & does not hold, we use the somewhat coarse bound of min(k; 2n)
k.k,
S k to obtain
217
log
Σc,er, En (t (22 - Upp yep gp
EnplE g
sup 68. E XN
E
(cost(P, cost(P,A))
< 2/ 7. 33 log Pllo min(k,,2) 29) i log"
(11)
We have P S 1/k²2 due to Lemma 6 Since
Pll 0 S poly(k, -, 2' < 0(1) and by our
choice of [2], combine Equations 10 and
11
with the law of total expectation obtain
loge
Σc,er, Epec, (uy (-420(++1) -rp. 'w 9y
En
sup -8,--1 - ER xNr
(cost(P, S) + cost(P,A))
1=1
< 1/ kvk. log PPlo A-log* 5-1
[
-2
7: k3 log Pllo min 21) i- logg c-1
|
k22
< 1 y. lvk- log Pllo i log² g-1,
< 0(1)
(12)
Ω
log e-1
Disclosure of Funding Acknowledgements
Kapser Green Larsen was partially supported by the Independent Research Fund Denmark (DFF) under Sapere Aude Research Leader grant No 9064-00068B.
David Saulpic has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (Grant agreement No. 101019564 "'The Design of Modern Fully Dynamic Data Structures (MoDynStruct)".
erc
Chris Schwiegelshohn was partially supported by the Independent Research Fund Denmark (DFF)
under Sapere Aude Research Leader grant No 1051-000 105-00066B and the Innovation Fund Denmark under grant agreement No 0153-00233A.
Omar Ali Sheikh-Omar was partially supported by the Innovation Fund Denmark under grant agreement No 0153-00233A.
10

---

References
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027-1035, 2007. URL http: htt.ttp:
org/ prtg/iitaiion.co wtt.:o..ccmmmmm11mm331111 1283494
Olivier Bachem, Mario Lucic, and Andreas Krause. Scalable k -means clustering via lightweight coresets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 1119-1127, 2018a. doi: 10. 00.1145/2198899:2299999
URL httph: org/ 10. 1445/229819 921999991999999999 3219973
Olivier Bachem, Mario Lucic, and Silvio Lattanzi. One-shot coresets: The case of k-clustering. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-/1 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pages 784-792, 2018b. URL http:
//proceedings mlr wwwppppwsssseeepeeeepeeppp 2/84/bachem18a.. htmm
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 Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 569-579, PMLR, 2020. URL attp://proceedingg mlr, wall.pres ptress/v11/// hww199/baee2aa.a html
Sayan Bandyapadhyay. Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, 1, Glasgow, Scotland ( (Virtual Conference). volume 198 of L.Ples, pages 23:1-2:: 1-23:15. Schloss Dagstuhl- Leibnii-7Zentrum für Informatik, 2021, doi: 10.42300..PIcss.CAAPPPP.. .23. StRpstt:::/// //do::://ddoiie org 10. 4230/LIPICC ICALP 2021 .23
Luca Becchetti. Mare Bury, Vincent Cohen Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenttrnn lindenstrauss lemma. In Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1039-1050, 2019. URL htt.httts:///oii.... org /111//131336663311111
Jock A. Blackard and Denis Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculture, 24(3):131-151, 1999. ISSN 0168-1699. doi: http://doi.org/10..000
S0168- 169966900990000-600 URL httth::///// http://wwwww.wwwcww/......... wwtp:/ttt.cccccccccceeeeeeeeeeee http///cicne/etice////pp/// 50168169999000460
Christos Boutsidis, Michael W. Mahoney, and Petros Drineas. Unsupervised feature se- lection for the $kş-means clustering problem. In Advances in Neural Information Pro- cessing Systems 22: 23rd Annual Conference on Neural Information Processing Sys- tems 2009. Proceedings of meeting held 7-10 December 2009, Vancouver, British Columbia, Canada., pages 153-161, 2009. URL http::///ppprr..ips.... cc/paper/ 3724 www.-uusrrrrieeeeettteeeeee www.uurooeeeeeiiooooeooeeeeeoeee tarethe--2 means wwwsseringtteeeepeeeeeeee problem
Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. Random projections for Sk$- SkS-means clustering. In Advances in Neural Information Processing Systems 23: 24th Annual Conference
Neural Information Processing Systems 2010. Proceedings of meeting held 6-9 December 2010, Vancouver, British Columbia, Canada., pages 298-308---22 306, 2010. http:: http:://ppppraa.pee ceapeess.iips... cipa.cc/
paper /390/ h 1an000r-andomm..m www.rranodooooccciiroeeeereeeeee
for means clustering
Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal coresets for least-squares regression. IEEE Trans. Inf. Theory, 59(10)6880 6892, 2013. doi: 10. 10.1109/TT.2201322222222. 111109//1I1 2013. 2272457
Christos Boutsidis, Anastasios Zouzias, Michael Mahoney, and Petros Drineas. Randomized dimensionality reduction for k-means clustering. IEEE Trans. Information Theory, (24: 1062, 2015. doi: 10.1109/TT22201423775577, URL, https:/ /tattts:://do...o org 110..1109/TTTT 1w.109//ITTT. 2014 28775327

---

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering with missing values. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin. Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Process- ing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 17360- 17372, 2021a. neurips. wwtpppppppppppccpctpttcccteaaett
www.rstttbsttttttt.ommmmeo html
Vladimir Braverman, Shaofeng H.-C. Jiang. Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minot graphs and beyond. In Dániel Marx. editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference. January 10 13, 2021, pages 2679-2696. SIAM, b021 doi: 02.1137/1998166 191641977665.555 URL httpa://doi.org/ 111.:/....1.1111111111
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets.
CoRR, abs/2209.01901 2022. doi: 10.48550/arXi..2200.0002 2101000 URL https://///oo..rr////// 19650/arXiv. 2209.01901
Moses Charikar and Erik Waingarten. The johnson-lindenstrauss lemma for clustering and subspace approximation: From coresets to dimension reduction. CoRR, abs/2205.0007// 2022a. doi: 10.48550karXiv 220500077. https://:///doi k8.
10. 48550/ aivv
2205. 00371
Moses Charikar and Erik Waingarten. Polylogarithmic sketches for clustering. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of L.Ples, pages 38:1-38:20. Schloss Dagstuhl Leibniz-Zentruum für Informatik, 2022b. doi: 1.423001.PP.s11AA...22.....
UtL.https://doi.coom org/ wttpr//g.......1121 ww2.0/2/1III...... ICALP 2022.33 338
Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923-9447) 2009.
Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal embeddings in sublinear time. 62nd IEFE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1209- 1216. IEEE, 2021. doi: 10.11099FOCS52299.2200 20000005522999221001010 URL
https://doi. org/ 10. 1ww.//00S/22999.... 2w2.:5229999222......22 202210001111
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 163-172, 2015.
Vincent Cohen-Addaa and Jason Li. On the fixed-parameter tractability of capacitated clustering, In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 41:1-41:14, 2019. doi: D042300LPIes..ICALPP.0000 https://dol. stttp:://do.orr//111 10. 4230/ ICALP 2019.41
URL
Vincent Cohen-Addad and Chris Schwiegelshohn. On the local structure of stable clustering instances. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA. USA, October 15-17. 2017, pages 49-60, 2017. doi: N0.1109/FOCS.2017.1 URL https:
//doi.org//a 1 1009 CF.00/FFOG /Fw.//FCCO.///// 2017 .4
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 202 pages 169-182. ACM, 2021a. 3406325.3451022
doi: 10. 14/144443335555510222 URL httph: / //ooi or.//0..11/3
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edi- tors, Advunces in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 21085-21098, 2021b. URL https: httptttp:///rroeee/eee /ttp:///ppopc.s.../eee/ neurine httppp.ccpppeeee palppppppppppaaaaaeeeeep 40556555322223118222401116566663 http:///4a00o020222ebbbberreeeee Abstract. html
12

---

Vincent Cohen- Addad, Kasper Green Larsen. David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Anmual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1038-1051. ACM, 2022. doi: 10.1145/3519935.355 1911999955.339944 3519946. URI.
https: //opii://do.... org/ 10. 1545/35 3519946
Petros
Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay. Clustering large graphs via the singular value decomposition. Machine Learning, 56(1-3):9-33, 2004. doi: 10. 10230/::///CHH.. (023//BMAACHH.00003311111
URL https:://oi..rrgg/g///o/ 1023/ MACH
0000089113.59011 59016.96
Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. Theor. Comput. Sci., 697: 1-36, 2017. doi: 10. 10.10166..es.22117.66..
URL http://///doi ht11://0000...111.......... wtt.o//..cc..........ee 2017
06.021
Dan Feldman. Core-sets: An updated survey. Wiley Interdiscip. Rev. Data Min. Knowl. Discov, 10 (1), 2020. doi: 10.1002/widm. 1335. Utt.https:///o..oorr orgo www.://///////////.....
1335
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium Theory of Computing, STOC 2011, San Jose, CA. USA, 6-8 June 201 I, pages 569-578, 2011.
Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. Coresets and sketches for high dimensional subspace approximation problems. In Proceedings of the Twenty- First Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 630-649, 2010.
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering. SIAM Comput., 4963)6001-657, 2020. doi: 10.1137/18M1 URL 00.1
Zhili Feng, Praneeth Kacham, and David Woodruff. Strong coresets for subspace approximation and k-median in nearly linear time. CoRR, abs/1912. 12003, 2019. URL UtL.http://axxiv.orr
abs abs/1912. 12003
Zhili Feng, Praneeth Kacham, and David P. Woodruff. Dimensionality reduction for the sum-of- distances metrie. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages //proceedings.nt mlr areess/v139/ wttss////3/////egg...m html
PMLR, 2021. URL http
Hendrik Fichtenberger, Mare Gillé, Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. BICO: BIRCH meets coresets for k-means clustering. In Algorithms ESA 2013 - 21 Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 481- 492, 2013.
Gereon Frahling and Christian Sohler. A fast k-means implementation using coresets. In Nina Amenta and Otfried Cheong, editors, Proceedings of the 22nd ACM Symposium on Computational Geometry, Sedona, Arizona, USA, June 5-7, 2006, pages 135-143. ACM, 2006. doi: 10.1145/ 1137856.1 137879. htl.sttts:://// //doi hteddii.og//////o org. 11 /111//11///55111 1177566 1137879
Sariel Har-Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. Discrete & Computational Geometry, 37(1):3-19, 2007.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291-300 2004.
Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC 2020, 2020. doi: 10.1 145/3357773333844299 StRL.ttts:://// :/doi
org 10. /1411/151//7111..1 33343333333773333382666 3384296
13

---

Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. Epsilon- coresets for clustering (with outliers) in doubling metrics. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814-825, 2018. doi: 10. 109/FOCC. 2018.00082.
Epsilon-coresets
1109 /FCCS. 2018. 00082
Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 7587-7598, 2019.
Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for regressions with panel data. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020. December 6- 12, 2020, virtual, 2020. URL https: http://ooceediinn.nereieirppeeep Abstract. Abbrrsatttt..tt--aaaaatttttt.tt
Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for time series clustering. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual. pages 22849-22862, 2021. URL https: https::/ http://///ooceeeg...eeeee www.nneuriiccooo wtwpp//gwe.eerrpppepppepeeeeeeee pcppp/////////////////aa/ 22011hashhh c110basee44b22276bb66663333 Att.aaaat.t222eaaaaararatttttat
122461 Aww.taat.tttatttaaaaaaaa
Lingxiao Huang, Jian Li, and Xuan Wu. Towards optimal coreset construction for (k, z)cclssterigg: Breaking the quadratic dependency on k. CoRR, abs/221 11933, 2022. doi: 10.48550/arXiv.2211.
11923. URL htIl.htpss://// //doii.///oi..o org/ 10. 48550/ ar 2211.11922 11923
Shaofeng H.-C. Jiang. Robert Krauthgamer, Jianing Lou, and Yubo Zhang. Coresets for kernel clustering. CoRR, abs/21 10.02898, 2021. URL /ttp:/ wtwp///////////../a////////// 02898
Zohar S. Karnin and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1973-1993. PMLR, 2019, URL htttt:://prreet http:::://ooceeedeee ings. mlr wal..ppess//vee www99//karnn19ee html
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Evangelos Simoudis, Jiawei Han, and Usama M. Fayyad, editors, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) Portland, Oregon, USA, pages 202 207. AAAI Press, 1996. URL http: /www//wwwwwwc/oc aaai. org Liwtrrrr/brb//99////0 19tp//999/////996.9 kdd96 033 php
Michael Langberg and Leonard J. Schulman. Universal e-approximators for integrals. In Proceedings of the Awenty-First Annual ACM-SIAM Symposium Discrete Algorithmss SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 598-607, 2010.
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Nonlinear dimension reduction via outer bi-lipschitz extensions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1088-1101, 2018
Tung Mai, Cameron Musco, and Anup Rao. Coresets for classification simplified and strengthened. In Mare Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021, virtual, pages 11643-11654 2021. URL httptp:://proceedingg..ooo aaw.aaaeaaosaeeeeeaaaaarrraaaeaa Abstract html
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1027-1038, 2019.
Pascal Massart. Concentration incqualities and model selection. 2007.
14

---

Alejandro Molina, Alexander Munteanu, and Kristian Kersting, Core dependency networks. In Sheila A. Mcllraith and Kilian Q. Weinberger. editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Iniel- ligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3820-3827. AAAI Press, 2018. URL / //www/ aaai, org/oca/iddex....oeeeeeeooooo/ee php/
Alexander Munteanu and Chris Schwiegelshohn. peresets-methode and history: A theoreticians design pattern for approximation and streaming algorithms. Künnstlchhe Intell., 32(1):37-53, 2018.
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6562 6571, 2018. URL httph:tp: / /procedding peurips.cc/paper /211// http://ppppeee/1///aaaaaeaaaaaee htt.:///aeabbbeeeooooooooooo6663 wwt.:/fffffttttttttttaaa...aaa.. html
Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in euclidean space. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 20/9, pages 1064-1069) ACM, 2019. doi: 10.11445/311227633336300 URL https: //doi org/10. 1145/ 3313276.3316307
Jeff M. Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discret. Comput. Geom., 63(4))867-887 887, 2020. doi: 10.1007/004454019-00014444 URRhhttps://do
org/10. 1007 00000/000454401-0001444
Gilles Pisier. The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics. 94, 1999.
Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 3/- - June 03, 2014 pages 764-773. ACM, 2014. doi: 10.1 10.1145/2591796 2591797. URL https:://// / htt:://d.....rro 10. 145/ 2591796.9979999 2591797
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algo- rithms for fair k-means. In Approximation and Online Algorithms- 17th International Work- shop, WAOA 2019, Munich, Germany, September 12-13 13, 2019, Revised Selected Papers. pages 232-251, 2019. doi: 10. 00110779978-3300--3944799999 16. URL https: ott///ii.org11...10....0
978-3-030-
Chris Schwiegelshohn and Omar Ali Sheikh-Omar. An empirical evaluation of k-means coresets. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPles, pages 84:1-84:17. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022. doi: 10.4230/L.PPcs.ESS... F.S. URL htt..https://// htttps::/ddoi.or//000// http://..433////// /30/LLIIII......../...../ ESA 2022.84
Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEFE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris. France, October 7-9, 2018, pages 802 813, 2018. doi: 10. (000///OS.2008.000000 URL httphttts://// //tpi::://doo.roeo org/ 10. 1109 /0///FCCS... 20188000811
Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: http://ooooeedge.eeeeeeee
Abstract.
15

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs in the supplementary material. Due to space constraints, could not include them in the main body.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] These data sets are unlimited.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [No] We did not generate data sets ourselves.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] We did not generate data sets ourselves.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [No] Not applicable.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [No] Not applicable.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [No] Not applicable.
16


Reviews:
[{"review_id": "hSVmUSlVmW", "reviewer": "Reviewer_1Yz9", "summary": "The authors address the problem of coreset construction for the known k-means problem. They propose a coreset construction scheme and prove that it achieves coresets of size smaller than the state of the art, in some regimes.\nTo carry out the analysis, the authors propose a novel method that avoids terminal embeddings, which are common in the analysis of prior works. The authors claim this novel technical contribution may be of independent interest as well.\nEmpirical evaluations are then carried out to test the impact of the proposed approach against known techniques.\n", "questions": "See few question above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed scheme indeed achieves state of the art coreset sizes for one of the cornerstone problems in the field.\n- The analysis are novel and very interesting.\n- The paper is relatively well written.\n\nWeaknesses:\n- Related work section is rushed through and lacks details. It does not contribute to the reader's knowledge, and should be better written in my opinion.\n- Missing important discussions. Examples:\n  * The validity of Assumptions 1-4 is placed in the appendix. At least a brief explanation should be placed in the main text. \n  * A discussion as to why this result cannot be extended to l_z clustering can be very helpful and enriching. \n  * It seems that the proposed algorithm, after ensuring the validity of the assumptions, samples each point according to some simple quantity which resembles the sensitivity distribution known from many prior works. A comparison or discussion is needed here.\n- As of Assumption 3 regarding the input weights: to ensure integer weights (as stated in the appendix), some scaling and rounding is required. Doesnt this produce a dependency on the smallest weight, or, alternatively, on the model's precision? If so, this is an important note.\n- The experimental results are not sufficient: \n  * Important details are missing.\n  * The proposed method is not shown to achieve better results than the competing methods. \n  * Running time are not reported, which is crucial, as it seems that the proposed method would (theoretically) achieve much larger computational times. This is due to the computations required to enforce Assumptions 1-4 (which include a computation of an alternative coreset, e.g., the sensitivity coreset used as a competing method).\n- At the end of the day, the proposed algorithm is not novel as it simply computes a (previously known) sampling probability for every input point, which is based on some (previously known) approximation for the problem, then it samples points from this distribution and does some reweighting.  Also, as the authors claim, enforcing Assumptions 1-4 is also not novel. The only novel part seems to be the analysis. Hence, in my opinion, the paper's main contribution is not sufficient.\n\nMinor comments:\n- The first paragraph on Page 2 is important and should be somehow better emphasized.\n- Line 50: \"may be reduced to log(k/\\eps)\\eps^-2 using dimension reduction techniques\". some citation should be added at the end of this claim. \n- Line 50: \"to technique\" (typo).\n- Equation at Line 50: missing closing bracket.\n- Typos at Line 63.\n- The equation after Eq. (2) utilizes the point on the left and on the right hand sides, but p does not seem to be defined.\n- Lemma 5: where is X defined?\n- Line 210: the maximum distortion is reported in the experiments. Do you have insights on the average distortion? The average distortion might be a more accurate indicator.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OVmjILjE8Qj", "reviewer": "Reviewer_22jd", "summary": "The paper studies coresets for k-means clustering in d-dimensional Euclidean space. The paper is of theoretical nature and shows an improved upper bound of $O^\\ast(\\epsilon^{-2}k^{1.5})$ on the size of coresets that can be obtained by group sampling. This improves the current best bound of $O^\\ast(\\epsilon^{-2}k^2 \\min\\{\\epsilon^{-2},k^2\\})$. ", "questions": "My suggestion is to improve the technical parts. Also the plots of the experiments may be improved (one can barely see the differences in cost.)", "limitations": "No potential negative societal impact in sight.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an important and interesting problem, which is under active research. The obtained upper bound is a further step towards closing the gap to the current lower bound.\n\nThe work is somewhat incremental since it heavily uses results from previous work and basically achieves the result by improving a part of it -- the cost vector net.\n\nOn the other hand, the obtained bound is nice and is certainly worth to be published.\n\nAnother weakness is that the notation and the technical details are not always clean and convincing. Also the experiments are not that meaningful.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MrjRv2gcP_B", "reviewer": "Reviewer_jVkM", "summary": "The paper presents a theoretical analysis leading to smaller coreset sizes for the problem of $k$-means. The coreset can then be extended also to the $k$-median problem.  \n\nThe authors provide an improvement over the work of Cohen-Addad et al. [2022], by finding nets (discretizes set of solutions) with better properties, to obtain their coreset size. This in term leads to the smallest coreset size for $k$-means with the emphasis that the coreset size should not be linearly in $k$. ", "questions": "1) What is $p$ at the inequality below Eq. 2? I assume $p \\in C_i$, right? \n2) Why does it imply that after $t = \\frac{1}{\\varepsilon^{-2}}$ rounds, $(I - \\Pi_U\\Pi_U^T)s = \\overset{\\to}{0}$? please clarify this point.\n3) From what I understood, $Pi_U$ is the span of all previously added vectors from Lemma 5. So basically, this is a set, right? If so, what does it mean to have $\\left\\| Pi_Us - s^\\prime \\right\\|$? Please do clarify.", "limitations": "The authors clearly addressed the limitation of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n    1) A smaller coreset size for the k-means problem, leading to a subquadratic coreset size in $k$ (the number of means).\n    2)  While the paper is based on a paper by Cohen-Addad et al. [2022], the authors present techniques that hinge upon finding better nets for obtaining smaller coreset sizes for both the $k$-means and $k$-median problems. In other words, the authors present an improvement on the techniques of Cohen-Addad et al. [2022], by generalizing the techniques to rather finding nets with better properties.\n\n* Weaknesses:\nThe paper is somewhat hard to follow, and also contains many grammatical errors.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8Hu0PAeIr8Y", "reviewer": "Reviewer_XcEV", "summary": "\nThe paper considers the problem of providing a bound on the size of the coresets for the K-means problem which is closer the lower bound than the existing state of the art approaches. Some experimental results are also provided to support the analysis in the paper.\n", "questions": "(A)Does this analysis follow through for other clustering problems such K-median, K-mediods etc? \n\n(B) It seems like you are able to get a better clustering nets because you can bound the error by the geometric mean (smaller) than the arthimetic mean. Is this the tightest one can get? \n\n(C) The experimental section is showing the cost of the various algorithms as well as the distortion results. However, it would be interesting to show the scaling of the size of the coresets. These are provided in the supplementary and would be better served if shown in the main paper? \n", "limitations": "The paper would be a nice contribution to the clustering literature but I wonder if it would be better suited to a primarily theoretical audience like COLT or similar. I provided an initial lower rating to reflect that and will adjust it based on the upcoming discussions. \n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is highly compressed to fit into the confines of the conference submission. Though the writing is clear, it heavily relies on reading up on the results from Cohen-Addad et al's recent papers. \n\nThe setting is of prime interest given that K-means shows up in various machine learning settings. The result of improving the min(k, 1/eps^2) to the \\sqrt(k)\nis pretty significant because now it is clearer that there will be a potential algorithm matching the lower bound of O(k/eps^2).\n\nI checked over the main theorems and approach but did not work through all the details.\n\nThe paper is solving an important problem in clustering but the reduction from k to \\sqrt(k), while theoretically very interesting, is a bit too narrow. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept