Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents coresets for a robust version of the $k$-clustering problem where the cost of clustering is taken over the dataset after removing $m$ outliers. The coreset size is polynomial in $k$ the number of clusters and linear in $m$, the number of outliers. The paper also shows a lower bound on the coreset size implying that the linear dependence on $m$ is necessary. The theoretical results are validated with experiments on real-world datasets.
strength_and_weaknesses: Strengths: 
1. The problem of robust clustering is well studied and important one while at the same time being computationally expensive. Using coresets for such computationally expensive problems is a justified and popular approach.  This paper improves the size of coreset for the problem significantly and also provides a lower bound for the same. 
2. A good set of experiments is performed to validate theoretical claims and the code is provided. 

Weaknesses: 
1. The paper appears to rely heavily on the paper by Braverman et al. 2022 for the coreset construction idea and the proof techniques. In that regard seems to be lacking in novelty. The novelty section needs to be highlighted better as to what are the technical challenges faced in comparison to the Braverman et al. paper. Do mention clearly the subtleties when adopting the technique to incorporate outliers. 
2. While the paper is written nicely in terms of language and notations, there are a few points which I believe will enhance the completeness aspect. I list them below in the section on clarity.
clarity,_quality,_novelty_and_reproducibility: I found it difficult from the paper itself to understand which rings are classified as groups and which are not. I had to read the Braverman paper to understand. I think the notion of marked (heavy) rings with higher costs and unmarked ones is not clearly stated here. It would be useful if it is explained clearly in the paper.

A detailed time analysis of the algorithm will be useful. Also, it will be good to give an overview of the computational complexity of original by problem. 

The size of L in proof of theorem 3.1 is $t$ or $m$? Also, can you please explain how does the proof work for all $C$ and not only for a fixed $C$. In other words, I am a bit unclear as the outliers change with change in centers, so an explanation as to why same subset works as the coreset will be appreciated.

Usually in coreset literature while performing experiments you solve the problem on the full data, take the cost as 'optimal' cost and also solve on coreset and plug the solution obtained from coreset back in full data and compare that cost obtained with the 'optimal' cost. I understand that what you report here is the coreset guarantee with random set of centers, however the above measure might be useful as well. 

Also, if we use the coreset obtained using Braverman et al. technique for vanilla clustering as a baseline how different it will be compared to uniform or sensitivity-based sampling. Can you provide your comments?

I did not check proofs in the appendix thoroughly, but they appear ok. Code is provided and I believe the empirical results are reproducible.
summary_of_the_review: Overall, I believe that the results of this paper will be of interest to the community. However, the paper needs to highlight its contributions in terms of novelty more clearly and also improve the writing to include few concepts for the sake of completeness. I believe if these changes are made the paper will present a better case for acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies coresets for robust clustering. A coreset is a small proxy of the dataset, which is yet sufficient to perform the task at hand while not significantly compromising the quality of the solution. The goal of the robust clustering task is to cluster a set of data points that contains a number of adversarial outliers. Concretely, given a clustering objective $cost$ (e.g. $k$-means) and a set of points $P$, the robust clustering objective with $m$ outliers is defined as the minimum cost achievable by a clustering that is allowed to remove up to $m$ datapoints: $\min_{\text{clustering }C} \min_{M\subseteq P, |M|\leq m} cost(P \backslash M, C)$.

The main result of this paper is a coreset for the robust clustering problem with a range of clustering cost objectives that includes $k$-means and $k$-median. Specifically, the coreset has size $O(m) + \mathrm{poly}(k \epsilon^{-1})$, where $k$ is the desired number of clusters and $\epsilon$ is an error tolerance. This is quite satsifying since previous work shows that $\mathrm{poly}(k \epsilon^{-1})$ is tight for the non-robust case (even though the polynomial dependency doesn't quite match the lower bound). The runtime is O(|P| k d), where d is the dimension of the data.

The idea is to first run an approximate but fast robust clustering algorithm from previous work (Bhaskara et al), and then define the coreset as the set of worst fitted points wrt this clustering plus a random sample. The most technical part is this sampling process, which builds on previous work of Braverman et al.
strength_and_weaknesses: Strengths:
- The robust clustering problem is important in practice. Coresets are very relevant in large scale and dynamic applications where going maintaining and processing all the data points is impractical.
- The algorithm is simple and intuitive.
- The experimental results on four public datasets are promising. In particular, the authors' coresets have significantly better quality than trivial ones, e.g. uniform sampling. In addition, the coreset generation time seems to be >10x faster than the time if one were to run robust clustering without a coreset. This shows that coreset generation can be used as a preprocessing step to significantly speed up robust clustering.

Weaknesses:
- I would like to have seen a comparison with the algorithm of Bhaskara et al. In theory it gives a $O(1)$-approximation, but how does it do in practice compared to the coreset approach? Also, there are other, simpler heuristics for coreset generation that would be nice to be considered. For example, what happens if I just perform uniform sampling on the clusters of Bhaskara (plus the outliers)?
- There is some confusion with symbols in various places: $P$ vs $X$, $n$ not defined, what is $c^*$ in Lemma F.1, etc.
clarity,_quality,_novelty_and_reproducibility: - I believe this paper significantly contributes on the field of algorithms for robust ML.

- The result looks correct and the writing is intuitive and clear.

- The authors provide the code and data for their experiments.
summary_of_the_review: In summary, I find this paper interesting and I think it makes significant theoretical progress in a fundamental ML problem, and is also promising for practical applications. I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents near-optimal coresets for robust Euclidean clustering. Given k, z, m, and a set of n points P in R^d, we look for a k-clustering of P excluding a set of outliers L of size at most m, minimizing the sum of (power z of) distances of points to their centers. This gives k-median and k-means objectives for z = 1, 2.

The authors present a coreset of size O(m + poly(k/epsilon)), which adds error epsilon to the approximation.
- Best coresets for non-robust problem have size poly(k / epsilon).
- Linear dependence on m is necessary (the paper gives a simple example).
- Dependence of k^3 and epsilon^5 (k-median) or epsilon^8 (k-means) sound too big, but the experiments show that one can use much smaller dependence and beat prior work.
- Omega(k/epsilon^2) is a lower bound for the non-robust case.
- Prior work for robust algorithms either had exponential dependence on m or bicriteria for the number of outliers.

This work heavily builds on the techniques from the recent Braverman et al. [FOCS 2022], though certain pieces need to be adapted to the outlier setting.
strength_and_weaknesses: S1: Strong results and significant improvement of the state of the art.
S2: Timely contribution as the non-robust version has been only recently settled and having robust algorithms is a hot topic.
S3: Great practical performance despite the large dependence on k and epsilon.

W1: There is still some gap between upper and lower bounds.
clarity,_quality,_novelty_and_reproducibility: Paper is written clearly and it is easy to read.
summary_of_the_review: Significant improvement of the state of the art for an important problem, and very good practical performance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper shows constructs coreset for (k,z,m)-robust clustering problem, where k is the number of clusters over the distance measure between two points are || - ||_2^z and m is the number of outlier points. The coreset size linearly depends on m, poly(k,eps^(-1)) and exponentially depends on z. The running time of the algorithm is yime taken to get a constant factor aprooximation of the problem plus O(nkd).
strength_and_weaknesses: strength:
- the result improves the coreset size by expotential factor in k abd m, by bringing it down to nearly optimal (m + ply(n,eps^(-1))).
- it presents extensive experimental results on real world datasets.

weakness/suggestions:
- a comparative discussion about its coreset vs exponential size coreset will be useful to motivate towards the probem
- are the groups consist of rings with at most 1 point? The discussion about groups could be further improved.
- a proof sketch of lemma 3.6 and 3.7 in the main paper could be useful. 
clarity,_quality,_novelty_and_reproducibility: The paper is very well written, including a good explaination of "The Power of Uniform Sampling", whose techniques they heavily rely on foe their proble. Both quality and novelty are at par. 

summary_of_the_review: The paper tackles a very important problem called robust clustering, which has many common applications. It improves the coreset size by exponential factor. It also shows emperical results on real datasets to back its theoretical claims and to show its benifits in improving scalability.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Strong results on an important problem with convincing experiments, everyone thought it was a clear accept.
justification_for_why_not_lower_score: see summary.
Decision: Accept: notable-top-5%