Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces
Authors: Vincent Cohen-Addad
David Saulpic
Chris Schwiegelshohn
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Clustering
sublinear algorithms
coresets
sampling

Abstract: In this paper, we consider the problem of finding high dimensional power means: given a set $A$ of $n$ points in $\R^d$, find the point $m$ that minimizes the sum of Euclidean distance, raised to the power $z$, over all input points. Special cases of problem include the well-known Fermat-Weber problem -- or geometric median problem -- where $z = 1$, the mean or centroid where $z=2$, and the Minimum Enclosing Ball problem, where $z = \infty$.

We consider these problem in the big data regime.
Here, we are interested in sampling as few points as possible such that we can accurately estimate $m$.
More specifically, we consider sublinear algorithms as well as coresets for these problems.
Sublinear algorithms have a random query access to the $A$ and the goal is to minimize the number of queries.
Here, we show that $\tilde{O}(\varepsilon^{-z-3})$ samples are sufficient to achieve a $(1+\varepsilon)$ approximation, generalizing the results from Cohen, Lee, Miller, Pachocki, and Sidford [STOC '16] and Inaba, Katoh, and Imai [SoCG '94] to arbitrary $z$. Moreover, we show that this bound is nearly optimal, as any algorithm requires at least $\Omega(\varepsilon^{-z+1})$ queries to achieve said approximation.

The second contribution are coresets for these problems, where we aim to find find a small, weighted subset of the points which approximate cost of every candidate point $c\in \mathbb{R}^d$ up to a $(1\pm\varepsilon)$ factor. Here, we show that $\tilde{O}(\varepsilon^{-2})$ points are sufficient, improving on the $\tilde{O}(d\varepsilon^{-2})$ bound by Feldman and Langberg [STOC '11] and the $\tilde{O}(\varepsilon^{-4})$ bound by Braverman, Jiang, Krauthgamer, and Wu [SODA 21].

Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces
Vincent Cohen-Addad" Google Research, Zurich.
David Saulpic" Sorbonne Université, Paris
Chris Schwiegelshohn' Aarhus University
Abstract
In this paper, consider the problem of finding high dimensional power means: given a set A of n points in Rd find the point m that minimizes the sum of Eu- clidean distance, raised the power 2, over all input points. Special cases of problem include the well-known Fermat-Weber problem or geometric median problem where Enclosing Ball problem, where = oc.
the mean or centroid where 2, and the Minimum
We consider these problem the big data regime. Here, we are interested sampling as few points possible such that specifically, we consider sublinear algorithms as well as coresets for these prob- lems. Sublinear algorithms have random query access the set A and the goal is to minimize the number of queries. Here, we show that Ô (e (==3) samples are sufficient to achieve a (I++) (1 -approximation, generalizing the results from Cohen, Lee, Miller, Pachocki, and Sidford [STOC 166] and Inaba, Katoh, and Imai [SoCG *94] arbitrary z. Moreover, we show that this bound is nearly optimal, as any algorithm requires at least ? (-=*+1) queries to achieve said approximation.
accurately estimate m. More
The second contribution are coresets for these problems, where we aim to find find small, weighted subset of the points which approximates cost of every candidate point E Rdd up (1 + E) factor. Here, we show that (s-2) points are suf- ficient, improving the Ô (ds-2) bound by Feldman and Langberg [STOC '11] and the (E=4) bound by Braverman, Jiang, Krauthgamer, and Wu [SODA 21].
1 Introduction
Large data sets have shifted the focus of algorithm design. In the past, an algorithm might have been deemed feasible if its running time was polynomial the input size and so a textbook fast algorithm can have time complexity for example quadratic. For truly gargantuan data sets, even linear time or nearly linear time algorithms could be considered too slow or requiring too much memory. This led to the emergence of the field of sublinear algorithms: How well can solve problem without reading the entire input?
Except for trivial problems. deterministic time sublinear algorithms do not exist. Our primary tool in designing sublinear algorithms is thus the following basic approach:
Take a uniform sample of the input.
Run algorithm on the sample.
Hence, the performance of sublinear algorithm is often measured in terms of its query complexity, iee. the number of samples required such that we can extract high quality solution in the second
"Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

step above that generalizes to the entire input. Sublinear algorithms have close ties to questions in learning theory and estimation theory, where we are similarly interested in quality to sample size tradeoff.
A perhaps very fundamental problem of primary importance in machine learning and data analysis is to efficiently estimate the parameters of a distribution. For example, given a distribution D, how many samples do we need to estimate the mean? Even such simple and basic question has surprisingly involved answers and are still subject to ongoing research (Lugosi & Mendelson (2019); Lee & Valiant (202T))
In this paper, we investigate the possibility of estimating power means in high dimensional Euclidean spaces. Specifically, given arbitrary set of points A, we wish to determine the number of uniform queries S such that we can extract a power mean m with
cost(m)
Σ PEA
1p mll² s (1+
min P
Σ lpp mll", PEA
where ||p|| denotes the Euclidean norm of a vector p.
The power mean problem captures number of important problems in computational geometry and multivariate statistics. For example, for = = 1, this corresponds to the Fermat-Wett problem also known as the geometric median. For = 2. the problem is to determine the mean centroid of the data set. Letting = -> oo, we have the Minimum Enclosing Ball (MEB), where one needs to find the Euclidean sphere of smallest radius containing all input points.
For = 2, the problem not well studied, but still has many applications. First, higher powers allows us to interpolate between no sublinear algorithm Skewness (a measure of the asymmetry of the probability distribution of vealev random variable about its mean) and kurtosis (a measure of the "tailedness" of the probability distribution) are the centralized moments with respect the three and the four norms and are frequently used in statistics. The power mean is way of estimating these values for multivariate distributions.
and - oc, which is interesting as the latter admits
Another application is when dealing with non-Fuclidean distances, such as the Hamming metric, coreset constructions for powers of can be reduced coreset constructions for powers 2z. So for example if we want the mean in Hamming space, we can reduce it to the 2 = 4 case fin squared Euclidean spaces Huang & Vishnoi (2020).
These problems are convex and thus can be approximated in the near-linear time efficiently via convex optimization techniques. However, aside from the mean (z = 2), doing so in sublinear setting is challenging and to the best of our knowledge, only the mean and the geometric median (z 1) are currently known to admit nearly linear time algorithms.
Our main result is:
Theorem 1. There exists an algorithu that, with query complexity O(5- volylog(s-"))ll log" 1/5), computes a +1+ + 8) approximate solution to the high dimensional power mean problem with probability at least 1- 5.
A key component in designing this algorithm is a novel analysis for coresets for these problems. Corescts are succinet summaries that approximate cost for any center solution
Theorem 2. For any set of points in d-dimensional Euclidean space, there exists an e-coreset for the high dimensional power mean problem of size Ō 20(z)).
With the exception of the mean. previous coresets for these problems achieved bounds - 2.)0(=).
min (d, = 2)) Glhhen-Adaa et al.. 2021 y; Braverman et al. (2021); Feldman & Langberg (001]) ) or had weaker guarantees such merely approximating optimal solution or requiring removal of outliers from the data set.
Comparing the bounds in Theorem 1 and Theorem 2 one may question whether the exponential de- pendency in 2 is necessary for computing an approximation. Indeed, previous sublinear algorithms
TTo see this, we place n points at and one point with probability 1/2 at and with probability 1/2 at 0. Any 2 - e approximation can distinguish between the two cases, but this clearly requires us to query 2(()) points.

---

Hence, one needs to use new tools. A natural starting point is to use techniques from coresets, as they allow us to preserve most of the relevant information, using a substantially smaller number of points. Unfortunately, coresets have drawback: the sampling distributions used to construct core- sets is non-uniform and therefore difficult use in a sublinear setting. The first step therefore to design coresets from uniform sampling. To do this, we use and improve upon a technique originally introduced by Chen (209). Chen showed that, given a sufficiently good initial solution q, one can partition the points into rings exponentially increasing radii such that the points cost the same, up for both the geometric median and the mean had a query complexity of O(==²), and thus matched our coresets bounds. Unfortunately, we show that the exponential dependency in the power is indeed necessary even in single dimension:
Theorem 3. For any ε > 0 and z, any algorithu that computes with probability more than 4/5 a (1 + approxximatin for a one-dimensions power mean has query complexity (1(==+1).
Hence, up constants in the exponent, our sublinear algorithm is tight. Moreover, the algorithm is very simple to implement and performs well empircally.
1.1 Techniques
While stochastic gradient descent has been used for a variety of center-based problems (Clarkson
ct al. (2012); Cohen al. (0016), it is difficult to apply it for higher powers. Indeed, Cohen et al. (2016) remark in their paper that even for the mear (z = 2) their analysis does not work as the objective function neither Lipschitz, nor strictly convex.
to constant factors. Thereafter, taking uniform sample of size Ö(d- =²²) from each ring produces a coreset. Since there are at most O(log n) rings in the worst case, this yields coreset of size Ö(d E log n).
To realize these ideas in sublinear setting, we are now faced with a number of challenges. First, rings that are particularly far from q may contain very few points. This makes difficult for a sublinear algorithm to access them. Second, partitioning the points into rings depends on the cost of q. It is very simple to construct examples where estimating the cost of an optimal power center requires ((z) many queries. Finally, this analysis loses both factors log n and d, which we aim to avoid.
We improve and extend this framework in two ways. First, we show that it is sufficient to only consider Ologg=")) many rings, which, in of itself, already removes the dependency on log n. Moreover, we show that it is possible to simply ignore any ring containing too few points, i.e. any ring with less than c=+0(1) points may be discarded. The intuition is that, while rings with few point may contribute significantly to the cost, these points do not influence the position of the optimal center by much. Thus, using a number of carefully chosen pruning steps, we show how to reduce both the problem of obtaining a sublinear algorithm as well as obtaining coresets to sampling from a select few rings containing many points.
The second improvement directly considers an improved analysis of sampling from rings. The standard way to prove a coreset guarantee is to show that using s log 1/8 samples we preserve the cost of a single solution with probability and have obtained a coreset, which we call the "naive" union bound. This works in certain cases such as finite metrics, but is insufficient if we have infinitely many solutions such as Fuclidean spaces. The simplest way to improve over the naive union bound is to discretize the space and then apply the naive union bound on the discritization. In literature this is sometimes called an e-net bound. This can be optimal or close to optimal for certain metrics, but so far these arguments have only lead to Ö(s-2 min(d, e-2) bounds for coresets in Euclidean spaces.
delta. If there exist T solutions then we set 1/T
Instead of applying a union bound over the discretization "one shot", we apply union bounded over nested sequence of increasingly better discretizations. Essentially, instead of only using set of centers C. as substitute for all centers is Rdd, we use centers c² E Ch for different values of h E {l.... log 1/E}. In literature, this is known chaining, Nelson (2016) for survey. We can then write, for any input point set P, Epep cost(p, c) EpEp Enzo cost(p, c*+1) - cost(p, c²), where cost(p, d is defined to be 0 and |cost(p, c²)) cost(p,, c) S 2 2-"cost(p, c). We now only
'For the special case of the mean, Inaba et al. Inaba et al. 1994 observed that 02) samples are never- theless sufficient.
3

---

apply the naive union bound for successive summands, i.e. we approximate EpEp cost cost(p,c*+1)) cost(p, c²) up to an error of EpEp Costtoss(ppp c).
Essentially, the idea is to use sequence of solutions ep that approximate a candidate solution with increasing accuracy as h + oc. Approximating the cost of a candidate center e can then be written as a telescoping sum of solutions Ch. L.c. cost(e) = ">= cost cost(cn++1 cost(c)), where cy is of the order 2 and (cu) == O. The notion of distance between
solution that has distance candidate solutions is perhaps most easily understood by imagining a solution to be a cost vector o where the ith entry corresponds to the cost of the ith point of A when using
candidate center, ie., off = cost(p,, c). Informally, we consider two solutions c and to have distance at most 2 -h Ilpp: - cl - Ip: e' 1 2 (Ilp. - clf + llp d'll²) for all points p. E A.
1.2 Related Work
Sublinear Approximation for Clustering: A number of sublinear algorithm are known for clus- tering problems. For k-Median, under the constraint that the input space has a small diameter, constant factor approximation is known (Czmma & Sohler (007)) Bavid (2007) proposed a different set of conditions under which a sublinear algorithm for k-median and k-means exists. Other approximations, with different constraint are also known: for instance, MMyerson instance,MMyyrrson et al. (2004)
give an algorithm achieving a ((1) appp-ppprxiiaaooonn in time poly(k/s) for discrete metrics, when each cluster has size ((ne/K) /k). For the 1-median problem, this assumption is always satisfied, and their algorithm gives a constant factor approximation in constant running time. The algorithm by Cohen et al. (0166) produces a (1 + -lapprooximation in time min nd log" (m/E), d/E²) for Eu- clidean spaces of dimension d. Ding 2020 202T) and Clarkson et al. (2012) showed how obtain sublinear algorithms for the minimum enclosing ball problem assuming that either the algorithm is allowed to drop a fraction of the points, or with additive error. For the unconstrained version of the problem, no sublinear time algorithm is possible. For the k-means problem, Bachem et al. (2016) showed how to approximate the + algorithm in sublinear time. To our knowledge, no algorithm is known for higher distance powers 2.
Coreset Constructions: A coreset is weighted subset of the input points, such that the cost of any clustering is the same on the coreset than on the input points, up to (1 + 8) factor. The arguably most widely studied problem is coresets for the i clustering problems with powers of distances. Following a long line of work Bachem et al. (2018); Becchetti et al. 2009); 1 Braverman et al. (2021); "Cohen-Addan et al. (2021 Feldman Langberg (201 Feldman et al. (2020); Feng et al. 2021;; Fichtenberger et al. (2013): [Har-Peled & Kushal (2007): Har-Peled & Mazumdan
Chen [
(2004) Huang & Vishnoi| (2020); Langberg Schulman (2010); Sohler & Woodruff (2018), we
now know that coreset of size Okk 20(=) min(k, max x 2.0))) exist. In a low- dimensiona regime, this may be improved For the special case of clustering with a single center, this yields the state of the art O(E bound due to Braveermnnn et al. (2021). For the Minimum Enclosing Ball problem and its generalizations, these algorithms yield no space saving, although sketches of weaker gaurantees of size O(==!) exist (Badoiu & Clarkson )2 Given coreset, it is easy to compute (1 (1++) aapproximaatiooonn in time independent of n:: one just needs to find a (1 + -)aapproximttooon on the coreset points.
de::2ee-22063 and Ō(de--2x) Feldman & Langberg (011))
Coresets have also been studied for many other problems: we cite non-comprehensively fair cluster- ing Cohen-Addda & [ii (019); 20un):Huung al. Indyk et al. (2020), diversity maximization Ceccarello et al. (2018) Indyk et al. (2014) logistic gression Huggins et al. (2016); Munteanu et al. (2018), dependency networks Mollna et al. (2018), or low-rank approximation Maalouf et al. (2019). The interested reader is referred to the recent surveys for more information FeldrmanionnFeldman Feldman 2020); Munteanuu & Schwiegelshohn (2018).
et al. (20T9) determinant maximization
1.3 Organization
We prove our key sampling result in Section 2 sublinear setting (Section 3 and to coresets (Section 4 We conclude with a short experimental evaluation. Due to space constraints, all proofs are included in the supplementary material.
We follow up on that result by applying it to the
1.4
Preliminaries
V E 23. Similarly, we define the Hamming norm ||./|| Ed_ |rs]. For set of points A, we say that ||Al]o is the distinct number
We denote the Euclidean distance of vector x by |||||| :=

---

of points. Note that if A contains multiplicities |A| * || We write Ō(r) to denote O log" z) where a is any constant. For any set and candidate solution we defined cost(A, c) EpEA lpp - clls. If the set is clear from context, we simply write cost(c). We frequently use the following generalized triangle inequality, see Coheen-AAdda & Schwiegelshohn 2017): Makarychey al. 2019) for proofs and similar statements.
Lemma (Triangle Inequality for Powers). Let a, b, c be an arbitrary set of points in a metric space with distance function d and let be a positive inleger. Then for any
1 1+8
=-1
d(a, b)a (1++)) ((a,)))
d(a,c))
d(b,c)²
1 3-1
Id(a. -(a,)))) ((),c)²
d(b, c)².
We also use the fact that uniform sampling is efficient to approximate the density: we review details on sampling in bounded VC dimension in the supplementary material.
Lemma et al. (2001). Given a range space (X, R) with VC-dimension d, an constants E, 6, n,
and a uniform sample S X of size at least O - (d log 1/11 log 1/8)), we have for all ranges
Re E R with [X n R) 2 n |X|
IXnR
SN
X n R X
S
SS|
and for all ranges R E R with [X n R| S 77
|X]
X n R
|S R
E
X
S
with probability at least 1-
The only range space we will consider is the one induced by Euclidean spheres centered around single fixed point. The VC dimension induced of this range space 2, which seems to be a well known fact, although we could not find a reference. For completeness, we added a short proof in the supplementary material.
First, we recall the commonly used coreset definition for clustering problems in Euclidean spaces.
Definition 1. Let A be set of points in RRd, Then a set SL is strong (c, z)-coreset if there exists weight function w + RR+ and a constant such that for any point e.
Σ ll cli Euplp- cll= + K) PEA
Se. Σ -
PES
PEA'
We say that Q is weak (s, c)oorest if for some [0, any point satisfying E Wip
lp d1I² S (1 + E))armmin Epen Wp ||p c|l= also satisfies EpEa llp cl1 S (1 +
cER
E arggmin EpEa 1p cl|=. CERd
The difference between the two notions is that strong coresets give a guarantee for all candidate centers, whereas the weak coreset guarantee only applies for the optimum. In an offline setting, there is no difference in the size for our construction for either guarantee. In the sublinear setting, we will be satisfied with weak coreset as it can be obtained with nearly optimal query complexity.
2 Uniform Sampling Routine
In this section, we outline the proof of our basic sampling subroutine. We assume that we are given a point g, and set of points R such that for all p, p'
ll 41l
Ilp' -
In the following sections, we refer to R as ring. Under this assumption, the following claim holds.
5

---

Theorem 4. Let and R be defined as above and let Q be uniform random sample consisting of E O log 1/6) points. Then with probability at least 1 we have for all candidate centers
c
Cost R, c)
Σ PEs2
[2] 1pp
cll²
E (cost(R, q) + cost R, c)).
We prove this theorem, first by proving the following slightly simpler result and then showing how to apply the result recursively to remove dependency in R|lo:
Lemma 3. Let q and A be defined above and let St be a uniform random sample consisting of E O(e-2.log || log 1 1/5) points. Then with probability at least 1 - 6, we have for all candidate (cost R, q) cost c)).
centers that coss(( R2 c) Epen .
R
c|l S
To set up a chaining analysis, we require two ingredients: (1) a notion of nets and (2) a Gaussian process. We focus on the latter first. For any point c, let of be the |R] dilldimmeiio vector, henceforth called a cost vector, such that Up. = lpp, ell for some arbitrary but fixed ordering of the points in R. Note that ||e||| cost(R, c). Let Pj E with j {L....,s) be the jth point of the sample. Observe for any cost vector induced by some center we have
En
Ups
Σ lp cl|= cost(R, c).
We now symmetrize the expectation. Gaussians with mean and variance Then have for any collection cost vectors N (see Appendix B.3 of Rudra & Wootters (2014)
Let .1...... Is be standard Gaussian random variables, i.e.
R Upp ||u|| Σ J
R Σi=1
Up3 9j
Supup VEN
En sup VEN
cost R, q) + ||0||
cost R, 4) + |1||1
Note that the first term in Equation is the expected maximum deviation from the (normal- ized) expected cost of the sample, if the cost vectors are induced by centers. In other words, if
11 [R] [|:;-|ll (Css((
sup
cost (oa)
< E, we have the desired coreset guarantee. Our cost vectors will
cER
not be induced by centers for technical reasons, but are in a well-defined sense close enough such that it will be enough bound the deviation for these approximate cost vectors obtain bound for all center induced cost vectors. Introducing Gaussians is standard in this type of analysis as concentration bounds typically used for weighted Bernoulli random variables such Hoeffding or
Eis 1 1pll-olff-02 (l.l( +osu
Bernstein too weak. Our goal is therefore to show that Eg sup
< 2
CER4
We now define the nets we will use.
Definition 2. Let R. be set of points and let be candidate solution. For B > O, we say that set of vectors Ng is a --net of R. if there exists a vector v' E Ng such that for every point p R with |pp cll < lpp ql1, we have
||l
c|l
0/6 S (1Ip- cl1² 8 [p -911).
We need show the following three properties:
Epe R. cost R. costt
[R]
By
bounding
En sup vEN./10
costl R.C))
we
can
also
bound
Ei [ Up ell" coat (t,c)
En sup CERd
cost R. +cost R.c)
There exist B-nets of size exp (2 (29 [R]o 8-2 log =/3a

---

3. Let u be a cost vector written as telescoping sum = Σi=1 DoU; 2:-1 of cost vec- tors from ne-nets. Let v', be cost vectors from successive B and 3/2 nets No and N3/2. respectively. By bounding the term En sup
Žj=1 [ 11/; 2/ 93| can also bound of uM
Eg sup VEN:
Σラ=
[R Up, 93
We start with item via the following lemma.
E L2 ||vlla| cost Foant
Lemma 4. Let Ne/10 be e/10-net of R. Then if suPveN./10
we have
10
Ei=1 - [1,, -ell-- S for all Rd. costi (ooo()))
SuPEER"
To prove item 2, we use terminal embeddings Elkin et (017): Mahabadi al. (2018) Narayanan & Nelson 2019), defined follows.
Definition (Terminal Embeddings). Let A be a set of points in Rd. A mapping f TRd + R² is terminal embedding for all p E A and all Rd
(1- 11p 2/2 (1(()) [(ella (1 (6) c|/2.
The guarantee of terminal embedding is very similar the guarantee of the famous Johnson Lindenstrauss lemma, but stronger in one crucial detail. A terminal embedding preserves not only distances between the points of but also the distance between an arbitrary point in IRd and any point of A. Despite this stronger guarantee, the target dimension of terminal embedding is in fact no worse than that of the Johnson Lindenstrauss lemma. Specifically:
Theorem 5 Narayanaa & Nelson (2019)). For any n point-set A R2, there exists terminal embedding f R H with E log n for some absolute constant %
We now use the terminal embeddings show that small nets exist.
Lemma 5, Let R and be defined as above. Then for every 3 >> O, there exists a ß-net of R of size most exp(y 23 32 log |/loo log== where 7 is an absolute constant.
We now move onto item 3.
Lemma 6.
Let and q be defined as above and Qi be a uniform sample consisting of s points. Then for any point and s 2 Fr-3282.. 2. log Rlllologg e- = some absolute constant т), we have
< e. Moreover, if Eim [R] Ip, -f
EqE. sup CER'
2222 = log || log* e log 1/8
cont t.grr
Σi R coatl (l.g) + (2,c)
-
for some absolute constant n,, then we have sup cERd
S E, with probability at least
6.
The proof of Lemma is direct consquence of Lemma and Equation To finally prove Theorem 4 we apply Lemma recursively. The result is essentially special case of Theorem 3.1 from Braverman al. (021).
Lemma 7. Let R. and 9 be defined as above. Suppose uniform sample of size Ö(T -lo || 6 for all candidate centers
log 1/8) satisfies with probability at least
[R]
Icost( R, c)
1lp
<
c ((oot(( R, q) + cost( cost(R, c)).
PEN
Then uniform sample of size Ö(T log 1/8) achieves the same guarantee.
3 Sublinear Algorithm and Analysis
We first describe algorithm that succeeds with constant probability. This probability can be amplified (non-trivially) using independent repetition. In the following we will use parameters and y that depends on which will specify later. We let A be the set of input points.
7

---

Algorithm Sublinear Algorithm for Power Means
1. Sample random point q.
2. Sample a set S O(e poly(e-1)) points uniformly at random.
3. Compute the maximum distance d such that there exist 2/3 E n 1 points with distance
least d from q. Discard all points at distance greater than
4. Define rings R2 such that R2 n S contains all the points distance (d 2- d. 2- from q. {1....,8] (3)-
with i
5. If R2 O S] en |S), remove all points in R2 n.S from S.
6. Define R; = n.
|RnnI
R |s| Weigh the points R₃ n by [R,S8]
7. Solve the problem on the (weighted) set S.
Our goal is to show that S satisfies a weak coreset guarantee. Specifically, we will show that S' has the property that for all points A' C at distance at most d (defined in Algorithm [ from & there S + R+ such that S is strong coreset for A'. We then show that
exists weight function strong coreset for is also weak coreset for A, i.e. we preserve the cost of all points in A', and we preserve the optimum for A.
In order to call Theorem onn only few rings, we now show that the loss incurred by only considering A' is indeed negligible.
Pruning Lemmas We first show that we can safely discard points that are sufficiently far away. as parameterized by 7. We recall the meaning of parameters: a the approximation-factor of the initial solution, 3 is such that points distance closer than 2 d can be merged to the center (see Lemma 9). 7) is such that rings with less than an en-ffracioon of the points can be discarded (see Lemma T0
Lemma 8. Suppose we are given an a-approximate center q. Let B(q, r) be the ball centered at 1/2 Then the following two statements hold.
with radius 4. (2x-rT)
1. Any a-approximate center is in B(g.r).
2. For any two points c, E B(g, r) and for any point p with Ip - a11² > 7 r with
>> - (12z)², we have [pp - clf S (1+ e) cclls.
Unfortunately, we are not given a knowledge of OPT priori. We therefore have to describe how implement this lemma is an a approximation with probability at least 1 - 1/a.. Second, the number of points that cost more than 7 2 a OPT is at most 1/7 n. Combining this observation with Lemma ensures that we are not considering any points that are too far away. Since it is difficult to determine OPT in sublinear fashion, we will rely on additional pruning arguments for points that are close to g.
sublinear fashion. For this, observe the following. First, the point
We proceed here in two steps. First, we consider the points that are very close to Second, we will show that the rings which contain too few points be efficiently sampled have an overall negligible contribution to the cost.
Lemma 9. Suppose that q is an a-approximate solution. Let Anear C A be a set of points with cost al most (e/(a5z))² OPT, Let À = (1 + Anear! Then for any candidate solution e we have
À 11 cl1= - Σ
lp cl2 Se/a
Σ PEAncar
1p cp + OPT
PEAncar
For rings with few points, we have the following.
Lemma 10. Suppose that q that is an a-approximate solution. Let Reheap the union of rings with
RR Al< < E.n n and with radius at most 4(7, x-OPT) where y is given by Lemma Then, for any candidate solution c.
Σ PE
Ipp cll 4 ..mm-7.a-
1pp-cli cl1=.
AEA
8

---

While we will defer the exact parameterization to later, observe that for 3 E OOlog 1/s), E 20(=)
and 17 O(=*) this entire sum can be bounded by O OPT.
The next lemma states that we can use these pruning results in a sublinear fashion.
Lemma 11. Let be point that is a-approximation and let S be uniform sample consisting 0f (a 17 e "polylog(s 8 8-1)) points. Then with probability at least 1 - 6 for all rings Ra,
[R N A max (n (A) R4 nS n
S
R4 n + e max (n 77 |8 n Al).
JS]
Furthermore, let d as in the algorithm, Le., such that 3 e n |s| S S (B(g, d) n ns) Then < (3(en)_1. (00PT 1/s
"
Since do not know r, also do not know which of the rings with i < 0, if any, satisfy 2 d >> (E/a52) (n/3a)'/z 1/= However, the maximum number of these rings is at most log( 5az which will turn out to be of the order Ollog==)). For all of the rings that are not light, i.c. we
1/2
30
cannot discard or snap to q. we now use Theorem To ensure that we can call Theorem invoke Lemma 2 for every ring.
we
While the aforementioned algorithm is guaranteed to produce a (1++)- approximation with constant probability, amplifying this is non-trivial. Indeed, when running the algorithm multiple times, it is not clear how to distinguish a successful run from an unsuccessful one. The main issue in amplifying the probability lies in the initial solution q. any invocation of Lemma 2 or Theorem 4 allows us to control the failure probability. The simplest way to achieve success probability
Probability Amplification
is condition on ||q - cll= S OPT, Unfortunately, this makes dependent on ó, which significantly increases the sampling complexity.
Instead, we use the following algorithm. We sample E Olog 1/6) points Q1... .m uniformly at random. For each point, we additionally sample O( ((oo" 1/E + log 1/5)) points Sq. For qs, let d, denote the minimum radius such that the points in S [B d,) n S. > 2 We output the point with minimal d,.
The following lemma shows that this point is, with probability at least 1 - 8, a 8 approximation.
Lemma 12. Given query access to A, we can identify with probability solution using O(e=2(log) 1/s + log 1/5) log 1/5) samples.
8 ss-appoxximate
To achieve an overall success probability of 6, only need to sample from non-cheap rings. Thereafter, a high probability bound can be obtained by applying Theorem Alpplicee to all R. The range space induced by rings centered around single point q has constant VC dimension. Hence, Lemma 2 guarantees that a constant size sample will allow us to distinguish cheap rings from non- cheap ones.
Improved Coreset Constructions
Our algorithm is as follows. First, we compute a point g that is reasonably good approximation cost(g) to the optimum In the following, let a = OPT Let A = cost(g) be the average cost of the input points when clustering them to q. We now partition the points into rings, defined as follow:
log 3x
R; = fp e A (5=)² " 2 < lp All < (=)² 22+1
A). Let Ras = =
R4-
For each ring R₁ with i log 22 32 we sample a subset S, of points uniformly at random, where each point is weighted by
[R We weigh q by the number of points in A \ RM- Finally, we set A = Ei>log(2s) (25)30 EpER, ||p al. We claim, for s E Ō(==2) that for the weights defined
Jog )a S, (g) together with the constant is a coreset.
above. U
The analysis for every ring R; E RM is merely application of Theorem For the remaining points, we use the following lemma.
'We described an option in detail for the sublinear algorithm. In the interest of keeping the presentation succinct, we defer to that part of the paper and omit further discussion.

---

Lemma 13. Let RM and R. be defined as above. Then for any point E R we have
[cost(A, c) - (cost( RMM, , + + RMd 11q cll²) S e cost( c)-
5 Experimental Evaluation
While we can prove that the algorithm can compute good solution in constant time for every constant & and 2, even for moderately small (e.g. 1/2) the sampling complexity becomes quite large for even small values of as indeed our lower bound shows is necessarily the case. Our experiments therefore aim at evaluating the performance of the sublinear algorithm on realistic, not necessarily worst case data sets.
As baseline algorithm, we implemented simple version of batched gradient descent. Since all considered objectives are convex, we can expect such an algorithm to find good solution in a rea- sonable time. The sublinear algorithm ran Algorithm| [T before calling the batched gradient descent. The code can be found at htttt::///// / thub. com/Daaaaaiaac http://aaaaaaa---aaaa mean We selected two data sets from the UCI repository Dua & Grafi (2017), both of which are under the Creative Commons li- cense. The first data set is the 3D Road Network data set from Kaul et al. (2013). It consists of elevation information with the attributes longitude, latitude and altitude. The total number of points is 434,874. For this data set, we considered all powers from = = 3 to 7. The second data set is the USCensus data set, consisting the records from 1990 census. The total size of the data set was 2,458,28 samples, each with 68 attributes. For this data set, we considered the powers = = 3, 4,
The results essentially confirmed that the sublinear algorithm succeeded in finding good candidate solution in a fraction of the time as batch gradient descent for essentially all considered problems.
A more extensive discussion can be found in the supplementary material.
Conclusion and Future Work
We gave sublinear algorithms and coresets for any power of means. Our bounds nearly tight for the sublinear algorithms and we conjecture the coreset bound to be optimal, up to polylog factors.
The most immediate open question is whether our results generalize to coresets for k-clustering objectives. seems likely that coresets of size Okk2/e2) are achievable using our techniques. Im- proving either this bound the -kk=-2-2 from Cohen-Addad et al. (2021) is arguable the most important open problem coresets.
In terms of sublinear algorithms, there is still sub-optimal dependency the by factor e01()) Obtaining tight bounds would be interesting. Finally, it is also an interesting open question whether sublinear algorithms for lp with p 2 exist. independent can exist, even for the mean or the median. Is it nevertheless possible to obtain a sublinear algorithm that is independent of d?
known that for these spaces, coreset that is
10

---

Acknowledgments and Disclosure of Funding
The work of David Saulpie is [partially] funded by the grant ANR-19-CE448-0016 from the French National Research Agency (ANR).
References
Bachem, O., Lucic, M., Hassani. S. H., and Krause, A. Approximate k-means++ in sublinear time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2016.
Bachem, O., Lucic, M., and Krause, A. Scalable -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, pp. 1119-1127, 2018. doi: 10.1145/ 3219819 URL https://doi. org/ 10. /145/ /tt.///21191999129973939
Badoiu, M. and Clarkson, K. L. Optimal core-sets for balls. Comput. Geom., 40(1): 2008. doi: 10.1016/1 wtt.commeo.2007.000 04.002
URL http:://x..doii / comgeo. 2007.
Becchetti, L., Bury, M., Cohen-Addad, V., Grandoni, F,, and Schwiegelshohn, C. Oblivious di- mension reduction for k-means: beyond subspaces and the johnson-line -indenssndssssss lemma. In Proceedings of the 51 Annual ACM SIGACT Symposium Theory of Computing, STOC, pp- 1039-1050, 2019. URL haLLhttps://ooo /ttp:::://oi.or/11....
Ben-David, S. A framework for statistical clustering with constant time approximation algorithms for K-median and K K-means clustering. Mach. Learn. 66(2-3):243-2577 2007. doi: 10.1007/ s10994-006-0587-3
org/
Blumer, A., Ehrenfeucht, A., Haussler. D., and Warmuth, M. K. Learnability and the vapnik-
chervonenkis dimension. J. ACM, 36(4))929 965, 1989. URL httts://ddoi.org/100 1145/
76359. 76371
Braverman, V., Jiang, S. H., Krauthgamer, R., and Wu, X. Coresets for clustering in excluded- minor graphs and beyond. In Marx, D. (ed.), Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pp. 2679- 2696. SIAM, 2021. doi: 1. 1.9781611976465
URL httth::t///o org 10. 1137/
Ceccarello, M., Pietracaprina, A., and Pucci, G. Fast coreset-based diversity maximization under matroid constraints. In Proceedings the Eleventh ACM International Conference on Web Search and Data Mining, pp. 81-89, 2018.
Chen, K. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923-947, 2009.
Clarkson, K. L., Hazan, E., and Woodruff, D. Sublinear optimization for machine learning. J. ACM, 59(5):23:1 2012. doi: 10.114522771656.22716688 URL httpp://///oooorro/ /ttp///oooooo//.....
1145/2371656. 2371658 23711665
Cohen, M. B., Lee, T., Miller, G. L., Pachocki, J., and Sidford, A. Geometric median in nearly lin- ear time. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2016.
Cohen-Addad, V. and Li, On the fixed- parameeeee tractability of capacitated clustering. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pp. 41:1 11:14,, 2019. doi: 10.4200LLPKss.CCALP2200900 URL FRLphttps: 7/doi org/10../0000 111.0.23//LIIicc. ICALP 2019. 41
Cohen-Addad, V. and Schwiegelshohn, C. 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, pp. 49-60, 2017. doi: 10.1 T0L100/FOCS.000...0 URL. httpp::
//doi. org/10 10. F1C9/FOCC.... 2017.

---

Cohen-Addad V., Saulpie, D., and Schwiegelshohn, C. A new coreset framework for clustering. In Khuller. S. and Williams, V. V. (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. ACM, 2021.
Czumaj. A. and Sohler, C. iiblinear-time approximation algorithms for clustering via random sampling. Random Structures & Algorithms, 30(1-2):226-56, 2007.
Ding, H. A sub-linear time framework for geometric optimization with outliers in high dimensions.
In 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy ( (iiiiul Conference), pp. 38:1-38:21, 2020. doi: 1044200LIPics.BAA.2000)
URL https:
//doi.org 10. 4230/LIPIcs ESA. 2020.38
Ding, H. Stability yields sublinear time algorithms for geometric optimization in machine learning. In Mutzel, P., Pagh, R., and Herman, G. (eds.), 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPlcs, pp. 38:1-38:15 Schloss Dagstuhl LeibnizzZZetrrum für Informatik, 2021.
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL http::/arrchive.iess uci. edu/ml
Elkin, M., Filtser, A., and Neiman, O. Terminal embeddings. Theor. Comput. Sci., 697:1-36, 2017. URL httpttt//dd/iiorrge 1016/ tcs 2017 (0.06660121 021
doi: 10. fo.10166..cs..017.000
Feldman, D. Core-sets: An updated survey, Wiley Interdiscip. Rev. Data Min. Knowl. Discov, 10 (I), 2020, doi: 10.1002/widm. 1335. URL https::tt/ii.oooooo org/ 10. 10.000//iimm 1335
Feldman, D. and Langherg, M. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pp. 569-578, 2011.
Feldman, D., Schmidt, M., and Sohler, C. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM J. Comput., 49(3):601-657, 2020, doi: 10.1137/ 18M1209854. htLp:tss: http:/iiioorggg///// 2tg/10.10 1..0.11331 1137/ 11137/88812198888
Feng, Z., Kacham, P., and Woodruff, D. Dimensionality reduction for the -fi-ta--distnces metric. In Meila, M. and Zhang. Т. (eds.), 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, pp. 3220 3229. PMLR, 2021. URL http::/ mlr. .rres/ v139/feng21a.b2 html
Fichtenberger, H., Gillé, M., Schmidt, M., Schwiegelshohn, C., and Sohler, C. BICO: BIRCH meets coresets for k-means clustering. In Algorithms ESA 2013 2/ Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pp. 481-492 2013.
Har-Peled, S. and Kushal, A. Smaller coresets for k-median and k-means clustering. Discrete & Computational Geometry, 37(1)33-19 2007.
Har-Peled. S. and Mazumdar, S. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium Theory of Computing, Chicago, II, USA, June 13-16, 2004, pp. 291-300, 2004.
Huang, L. and Vishnoi, N. K. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, 2020. doi: 10. (0.1145/55 00.1145/3357711.3338299 URL https:///oi. .eriiiorg//o 10.
1145/3357713 3384296
Huang, I., Jiang, S. H., and Vishnoi, N. K. Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- fion Processing Systems 2019, NeurIPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pp- 7587-7598, 2019.
Huggins, J., Campbell, T., and Broderick, T. Coresets for scalable bayesian logistic regression. In Advances in Neural Information Processing Systems, pp. 4080-4088, 2016.
12

---

Inaba, M., Katoh, N., and Imai, H. Applications of weighted voronoi diagrams and randomization to variance- based k-clustering (extended abstract). In Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, USA, June 6-8, 1994, pp. 332-339, 1994. 11111/1777744... doi: 10.1145/174244118042 URI.https://doo org/ 10. 11..114/111 177424. 178042
Indyk, P., Mahabadi, S., Mahdian, M., and Mirrokni, V. S. Composable core-sets for diversity and coverage maximization. In Hull, R. and Grohe, M. (cds.), Proceedings of the 33rd ACM HGGMOD-SIGACT-SSIGAN
Symposium on Principles of Database Systems, PODS' 14, Snowbird, UT, USA, June 22-27, 2014, pp. 100-108. ACM, 2014. doi: 10.1 4444//559438.255555666 URL https://doi. org/10. 10. 1145 1145/2594538.554556
Indyk, P., Mahabadi, S., Gharan, S. O., and Rezaei, A. Composable core-sets for determinant maximization problems via spectral spanners. Chawla, S. (ed.), Proceedings the the 2020 ACM- SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, Jamuary 5-8, URL https://doi.
2020, pp. 1675 1694. SIAM, 2020. doi: org 10. 1137 9781677811111 11711991999999991 103
Kaul, M., Yang, B., and Jensen, C. S. Building accurate 3d spatial networks to enable next generation intelligent transportation systems. In 2013 IEEE 14th International Conference Mobile Data Management, Milan, Italy, June 3-6, 2013 Volume 1, pp. 137-146, 2013. doi: 10.1109/MDM. 2013.24. L petttps://di... wttp://do...oooo www.//...///.......
Langberg, M. and Schulman, L. J. Universal e-approximators for integrals. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp. 598-607, 2010.
Lee, J. C. and Valiant, Optimal sub- gub-gaussian mean estimation in To appear at FOCS'21, 2021.
Li, Y., Long, P. M., and Srinivasan, A. Improved bounds on the sample complexity of learning.
J. Comput. Syst. Sci., 62(3):516 527, 2001. doi: 10. 10.10066/ess..0000. 2000. 1741. URL https://doi.
2000. 1741
Lugosi, G. and Mendelson, S. Mean estimation and regression under heavy-tailed distributions:
A survey, Found. Comput. Math., 1955):145--1190 2019. doi: 10. 00.10077/11200--01--000227
URL https://dol: ot.
1007 000000000000000000000----------0
Maalouf, A., Jubran, I., and Feldman, D. Fast and accurate least-mean solvers. In Advances in Neural Information Processing Systems, pp. 8307-8318, 2019.
Mahabadi, S., Makarychev, K., Makarychev, Y., and Razenshteyn, I. P. Nonlinear dimension duction via outer bi-lipschitz extensions. In Proceedings of the 50th Annual ACM SIGACT Sym- posium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp- 1088-1101, 2018.
Makarychev, K., Makarychev, Y., and Razenshteyn, I. P. Performance of johnson-lindenttraue -indenstrntnssss transform for k- k-means and k-medians clustering. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1027-1038, 2019.
Meyerson, A., O'callaghan, L., and Plotkin, S. A k-median algorithm with running time independent of data size. Machine Learning, 56(1):61 2004.
Molina, A., Munteanu, A., and Kersting, K. Core dependency networks. In Mellraith, S. A. and Weinberger, K. Q. (eds.), Proceedings of the Thirty-Second AAAI Conference on Artifi- cial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI- 18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 3820-3821 AAAI Press, 2018. URL attps://vee aaai org/ ocs/ htt///iddexxe/eee
Ttt.AA///AAA1///ppr///aaaa /16477
Munteanu, A. and Schwiegelshohn, C. Coresets-methods and history: theoreticians design pattern for approximation and streaming algorithms. Künstliche Iniell., 32(1):37-53, 2018.
13

---

Munteanu, A., Schwiegelshohn, C., Sohler, C., and Woodruff, D. P. On coresets for logistic regression. In Bengio. S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 6562-6571, 2018. https:::: http:///oooeeee..ce//o/ wewpinngg.nneuuipe nww.eeuriip.... cc/ cc/paper/ 2201BInash/B3bf6666866666
Abstract .ttml
Narayanan, and Nelson, J. Optimal terminal dimensionality reduction euclidean space. In Charikar, M. and Cohen, E. (eds.). Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 1064-1069. ACM, 2019. doi: 10.1145/331327633316300
UtL.ttts:://eee org 10 /145/ 3316307
Nelson, J. Chaining introduction with some computer scienceeeeeeeeeeeieeeeeeeeeee sciencce Bull. EATCS, 120, 2016.
URL http::/eetces hatgg//btts//iie /eweaasssinnee.tteeeeee pbtp:/beatcc//arricc/////i/o///s
Rudra, A. and Wootters, M. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Shmoys, B. (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 3/- June 03, 2014, pp. 773-773. ACM, 2014. doi: 10. 10.11457299177922999777 URL wttph:tp:/tt/ //tp:::://dd.../ org 10. 1145 2591796. 2591797
Schmidt, M., Schwiegelshohn, C., and Sohler, C. Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithmss 17th International Workshop, WAQA 2019, Munich, Germany, September 12-13. 2019, Revised Selected Papers, pp. 16. URL htwp::ttp////to //doi.//doiio org/ 10. 1007 9988 3- 0108-----0--------111111
2019. doi: 10.
Sohler, C. and Woodruff, D. P. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pp. 802-813, 2018. doi: 10.1109/FOCSS
URL
wttg///..11//FOOOOOOO https: owg/ 1109/ 2018 00081
14


Reviews:
[{"review_id": "x3J5RZz7U4", "reviewer": "Reviewer_isuV", "summary": "Given n points in R^d, the goal is to compute a center x in R^d that minimizes the sum (dist(p,x))^z of distance to the power of z over every input point p. The main (sub-linear time) algorithm uniformly sample ~1/eps^z points and use smart processing to obtain a (1+epsilon) approximation to the desired center x. Nice application is differential privacy. Lower bounds are also provided. More generally, the authors suggest such coreset that approximates every query center.\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I already reviewed a previous version of this paper. Corrections and references were added. \nThere are still some concerns.\n\nStrengths:\n- Fundamental problem in machine learning and optimization\n- Clear writing\n- Open Python code which is not so common these days and will be appreciated by the non-theory guys\n- Interesting non-trivial algorithm\n- Novel approach with potential many applications.\n\nWeaknesses:\nI am mainly concern with relation to existing work and novelty.\nFor example, it is claimed that their coreset of size ~O(1/eps^2) improves the coreset of ~O(d/eps^2) by Feldman and Langberg  [STOC'11]. However, [STOC'11] also suggested how to remove the d using the fact that the optimal center can be approximated by ~1/epsilon points, which implies a VC-dimension that is independent of d.\nAlso, when the authors write O(1/eps^2) instead of 2^{100z}*O(1/eps^2) that should mention that z is fixed.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "OK", "review_text": "", "extra_scores": {"ethical_concerns": "OK", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 (including last times)"}, "extra_text": {}}, {"review_id": "cyxIbbhcnCl", "reviewer": "Reviewer_mXmR", "summary": "The paper handles the following problem: Given a set of $n$ points in $R^d$, the goal is to compute in sublinear time an approximation for the point that minimizes the sum of euclidian distances to the power of $z$ over the input points.\n\nAlso, it suggests a coreset for this problem.\n", "questions": "", "limitations": "", "rating": 6, "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": "The paper provider a solid theoretical contribution. It suggests a sublinear time algorithm for approximating the point that minimizes the sum of euclidian distances to the power of $z$ over a given input set of points.\nThe required number of points (samples) in order to obtain with probability at least $1-\\delta$ a $1+\\varepsilon$ approximation to the optimal solution is $O(\\varepsilon^{-z-3}log^2(1/\\delta)polylog(\\varepsilon^{-1}))$ (generalization over prior works)\n\nThe paper also shows that we can compute a coreset for such a problem, where the size of the coreset is $O(\\varepsilon^{-2}2^{O(z)})$.\n\nFinally, they show that the exponential dependency in $z$ is necessary for computing an approximation.\n\nTo do so, they used and improve the technique introduced by Chen [7] (i.e.,  given a fine initial guess, partition the points into rings that grow exponentially according to their costs) by showing that it is sufficient to only consider O(log \\varepsilon^ {−1}) rings.\n\nThey suggest an improved analysis of sampling from rings. The state-of-the-art analysis by Feldman and Langberg [15] reduces the problem of computing a coreset to sampling in a (weighted) range space of bounded VC dimension.  They improve over the previous analyses via the chaining technique.\n\nI liked the paper, it has a solid theory and novel ideas, it's written well. \nHowever, the experimental results section is very weak see Limitations section. \n\nNote: I couldn't check the proofs due to time constraints and since they are long.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n1. Experimental results:\n   a. The paper should have experimental results in its main body. \n\n   b. Why there are no graphs at all? the reader is interested in understanding the phenomena not just looking at the numbers.\n  \n c.  You should compare yourself to other methods, e.g.,  \n         --- to uniform sampling in all cases, \n         --- Feldman and Langberg in the relevant cases, \n         --- and many other results in the cases of z=2 (e.g., median of means).\n  \n d. Also, when comparing your results to other methods (e.g., uniform sampling), the x-axis of the graph can be the time took to compute the approximation (including the time took to compute the small subset) not the size of the coreset. \n   \n e. More discussion needed, e.g., when your coreset performs better in practice (at what z values), when it is better than uniform sampling and why? \n\n2. Can you explain why it is interesting to solve the problem when z is not 2,1 or inf?\n\n3. No conclusion or future work was provided.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "ItzY2rrh1Zp", "reviewer": "Reviewer_FUAC", "summary": "The paper gives sub-linear time algorithms for approximating ($1+\\epsilon$ approximation) the centroid of a set of points in $d$-dimensional real space, under a distance function which is a power $z$ of the Euclidean distance. So, in particular, for $z=1$ the problem is estimating the Fermat-Weber point, and for $z=2$ the problem is estimating the mean. The algorithms use a random sample of the point set. Moreover, the paper also gives a probabilistic construction of a coreset of size independent of the dimension $d$ that estimates well the cost of any candidate center. The algorithms employ an interesting modification of an algorithm by Chen, as well as dimension reduction and a probabilistic analysis using chaining.", "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": "The sub-linear time algorithms for $z=1$ and for $z=2$ in fact do not improve upon previous work (the authors note that). In fact, for $z=2$ a rather simple probabilistic analysis would show that sampling (with replacement) uniformly at random $O(1/\\epsilon^2)$ points yields a good estimate of the mean. Thus, the main contribution here is for $z > 2$. It would be useful to point out applications of larger $z$. That there exists a coreset of size $\\tilde{O}(\\exp(z)/\\epsilon^2 )$ I believe was not known (but independence of the dimension was known). So may take is that this is the main contribution of the paper, improving the coreset size from $\\tilde{O}(\\exp(z)/\\epsilon^4)$ to $\\tilde{O}(\\exp(z)/\\epsilon^2)$. This contribution is substantial and thus the paper is interesting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "EfzppGb5X0T", "reviewer": "Reviewer_av2R", "summary": "The paper studies sublinear algorithms for Power means i.e., given a set of $n$ points $a_1,\\ldots, a_n$, compute a center $c$ that minimizes (upto $1+\\varepsilon$) factor the objective $\\sum_{i = 1}^n d(a_i, c)^z$ for any $z \\ge 1$. The authors show that $\\varepsilon^{-z-3}$ uniformly random samples is enough to achieve a $1+\\varepsilon$ approximation. They also construct coresets of size $\\varepsilon^{-2}$.", "questions": "", "limitations": "", "rating": 7, "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": "They proceed to prove that the uniform sampling works as follows:\n- $q$ be an approximate solution\n- Divide the $n$ points into rings based on their distance from $q$\n- They argue that if the rings are very sparse, then they can be ignored as they won't contribute to the cost much\n- For rings that are dense enough, uniform sampling for that ring approximates the cost well.\n- To prove that uniform sampling from a ring works to approximate cost well, they consider a net over the vector of distances from a point $c$ to the set of points in $R$. They only require that the net-vectors approximate the distances of points $p$ in the ring such that $d(p, c)$ is comparable to $d(p, q)$. They then obtain a bound on the size of the net and then argue using a chaining argument that uniform sampling from the ring approximates cost of the ring with respect to any potential center $c$.\n\nStrengths:\n- Important problem for which algorithms weren't known for general $z$\n- Obtain sizes that are close to optimal using a simple and nice lowerbound\n\nWeaknesses:\n- Paper is very poorly written which makes it harder to understand what is actually going on. For example, I don't understand what is happening in the expectation in line 191. The authors take expectation of supremum over all the centres $c$, but then use $v$ in the expectation and then say for every $v$ in the net. Do you have to prove the bound for every $v$ in the net or only for $v$  in the net that is close to distance vector of center $c$ or is it a typo?\n- There definitely is novelty in their algorithms and proof techniques but the paper in its current form is very hard to be reviewed and check for bugs which makes me recommend not accepting the paper.\n\nSuggestions:\n- I believe once the paper is written well and easy to comprehend, the results are definitely strong enough to be accepted at a top place. I'd suggest you rewrite the Techniques section to give a much better overview of the algorithms and better explain how various lemmas help in proving the theorems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a strong paper making contributions to sublinear time algorithms and coresets for power means clustering. All reviewers agree it should be accepted, and I think it is a candidate spotlight paper.
Decision: Accept (Spotlight)