Coresets for Clustering with Missing Values
Authors: Vladimir Braverman
Shaofeng H.-C. Jiang
Robert Krauthgamer
Xuan Wu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: coreset
clustering
k-means
missing values

Abstract: We provide the first coreset for clustering points in $\mathbb{R}^d$ that have multiple missing values (coordinates). Previous coreset constructions only allow one missing coordinate. The challenge in this setting is that objective functions, like \kMeans, are evaluated only on the set of available (non-missing) coordinates, which varies across points. Recall that an $\epsilon$-coreset of a large dataset is a small proxy, usually a reweighted subset of points, that $(1+\epsilon)$-approximates the clustering objective for every possible center set.

Our coresets for $k$-Means and $k$-Median clustering have size $(jk)^{O(\min(j,k))} (\epsilon^{-1} d \log n)^2$, where $n$ is the number of data points, $d$ is the dimension and $j$ is the maximum number of missing coordinates for each data point. We further design an algorithm to construct these coresets in near-linear time, and consequently improve a recent quadratic-time PTAS for $k$-Means with missing values [Eiben et al., SODA 2021] to near-linear time.

We validate our coreset construction, which is based on importance sampling and is easy to implement, on various real data sets. Our coreset exhibits a flexible tradeoff between coreset size and accuracy, and generally outperforms the uniform-sampling baseline. Furthermore, it significantly speeds up a Lloyd's-style heuristic for $k$-Means with missing values.

Coresets for Clustering with Missing Values
Vladimir Braverman Johns Hopkins University vovaccs. j.u. edu
Shaofeng H.-C. Jiang Peking University
shaofeng.jianggplle jiang@pku. edu.
Robert Krauthgamer
Xuan Wu
Weizmann Institute of Science
Johns Hopkins University wu34127900gmail com
robert. krauthhgamrrOeeiznaaaaae ac
Abstract
We provide the first coreset for clustering points in R' that have multiple missing values (coordinates). Previous coreset constructions only allow one missing co- ordinate. The challenge in this setting is that objective functions, like k-MFANS, evaluated only on the set of available (non-missing) coordinates, which varies across points. Recall that an e-coreset of a large dataset is small proxy, usually a reweighted subset of points, that (1 + elaapproxssstes the clustering objective for every possible center set.
Our coresets for k-MEANS and k-MEDIAN clustering have size (jk) (e n)?, where is the number of data points, d is the dimension and j the maximum number of missing coordinates for each data point. We further design an algorithm to construct these coresets in near-linear time, and consequently improve recent quadratic-tims PTAS for K-MEANS with missing values [Eiben et al., SODA 2021] to near-linear time.
We validate our coreset construction, which is based on importance sampling and is easy to implement, on various real data sets. Our coreset exhibits flexible tradeoff' between coreset size and accuracy, and generally outperforms the uniform- sampling baseline. Furthermore, it significantly speeds up a Lloyd's-style heuristic for K-MEANS with missing values.
Introduction
We consider coresets and approximation algorithms for k-clustering problems, particularly k- ! and more generally (k, CLLUSTERIG (see Definition 2.1), for points in Ed with missing values (coordinates). The presence of missing values in data sets is a common phenomenon, and dealing with it is fundamental challenge in data science. While data imputation is very popular method for handling missing values, often requires prior knowledge which might not be available, or statistical assumptions on the missing values that might be difficult verify [A1101, 19]. In contrast, our worst-case approach does not requires any prior knowledge. Specifically, in our context of clustering, the distance dist(ax, c) between clustering center point and data point & is evaluated only on the available (i.e., non-missing) coordinates. Similar models that aim to minimize clustering costs using only the available coordinates have been proposed in previous work [HB01, Wag04, CCB16. WLH 19], and some other relevant works were discussed in a survey [HC10].
Clustering under this distance function, which is evaluated only the available coordinates, is formidable computational challenge, because distances do not satisfy the triangle inequality, and
usual &- MEANS problem (without missing coordinates), the input a data set X c Rdd and the goal is to find a center set C c Rd |C| = k that minimizes the sum of squared distances from every E X to C.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

therefore many classical and effective clustering algorithms,, such as k-MEANS++ [AV07], cannot be readily applied or even be defined properly. Despite the algorithmic interest in clustering with missing values, the problem is still not well understood and only a few results are known. In a pioneering work, Gao, Langherg and Schulman [GI.S08] initiated the algorithmic study of the k-CENTER problem with missing values. They took a geometric perspective and interpreted the k-CENTER with missing values problem as an affine-subspace clustering problem, and followup work [GLSI0, LS13] has subsequently improved and generalized their algorithm. Only very recently, approximation algorithms for objectives other than k- CENTER, particularly k-MEANS, were obtained for the limited case of at most missing coordinate in each input point [MF19] or for constant number of missing coordinates [EFG* 21].
We focus on designing coresets for clustering with missing values. Roughly speaking, an e-coreset is a small proxy of the data set, such that the clustering objective is preserved within (1 + e) factor for all center sets (see Definition 2.2 for formal definition). Efficient constructions of small c-coresets usually lead to efficient approximations schemes, since the input size reduced to that of the coreset, see c.g. [HJLWI8 18. FRS19, MF19]. Moreover, apart from speeding up approximation algorithms in the classical setting (offline computation), coresets can also be applied to design streaming (HM04, FSO5, BFL + 17], distributed [BELI3, RPS15, BLKI8), and dynamic algorithms [Cha09, HK20], which are effective methods/models for dealing with big data, and recently coresets were used even in neural networks [MOB* + 20].
1.1 Our Results
Our main result, stated in Theorem 1.1, is a near-linear time construction of coresets for k-MEANS with missing values. Here, an e-coreset for k-MEANS for data set X Idd with missing coordinates is weighted subset S C X with weights : S - R,, such that
Coresets.
VC C RRI k,
Σ w(x) dist (z, C) c1 F
Σ x
tistt(z, C),
where dist(r,, c) == :iVV=V-Va
Eisee di not missing (xe )2 and dist(rr, C) := minnge dist(a, c); note that the center set C does not contain missing values. More generally, our coreset also works for (k;, =)- CLUSTERING, which includes k-MEDIAN (see Definition 2.1 and Definition 2.2). Throughout, we use Ō(f) to denote Off poly log.).
Theorem 1.1 (Informal version of Theorem 3.1). There is an algorithm that, given 0 < E < 1/2, integers d, j. k 2 1, and set X C Cdd of points each having at most j missing values, it constructs with constant probability an e-coreset for k-MEANS on X of size m (jk) (i.)))(( d n)g and runs in time Ô ((kk)(mmi)( nd + m).
Our coreset size is only low-degree polynomial of d, 6 and log n, and can thus deal with moderately- high dimension or large data set. The dependence on (number of clusters) and j (maximum number of missing values per point) is also low-degree polynomial as long as at least one of k and j is small. Actually, we justify in Theorem 1.2 that this exponential dependence in min k}} cannot be further improved, as long as the coreset size is in a similar parameter regime, i.e., the coreset size is of the form f k) poly(c looo n)) We provide the proof of Theorem 1.2 in the full version.
Theorem 1.2. Consider the k-MEANS with missing values problem in R& where each point can have most j missing coordinates. Assume there an algorithm that constructs an e-coresef of size f(ik) poly(e- ddog n),, then f(j,k) k) can not be as small as 20(min(j.k)).
Furthermore, the space complexity of our construction algorithm is near-lineat, and since our coreset is clearly mergeable, it is possible to apply the merge- aange-aad-reduce method [HM04] to convert our construction into a streaming algorithm of space poly logn. Prior to our result, the only known coreset construction for clustering with missing values is for the special case j = 1 [MF19] and has size kO(k) (e 2d log n.). Since our coreset has size poly -t -=dlog when j = 1, it improves the dependence on l over that of [MF19] by a factor of (((().
"In fact, [MF19] considers slightly more general setting where the input are arbitrary lines that are not necessarily paralll..
2

---

Near-linear time PTAS for k-MEANS with missing values. Very recently, PTAS for k- MEANS with missing values, was obtained by Eiben, Fomin, Golovach, Lochet, Panolan, and Simonov 21]. Its time bound is quadratic, namely O(2 n²d), and since our core- set can be constructed in near-linear time, we can speedup this PTAS to near-linear time by first constructing our coreset and then running this PTAS on the coreset.
Corollary 1.3 (Near-linear time PTAS for K-MEANS with missing values). There an algorithm that, given 0 < e <<< 1/2, integers d, j, k 2 1, and a set X C CR points each having at most missing values, it finds with constant probability (1 + apppppooimmation for k- 3-MEANS on X, and nd + spoly(sk/e).d00))
runs in time ò ((jk))
Experiments. We implement algorithm and validate its performance on various real and synthetic data sets in Section 4. Our coreset exhibits flexible tradeoff's between coreset size and accuracy, and generally outperforms a uniform-sampling baseline and baseline that is based on imputation, in both error rate and stability, especially when the coreset size is relatively small. In particular, on each data set, coreset of moderate size 2000 (which is 0.5%-5% of the data sets) achieves low empirical error (5%-20%). We further demonstrate an application and use our coresets to accelerate a dloyd''sstyle heuristic adapted the missing-valuee setting. The experiments suggest that running the heuristic on top of our coresets gives equally good solutions (error < 1% relative to running on the original data set) but is much faster (speedup > 5x).
1.2 Technical Overview
Our coreset construction is based on the importance sampling framework introduced by Feldman and Langberg [FL11] and subsequently improved and generalized by [FSS20, BJKW21]. In the framework, one first computes importance score d for every data point E X, and then draws independent samples with probabilities proportional to these scores. When no values are missing, the importance scores can be computed easily, even for general metric spaces [VX12b, FSS20, BJKW21]. However, a significant challenge with missing values is that distances do not satisfy the triangle inequality, hence importance scores cannot be easily computed.
We overcome this hurdle using a method introduced by Varadarajan and Xiao [VX12a] for projective clustering (where the triangle inequality similarly does not hold). They reduce the importance- score computation to the construction of a coreset for k-CENTER objective; this method is quite different from earlier approaches, e.g. [FL11, VX12b, FSS20, BJKW21J, and yields coreset for k-MEANS whose size depends linearly on log n and of course on the size of the k- R--CENTER coreset. (Mathematically, this arises from the sum of all importance scores.) We make use of this reduction, and thus focus on constructing (efficiently) a small coreset for k- k-CENTER with missing values.
An immediate difficulty is how to deal with the missing values. We show that it is possible to find a collection of subsets of coordinates I (so each / E I is a subset of [d), such that if we construct k-CENTER coresets Sy the data set "restricted" to each I E I. then the union of these S 's is a k-CENTER coreset for the original data set with missing values. Crucially, we ensure that each "restricted"" data set does not contain any missing value, so that it is possible to use classical coreset construction for k-- CENTER. Finally, we show in a technical lemma how to find a collection as necessary of size [Z] S (mia))))
Since a "restricted" data set does not contain any missing values, we can use a classical k- CENTEER coresct construction, and a standard construction has size O(ke - [AP02], which is known to be tight. We bypass this ed limitation by observing that actually ((1)- coreset for k- CENTER suffices, even though the final coreset error is e. We observe that an (1))-coreset can be constructed using a variant of Gonzalez's ' algorithm [Gon85].
To implement Gonzalez's s algorithm, a key step is to find the furthest neighbor of given subset of at most O(k), points, and a naive implementation of this runs in linear time, which overall yields a quadratic-time coreset construction, because the aforementioned reduction of [VX12a] actually requires (n/kk) successive runs of Gonzalez's ' algorithm. To resolve this issue, we propose a fully-dynamic implementation of Gonzalez's 's algorithm so that a furthest-point query is answered in time poly log n), and the point-set is updated between successive runs instead of constructed from scratch. Our dynamic algorithm is based on a anddo--rojeetto method that was proposed for furthest-poins point queries in the streaming setting [Ind03]. Specifically, project the (restricted) data
3

---

set onto several random directions, and on each projected (one (one-dimensiona) data set we apply data structure for intervals.
1.3 Additional Related Work
Coresets for k-MEANS and k-MEDIAN clustering have been studied extensively for two decades, and we only list few notable results. The first strong coresets for Euclidean k-MEANS and k- MEDIAN were given in [HM04]. In the last decade, most work on coresets for clustering follows the importance sampling framework initiated in [LSI0, FL11]. 1]. In Euclidean space, recent work showed that coresets for k-MEANS and k MEDIAN clustering can have size that is independent the Euclidean dimension [FSS20, SWI8, HV20J. Beyond Euclidean space, coresets of size independent of the data-set size were constructed also for many important metric spaces [HJLW18, BJK 12,, CASS21J. A more comprehensive overview can be found in recent surveys [Phil 17, Fel20].
Recently, attention was given also non non-tradien traditional settings of coresets for clustering, including coresets for Gaussian mixture models (GMM) [LFKF17, FK 11]; simultaneous coresets for large family of cost functions that include both MEMIDDA and k CENTER [BJKW 19]; and coresets for clustering under fairness constraints [HJV19]. Also considered were settings that capture uncertainty, for example when each point is only known to lie in a line (i.c., clustering lines) [MF19], and when each point comes from finite set (i.e., clustering point sets) [JTMF20].
Preliminaries
represent a data point as a vector in (R U (2)) and a coordinate takes "?" and only if missing. Let I2 be a shorthand for (IR (?))d. Throughout, we consider a data set X Rd. The distance is evaluated only on the coordinates that are present in both x, i.c.,
Yx, y TRG,
dist(r,
Σ co
(x: --)3
For Rt denote the set of coordinates that are not missing by I == {i: #?}. For integer For two points p. g Rd and index set Lp O Lg. define the 1, let [m] : {....., m.. I-induced distance be disty q) == V kez (Pi 9:)² A point x E R3 is called a j-point if it has at most missing coordinates, i.e., [T 2 j-
We consider general k-clustering problem called (k, cllusterrn,, which asks minimize the following objective function. This objective function (and problem) is also called k-MEDIAN when 1 and k-MEANS when z
Definition 2.1 ((:, CLUUSTRRR))) For data set X C Rd and a center set C' C . containing (usual) points, let
cost (x,t)((x) Σ dist (2, C).
TEX
Definition 2.2 (c- (e-Coreset for 2k: -LUSSTEERR)))) For data set X Rd. say weighted set S X with weight function w : S R. is an e-coreset for (k, CLUSTERING, if
VC c Rd ...1I |C|
w(x) dist (x, C) (1 cost, (X,
FES
3 Coresets
Theorem 3.1. There is algorithm that, given input data set X C. Rd of size |X| consisting of j- j-points and parameters k and < E < 1/2, constructs with constant probability
an e-coreset of size m Ō Ô pK--s-r (dlog m) 42) for (k, -I..SSSSTRI of X, and
(j+b)+*k41
runs in time Ô (j+R)i1R11 jokt
nd + m

---

Theorem 3.1 is the main theorem of this paper, and we only present sketch of the proof in this section due to the space limitation. Please see the full version for a more detailed and self-contained proof, as well complete description of our algorithm. We remark that (+RR)² IN which is used in the statement of Theorem 1.1.
P S (jk))(min((.))
As mentioned in Section 1, we use importance sampling method which is a well-known technique for constructing coresets [FL11, FSS20J. A key step is to compute for every data point E X an importance score ON 2 0 that estimates its maximum relative contribution to any solution. The computation of } is standard in metric spaces, see e.g. [FSS20, BJKW2IJ, but this is not applicable for us because distances with missing values do not satisfy the triangle inequality, Hence, we employ an alternative approach proposed by Varadarajan and Xiao IVX12a, Lemma 3.1], which reduces the computation of (az) to finding coresets for k-CENTER. This coreset concept, adapted to setting, is defined follows.
Definition 3.1. An a-coreset for ke-CENTE of data set X C Ry is a subset Y C such that
AC C R
R |||| k,
maxdist C) I a max dist(y. C). =EX
NEY
We focus on an efficient construction of an Ö(1) -coreset for k- k-CENTER. The main concern is that the reduction in [VX12a, Lemma 3.1] requires constructing k-CENTER coreset for multiple data sets. Fortunately, these data sets are related - each data set is a subset of the previous one and thus to execute the reduction in near-linear time, we need k-CENTER coreset construction that supports efficient point deletions. Such a dynamic coreset for k-CENTER with missing values is our main technical contribution. We stated next, and outline its proof in Section 3.1.
Lemma 3.2. There is a randomized dynamic algorithm with the following guarantees. The input is dynamic set X Ie of j-points, such that X undergoes q adaptive updates (point insertions and deletions) and the points ever added are fixed in advance (non- nion-adaptively) The algorithm
maintains in time Ô (j+k)1t811
Hah (j + k log () + k22 log 9) per update, a subset Y S X size
(U+k)++R41 jōkt-1
-logd) such that with constant probability, Y is an Olk/dlog 9) coreset for k-CENTER on X after every update.
3.1 Proof of Lemma 3.2: Dynamic Ó(1)-Coresets for k--Center Clustering
As mentioned, the high level idea is identify collection I of subsets of coordinates (so each T I satisfies 1 C [d), construct for each 1, E I an a-coreset Y; (for determined later) for k- d-CENTER on the data set X with coordinates restricted on 1, (as defined below), and then their union U, Y; would be the overall a d-coreset for k-- h-CEETER on X.
Definition 3.2. For a point p E R and subset I C Lp. define P/r E R in the obvious way, by selecting the coordinates (px) {pr) Define the T-restricted data set to be X y == {p)r p E X, Tp)- Since each vector in X1r arises from a specific vector in X, a subset Y C X1r corresponds specific subset of X, and we shall denote this subset by Y-1
We observe that X1z C ! namely, has no missing values (because of the condition / C Ip). Thus, the metric space on the restricted data is an ordinary metric space that satisfies the triangle inequality, and so our goal is reduced to constructing k-CENTER coresets for this ordinary setting. However, another key step is identify small collection I such that the union of the coresets restricted on Z yields a coreset. To this end, we consider the so-called (j, k, d))family of coordinates as in Definition 3.3. We show in Lemma 3.3 that such a family guarantees the correctness of the coreset, and in Lemma 3.4 that small family exists and moreover can be constructed efficiently.
Definition 3.3. A collection of sets I C 2/ is called (j. kt, d)-family if for every two disjoint subsets K C [d] = j. K| = k, the family includes I E I that misses J and contains K, i.c. InJ = and I.
Lemma 3.3. Suppose I is a (j, family Let X C Rd be a set of j-points, and for every I E I. let Y, be an a-coreset for k- CENTER X Then UsezY, is an av d-coreset for k-Center on X.
5

---

Proof. It suffices to show that for any center set C' = {c' ......'Ip S R with & points and x' E X, if dist(z, (z, 0) 2 for some 2 O, then we can find coreset point E UsezY, such that
dist(y, C) 2 ava
For E [k], let t; E arg maX [ cal, i... f; is the index of coordinate that contributes the most in distance dist(x, ct), so [tt, c,, z va Let be any k-subset such that K S I and
(t1..... } S K. Since I is (j. k fa-flmily and [p 2 d - j. by definition, there exists an / C I such that K _ T _ Ts- We note that
p Cir) = (2, C) min dist, (1r, (x, 2 min dist (x, 2 min iE(K]
Ftz C. Z r
EE
Vd
Since I S la, we know that æ E X11- As Y, is an a-coreset for X11. we know that there exists E y such that
dist(z)1, Cp)
dist(y, C) d C) dist(y) C1))
a
avd
Lemma 3.4 asserts the existence of a small (j. k. d)- fa-mallyy. We remark that this combinatorial structure has been employed in designing fault-tolerant data structures and algorithms (ef. [DK11, DGR21, KP21)), and they obtained similar bounds although their context and language different.
(0- logd). Moreover, there is a
Lemma 3.4. There is a (j, k, d)-family of size [I] =0
jikt
randomized algorithm that constructs such I in time O(d [Z]) with probability at least 1 ZF...
k-CENTER coreset for restricted data set via Gonzalez's algorithm. Finally, the k-CENTER coreset for the restricted data set on each E I is constructed using an approximate version of Gonzalez's s algorithm [Gon85], where we first pick an arbitrary data point as the initial coreset, and in every iteration an Ó(1) ((1)-apprxximate furthest neighbor in the dataset is picked into the coreset, and we do this for & times. We show that the resulting coreset, consisting of A + points, is an ((1)-coreee for k- D-CENTER. The assumption that the input forms metric space is crucial, and this guaranteed since we always run on a restricted data set that satisfies the triangle inequality.
Dynamic implementation of Gonzalez's algorithm. To make this k-CENTER coreset construction dynamic, we adapt the random projection technique to Gonzalez's 's algorithm. We project the (restricted) point set onto several random lines and use one-dimensional data structure to construct k-CENTER coreset for each of these (projected) miedimensional data set. Note that the key step in Gonzalez's s algorithm is finding a furthest neighbor, and we can show that our projection method yields an (lkylog n) approximaaion of the furthest neighbor with high probability.
Lemma 3.5. Let A c Rdd, |A| = n, > and integer k 2 1. Let V be a collection of O log + log ) random vectors, each drawn independently from N00,, La). Then with probability at least 1 8, for every P C A and Q C A, |Q] < k, pf is a furthest point in from Q, and for every e E V we let (p", u) be furthest point in (P, from (Q, v), then
dist(p", ,Q) < Ok:vlogg) max dist(p", (Q)) wE
where we denote (X,u) = (10, v) x X).
For each one- dieedmmmesional line, we use a balanced search tree structure to support the point update and the furthest neighbor query. All operations can be done in O(k log m) time where is the number of currently inserted elements. This combining with the above lemmas implies Lemma 3.2.
4 Experiments
We implement our proposed coreset construction algorithm, and we evaluate its performance on real and synthetic datasets. We focus on k-MEANS with missing values, and we examine the speedup

---

Table 1: Parameters the datasets. the number of data points, d is the dimension, k is the number of clusters, is the maximum number of missing coordinates for each point. n.d.j are given, and & chosen by us.
Data set
d
k
j
Russian housing
30471
3
KDD cup
50000
31
5
30
Vertical farming
400180
Synthetic
200000
3
3
Empirical Enror %
35-
30-
25
5
10
15
20
25
30
35
Size of Farily [T]
Figure The average empirical error of Russian housing data with respect to family size on 10 independent experiments.
for a Aloyyd's-style heuristic. In addition to measuring the absolute performance our coreset, we also compare with a) uniform sampling baseline, which is a naive way to construct coresets, and b) an imputation-beds based baseline where missing values are filled by random values and then standard poportance-sampling coreset construction (cf. [FL11] is algorithms using C++ 11, on a laptop with Intel i5-8350U CPU and 8GB RAM.
top of it. We implement the
Datasets. We run our experiments on three real datasets and one synthetic dataset. Below, we briefly describe how we process and choose the attributes of the dataset, and the parameters of the datasets after processing are summarized in Table
1. Russian housing [Rus17] [ is dataset Russian house market. We pick four main numerical attributes of the houses which are the full area, the live area, the kitchen area and the price, and the price attribute is divided by 10 as it lies in the similar range of other attributes. Three columns regarding area contain missing values, and the price column doesn' 't contain any missing value.
2. KDDCup 2009 [KDD09] is a dataset on customer relationship prediction. We pick 31 numerical attributes that have similar magnitudes. Each column contains missing values.
3. Vertical farming [Sam21] I] is a dataset about cubes which are used for advanced vertical farming. We include all of four numerical attributes of the dataset. Each column contains missing values.
4. Synthetic dataset. We generate a large synthetic dataset to validate our algorithm's 's scalability, Data points are randomly generated so that 97% of them are in square and 3% of them are far away from the square. After that, we delete 25% of attributes at random. We remark that the 3% far away points is to make the dataset less uniform which prevents it from being trivial for clustering.
Implementation notes. In our experiments, we follow a standard practice fixing coreset size in each experiment (cf. [BBH+ 20, JTMF20J). Recall that when computing the importance score, our algorithm chooses family Z subsets of coordinates and work on each restricted data set Xir for 1 (see Section 3) For a fixed size coreset, family size [Z] is parameter that needs to be optimized. In Figure 1, we plot the empirical error (defined in (1), Section 4.1) for the Russian housing dataset with respect to the family size Σ]. Although Lemma 3.4 gives a theoretical upper bound on []] but our experiments suggest that much smaller size [ 20 is optimal in this case.
7

---

Russian Housing
KDDCup 2009
Our Coreset
100
Uniform Sampling
Uniform Sampling Imputation
Empiricll Errar (1)
imputation
Empirical Ernar (8)
80
15-
10-
20-
5-
2000
4000
600D
8000
10000
2000
4000
6000
8000
10000
Coreset
Coreset
(b)
Vertical Farming
Synthetic
Our Coreset
Uniform Sampling
Uniform Sampling
Empincaal Error (96)
50
Imputation
Empincal Error (90)
30-
Imputation
25-
40-
20-
30-
15
20-
10-
5-
10-
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Coreset Size
Coreset Size
(c)
(d)
Figure 2: Accuracy evaluation for the datasets with respect to varing coreset sizes, compared against uniform sampling and imputation baselines.
4.1 Accuracy of Coresets
We evaluate the accuracy versus size tradeoff of our coresets. Since the coreset should preserve the clustering cost for all centers, we evaluate the accuracy by testing the empirical error on selected set of centers C. Namely, for a data set X, a coreset D C X and a collection of center sets C, we define the empirical error of D as
(oost(D,C) - cost(X, (DB(C)))CO(((((C)))) Cost(X,
err
CEC
We use a randomly selected collection of centers C that consists of 100 randomly generated k-subset C' C IR.. Since both the evaluation method and the algorithm has randomness, we run the experiment for T = 10a times with independent random bits and report the average empirical eтror to make it stable. We choose 20 different coreset sizes from 200 to 9700 step size of 500, and report the corresponding average empirical error.
Results. We report the size versus accuracy tradeoff of our coreset for all four datasets in Figure and record the standard deviation in Figure 3. We compare these results against the abovementioned uniform sampling and imputation baseline. As can seen from the figures, the accuracy of our coreset improves when the size increases, and we achieve 5%-20% error using only 2000 coreset points (which within 0.5% 5% of the datasets). This 5%-20% error likely to be enough for practical use, since practical algorithms for M-MEANS are approximation algorithms anyway. Our coresets generally outperform both the uniform sampling and imputation basclines on almost every coreset sample size, and the advantage is more significant when the coreset size is relatively small. Moreover, our coresets have a much lower variance.
4.2 Speedup of I.lod''ssstyl Heuristic
Coresets often help to speed up existing approximation algorithms. Before our work, the only algorithm for k- 4-MEANS with provable guarantees for multiple missing values was [FFG+21]. Un- fortunately, [EFG+2] 22] is not practical even when combined with coresets, since it contains several
8

---

Russian Housing
KDDCup 2009
Coreset
0.35
Coreset
Uniform Sampling
Uniform Sampling
Imputation
0.30-
Imputation
3-
Su--Deviation
0.25
0.20
0.15
0.10
0.05-
0.00
2000
4000
600D
8000
10000
2000
4000
6000
8000
10000
Coreset
Coreset
(b)
Vertical Farming
Synthotic
2.0-
Coreset
0.25
Carsset
Uniform Sampling Imputation
Uniform Sampling
Imputation
Std-Devtation
1.5-
Std Deviettin
0.15
1.0-
0.100
0.05
0.0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Coreset Size
Coreset Size
(c)
(d)
Figure 3: Standard deviation for the size-error evaluation.
enumeration procedures that require ((e))(po))(e~>)))) time. We consider a variant of Lloyd's heuristic [Llo82] that is adapted to the missing-value setting, and we evaluate its speedup with coresets. The algorithm is essentially the same as the original Lloyd's algorithm, except that the distance as well as the optimal 1-mean for a cluster (which can be computed optimally in ((d) for cluster P 2FF), is computed differently. We show that our coreset can significantly accelerate this algorithm. In particular, we run the modified Lloyd's heuristic directly on the original dataset, and take its running time and objective value as the comparison reference. Then we run this modified Lloyd's heuristic again, but on top of our coreset and the uniform sampling baseline respectively, and we compare both the speedup and the relative error' against the reference. The experiments are run on the Russian housing data set where the number of iterations of the modified Lloyd's 's is set to T = 5000 and the number of clusters is set small value k = 3 so the heuristic is likely to find a local minimum faster. Again, to obtain a stable result, we run the experiments for 40 times with independent random bits and report the average relative errors and running time.
The relative error with respect to varying coreset sizes can be found in Figure 4a. We can see that the relative error of Lloyd's s algorithm running our coreset is consistently low, while the uniform sampling baseline has several times higher error and the error does not seem to improve even when improving the size. We note that relative eиrоrs for both coreset and uniform sampling significantly lower than that we observe from the empirical error in Figure 2a. In fact, they are not necessarily comparable since the empirical error in Figure 2a is always evaluated on same center, while what we compare in Figure 4a is the center sets found by the modified Lloyd's running on different data sets. This also helps to explain why improving the size of uniform sampling may not result in a better solution, since as shown in Figure 2a, uniform sampling has large empirical error (around 50%). so a good solution for the uniform sample may not be good solution for the original data set.
Results.
The running time of the modified Lloyd's top of our coresets can be found in Figure 4b, and the running time of Lloyd's on the original dataset is 22.9s (which is not drawn on the figure). To make fair comparison, we also take the coreset construction time into account. Note that coreset size is not a dominating factor in the running time of coreset construction, since the majority of time is
For E Rt. the relative error of against reference x² 0 is defined

---

Computing Coreset
Running Llyod
Our Coreset
Relative
Uniform Sampling
Time
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
Coreset Size
Coreset Size
(a)
(b)
Figure 4: Relative error and running time evaluation for the Lloyd's heuristic on the coreset, with respect to varying coreset sizes. The left figure demonstrates the relative error, and the right figure shows the running time of constructing coreset, and the time for the modified Lloyd's heuristic running top of coreset.
spent on computing the importance scores and the coreset size only affects the number of samples. A coreset of size only 1000 can achieve < 1% error, and the running time of constructing the coreset and applying Lloyd's on top of it are 3s and 0.8s, respectively, which offers more than 5 times of speedup. We remark that experiments only demonstrate the speedup in single-machine scenario, and the speedup will increase the parallel or distributed setting.
5
Conclusion
Our coreset construction builds upon the sensitivity-sampling method (cf. [FL.1]]. However, central technical challenge is that the standard method to compute the sensitivity scores breaks, because distances between points with missing values do not satisfy the triangle inequality. We overcome this using another known method, of [VXI2a], that requires coreset for k-CENTER. Our main innovation a near-linear time algorithm that computes an (appaappoee C-ENTER coreset for points with missing values. To this end, we need the following key steps, which constitute our main technical contribution.
We reduce the k:- R--CENTER coreset construction with missing values, to the construction of traditional k-CENTER coresets (i.e., without missing values) on a series of instances. These instances built by restricting data points with missing values carefully-chosen collection of subspaces. The guarantee needed from this collection a certain combinatorial structure, and we indeed prove it exists.
The method of Varadarajan and Xiao exccutes the k E-CENTER coreset algorithm many times, and overall takes quadratic time. To improve the running time, we design an efficient dynamic algorithm for the well-known Gonzales' algorithm (which computes O(1)- approximate k- E-CENTER coreset). The main idea in this dynamic algorithm to project the data points onto (data-oblivious) random ID lines, and build each line dynamic data structure that supports furthest-neighhor queries (in ID).
Finally, we implemented our algorithm and the experiments indicate that our algorithm is efficient and accurate enough to be potentially applicable in practice.
Future directions. As an immediate follow-up, one could try improve our coreset size, e.g.. removing the dependence in log n. Our input can be viewed as axis-parallel affine-subspaces. Hence, another an interesting direction is to obtain coresets for the more general setting where the input consists of general affine-subspacee
Potential negative societal impacts. Our paper focuses on computational issues (improving time and space) of known clustering tasks. Clustering methods in general have potential issues with fairness and privacy, which applies also our work, but our research is not expected to introduce new negative socictal impact beyond what is already known.
10

---

Acknowledgments and Disclosure of Funding
The majority of this work was done when Shaofeng Jiang was Aalto University. This work is partially supported by ONR Award X00014-18-1-22 by the Israel Science Foundation grant #1086/18, by a Weizmann- Making Connections Grant, and by Minerva Foundation grant.
References
[A110]] Paul Allison. Missing data. Sage publications, 2001.
[APO2] Pankaj K. Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algo- rithms for clustering. Algorithmica, 33(2):201-226, 2002.
[AV07] David Arthur and Sergei Vassilvitski.. k-means++: the advantages of careful seeding. In SODA, pages 1027-1035. SIAM, 2007.
[BBH+20] Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth. In International Conference on Machine Learning, pages 569-579, PMLR, 2020.
[BELI]] Maria-Floring Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general communication topologies. In NIPS, pages 1995-2000 2013.
[BFL+17] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin Yang. Clustering high dimensional dynamic data streams. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 576-585, PMLR, 2017.
[BJKW19] Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. International Conference on Machine Learning. pages 744-753. PMLR, 2019.
[BJKW21] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Core- sets for clustering in excluded-mine minor graphs and beyond. In SODA, pages 2679-2699 SIAM, 2021.
[BLKI8] Olivier Bachem, Mario Lucic, and Andreas Krause. Scalable k-means clustering via lightweight coresets. In KDD, pages 1119-1127, ACM, 2018.
[CASS21] Vincent Cohen-Addad, David Saulpic, and Chris Schwicgelshohn. A new coreset framework for clustering. STOC, 2021.
[CCB16] Jocelyn Chi, Eric C. Chi, and Richard G. Baraniuk. k-POD: method for means clustering of missing data. The American Statistician, 70(1):91-99, 2016. doi: 10. N0.1080/000313000 2015. 1086685.
[Cha09] Timothy M. Chan. Dynamic coresets. Discret. Comput. Geom., 42(3):469 2009.
[DGR21] Ran Duan, Yong Gu, and Hanlin Ren. Approximate distance oracles subject mul- tiple vertex failures. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). pages 2497-2516. SIAM. 2021.
[DK11] Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium Principles of distributed computing, pages 169-178, 2011.
[EFG+21] Eduard Eiben, Fedor V. Fomin, Petr A. Golovach, William Lochet, Fahad Panolan, and Kirill Simonov. EPTAS for k-means clustering of affine subspaces. SODA, pages 2649-2653 SIAM, 2021.
[Fel20] Dan Feldman. Introduction to core-sets: an updated survey. arXiv preprint arXiv:2011.09384, 2020.

---

[9K Dan Feldman, Zahi Kfir, and Xuan Wu. Coresets for Gaussian mixture models of any shape. arXiv preprint arXiv: 04895, 2019.
[FLII] Dan Feldman and Michael Langberg. unified framework for approximating and clustering data. In STOC, pages 569-578 ACM, 2011. https://arxiv, org/ //bs// 1106. 1379.
[FRS19] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields PTAS for k-means in doubling metrics. SIAM J. Comput., 48(2)4452-480, 2019,
[FS05] Gereon Frahling and Christian Sohler. Coresets in dynamic geometric data streams. In STOC, pages 209-217. ACM, 2005.
[FSS20) Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM J. Comput., 49(3):601-657, 2020.
[GLS08] Jie Gao, Michael Langberg, and Leonard J. Schulman. Analysis of incomplete data and an intrinsic-dimension Helly theorem. Discret. Comput.
2008.
[GLS10] Jie Gao, Michael Langberg, and Leonard J. Schulman. Clustering lines in high- dimensional space: Classification of incomplete data. ACM Trans. Algorithms, 7(1):8:1- 8:26, 2010.
[Gon85] Teofilo Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret- ical computer science, 38:293-306, 1985.
[HB01] Richard J Hathaway and James C Bezdek. Fuzzy c-means clustering of incomplete data. IEEE Transactions on Systems, Man, and Cybernetics, Purt B (Cybernetics)) 31(5):735-744, 2001. 2001.
(HC10) Ludmila Himmelspach and Stefan Conrad. Clustering approaches for data with missing values: Comparison and evaluation. In ICDIM, pages 19-28. IEEE, 2010.
[HJLW18] Lingxiao Huang, Shaofeng H-C Jiang, Jian Li, and Xuan Wu. Epsilon-coresee for clustering (with outliers) in doubling metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 114-225, IEEE, 2018.
[HJV19] Lingxiao Huang. Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for clustering with fairness constraints. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[HK20] Monika Henzinger and Sagar Kale. Fully-dynamic coresets. ESA. volume 173 of LIPIcs, pages 57:1-57:21. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020.
[HM04] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median cluster- ing. In STOC, pages 291-300. ACM, 2004. fttps://arxile org/ abs//81b/1110....///
/810. 12826.
[HV20] Lingxiao Huang and Nisheeth K Vishnoi. Coresets for clustering in Euclidean spaces: Importance sampling is nearly optimal. In Proceedings the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1416-1429, 2020.
[Ind03] Piotr Indyk. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In SODA, pages 539 545. ACM/SIAM, 2003.
[TMF200 Ibrahim Jubran, Murad Tukan, Alaa Maalouf, and Dan Feldman. Sets clustering. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4994-5005. PMLR, 13-18 Jul 2020.
[KDD09] Kddcup. http:////.dd......dddd/oo/////// 2009 /Data, 2009.
[KP21] CS Karthik and Merav Parter. Deterministic replacement path covering. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 704-723. SIAM, 2021.
12

---

[LFKF17] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training Gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, 18(1):5885-5909 2017.
[Llo82] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2):129 136, 1982.
[LR19] Roderick JA Little and Donald B Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
[LS10] Michael Langberg and Leonard J Schulman. Universal e-approximators for integrals. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 598-601 SIAM, 2010.
[LS11] Euiwoong Lee and Leonard Schulman. Clustering affine subspaces: Hardness and algorithms. In SODA, pages 810-827. SIAM, 2013.
[MF19] Yair Marom and Dan Feldman. k-means clustering of lines for big data. In NeurIPS, pages 12797-12806, 2019.
[MOB 200 Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feldman. Data-independent neural pruning via coresets. ICLR. OpenReview.net, 2020.
[Phi17] Jeff M Phillips. Coresets and sketches. In Handbook of discrete and computational geometry, pages 1269-1288. Chapman and Hal//CRC, 2017.
[RPS15] Sashank J. Reddi, Barnabás Póczos, and Alexander J. Smola. Communication efficient coresets for empirical loss minimization. In UAI, pages 752-761, AUAI Press, 2015.
[Rus17] Sberbank russian housing market.
2017. 2017.
[Sam21] Salah Sammari. Vertical farming. https: //wp://wwwww/// www..kaall....///ddduaaeeeeeeeee
work-for- www.oo-pparaaaiieeriiiioll 2021.
[SW18] Christian Sohler and David P Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 2018 IEEE 59th Annual Symposium on Founda- tions of Computer Science (FOCS), pages 802- 813. IEEE, 2018
[vH14] Ramon van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
[VX12a] Kasturi Varadarajan and Xin Xiao. A near-linear algorithm for projective clustering integer points. In Proceedings of the twenty-third annual ACM-SIAM symposium Discrete Algorithms, pages 1329-1342. SIAM, 2012.
[VX12b] Kasturi R. Varadarajan and Xin Xiao. On the sensitivity of shape fitting problems. In FSTTCS, volume 18 of L/Ples, pages 486-497. Schloss Dagstuhl Leibnniz-Zentrum für Informatik, 2012.
[Wag04] Kiri Wagstaff. Clustering with missing values: No imputation required. In Classification, clustering, and data mining applications, pages 649-658. Springer, 2004.
[WLH+ 19] Siwei Wang, Miaomiao Li, Ning Hu, En Zhu, Jingtao Hu, Xinwang Liu, and Jianping Yin. K-Means clustering with incomplete data. IEEE Access, 1:69162-6917,, 2019. doi 10. AACC/// 2019. 2910287.
13


Reviews:
[{"review_id": "oDNyXLA-VRo", "reviewer": "Reviewer_7KH2", "summary": "This work considers a setup when points might have coordinates that are missing, and the distance between them is defined only by using the filled-in coordinates that they have in common. Note that this means that the distance function is not even a metric, and indeed has very few nice properties that we can depend upon. ", "questions": "", "limitations": "", "rating": 9, "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": "This is the first work to give coresets for multiple missing coordinates, and it improves the coreset size upon existing results even for the one missing coordinate case. \n\nIn most papers regarding coresets, there are two meta approaches -- either via aggregation using a fine mesh, or via using importance sampling, especially using the framework developed by Langberg et al. This work uses an existing framework to reduce the importance-score computation to the computation of k-center coresets,and being able to compute these k-center coresets for missing coordinates is the main technical contribution. At its heart is a nice implementation of an existing algorithm that makes it more efficient. I also found the restriction into the collection of subsets to be a very interesting construction.  \n\nOverall the work seems quite novel and is nicely written. My only slight crib is about the experiments. While uniform sampling is the most obvious baseline to compare with in this setting, perhaps it would be useful to see some other baselines that might not have a theoretical guarantee (at least in the worst-case setting). For instance, filling in the missing values using a suitable heuristic, and then using the standard k-means coreset -- how will that perform in practice.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No significant societal impact. Limitations include no known lower bound, especially figuring out whether the exponential dependence on j & k is needed. Other limitations include the experimental results, as mentioned above.  ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "jfjlhEB0kDK", "reviewer": "Reviewer_DJy9", "summary": "The paper suggests a coreset for clustering points in $\\mathbb{R}^d$ that have multiple missing values (coordinates) including K-means and K-median.", "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 paper gives the first coreset handling clustering points in $\\mathbb{R}^d$ that have multiple missing values.\nThe coreset construction is based on the importance sampling framework introduced by Feldman and Langberg. The main challenge in this coreset with missing values is that distances do not satisfy the triangle inequality, hence importance scores cannot be easily computed. To overcome this hurdle, the authors used a method introduced by Varadarajan and Xiao for projective clustering.\n\nI enjoyed reading the paper, the paper is well written, the results are interesting (also very strong), and the authors evaluate the performance of their results on real and synthetic datasets.\n\n\ncomments:\n\n1) Very important: please provide a detailed paragraph about the novelty of your work.  \nIt seems that the paper relies on other papers for suggesting the coreset, while I believe that there is something very strong hidden in the approach --> please elaborate more on this point, since it is very important.\n\n2) Remove the additional n in \"Running\" in Figure 4 (b).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The coreset size is exponential in k and j, where k is the number of clusters and j is the number of missing values. This is a large bound when both j and k are large values.  \n----> My question is how hard the problem really is? what is the lower bound for the coreset?\n\n2. Please address the novelty question above.\n\n3. Experimental results: please add variance to the graphs.\n\n4. Missing conclusion and future work section.\n\n      \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours "}, "extra_text": {}}, {"review_id": "dhT03KjzAsi", "reviewer": "Reviewer_Lwwe", "summary": "The paper describes the first algorithms for coresets for k-means clustering with missing data coordinates for some points in d-dimensions, with provably guarantees.  The algorithm runs in linear time O(nd) times factor depending only on j (most possible missing values per coordinate) and k (number of allowed clusters).  A SODA 2021 paper provides a PTAS for this problem, but it has worse dependence on j, k, epsilon and has a base cost of O(n^2 d), so quadratic in n.  This paper demonstrates their approach is implementable, and practical.  \n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Coresets for k-means clustering (and related problems) is a heavily studied area, and some improvements in paper seems incremental and not so consequential.  I feel this paper is *not* of that sort.  Missing values in data is a real and serious issue, and this paper basically provides the first scalable solution.  The main innovation is a provably accurate way to construct the coreset that then integrates (and relies on) natural and standard algorithms (Gonzalez & Lloyds, etc).  \n\nMoreover, I found the writing of the paper good.  It does not develop any especially deep or important techniques (although the dynamic k-center result is something), but it expertly borrows and builds on several choice advances from the literature.  Sometimes non-standard approaches were needed, and the paper does a good job of pointing out what was standard and what needed extra care and development.  After highlighting the main theoretical developments, it leaves space to carefully describe the experiments which do a good job of demonstrating the algorithms empirical advantages.  \n\n\nI do have one main complaint/suggestion.  The overall algorithm is not totally clear.  Section 1.2 does an ok job of overviewing it, but that section also provides intuition for various choices and where simple techniques fail.  I suggest the paper adds a short section just outlining the main algorithm -- there should be space.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was glad to see the paper had (short) sections addressing these points, even though as a mostly core/theory paper the real impacts are distant.  They could have also mentioned issues with imputing missing data, but it is forgivable since again the impact of this paper on actually societal issues is quite hard to extrapolate.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6_xTNJpf7Lz", "reviewer": "Reviewer_wxoY", "summary": "The paper provides the first coreset for clustering tasks, where each of the input d-dimensional points might contain up to j missing values. The coreset construction time is near-linear. The main technical result of the paper is a reduction from the above problem, to the problem of computing a dynamic coreset for the k-center problem with missing values. The authors utilize the sensitivity sampling framework for this task.\nUsing this coreset, the authors improve the running time of an existing PTAS for the problem, from quadratic, to near-linear time. The authors provide experimental results which demonstrate the effectiveness of the coreset in practice, as compared to a uniform random sample.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- In overall I really like this paper. The reduction to the dynamic k-center problem as well as the solution for this problem via the restriction of the input set into multiple sets with not missing values is very interesting.\n- The paper is mostly well written.\n- The paper presents significant improvement of the state of the art for this problem.\n- The provided coreset is original, and seems very useful for real-world problems, as shown in the experimental results section.\n\nDetailed comments and suggestions:\n- I did not find the exact definition of \\tilde{O}, which is very important.\n- There is a typo in the legend of Fig. 4(b).\n- The comparison to the previous work of MF19 is not very accurate. MF19 handles any input set of lines, which are not necessarily axis-parallel. The proposed work handles j-dimensional subspaces (for j >=1), but which are axis parallel.\n- It was difficult to sum-up the final coreset construction algorithm, as it is spread across the whole paper. A stand-alone pseudo-code would be very helpful.\n- In some claims the dependency on some constants, e.g., the probability of failure \\delta, is explicitly stated, while in others it is not. I would suggest explicitly adding the dependency on all parameters / constants in all the claims.\n- The standard deviation in the experiments is reported only for the Russian housing dataset. Is there a reason why this is not reported for the other datasets?\n- Missing a conclusions and future work section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This has been addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides core set construction for clustering such as k means with multiple missing values. All the reviews are highly positive and support acceptance. The authors should carefully address all the comments that the reviewers have brought up including adding new baselines to their experimental evaluation.
Decision: Accept (Spotlight)