Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The abstract already presents four contributions (first, second, etc.) of the paper. My summary: the submission extends the Kernel Thinning algorithm recently proposed by Dwivedi and Mackey (2021) to more general settings (kernel types). It also removes some dimension-dependent log factors in the bound. 
main_review: In terms of writing, the paper is quite technical and lacks intuition. I don't think putting so many results in the main body is necessary, e.g., there are six remarks after Theorem 1. 

I also have some concerns regarding the significance of the results. The summary from the authors emphasizes the error improvement from $n^{-1/4}$ to $\sqrt{\log n/ n}$, but this seems to be the main contribution of the prior work by Dwivedi and Mackey (2021). As for the current submission, the improvements are in the log factors. I didn't check the proofs of these two papers as they have 85 pages in total. Given that the prior work is twice the current length, I wonder if the authors can explain the technical novelty of the present paper that leads to the logarithmic improvement. In other words, why the prior work has the log factors?

The second contribution of the submission is  "we show that, for analytic kernels, like Gaussian and inverse multiquadric, target kernel KT admits maximum mean discrepancy (MMD) guarantees comparable to square-root KT without the need for an explicit square-root kernel." I know this is related to Fourier transforms. Do the authors know under what condition the $\mathbf{explicit}$ square-root kernels exist?

The experiments seem to be generated by the same software/scripts Dwivedi and Mackey (2021) used. It will be good if the author can also compare the run time of these algorithms. The proposed heuristics inherit the better rates the Dwivedi and Mackey (2021) algorithm provides and its quadratic time complexity. I would think that a more significant contribution would be reducing this algorithmic complexity, especially important for practical applications. 
summary_of_the_review: I don't find the contribution of the current paper very significant compared to the Dwivedi and Mackey (2021) work. The paper adopts several critical theoretical contributions and algorithm designs from the prior work, maybe also the code. The writing is also technical and lacks intuitions and insights. I suggest the authors focus on improving the quadratic time-complexity instead, which should increase the significance/popularity of both works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This article studies a generalization of kernel thinning previously proposed in Dwivedi and Mackey (2021). The authors proposed a new variant of kernel thinning that does not require the knowledge of the square root of the kernel, for which they proved single function guarantees as well as the MMD guarantees. Several numerical simulations were conducted to support the theoretical claims.
main_review: It is hard to follow the ‘flow’ of this work. For instance, the definition of  KT-Split is only given in the appendix. It is preferable to recall briefly the principle and the intuition behind this algorithm in the main paper. The reader may ask some legitimate questions: what is the role of the kernel k_{split} in the algorithm? What are the benefits we gain from studying power kernel thinning?

The presentation of the paper is non-conventional. For example, Theorem 1 is followed by many remarks. The content of these remarks may fit in one or two paragraphs and the presentation would be more elegant.
summary_of_the_review: Up to my knowledge, the proposed algorithms and the corresponding theoretical guarantees are new in the community. However, the manuscript is heavily technical and dense. I am afraid that only readers familiar with kernel thinning may grasp the contribution of this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes "generalised kernel thinning", which builds on the "kernel thinning" (KT) algorithm of [Dwivedi and Mackey, 2021]. The main generalisation is to replace the square-root kernel in the algorithm with k_{split}, which results in applicability without the knowledge of the square-root kernel, and theoretical guarantees are proved. Moreover, two instantiations of this generalisation are proposed, the alpha-power KT and KT+. 
main_review: I must apologise in advance that I am not an expert in the field of thinning, and the vast majority of the references were unfamiliar to me. However, I saw much more positives than negatives while reading the paper. 

Firstly, the paper was written in a clear manner, with a very convincing motivation of the problem. The contributions were well outlined in the context of existing works. The significance of the theoretical results were clear, and as far as I could see, the results were correct. One aspect I particularly appreciated was the amount of effort put into analysing all the different types of distributions and kernels, and summarising them in various tables. 
summary_of_the_review: The paper motivates the problem in a clear and convincing way even for a non-expert, and clearly outlines its contributions. The results are significant, and as far as I can see, correct and sound. I recommend this paper to be accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper's claims seem correct and sound. Claims are substantiated by a theoretical analysis, though the bulk of the paper's ideology comes from the previous publication (which the current paper extends). Experiments seem very similar to the previous paper's experiments.
main_review: The paper seems as an extension of results of a previous paper. The algorithm for finding a subsample is the same, the first part of it (KT-split) is applied with a general kernel (split kernel), which may differ from square root kernel. Therefore, an interesting question is how the analysis given in arXiv:2105.05842 corresponds with an analysis given in terms of RKHS covering number. Is a new analysis leads to the same thinning error, when applied to square root kernel (or, the square root is somehow special?).

Figure 2 shows that Root KT and Target KT give the same error as a function of coreset size. Is there any explanation of such behavior?

Experimental part convinces that root/target KT gives smaller errors than iid, though Fig 3 shows more complicated picture when KT+ is compared with ST (Hitch IMQ k). Is there any explanation of that?
summary_of_the_review: I believe this is a borderline paper. Some aspects of it were published before. A new analysis is presented (based on RKHS covering number).
review_title: null

Meta-review: The focus of the paper is kernel thinning, i.e. the extraction of a core set from a sample with good integration properties meant in MMD (maximum mean discrepancy, hence worst case) sense. Particularly, the authors propose generalizations of the kernel thinning method (Dwivedi and Mackey, 2021) which relax the assumptions imposed on the kernel (k) and the target distribution (P), and possess tighter performance guarantees.

Designing compressed representation of samples for integration is a fundamental problem in machine learning and statistics with a large number of successful applications. As assessed by the reviewers, the authors deliver important new theoretical insights in the area which can be also of clear practical interest. They also pointed out that the self-containedness of the paper could be improved and additional intuition would help the dissemination of the results among the members of the ICLR/ML audience.
Decision: Accept (Poster)