Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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. 
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. 

In 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.  

Overall 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.

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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: The paper gives the first coreset handling clustering points in $\mathbb{R}^d$ that have multiple missing values.
The 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.

I 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.


comments:

1) Very important: please provide a detailed paragraph about the novelty of your work.  
It 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.

2) Remove the additional n in "Running" in Figure 4 (b).
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.  
----> My question is how hard the problem really is? what is the lower bound for the coreset?

2. Please address the novelty question above.

3. Experimental results: please add variance to the graphs.

4. Missing conclusion and future work section.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
Using 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.
main_review: Pros:
- 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.
- The paper is mostly well written.
- The paper presents significant improvement of the state of the art for this problem.
- The provided coreset is original, and seems very useful for real-world problems, as shown in the experimental results section.

Detailed comments and suggestions:
- I did not find the exact definition of \tilde{O}, which is very important.
- There is a typo in the legend of Fig. 4(b).
- 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.
- 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.
- 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.
- 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?
- Missing a conclusions and future work section.
limitations_and_societal_impact: This has been addressed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.  

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).  

Moreover, 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.  


I 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.  

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_title: null

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)