Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This article studies a family of quadrature rules suited for functions that belongs to an RKHS. The proposed construction is based on a recombination algorithm that takes a discrete measure $\nu_{N}$, that approximates the initial measure $\mu$ (for example, a Monte Carlo approximation),  and outputs another discrete  measure $\mu_{n}$. The weights of the quadrature are obtained by enforcing that the quadrature rule is exact on n functions $\phi_{1}, \dots, \phi_{n}$ that are taken to be equal to $\phi_{i} := k_{0}(x_{i},.)$ where $k_{0}$ is a ‘low rank’ kernel. 

The contributions of the paper may be summarised as follows:
- A generic result (Theorem 1) that gives the upper bound of the worst-case error (on the unit ball of the RKHS) for the proposed algorithm for an arbitrary 'low rank' kernel $k_0$
- The instantiation of Theorem 1 to the case when $\nu_{N}$ is the Monte Carlo approximation of $\mu$ and $k_0$ is obtained from the Mercer decomposition of $k$
- The instantiation of Theorem 1 to the case when $\nu_{N}$ is the Monte Carlo approximation of $\mu$ and $k_0$ is obtained through the Nyström approximation
- Several numerical simulations that illustrate the theoretical rates. 

The article is well written and the proven results were widely discussed and compared to the existing results in the literature. 


strengths_and_weaknesses: 

Strengths:
* The empirical versions of the algorithms are flexible and may be used in domains where the eigenfunctions of the integration operator are not tractable.
* The proposed quadrature rules are convex, which is an important property in misspecified settings
* The theoretical analysis is insightful and may be used for other applications 


Weaknesses:
 
* The empirical versions of the quadrature (when $\nu_N$ is Monte Carlo approximation of $\mu$) are very useful in practice, yet they come with weak convergence rates: the second term in the r.h.s. of the bound (5) in Theorem 1 is $\mathcal{O}(1/N)$, which is typically a slow rate in the kernel-based quadrature literature. 
questions: 
Questions and suggestions:

* In Section 3, it is not clear what you mean by the opt version: the optimization of (15) is done in the simplex or $R^{N}$?

* How do you explain the fact that in Corollary 2 the boundedness assumption (condition (a) in Theorem 8) is not required?

* It would be nice to add the N-th eigenvalue as a benchmark in the graphs

* Theorem 8 and Theorem 10 were mentioned implicitly in Table 1. In my opinion, I believe that they deserve to get an explicit mention in the main paper. 
limitations: -
review_title: null

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 problem focuses on the quadrature problem, more specifically on bounding the maximum mean discrepancy between a quadrature approximation mu_Q= sum w_i delta_{x_i} and a target distribution mu, where the (xi) is a n-subset of an available bigger sample DN of i.i.d. samples of mu.
They focus on convex rules i.e. when the weights are positive and sum to 1.

The main idea is to consider a basis of n functions phi_1.. phi_n approximating RKHS functions, then sample N points (y1…yN), and select a n-subset (x1..xn) reweighted by (w1..wn). There are thus two sources of error (1) approximating k/the RKHS by a n-finite dimensional one, e.g. through Nystrom or Mercer approximations, (2) the empirical measure supported on y1…yN.

They provide several results, in particular th 1, which becomes more explicit in Cor 2 through Mercer approximation and Cor 4 through Nystrom approximation. The authors evaluate empirically their algorithm on small dimensional datasets (with either Nystrom or Mercer approximations) and compare it to the Monte Carlo rate , uniform grid and iid Bayes (weights minimizing equation 14) and demonstrate it achieves faster rates in practice than Monte Carlo.

strengths_and_weaknesses: Strengths
The paper is quite well written, and well referenced regarding kernel quadrature rules. It tackles an important problem, quadrature rules, which enables to approximate integrals accurately, with applications in Bayesian inference for instance.  The proposed algorithm has complexity O( nN + n 3 log(N/n) ) which is competitive with herding in high dimensions, where the latter become intractable because of the global optimization subroutine. 

Weaknesses

Maybe I am missing something, but I think the bound in Theorem 1 does not advocate for faster rates than Monte Carlo.

In theorem 1, the expected squared MMD (where the expectation is taken wrt the available sample DN) is bounded by a constant c_1(n) (later on it will depend on n) + c_2/N. 

Classical bounds on (squared) MMD (e.g. “A kernel two sample test”, Gretton et al.) between the empirical measure on DN (without quadrature weights) and the target mu is already of order c_2/N. Hence, from this bound it does not seem that the quadrature provides a better approximation of the target distribution mu, since if I understood well, Qn  (of size n \le N) can be of the same size than DN (size N) a priori.

The bound of Theorem 1 starts to be interesting if n is always much smaller than N and the term int(k-k0)dmu is much smaller than 1/n.
The first condition is typically satisfied (the authors claim l98 they will take N ~ n^2 ) later, so c_2/N becomes of order c_2/n^2, which is faster than Monte Carlo (c/n) . However, for the second term c_1(n)  it is less clear. Corollary 2 (Mercer approximation) yields a term c_1(n), indeed decreasing with n,  but it is not clear how fast c_1(n) decreases, faster than 1/n? Same question for Corollary 4 (Nystrom approximation) which is not very explicit in n. 

if it is not faster than 1/n, then the quadrature rule (supported on n points) does not have a better upper bound currently than any empirical measure supported on n points of DN.

However, the experimental results show that the steep is lower (better) than the Monte Carlo rate, which encourages the method. 
In the experiments, it would be interesting to report the steeps and understand the dependence of the rate with respect to n but also with respect to the dimension.
 
For these reasons, I tend to reject the paper, but I am ready to revise my opinion if the authors can clarify their results.

questions: - Is it possible to clarify the dependence in number of samples in the quadrature n and dimension d in the bounds of Cor 1 and 2?
- can you report the slopes for various dimensions and infer a dependence dimension experimentally?


Minor comments
l55: “hybrid approaches” -> hybrid between what and what?
l69: a subset (xi)_{i=1}^n (n instead of N)
l71: (iii) in practice, constructing N>> n samples can be a challenge as well (eg MCMC methods are expensive)
l138: Nystom 
limitations: The limitations of the theoretical and empirical results could be discussed much more extensively, see comments above.
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: The authors investigate the properties of kernel quadrature rules with convex weights. The authors proposed new algorithms that take as input i.i.d. samples, a suitable kernel, and provide a small integration error in the worst-case over the associated reproducing kernel Hilbert space. Two strategies are proposed based on kernel approximations via Mercer decompositions and Nystrom approximations along with recombination algorithms for point measures.


strengths_and_weaknesses: 
Strengths of the work include (a) perhaps a novel combination of two concepts: Spectral properties of kernels, and recombination results about point measured, and (b) the ability to simultaneously analyze strategies involving Mercer decomposition, and Nystrom approximations.

Limitations are (a) lack of clear discussion on when the proposed methods improve over prior strategies, while a summary is provided in Table 1, it is unclear if the methods indeed provide an improvement, (b) missing prior works, and (c) lack of stronger baselines that can be used in experiments. (see questions for more details),

questions: 

I have a few major concerns:

1. For their Nystrom strategies (which are generically feasible for implementation), it is unclear if the mentioned bound can provide a better than Monte Carlo rate since that needs n / sqrt(l) < 1/ N which in turn means l > n^2 * N --- which is necessarily larger than N. On the other hand, the Mercer strategy in this work has a key limitation as it requires the knowledge of eigenfunctions, which is unknown for almost any generic (k, P) pair (other than a few exceptional pairs). Can the authors provide a detailed discussion about this aspect---as to the achieved rate in terms of the total number of queries---and provide concrete examples where their methods provide an improvement over prior strategies? In particular, further unpacking of Table 1 is needed, and it is unclear to me if the proposed strategy (E.g., see Table 2 https://arxiv.org/pdf/2105.05842.pdf].)

2.  This work is missing relevant references on recent new developments on Kernel thinning (KT)---which would have a tick on all C, M, E, in Table 1 of this work. Moreover, KT provides an error of order 1/n^2 + 1/N (in terms of the notation of this work) up to logarithmic factors for the WCE with n point output, and N point input (typically referred to as MMD in the literature). See [Table 2 https://arxiv.org/pdf/2105.05842.pdf], [Table 3 https://arxiv.org/pdf/2110.01593.pdf] for error rates, and [Example 6 https://arxiv.org/abs/2111.07941] for the new variant that provides near-linear runtime (N log^3 N), which is significantly faster than the strategies mentioned. 

3. [Sec 1.2 https://arxiv.org/pdf/2105.05842.pdf] (KT paper) would also be a useful reference for some other works like P-greedy, black box importance sampling, etc. which are not referenced here and are relevant for the work.

4. For experiments, I believe KT should be added. Moreover, like the strategies in this work, even KT and herding output should be combined with 'opt' to provide a fairer comparison to their best-performing variant (N.+emp.opt]. 

5. At least one of the algorithms from Remark 1 should be discussed with some brief intuition for the readers to become aware of the high-level ideas used.

6. What is the probability in Thm 3 / Corr 4 taken over (is it the draw of Z)?

Minor comments:

- l 38/39: A reference is needed.

limitations: See questions.
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: The paper addresses a problem of kernel quadrature rules and proposes a new quadrature with positive weights that leverages recombination algorithms (stemming from Caratheodory’s Theorem) and either Mercer’s or Nystrom approximation of the kernel. Based on each version, there is also a derivation of corresponding convergence rates. The proposed methods are empirically verified on a classical setup for testing efficiency of general kernel quadrature methods.

strengths_and_weaknesses: Originality: 

The paper addresses an established task of kernel quadratures. The method is based on well-known techniques of recombination and spectral kernel approximation combined in a unexplored way to obtain convex quadrature method. The paper emphasizes the major difference of their method being th convex weights of the quadrature points.

Quality: 

I’m not entirely convinced by the very brief motivation for the convex weights, perhaps it would benefit the paper to elaborate the need for the convex quadrature in a more comprehensible way.

It seems that extensive supplementary material provides a substantial theoretical support for the proposed method, unfortunately, I was not able to check that in detail.

The Experimental Section lacks explicit comparison with the other practical methods apart from the worst and best case baselines on a known setting with Sobolev and Korobov spaces, e.g. there is no DPP-based method in the Figures.

It is also not immediately clear whether convexity of the weights has a crucial role in any performance advantages, thus the motivation for convex quadrature rules lack empirical support (at least in the experiments conducted and the conclusions drawn from their results).

The only method that is consistently bringing advantages across all Figures is +opt variation which assumes knowledge of expectations andadditional optimization over the weights, however Table 1 does not include this information which brings a little bit of a confusion. I wish that was a little bit more clearly stated in the paper.

Clarity:

There is a general issue with exposition, at least for someone less acquainted with the area. Abstract as well as Related Work would greatly benefit from a more extended exposition. As mentioned above, the motivation for the convex weights is also very short and could be made more clear with more explanations. Experimental Section doesn’t make it any clearer in this regard too, perhaps adding an ablation study coud offer more transparent understanding. The paper doesn’t discuss how their derived bounds compare against other methods, even under different assumptions, perhaps there should be matching setups allowing comparison.

Significance:

It is definitely an interesting method, and perhaps will raise a good amount of interest in the kernel community. However, I’m not sure whether the paper makes a good work at demonstrating the advantages of the proposed approach over existing methods. It first argues that convex quadrature is essential, but later fails to confirm this empirically, unfortunately, and it seems positive weights do not play a major role in theoretical analysis neither.

questions: What are the consequences of treating a less general quadrature problem without weighting function $g$?

Could authors elaborate more on the need of convex quadrature? And how the positiveness of weights affects practical performance?

How the choice of recombination algorithm affects the performance?

limitations: The potential negative societal impact is not applicable to this submission.

The paper addresses a less general case of kernel quadrature, i.e. there is no weights function $g$ in the problem formulation (also stated in the related literature paragraph).

The method implies an ability to sample datapoints from target measure for recombination technique, however this could be problematic (this limitation is also stated by authors).
review_title: null

Meta-review: metareview: We thank the authors and reviewers for their work throughout the reviewing process. The paper generated detailed and interesting discussions. While there remains minor concerns, we are confident that the paper brings new elements and will generate exciting discussions in the kernel quadrature community, and we are happy to recommend acceptance. We trust the authors to use all information in the discussion threads to polish the camera-ready version of the paper.
confidence: Certain
Decision: Accept