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 proposes a new sketching method for vectors, which allows one to retain the guarantees associated with k-means but with dimension bounded by sqrt{n}, which can be much less than d. The framework can be applied using three standard random matrices (sub-Gaussian, ROS or Nystrom), and of course the reduced dimension allows for better algorithmic runtime. 

The core contribution is the creation of a sketch of the form SQK, where S is the full random matrix, Q is a sampling matrix (a random submatrix of the identity matrix), and the multiplication of Q by K yields the approximate kernel matrix between the sampled data points and the point set.
strengths_and_weaknesses: Strengths: The overall result is a non-trivial improvement for an important problem.

Weaknesses: I felt the presentation could be greatly improved. There are multiple choices made regarding the construction of the sketch (basically, the SQK format used by the authors), without sufficient explanation, overview or discussion of the import of these choices. The steps of the algorithm should be discussed and explained in depth and they are introduced. A similar issue is that the current technique isn't placed in context - what is its relation to earlier used techniques, and in what way is it different. The overall presentation is poor, and also doesn't allow one to judge the novelty of the paper.

--------------------

In response to the authors' rebuttal, I have raised my overall score.
questions: Please address the above concerns.
limitations: N/A
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: This paper studies statistical properties and computational efficiency of randomized sketching for kernel k-means clustering. Compared to most existing works, this paper focuses on characterizing the optimal excess clustering risk upper bounds for three types of randomized sketching. In this paper, randomized sketching involves multiplying the kernel matrix by a "random" matrix (also called a sketch matrix). Overall, the paper provides a detailed overview of background materials (i.e., kernel k-means and randomized sketching). 
strengths_and_weaknesses: Strengths:
+ The main strength of this work is related to the provided statistical analysis and upper bounds for the the optimal excess clustering risk. Based on the provided table, this work shows that sketch dimension can be substantially reduced without compromising accuracy. 
+ Another strength of this work is providing a nice overview of kernel k-means clustering and randomized sketching. Although these materials are very standard, it is nice to provide them for general readers. 
+ This work also presents a "unified" algorithm with time/space complexity analysis, which is beneficial. 

Weaknesses:
- From a computational standpoint, the contribution of this work is limited. The three randomized sketching methods have been used for various kernel-based methods, including more sophisticated clustering techniques such as spectral clustering. 
- Although the improved upper bound is interesting, experimental results do not directly show the benefits of this statistical analysis. In other words, it is shown that the proposed randomized methods are more efficient compared to the exact kernel k-means, but no comparison with the other cited works. 
questions: Can you please explain how Section 4.1 relates to the other sections? It looks like the main contribution of this subsection is to include some results from (Lattanzi & Sohler 2019). However, the significance of this new result has not been discussed in other places, such as experimental results. 
limitations: There should be some more discussion on the significance of the statistical analysis for practitioners. Although this work provides an interesting upper bound, how does this result translate for analyzing large data sets? Can this approach be used for clustering a data set with a few hundreds of thousands of samples?
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper investigates the statistical analysis and computational requirements of kernel k-means based on randomized sketches.
The authors proposed a randomized sketches framework for kernel k-means and construct three specific examples of sub-Gaussian sketches, ROS sketches, and Nystrom to kernel k-means.
The proposed methods obtain the optimal excess risk upper bound $\mathcal{O}(\sqrt{k/n})$ with the least sketch dimension $\Omega(\sqrt{n})$ in the theoretical analysis.
Meanwhile, they reduce the time cost to $\mathcal{O}(n\sqrt{n}+n\sqrt{n}kt)$
and the space complexity to $\mathcal{O}(n\sqrt{n})$, which make a good improvement in computational requirements.
Finally, this work adopts the improved kernel k-means++ for the proposed randomized sketches kernel k-mean and derives the similar bound.
The experimental results on both simulated data and real-world data
verified the theoretical results of the proposed methods (sub-Gaussian sketches kernel k-means, ROS sketches kernel k-means, and Nystrom kernel k-means).
strengths_and_weaknesses: The paper has the following contributions: 
1) proposed a unified randomized sketches framework to kernel k-means;
2) proposed three novel and specific examples (sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystrom kernel k-means);
3) obtained the state-of-the-art risk bounds of the proposed methods in theoretical analysis;
4) made significant improvement in reducing computational requirements,
5) derived the similarity optimal bound of approximate solutions in k-means++.

Those contributions are novel and significant. The experimental evaluations in simulated and real case settings illustrate the theoretical analysis of the proposed methods. The paper is well organized, well written, and technically sound. The exposed materials can be followed up fairly. All the relevant papers are properly cited. Overall I enjoyed reading this paper, which nicely generalizes randomized sketches to the kernel k-means.
questions: A solid theoretical analysis is provided. A clear comparison with the results of recent works is given in Table 1. The experiment results on synthetic and real data show the effectiveness of the proposed methods. Nevertheless, there are some minor issues.

1) The experiments in this paper are convincing. It would be much better if the figures are more beautiful.

2) The author should double check the text. There are few typos. For example, in Table 1, the citations are connected with the text. "real-word" should be "real-world".

3) In line 200, it is a little bit confusing that the authors present $K$ followed by $\hat{K}$

4) The conclusion section of this paper is missing.
limitations: This paper describes the scope of application of the proposed methods in detail, and does not involve negative social impact.
review_title: null

Meta-review: metareview: The paper analyses the performance of a class of sampling-based sketches for the kernel k-means clustering problem. The main contribution is a proof that the excess clustering risk of these sketches is optimal when a smaller sketch is used than in previous state-of-the-art approaches to sketching kernel k-means. Clear comparisons with the prior state-of-the-art results shows that the method greatly reduces the computational complexity of sketched kernel k-means, and experimental validation shows that the method is competitive in terms of accuracy.
confidence: Certain
Decision: Accept