Convergence guarantees for kernel-based quadrature rules in misspecified settings
Kernel-based quadrature rules are becoming important in machine learning and statistics, as they achieve super-√ n convergence rates in numerical integration, and thus provide alternatives to Monte Carlo integration in challenging settings where integrands are expensive to evaluate or where integrands are high dimensional. These rules are based on the assumption that the integrand has a certain degree of smoothness, which is expressed as that the integrand belongs to a certain reproducing kernel Hilbert space (RKHS). However, this assumption can be violated in practice (e.g., when the integrand is a black box function), and no general theory has been established for the convergence of kernel quadratures in such misspecified settings. Our contribution is in proving that kernel quadratures can be consistent even when the integrand does not belong to the assumed RKHS, i.e., when the integrand is less smooth than assumed. Specifically, we derive convergence rates that depend on the (unknown) lesser smoothness of the integrand, where the degree of smoothness is expressed via powers of RKHSs or via Sobolev spaces.
%%% UPDATE %%% Thank you for your concise response. I remain confident that this paper would make a solid contribution to NIPS this year. %%% END %%%   This paper extends results on kernel quadrature to the misspecified setting, where the integrand is not smooth enough to belong to the RKHS H characterised by the kernel. The main result of the paper is that kernel quadrature is adaptive to unknown smoothness; this is provided that the integrand belongs to a RKHS on the Hilbert scale between H and L2.
I would like to congratulate the authors on an excellent paper. This is an important contribution to the literature on kernel quadrature and established useful theoretical guidance to practitioners - namely, to err on the side of using kernels that are `too smooth' and allow automatic adaptation to occur. Given the importance of numerical integration, I expect this work to have substantial impact.  I have some very minor comments.  The literature tends to refer to "kernel quadrature" when the weights w_i are those that minimise the worst-case error for fixed locations X_i, i.e. the weights w_i that are used in Bayesian quadrature. This agrees with your definition on page 3, line 105. However, defined in this way, quasi Monte Carlo (QMC) is *not* kernel quadrature (the weights are uniform weights). I do take the authors' point that QMC can be studied in RKHS, but I would clarify the wording on page 1, line 26 to emphasise that QMC is not itself a kernel quadrature method.  This work is close in spirit to ref [17] in the paper. In [17] it was argued that a QMC lattice rule for functions that are rougher than the integrand could be compensated for by building control variates with a kernel that was smoother than the integrand. The argument of adapting to unknown smoothness was also made in [17]. I believe the present paper implies that an alternative to [17] is to simply use a QMC lattice rule that is for smoother functions. This work is perhaps a nicer solution compared to [17].  On page 3, line 102, the phrase "it suffices" is a bit misleading. You are *choosing* to pursue a minimax strategy, but until this point the goal was not stated in terms this explicit.  In the supplement on page 1, line 13, I don't think Smale and Zhou (2007) is the original reference for this result (they cite another work).