Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This manuscript derived nearly optimal risk bounds for both kernel k-means and Nystrom kernel k-means of learning rate of O(sqrt(k/n)), which is interesting and attractive.
main_review: Pros:
1. Well-organized and clearly written, full and accurate understanding of related works.
2. A (nearly) optimal excess clustering risk bound is proposed in this paper, which is the main contribution of it.
limitations_and_societal_impact: Cons: 
1. Weak innovation, all contributions and most of the results of this manuscript can also be found in the journal: Nearly Optimal Clustering Risk Bounds for Kernel K-Means, Machine Learning, arXiv:2003.03888.
2. The Lemma3 mentioned in the main result and the Lemma10 mentioned in section 4.2 are not found in the script, making the result of this article unreliable.
3. Weak experiments. The employed datasets are synthetic , clearly unable to reflect real-world scenarios.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors provide a near-optimal risk bound for kernel $k$-means, namely $\tilde{O}(\sqrt{k/n})$, which improves upon the existing risk bound $O(k/\sqrt{n})$, and nearly matches the lower bound $\Omega(\sqrt{k/n})$, where $k$ is the number of clusters and $n$ is the size of the training set. They first derive a near-optimal risk bound for the empirical risk minimizer (ERM) and then extend it to general cases beyond ERM and $k$-means++. For efficiency, the authors also provide near-optimal risk bounds for Nyström kernel $k$-means for the case of using $\tilde{\Omega}(\sqrt{n})$ sampling points. The authors have performed numerical experiments to validate their theoretical findings. 
main_review: My impression is that this is an interesting work with solid theoretical contributions, so overall I am inclined to accept. Some minor comments are listed as follows:

1. Mentioning that $k$ is the number of clusters and $n$ is the size of the training set in the abstract.

2. The authors should check all the notations used in the main document carefully. For example, in Section 2.1, the definition of the empirical distribution $\mathbb{P}_n(\mathcal{S})$ at Line 73 is problematic because it always equals $1$. Line 82, $\mu = \Omega(\nu)$ does not mean $c_1 \nu \le \mu \le c_2 \nu$. 

3. For brevity, some notations/equations that are never used in the main body can be omitted or be placed in the supplementary material. For example, \mathcal{W}(\mathbf{C}, \mathbb{P}_n)  does not need to be expanded as the equation between Eqs. (1) and (2). The definitions of f_{\mathbf{C}} and \mathcal{F}_{\mathbf{C}} (Eq. (3)) are never used in the main document. In fact, I think the content between Lines 92 and 98 can all be removed (or move to the supplementary material). The notation $\mathcal{E}(\mathbf{C}_n)$ (excess clustering risk) has never been used in the statements of the theorems. 

4. Line 103, the authors should not use $\mathbf{C}$ to represent the collection of centroids corresponding to the lower bound. Perhaps renaming it as $\mathbf{C}_{lb}$. The authors should add "for example" before presenting Lemma 1. 

5. Between Lines 170 and 171, removing  "span" in the definition of $\mathcal{H}_m$. 

6. Checking the format of all the references in the References section. For example, in [2], it should be "NP-hardness of Euclidean". In [8], "risk" should be "Risk". 
limitations_and_societal_impact: As mentioned in the Checklist, the limitations have been addressed and potential negative societal impact is not applicable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors proposed optimal risk bound for clustering using kernel kmeans and Nystrom based kernel k-means. They improve the risk bound from k/sqrt(n) to sqrt(k/n).
main_review: 1. The paper is well organized and well written. 
2. The theoretical results are significant as the author shows near-optimal risk bounds. 


----
I appreciate for the response and increase my final score. 
limitations_and_societal_impact: 1. An overview of the algorithm in the main paper or supplementary would be beneficial.
2. Some more experiments on larger real data set would have been better.
3. Regrading the sample size in theorem-4 & 5: The notion of statistical dimension is also used to show importance sampling-based spectral property approximation "Avron H, Clarkson KL, Woodruff DP. Sharper Bounds for Regularized Data Fitting. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 2017 Aug". Do you think a similar sampling technique can be used here to get a better sample size?
4. Although the authors acknowledge about "discussing limitations" however, I did not find any discussion.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper provides a nearly optimal bound for consistency of kernel $k$-means clustering and gives an approximation scheme based on the Nystrom method that allows one to perform scalable data quantization. More specifically, a new upper bound in $\sqrt{\frac{k}{n}}$ is obtained for the excess risk in kernel $k$-means, which improves the state-of-the-art excess risk bound in $\frac{k}{\sqrt{n}}$. The same bound for the Nystrom approximation of the algorithm are also provided.
main_review: The paper proposes a nearly optimal excess clustering risk bound is proposed for ERM, which is the first (nearly) optimal excess risk bound for kernel $k$-means in terms of both $k$ and $n$. It improves the bound from $\frac{k}{\sqrt{n}}$ to $\sqrt{\frac{k}{n}}$, which is a significant advancement. Moreover, the general cases beyond ERM are also considered. The paper also considers the computational aspects, i.e., the paper states the same bound for Nystrom approximation of the algorithm. These results are important for kernel $k$-means and are very interesting. The paper also provides some numerical experiments to demonstrate the theoretical results. In summary, I think this is a good and well-written theoretical paper which is helpful to who are interested in kernel methods or kernel $k$-means.
limitations_and_societal_impact: Here are some comments:
1. It would be better to provide more intuition and clear descriptions of the proofs and the relations among them can help the reader better understand the content.
2. In Line 207, the paper mentions "improved $k$-kernel means++". What's this? Is this improved $k$-means++ ? The paper should provide a brief introduction about this.
3. It would be better to introduce the experimental results in more detail.
review_title: null

Meta-review: The work presents nearly optimal bounds for the excess clustering risk of kernel k-means, improving the rate of convergence from k/sqrt(n) to sqrt(k/n), and also shows that approximate (Nystrom with uniform sampling of sqrt(nk) landmark points) has the same order of excess clustering risk. This theoretical result is a strong contribution and of great relevance to the community.
Decision: Accept (Spotlight)