Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the average sensitivity of the Euclidean $(k, \ell)$-clustering problem, which measures the stability of the output in total
variation distance against deleting a random point from the input data. The authors first show that D^l-sampling has low average sensitivity, and then show that any approximation algorithm for Euclidean $(k, \ell)$-clustering can be transformed into an algorithm with a low average
sensitivity while almost preserving the approximation guarantee, via a coreset construction approach. They also extend their result to consistent and dynamic settings.
strengths_and_weaknesses: Strengths:
Generally, I think the topic is essential and the notion of average sensitivity on Euclidean $k$-clustering is interesting. This paper first provides an analysis of the average sensitivity of Euclidean $k$-clustering, which provides evidence of the stability of the well-studied k-means++ algorithm. The writing is good and explains the contributions well.

Weaknesses:
I have some concerns about the main result Theorem 3.1. See Questions. I may raise my score if the question is answered.






questions: - Thm 3.1. The authors argue that the algorithm can output a $(1+\varepsilon)\alpha$-approximation. However, it seems that they first do a dimension reduction and then construct a coreset on the reduction space. Then how can we obtain a constant approximation of the original space? A solution to the reduction space does not seem to be what we want.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Thanks for the response. It makes sense to me. I have the following additional question accordingly.

The average sensitivity contains an unexpected factor $d$, which seems to come from the coreset size in Theorem 3.4. However, there are several approaches to remove this dependence, e.g.,
- Lingxiao Huang, Nisheeth K. Vishnoi: Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. STOC 2020: 1416-1429
- Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn: A new coreset framework for clustering. STOC 2021: 169-182

A difference is that they apply two-staged importance sampling or partition datasets into rings, which makes it not easy to use the argument of Lemma B.1. However, since you consider coreset construction for 1-clustering, I conjecture that these approaches can help you remove the dimension dependence in the average sensitivity.
limitations: Not.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work focuses on the euclidean $(k, \ell)$-clustering problem with low average sensitivity. $k$-median and $k$-means are the two of the most studied problems and which are special cases of this work. They focus on the changes to the output distribution in the case that one of the input points is deleted.

They first show that $D^\ell$-sampling has average sensitivity of $O(k/n)$, which is also tight up to a constant factor. They also show a  general reduction from any algorithm to one that has low sensitivity by losing a factor $1+\epsilon$. They also show that their results can be extended to Consistent and Dynamic settings, two very interesting settings in the literature.


After Rebuttal:

I do not find the responses of the authors to the second and third questions that I asked convincing.

2- Basically the authors are arguing that their results is only interesting in a special setting that $\Delta$ is huge and if $k >> log(\Delta)$ their result is worst which is different from the claim in the paper.
3- The argument here is hiding some of the most important factor and focusing only on log with out explaining the reason behind it.

From my point of view, the two main applications of this work are significantly weaker than what presented in the paper. Reading the rebuttal and the other reviews, I updated my score.  
strengths_and_weaknesses: The paper is in good shape and the results are clear. I found the reduction interesting, it is based on coreset construction. From the analysis it seems that the approach cannot be extended to achieve better results as well. It is always interesting to understand $D^\ell$ sampling better since it is still one of the most basic algorithms for $k$-means. The ideas and techniques are nice but I do not see any major new ones in this work.

I am concerned about the consistent and dynamic settings, it seems that the authors have missed some of the most recent results. For example for consistent clustering, “Consistent k-Clustering for General Metrics” achieves better results than the one cited and also the results in this work. Moreover there are also results in a dynamic setting like “Fully-Dynamic Coresets” which is not considered in this work. From my point of view, the extensions to consistent and dynamic setting needs more work and is not clear and interesting currently.

Typo line 26: even k = 2

questions: 1- Can the hardness result be extended to general $\ell$? Is it possible to argue that the terms in the general reduction are tight?

2- Why is the consistent result interesting given the previous work?

3- Is there something that I am missing regarding the previous works in the Dynamic setting?

4- What are the new tools / ideas in this work? I think that the result is nice even if it is not possible to point out a concrete new technique. 

limitations: I think it is covered, notice that the goal of this paper is not private algorithms.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper addresses the problems of consistent and dynamic clustering. The metric used for measuring the consistency / stability of an algorithm is the average sensitivity.

The authors first provide a proof that two known clustering and sampling algorithms have very small average sensitivity.
The authors then show how to transform an approximation algorithm for the Euclidean clustering problem into a variation with guaranteed low average sensitivity. This is by providing a novel coreset construction algorithm with low average sensitivity, and then running the original approximation algorithm on the (stable) coreset.

Lastly, based on the low average sensitivity algorithm above, the authors propose algorithms for the consistent and dynamic clustering tasks in the random order models.

strengths_and_weaknesses: Strengths:
- The paper addresses important problem that are very relevant for the inevitability noisy data in the big data era.
- The paper is very well written. The formal claims are concise and are well explained beforehand. The proofs are clear and seem correct.
- The results are interesting; the proposed low average sensitivity algorithm is non-trivial, and makes an interesting use of the known compression scheme known as a coreset.
- One of the conclusions of this work, in my opinion, is important for future coreset construction algorithms: a low average sensitivity coreset construction algorithm yields a low average sensitivity (approximation) algorithm for tackling the problem. This acts as another application for coresets which is not usually discussed in the coresets literature.
- The link to consistent and dynamic algorithms in the random-order model is important.

Weaknesses:
- The "Dynamic clustering" paragraph at Line 76 is, in the best case,  misleading. Many existing coresets for the k-means problem do support fast update on new data arrival. Hence, computing and maintaining such a coreset for the dynamic data also yields a good and fast solution for the problem under the same dynamic-data model.
- The paper lacks a comparison or discussion on other dimensionality reduction techniques, e.g., https://epubs.siam.org/doi/abs/10.1137/18M1209854 .
- No empirical evaluation or comparison to competing methods. The empirical evaluation of the stability of the proposed algorithms and their impact when handling noisy datasets is crucial. Furthermore, the comparison of those variants to the known non-stable algorithms can reveal whether the new variants are indeed neccessary.
- Presentation: The disclaimer on the difference between the two very different "sensitivity" terms (at the bottom of Page 6) should have been made clearly emphasized earlier on. The two terms are very confusing, specially for the readers familiar with the coresets field.
- Limitations and future work are not mentioned.

Minor comment:
- Line 175-176: Can you provide a citation or a more formal claim?
questions: See questions above.
limitations: Limitations are not clearly mentioned.
review_title: null

Meta-review: metareview: I agree with the reviewers that the topic is essential, the notion of average sensitivity on Euclidean -clustering is interesting, and that the paper addresses important problem that is very relevant for the inevitability noisy data in the big data era.
As complained, the "dynamic data" section is a bit misleading compared to previous work and I suggest to remove it.
Please also add the discussion in the rebuttal to the paper or at least the supp. material.
confidence: Certain
Decision: Accept