Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper suggests a small coreset for the problem of clustering under kernel distances.
main_review: Coresets allow geometric problems to be reduced to small size, and then an expensive algorithm run on the coreset instead of the full input. Here the authors consider the problem of k-means where the distance function is given as a kernel. They show that coresets exist for this formulation, and so a brute-force algorithm can be used to solve this problem.

The technical framework is as follows: The authors present a known embedding from Hilbert to Euclidean space, and then the coreset of Braverman et al. satisfies the required approximation bounds. 

The theoretical contributions here seem very slight, more like observations, and I don't see the paper having the type of underlying innovation I would expect from ICLR. Also, I wasn't so impressed by an error of 10% using a coreset of 1000 points (although this application is somewhat outside my area of expertise).

typo on page 6: "importane-sampling"
summary_of_the_review: Nice result, but in my opinion not innovative enough for ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper suggests a coreset construction technique to the kernelized $(k,z)$-clustering, whose size is independent of $n$ (the number of points in the input data), in time that is near-linear in $n$.
main_review: The paper provides a coreset construction using the $D^z$ sampling technique to bound the probability of sampling any input point $p \in X$. The technique can be thought of as a generalization to the well-known technique $D^2$ sampling technique of David Arthur et al. due to the incorporation of the feature map.
While the paper is theoretical in nature and admits strong plausible results, I have some concerns:
1. The paper claims the first coreset for the problem of kernelized k-means problem. This claim is not true in my opinion due to the following. Even though the problem was not the main contribution of "A PTAS for k-Means Clustering Based on Weak Coresets" by Feldman et al., it was still mentioned in this paper. Another coreset paper mentions a coreset for kernelized k-means (for some type of kernels) where the coreset's size is exponential in k (see "Turning Big data into tiny data:
Constant-size coresets for $k$-means, PCA and projective clustering" by Feldman et al.). 
However, the best feature associated with your paper is the generation of coresets of smaller size with respect to any kernel function. A more proper claim would be the first coreset for $(k,z)$-kernelized clustering for any kernel function. 
2. Throughout the experiments, there was no need for the feature map itself as it is not commonly explicitly defined. However, Algorithm 3 requires its explicit existence which forms a bit of a problem. Can you please justify this? As far as I understood, Algorithm 3 uses the explicit feature map. How did you obtain this map? 
Practically speaking, I don't see why you need the explicit map, since the distance function can be slightly altered to apply the kernel trick also on points from $C^*$ (using $K$). This is due to the fact that $C^*$ is generated using points from $X$. Correct me if I am wrong.
summary_of_the_review: The paper is novel, well written, and admits theoretically and practically great results. I recommend acceptence.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper claims to present the first coreset for kernel k-means and other (k,z) kernel clusterings given oracle access to the kernel. The size of coreset is independent of the number of points and construction time is near linear in k. The authors use the coreset to get a (1+\epsilon) approximation for the kernel k-means. The theory is supported with experimental results.
main_review: Strengths:
1)Kernel k-means is an important problem in machine learning and since it is computationally expensive, the use of coresets to speed up the algorithm is an interesting and important problem.
2) Theoretically the paper uses a couple of nice small results (lemma 3.2 and corollary 3.3) to apply the coreset frame work in the kernelized setting. Overall the paper is not difficult to read.
3) Experimental results over large real datasets show significant speed ups for the kernelized k-means problem while preserving the accuracy. Code is also provided.

Weaknesses:
1)Less Novelty:  The algorithm for construction of coresets itself is not novel. Existing coreset frameworks for classical k-means and (k,z) clusterings  are  extended to the kernelized setting. 
2)Clarity:  Since the coreset construction algorithm is built up on previous works, a reader without the background in literature on coresets would find it hard to understand why the particular  sampling probabilities are chosen and why they give particular guarantees. It would be useful rewrite the algorithm preview and to give at least a bit of intuition on how the importance sampling scores are chosen and how they can give the coreset guarantees

Suggestions:
1) In the experiment section, other than uniform sampling, it would be interesting to use some other classical k-means coreset as baselines for comparison. 
2) Please highlight the technical challenges and contributions clearly when compared to coresets for classical k-means.
summary_of_the_review: Overall the paper discusses an important and interesting problem and the experiments performed on real datasets show the utitility of the method in practice. However the theory results are heavily based on existing coreset techniques for classical k-means and  I am not very sure if the paper has enough technical novelty for ICLR.
review_title: null

Meta-review: Overall it was decided to reject this paper mainly because it seemed to be a minor extension of known constructions. The reviewers agreed that it certainly is valuable that the paper presents the best known results for kernel k-means, but the paper was viewed by the reviewers as more of an observation and primarily an off-the-shelf application of techniques in the coreset literature. Because of this, the novelty was thought to be a bit below the bar. 

One suggestion for improving the presentation is that in the thesis of Melanie Schmidt, there seems to be such a construction for kernel k-means which is exponential in 1/eps, and so much worse than what is in this submission. While that's great and certainly something to add and discuss in the paper, the reviewers still felt the technical novelty here was not quite enough to merit acceptance.
Decision: Reject