Venue: NeurIPS 2022 Conference

Reviews:

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 considers the problem of providing a bound on the size of the coresets for the K-means problem which is closer the lower bound than the existing state of the art approaches. Some experimental results are also provided to support the analysis in the paper.

strengths_and_weaknesses: The paper is highly compressed to fit into the confines of the conference submission. Though the writing is clear, it heavily relies on reading up on the results from Cohen-Addad et al's recent papers. 

The setting is of prime interest given that K-means shows up in various machine learning settings. The result of improving the min(k, 1/eps^2) to the \sqrt(k)
is pretty significant because now it is clearer that there will be a potential algorithm matching the lower bound of O(k/eps^2).

I checked over the main theorems and approach but did not work through all the details.

The paper is solving an important problem in clustering but the reduction from k to \sqrt(k), while theoretically very interesting, is a bit too narrow. 

questions: (A)Does this analysis follow through for other clustering problems such K-median, K-mediods etc? 

(B) It seems like you are able to get a better clustering nets because you can bound the error by the geometric mean (smaller) than the arthimetic mean. Is this the tightest one can get? 

(C) The experimental section is showing the cost of the various algorithms as well as the distortion results. However, it would be interesting to show the scaling of the size of the coresets. These are provided in the supplementary and would be better served if shown in the main paper? 

limitations: The paper would be a nice contribution to the clustering literature but I wonder if it would be better suited to a primarily theoretical audience like COLT or similar. I provided an initial lower rating to reflect that and will adjust it based on the upcoming discussions.
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: The paper studies coresets for k-means clustering in d-dimensional Euclidean space. The paper is of theoretical nature and shows an improved upper bound of $O^\ast(\epsilon^{-2}k^{1.5})$ on the size of coresets that can be obtained by group sampling. This improves the current best bound of $O^\ast(\epsilon^{-2}k^2 \min\{\epsilon^{-2},k^2\})$. 
strengths_and_weaknesses: The paper studies an important and interesting problem, which is under active research. The obtained upper bound is a further step towards closing the gap to the current lower bound.

The work is somewhat incremental since it heavily uses results from previous work and basically achieves the result by improving a part of it -- the cost vector net.

On the other hand, the obtained bound is nice and is certainly worth to be published.

Another weakness is that the notation and the technical details are not always clean and convincing. Also the experiments are not that meaningful.
questions: My suggestion is to improve the technical parts. Also the plots of the experiments may be improved (one can barely see the differences in cost.)
limitations: No potential negative societal impact in sight.
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 presents a theoretical analysis leading to smaller coreset sizes for the problem of $k$-means. The coreset can then be extended also to the $k$-median problem.  

The authors provide an improvement over the work of Cohen-Addad et al. [2022], by finding nets (discretizes set of solutions) with better properties, to obtain their coreset size. This in term leads to the smallest coreset size for $k$-means with the emphasis that the coreset size should not be linearly in $k$. 
strengths_and_weaknesses: * Strengths:
    1) A smaller coreset size for the k-means problem, leading to a subquadratic coreset size in $k$ (the number of means).
    2)  While the paper is based on a paper by Cohen-Addad et al. [2022], the authors present techniques that hinge upon finding better nets for obtaining smaller coreset sizes for both the $k$-means and $k$-median problems. In other words, the authors present an improvement on the techniques of Cohen-Addad et al. [2022], by generalizing the techniques to rather finding nets with better properties.

* Weaknesses:
The paper is somewhat hard to follow, and also contains many grammatical errors.
questions: 1) What is $p$ at the inequality below Eq. 2? I assume $p \in C_i$, right? 
2) Why does it imply that after $t = \frac{1}{\varepsilon^{-2}}$ rounds, $(I - \Pi_U\Pi_U^T)s = \overset{\to}{0}$? please clarify this point.
3) From what I understood, $Pi_U$ is the span of all previously added vectors from Lemma 5. So basically, this is a set, right? If so, what does it mean to have $\left\| Pi_Us - s^\prime \right\|$? Please do clarify.
limitations: The authors clearly addressed the limitation of their work.
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: The authors address the problem of coreset construction for the known k-means problem. They propose a coreset construction scheme and prove that it achieves coresets of size smaller than the state of the art, in some regimes.
To carry out the analysis, the authors propose a novel method that avoids terminal embeddings, which are common in the analysis of prior works. The authors claim this novel technical contribution may be of independent interest as well.
Empirical evaluations are then carried out to test the impact of the proposed approach against known techniques.

strengths_and_weaknesses: Strengths:
- The proposed scheme indeed achieves state of the art coreset sizes for one of the cornerstone problems in the field.
- The analysis are novel and very interesting.
- The paper is relatively well written.

Weaknesses:
- Related work section is rushed through and lacks details. It does not contribute to the reader's knowledge, and should be better written in my opinion.
- Missing important discussions. Examples:
  * The validity of Assumptions 1-4 is placed in the appendix. At least a brief explanation should be placed in the main text. 
  * A discussion as to why this result cannot be extended to l_z clustering can be very helpful and enriching. 
  * It seems that the proposed algorithm, after ensuring the validity of the assumptions, samples each point according to some simple quantity which resembles the sensitivity distribution known from many prior works. A comparison or discussion is needed here.
- As of Assumption 3 regarding the input weights: to ensure integer weights (as stated in the appendix), some scaling and rounding is required. Doesnt this produce a dependency on the smallest weight, or, alternatively, on the model's precision? If so, this is an important note.
- The experimental results are not sufficient: 
  * Important details are missing.
  * The proposed method is not shown to achieve better results than the competing methods. 
  * Running time are not reported, which is crucial, as it seems that the proposed method would (theoretically) achieve much larger computational times. This is due to the computations required to enforce Assumptions 1-4 (which include a computation of an alternative coreset, e.g., the sensitivity coreset used as a competing method).
- At the end of the day, the proposed algorithm is not novel as it simply computes a (previously known) sampling probability for every input point, which is based on some (previously known) approximation for the problem, then it samples points from this distribution and does some reweighting.  Also, as the authors claim, enforcing Assumptions 1-4 is also not novel. The only novel part seems to be the analysis. Hence, in my opinion, the paper's main contribution is not sufficient.

Minor comments:
- The first paragraph on Page 2 is important and should be somehow better emphasized.
- Line 50: "may be reduced to log(k/\eps)\eps^-2 using dimension reduction techniques". some citation should be added at the end of this claim. 
- Line 50: "to technique" (typo).
- Equation at Line 50: missing closing bracket.
- Typos at Line 63.
- The equation after Eq. (2) utilizes the point on the left and on the right hand sides, but p does not seem to be defined.
- Lemma 5: where is X defined?
- Line 210: the maximum distortion is reported in the experiments. Do you have insights on the average distortion? The average distortion might be a more accurate indicator.
questions: See few question above.
limitations: Yes
review_title: null

Meta-review: metareview: I actually really liked the paper despite the weak accept reviews - and decided to bump this up. Improving the known coreset bound for k-means is extremely important, as that is a fundamental problem. While it does indeed heavily build upon prior work and doesn't get optimal bounds, it is giving a novel analysis for a very important problem (with a huge line of prior work with worse bounds), and thus I recommend acceptance. 
confidence: Less certain
Decision: Accept