Convergence guarantees for kernel-based quadrature rules in misspecified settings

Introduction

Numerical integration, or quadrature, is a fundamental task in the construction of various statistical and machine learning algorithms. For instance, in Bayesian learning, numerical integration is generally required for the computation of marginal likelihood in model selection, and for the marginalization of parameters in fully Bayesian prediction, etc . It also offers flexibility to probabilistic modeling, since, e.g., it enables us to use a prior that is not conjugate with a likelihood function.

For example, the simplest Monte Carlo method generates the points $X_{1},\dots,X_{n}$ as an i.i.d. sample from $P$ and uses equal weights $w_{1}=\cdots=w_{n}=1/n$. Convergence rates of such Monte Carlo methods are of the form $n^{-1/2}$, which can be slow for practical purposes. For instance, in situations where the evaluation of the integrand requires heavy computations, $n$ should be small and Monte Carlo would perform poorly; such situations typically appear in modern scientific and engineering applications, and thus quadratures with faster convergence rates are desirable .

One way of achieving faster rates is to exploit one’s prior knowledge or assumption about the integrand (e.g. the degree of smoothness) in the construction of a weighted point set $\{(w_{i},X_{i})\}_{i=1}^{n}$. Reproducing kernel Hilbert spaces (RKHS) have been successfully used for this purpose, with examples being Quasi Monte Carlo (QMC) methods based on RKHSs and Bayesian quadratures ; see e.g. and references therein. We will refer to such methods as kernel-based quadrature rules or simply kernel quadratures in this paper. A kernel quadrature assumes that the integrand $f$ belongs to an RKHS consisting of smooth functions (such as Sobolev spaces), and constructs the weighted points $\{(w_{i},X_{i})\}_{i=1}^{n}$ so that the worst case error in that RKHS is small. Then the error rate of the form $n^{-b},\,b\geq 1$, which is much faster than the rates of Monte Carlo methods, will be guaranteed with $b$ being a constant representing the degree of smoothness of the RKHS (e.g., the order of differentiability). Because of this nice property, kernel quadratures have been studied extensively in recent years and have started to find applications in machine learning and statistics .

However, if the integrand $f$ does not belong to the assumed RKHS (i.e. if $f$ is less smooth than assumed), there is no known theoretical guarantee for fast convergence rate or even the consistency of kernel quadratures. Such misspecification is likely to happen if one does not have the full knowledge of the integrand—such situations typically occur when the integrand is a black box function. As an illustrative example, let us consider the problem of illumination integration in computer graphics (see e.g. Sec. 5.2.4 of ). The task is to compute the total amount of light arriving at a camera in a virtual environment. This is solved by numerical integration with integrand $f(x)$ being the intensity of light arriving at the camera from a direction $x$ (angle). The value $f(x)$ is only given by simulation of the environment for each $x$, so $f$ is a black box function. In such a situation, one’s assumption on the integrand can be misspecified. Establishing convergence guarantees for such misspecified settings has been recognized as an important open problem in the literature [6, Section 6].

The main contribution of this paper is in providing general convergence guarantees for kernel-based quadrature rules in misspecified settings. Specifically, we make the following contributions:

In Section 4, we prove that consistency can be guaranteed even when the integrand $f$ does not belong to the assumed RKHS. Specifically, we derive a convergence rate of the form $n^{-\theta b}$, where $0<\theta\leq 1$ is a constant characterizing the (relative) smoothness of the integrand. In other words, the integration error decays at a speed depending on the (unknown) smoothness of the integrand. This guarantee is applicable to kernel quadratures that employ random points.

We apply this result to QMC methods called lattice rules (with randomized points) and the quadrature rule by Bach , for the setting where the RKHS is a Korobov space. We show that even when the integrand is less smooth than assumed, the error rate becomes the same as for the case when the (unknown) smoothness is known; namely, we show that these methods are adaptive to the unknown smoothness of the integrand.

As an important consequence, we show that if weighted points $\{(w_{i},X_{i})\}_{i=1}^{m}$ achieve the optimal rate in $W_{2}^{r}$, then they also achieve the optimal rate in $W_{2}^{s}$. In other words, to achieve the optimal rate for the integrand $f$ belonging to $W_{2}^{s}$, one does not need to know the smoothness $s$ of the integrand; one only needs to know its upper-bound $s\leq r$.

This paper is organized as follows. In Section 2, we describe kernel-based quadrature rules, and formally state the goal and setting of theoretical analysis in Section 3. We present our contributions in Sections 4 and 5. Proofs are collected in the supplementary material.

Our work is close to in spirit, which discusses situations where the true integrand is smoother than assumed (which is complementary to ours) and proposes a control functional approach to make kernel quadratures adaptive to the (unknown) greater smoothness. We also note that there are certain quadratures which are adaptive to less smooth integrands . On the other hand, our aim here is to provide general theoretical guarantees that are applicable to a wide class of kernel-based quadrature rules.

Kernel-based quadrature rules

Suppose that one has prior knowledge on certain properties of the integrand $f$ (e.g. its order of differentiability). A kernel quadrature exploits this knowledge by expressing it as that $f$ belongs to a certain RKHS ${\mathcal{H}}$ that possesses those properties, and then constructing weighted points $\{(w_{i},X_{i})\}_{i=1}^{n}$ so that the error of integration is small for every function in the RKHS. More precisely, it pursues the minimax strategy that aims to minimize the worst case error defined by

where $\|\cdot\|_{\mathcal{H}}$ denotes the norm of ${\mathcal{H}}$. The use of RKHS is beneficial (compared to other function spaces), because it results in an analytic expression of the worst case error (2) in terms of the reproducing kernel. Namely, one can explicitly compute (2) in the construction of $\{(w_{i},X_{i})\}_{i=1}^{n}$ as a criterion to be minimized. Below we describe this as well as examples of kernel quadratures.

Therefore, the worst case error (2) can be written as the difference between $m_{P}$ and $m_{P_{n}}$:

where $\|\cdot\|_{\mathcal{H}}$ denotes the norm of ${\mathcal{H}}$ defined by $\|f\|_{\mathcal{H}}=\sqrt{\left<f,f\right>_{\mathcal{H}}}$ for $f\in{\mathcal{H}}$. From (3), it is easy to see that for every $f\in{\mathcal{H}}$, the integration error $|P_{n}f-Pf|$ is bounded by the worst case error:

We refer the reader to for details of these derivations. Using the reproducing property of $k$, the r.h.s. of (3) can be alternately written as:

The integrals in (4) are known in closed form for many pairs of $k$ and $P$; see e.g. Table 1 of . For instance, if $P$ is the uniform distribution on ${\mathcal{X}}=^{d}$, and $k$ is the Korobov kernel described below, then $\int k(y,x)dP(x)=1$ for all $y\in{\mathcal{X}}$. To pursue the aforementioned minimax strategy, one can explicitly use the formula (4) to minimize the worst case error (2). Often ${\mathcal{H}}$ is chosen as an RKHS consisting of smooth functions, and the degree of smoothness is what a user specifies; we describe this in the example below.

2 Examples of RKHSs: Korobov spaces

The setting ${\mathcal{X}}=^{d}$ is standard in the literature on numerical integration; see e.g. . In this setting, Korobov spaces and Sobolev spaces have been widely used as RKHSs.Korobov spaces are also known as periodic Sobolev spaces in the literature [4, p.318]. We describe the former here; for the latter, see Section 5.

where $B_{2\alpha}$ denotes the $2\alpha$-th Bernoulli polynomial. $W_{\rm Kor}^{\alpha}()$ consists of periodic functions on $$whose derivatives up to$(\alpha-1)$-th are absolutely continuous and the$\alpha$-th derivative belongs to$L_{2}()$. Therefore the order$\alpha$represents the degree of smoothness of functions in$W_{\rm Kor}^{\alpha}()$.

For $d\geq 2$, the kernel of the Korobov space is given as the product of one-dimensional kernels (5):

The induced Korobov space $W_{\rm Kor}^{\alpha}(^{d})$ on $^{d}$ is then the tensor product of one-dimensional Korobov spaces: $W_{\rm Kor}^{\alpha}(^{d}):=W_{\rm Kor}^{\alpha}()\otimes\cdots\otimes W_{\rm Kor}^{\alpha}()$. Therefore it consists of functions having square-integrable mixed partial derivatives up to the order $\alpha$ in each variable. This means that by using the kernel (6) in the computation of (4), one can make an assumption that the integrand $f$ has smoothness of degree $\alpha$ in each variable. In other words, one can incorporate one’s knowledge or belief on $f$ into the construction of weighted points $\{(w_{i},X_{i})\}$ via the choice of $\alpha$.

3 Examples of kernel-based quadrature rules

We briefly describe examples of kernel-based quadrature rules.

These methods typically focus on the setting where ${\mathcal{X}}=^{d}$ with $P$ being the uniform distribution on $^{d}$, and employ equal weights $w_{i}=\cdots=w_{n}=1/n$. Popular examples are lattice rules and digital nets/sequences. Points $X_{1},\dots,X_{n}$ are selected in a deterministic way so that the worst case error (4) is as small as possible. Then such deterministic points are often randomized to obtain unbiased integral estimators, as we will explain in Section 4.2. For a review of these methods, see .

For instance, lattice rules generate $X_{1},\dots,X_{n}$ in the following way (for simplicity assume $n$ is prime). Let $z\in\{1,\dots,n-1\}^{d}$ be a generator vector. Then the points are defined as $X_{i}=\{iz/n\}\in^{d}$ for $i=1,\dots,n$. Here $z$ is selected so that the resulting worst case error (2) becomes as small as possible. The CBC (Component-By-Component) construction is a fast method that makes use of the formula (4) to achieve this; see Section 5 of and references therein. Lattice rules applied to the Korobov space $W_{\rm Kor}^{\alpha}(^{d})$ can achieve the rate $e_{n}(P,W_{\rm Kor}^{\alpha}(^{d})=O(n^{-\alpha+\xi})$ for the worst case error with $\xi>0$ arbitrarily small [11, Theorem 5.12].

These methods are applicable to general ${\mathcal{X}}$ and $P$, and employ non-uniform weights. Points $X_{1},\dots,X_{n}$ are selected either deterministically or randomly. Given the points being fixed, weights $w_{1},\dots,w_{n}$ are obtained by minimizing (4), which can be done by solving a linear system of size $n$. Such methods are called Bayesian quadratures, since the resulting estimate $P_{n}f$ in this case is exactly the posterior mean of the integral $Pf$ given “observations” $\{(X_{i},f(X_{i}))\}_{i=1}^{n}$, with the prior on the integrand $f$ being Gaussian Process with the covariance kernel $k$. We refer to for these methods.

For instance, the algorithm by Bach proceeds as follows, for the case of ${\mathcal{H}}$ being a Korobov space $W_{\rm Kor}^{\alpha}(^{d})$ and $P$ being the uniform distribution on $^{d}$: (i) Generate points $X_{1},\dots,X_{n}$ independently from the uniform distribution on $^{d}$; (ii) Compute weights $w_{1},\dots,w_{n}$ by minimizing (4), with the constraint $\sum_{i=1}^{n}w_{i}^{2}\leq 4/n$. Bach proved that this procedure gives the error rate $e_{n}(P,W_{\rm Kor}^{\alpha}(^{d})=O(n^{-\alpha+\xi})$ for $\xi$ > 0 arbitrarily small.Note that in , the degree of smoothness is expressed in terms of $s:=\alpha d$.

Setting and objective of theoretical analysis

where $b>0$ is some constant. Here we do not specify the quadrature algorithm explicitly, to establish results applicable to a wide class of kernel quadratures simultaneously.

Let $f$ be an integrand that is not included in the RKHS: $f\notin{\mathcal{H}}$. Namely, we consider a misspecified setting. Our aim is to derive convergence rates for the integration error

Analysis 1: General RKHS with random points

We first focus on kernel quadratures with random points. To this end, we need to introduce certain assumptions on (i) the construction of weighted points $\{(w_{i},X_{i})\}_{i=1}^{n}$ and on (ii) the smoothness of the integrand $f$; we discuss them in Sections 4.1 and 4.2, respectively. In particular, we introduce the notion of powers of RKHSs in Section 4.2, which enables us to characterize the (relative) smoothness of the integrand. We then state our main result in Section 4.3, and illustrate it with QMC lattice rules (with randomization) and the Bayesian quadrature by Bach in Korobov RKHSs.

There exists a probability distribution $Q$ on ${\mathcal{X}}$ satisfying the following properties: (i) $P$ has a bounded density function w.r.t. $Q$; (ii) there is a constant $D>0$ independent of $n$, such that

Assumption 1 is fairly general, as it does not specify any distribution of points $X_{1},\dots,X_{n}$, but just requires that the expectations over these points satisfy (8) for some distribution $Q$ (also note that it allows the points to be dependent). For instance, let us consider the case where $X_{1},\dots,X_{n}$ are independently generated from a user-specified distribution $Q$; in this case, $Q$ serves as a proposal distribution. Then (8) holds for $D=1$ with equality. Examples in this case include the Bayesian quadratures by Bach and Briol et al. with random points.

2 Assumption on the integrand via powers of RKHSs

To state our assumption on the integrand $f$, we need to introduce powers of RKHSs [28, Section 4]. Let $0<\theta\leq 1$ be a constant. First, with the distribution $Q$ in Assumption 1, we require that the kernel satisfies

For example, this is always satisfied if the kernel is bounded. We also assume that the support of $Q$ is entire ${\mathcal{X}}$ and that $k$ is continuous. These conditions imply Mercer’s theorem [28, Theorem 3.1 and Lemma 2.3], which guarantees the following expansion of the kernel $k$:

This is again a reproducing kernel [28, Proposition 4.2], and defines an RKHS called the $\theta$-th power of the RKHS ${\mathcal{H}}$:

This is an intermediate space between $L_{2}(Q)$ and ${\mathcal{H}}$, and the constant $0<\theta\leq 1$ determines how close ${\mathcal{H}}^{\theta}$ is to ${\mathcal{H}}$. For instance, if $\theta=1$ we have ${\mathcal{H}}^{\theta}={\mathcal{H}}$, and ${\mathcal{H}}^{\theta}$ approaches $L_{2}(Q)$ as $\theta\to+0$. Indeed, ${\mathcal{H}}^{\theta}$ is nesting w.r.t. $\theta$:

In other words, ${\mathcal{H}}^{\theta}$ gets larger as $\theta$ decreases. If ${\mathcal{H}}$ is an RKHS consisting of smooth functions, then ${\mathcal{H}}^{\theta}$ contains less smooth functions than those in ${\mathcal{H}}$; we will show this in the example below.

The integrand $f$ lies in ${\mathcal{H}}^{\theta}$ for some $0<\theta\leq 1$.

We note that Assumption 2 is equivalent to assuming that $f$ belongs to the interpolation space $[L_{2}(Q),{\mathcal{H}}]_{\theta,2}$, or lies in the range of a power of certain integral operator [28, Theorem 4.6].

Let us mention the important case where RKHS ${\mathcal{H}}$ is given as the tensor product of individual RKHSs ${\mathcal{H}}_{1},\dots,{\mathcal{H}}_{d}$ on the spaces ${\mathcal{X}}_{1},\dots,{\mathcal{X}}_{d}$, i.e., ${\mathcal{H}}={\mathcal{H}}_{1}\otimes\cdots\otimes{\mathcal{H}}_{d}$ and ${\mathcal{X}}={\mathcal{X}}_{1}\times\cdots\times{\mathcal{X}}_{d}$. In this case, if the distribution $Q$ is the product of individual distributions $Q_{1},\dots,Q_{d}$ on ${\mathcal{X}}_{1},\dots,X_{n}$, it can be easily shown that the power RKHS ${\mathcal{H}}^{\theta}$ is the tensor product of individual power RKHSs ${\mathcal{H}}_{i}^{\theta}$:

Let us consider the Korobov space $W_{\rm Kor}^{\alpha}(^{d})$ with $Q$ being the uniform distribution on $^{d}$. The Korobov kernel (5) has a Mercer representation

where $c_{i}(x):=\sqrt{2}\cos 2\pi ix$ and $s_{i}(x):=\sqrt{2}\sin 2\pi ix$. Note that $c_{0}(x):=1$ and $\{c_{i},s_{i}\}_{i=1}^{\infty}$ constitute an orthonormal basis of $L_{2}()$. From (10) and (13), the $\theta$-th power of the Korobov kernel $k_{\alpha}$ is given by

3 Result: Convergence rates for general RKHSs with random points

The following result guarantees the consistency of kernel quadratures for integrands satisfying Assumption 2, i.e., $f\in{\mathcal{H}}^{\theta}$.

(c) Let $c=1/2$. Then the rate in (14) becomes $O(n^{-\theta b})$, which shows that the integral estimator $P_{n}f$ is consistent, even when the integrand $f$ does not belong to ${\mathcal{H}}$ (recall ${\mathcal{H}}\subsetneq{\mathcal{H}}^{\theta}$ for $\theta<1$; see also (11)). The resulting rate $O(n^{-\theta b})$ is determined by $0<\theta\leq 1$ of the assumption $f\in{\mathcal{H}}^{\theta}$, which characterizes the closeness of $f$ to ${\mathcal{H}}$.

Let us illustrate Theorem 1 in the following setting described earlier. Let ${\mathcal{X}}=^{d}$, ${\mathcal{H}}=W_{\rm Kor}^{\alpha}(^{d})$, and $P$ be the uniform distribution on $^{d}$. Then ${\mathcal{H}}^{\theta}=W_{\rm Kor}^{\alpha\theta}(^{d})$, as discussed in Section 4.2. Let us consider the two methods discussed in Section 2.3: (i) the QMC lattice rules with randomization and (ii) the algorithm by Bach . For both the methods, we have $c=1/2$, and the distribution $Q$ in Assumption 1 is uniform on $^{d}$ in this setting. As mentioned before, these methods achieve the rate $n^{-\alpha+\xi}$ for arbitrarily small $\xi>0$ in the well-specified setting: $b=\alpha-\xi$ in our notation.

Then the assumption $f\in{\mathcal{H}}^{\theta}$ reads $f\in W_{\rm Kor}^{\alpha\theta}(^{d})$ for $0<\theta\leq 1$. For such an integrand $f$, we obtain the rate $O(n^{-\alpha\theta+\xi})$ in (14) with arbitrarily small $\xi>0$. This is the same rate as for a well-specified case where $W_{2}^{\alpha\theta}(^{d})$ was assumed for the construction of weighted points. Namely, we have shown that these methods are adaptive to the unknown smoothness of the integrand.

For the algorithm by Bach , we conducted simulation experiments to support this observation, by using code available from http://www.di.ens.fr/~fbach/quadrature.html. The setting is what we have described with $d=1$, and weights are obtained without regularization as in . The result is shown in Figure 1, where $r\ (=\alpha)$ denotes the assumed smoothness, and $s\ (=\alpha\theta)$ is the (unknown) smoothness of an integrand. The straight lines are (asymptotic) upper-bounds in Theorem 1 (slope $-s$ and intercept fitted for $n\geq 2^{4}$), and the corresponding solid lines are numerical results (both in log-log scales). Averages over 100 runs are shown. The result indeed shows the adaptability of the quadrature rule by Bach for the less smooth functions (i.e. $s=1,2,3$). We observed similar results for the QMC lattice rules (reported in Appendix D in the supplement).

Analysis 2: Sobolev RKHS with deterministic points

In Section 4, we have provided guarantees for methods that employ random points. However, the result does not apply to those with deterministic points, such as (a) QMC methods without randomization, (b) Bayesian quadratures with deterministic points, and (c) kernel herding .

where $\alpha:=(\alpha_{1},\dots,\alpha_{d})$ with $\alpha_{i}\geq 0$ is a multi-index with $|\alpha|:=\sum_{i=1}^{d}\alpha_{i}$, and $D^{\alpha}f$ is the $\alpha$-th (weak) derivative of $f$. Its norm is defined by $\|f\|_{W_{2}^{r}}=(\sum_{|\alpha|\leq r}\|D^{\alpha}f\|_{L_{2}}^{2})^{1/2}$. For $r>d/2$, this is an RKHS with the reproducing kernel $k$ being the Matèrn kernel; see Section 4.2.1. of for the definition.

Our assumption on the integrand $f$ is that it belongs to a Sobolev space $W_{2}^{s}$ of a lower order $s\leq r$. Note that the order $s$ represents the smoothness of $f$ (the order of differentiability). Therefore the situation $s<r$ means that $f$ is less smooth than assumed; we consider the setting where $W_{2}^{r}$ was assumed for the construction of weighted points.

The first result in this section is based on the same assumption on weights as in Theorem 1.

Let $\{(w_{i},X_{i})\}_{i=1}^{n}$ be such that $e_{n}(P;W_{2}^{r})=O(n^{-b})$ for some $b>0$ and $\sum_{i=1}^{n}w_{i}^{2}=O(n^{-2c})$ for some $0<c\leq 1/2$, as $n\to\infty$. Then for any $f\in C_{0}^{s}\cap W_{2}^{s}$ with $s\leq r$, we have

(a) Let $\theta:=s/r$. Then the rate in (15) is rewritten as $O(n^{-\theta b+(1/2-c)(1-\theta)})$, which matches the rate of Theorem 1. In other words, Theorem 2 provides a deterministic version of Theorem 1 for the special case of Sobolev spaces.

(b) Theorem 2 can be applied to quadrature rules with equally-weighted deterministic points, such as QMC methods and kernel herding . For these methods, we have $c=1/2$ and so we obtain the rate $O(n^{-sb/r})$ in (15). The minimax optimal rate in this setting (i.e., $c=1/2$) is given by $n^{-b}$ with $b=r/d$ . For these choices of $b$ and $c$, we obtain a rate of $O(n^{-s/d})$ in (15), which is exactly the optimal rate in $W_{2}^{s}$. This leads to an important consequence that the optimal rate $O(n^{-s/d})$ can be achieved for an integrand $f\in W_{2}^{s}$ without knowing the degree of smoothness $s$; one just needs to know its upper-bound $s\leq r$. Namely, any methods of optimal rates in Sobolev spaces are adaptive to lesser smoothness.

Theorems 1 and 2 require the assumption $\sum_{i=1}^{n}w_{i}^{2}=O(n^{-2c})$. However, for some algorithms, the value of $c$ may not be available. For instance, this is the case for Bayesian quadratures that compute the weights without any constraints ; see Section 2.3. Here we present a preliminary result that does not rely on the assumption on the weights. To this end, we introduce a quantity called separation radius:

In the result below, we assume that $q_{n}$ does not decrease very quickly as $n$ increases. Let ${\rm diam}(X_{1},\dots,X_{n})$ denote the diameter of the points.

Let $\{(w_{i},X_{i})\}_{i=1}^{n}$ be such that $e_{n}(P;W_{2}^{r})=O(n^{-b})$ for some $b>0$ as $n\to\infty$, $q_{n}\geq Cn^{-b/r}$ for some $C>0$, and ${\rm diam}(X_{1},\dots,X_{n})\leq 1$. Then for any $f\in C_{0}^{s}\cap W_{2}^{s}$ with $s\leq r$, we have

Conclusions

Kernel quadratures are powerful tools for numerical integration. However, their convergence guarantees had not been established in situations where integrands are less smooth than assumed, which can happen in various situations in practice. In this paper, we have provided the first known theoretical guarantees for kernel quadratures in such misspecified settings.

We wish to thank the anonymous reviewers for valuable comments. We also thank Chris Oates for fruitful discussions. This work has been supported in part by MEXT Grant-in-Aid for Scientific Research on Innovative Areas (25120012).

References

Appendix A Proof of Theorem 1

First we define the following integral operator $T:L_{2}(Q)\to L_{2}(Q)$:

From Lemmas 2.2 and 2.3 of , the condition $\int k(x,x)dQ(x)<\infty$ guarantees that $T$ is compact, positive, and self-adjoint. Therefore $T$ allows an eigen decomposition $T=\sum_{i=1}^{\infty}\mu_{i}\left<e_{i},\cdot\right>_{L_{2}(Q)}e_{i},$ where $\mu_{1}\geq\mu_{2},\dots\geq 0$ are eigenvalues of $T$ and $e_{i}$ is an eigenfunction associated with $\mu_{i}$. Based on this decomposition, define an operator $T^{\frac{\theta}{2}}:L_{2}(Q)\to L_{2}(Q)$ by $T^{\frac{\theta}{2}}:=\sum_{i=1}^{\infty}\mu_{i}^{\frac{\theta}{2}}\left<e_{i},\cdot\right>_{L_{2}(Q)}e_{i}$. Let $\mathcal{R}(T^{\frac{\theta}{2}})$ denote the range of $T^{\frac{\theta}{2}}$. From Lemma 6.4 of , we have $\mathcal{R}(T^{\frac{\theta}{2}})={\mathcal{H}}^{\theta}$. Therefore the assumption $f\in{\mathcal{H}}^{\theta}$ is equivalent to $f\in\mathcal{R}(T^{\frac{\theta}{2}})$.

For each $n$, define a constant $\lambda_{n}=n^{-2b+2c-1}$. Define a function $f_{\lambda_{n}}\in{\mathcal{H}}$ by $f_{\lambda_{n}}:=(T+\lambda_{n}I)^{-1}Tf$, where $I$ denotes the identity. From Lemma 3 of (see also Theorem 4 and Eq. (7.10) of ) and $f\in\mathcal{R}(T^{\frac{\theta}{2}})$, $f_{\lambda_{n}}$ satisfies

Below we separately bound terms $(A)$, $(B)$ and $(C)$.

To bound $(C)$, let $r$ denote the (bounded) density function of $P$ with respect to $Q$: $dP(x)=r(x)dQ(x)$.

Note that $(C)$ decays faster than $(A)$ since $c\leq 1/2$, and so the rate is dominated by $(A)$ and $(B)$. The proof is completed by substituting these terms in (19). ∎

Appendix B Proof of Theorem 2

If $\psi\in L_{1}$ is radial and satisfies (20), Calderón’s formula [12, Theorem 1.2] guarantees that any $f\in L_{2}$ can be written as

where $\psi_{t}(x):=\frac{1}{t^{d}}\psi(x/t)$. This equality should be interpreted in the following $L_{2}$ sense: if $0<\varepsilon<\delta<\infty$ and $f_{\varepsilon,\delta}(x):=\int_{\varepsilon}^{\delta}({\psi_{t}}*\psi_{t}*f)(x)\frac{dt}{t}$, then $\|f-f_{\varepsilon,\delta}\|_{L_{2}}\to 0$ as $\varepsilon\to 0$ and $\delta\to\infty$.

Following Section 3.2 of , we now take $\psi$ from Lemma 1 and consider the following approximation of $f$:

We will need the following lemma (which is not given in ).

Let $0<s\leq r$ and $\sigma>0$ be constants. If $f\in W_{2}^{s}$, the function $g_{\sigma}$ defined in (21) satisfies

The Fourier transform of $g_{\sigma}$ can be written as

In other words, ${\rm supp}(\hat{g_{\sigma}})\subset B(0,\sigma)$. Also note that for $\ |\xi|<\sigma$, we have $\int_{|\xi|/\sigma}^{1}|\hat{\psi}(t)|^{2}\frac{dt}{t}\leq\int_{0}^{1}|\hat{\psi}(t)|^{2}\frac{dt}{t}\leq 1$ from (20). Therefore,

B.2 Proof of Theorem 2

For each $n$, define a constant $\sigma_{n}=n^{\frac{b-c+1/2}{r}}$. Let $g_{\sigma_{n}}\in W_{2}^{r}$ be an approximation of $f$ defined in (21) with $\sigma=\sigma_{n}$. Then from Proposition 3.7 of , it satisfies

where $C$ is a constant depending only on $s$ and $f$. From Lemma 2 in Appendix B.1, $g_{\sigma_{n}}$ also satisfies

Below we separately bound terms $(A)$, $(B)$ and $(C)$.

Since $c\leq 1/2$, note that $(C)$ decays faster than $(A)$ and so the rate is dominated by $(A)$ and $(B)$. The proof is completed by inserting these terms in (24).

Appendix C Proof of Theorem 3

Define a constant $C_{d}\sigma_{n}=n^{b/r}$, where $C_{d}:=24(\frac{\sqrt{\pi}}{3}\Gamma(\frac{d+2}{2}))^{\frac{2}{d+1}}$ with $\Gamma$ being the Gamma function, so that $\sigma_{n}\geq C_{d}/q_{n}$. Then from Theorem 3.5 and Theorem 3.10 of , there exists a function $f_{\sigma_{n}}\in W_{2}^{r}$ satisfying the following properties:

where $C_{s,d}$ is a constant only depending on $s$ and $d$.

Moreover, from the discussion in p. 298 of , this function also satisfies

where $C$ is a constant only depending on $s$, $d$, and the kernel $k$.

We separately bound terms $(A)$, $(B)$ and $(C)$.

The proof is completed by inserting these bounds in (28)

Appendix D Experimental results for QMC lattice rules

We conducted simulation experiments with QMC lattice rules to show their adaptability to integrands less smooth than assumed. The RKHS is the Korobov space of dimension $d=2$. For the construction of generator vectors, we employed a fast method for component-by-component (CBC) construction by , using the code provided at https://people.cs.kuleuven.be/~dirk.nuyens/fast-cbc/. This method constructs a generator vector for lattice points whose number $n$ is prime. Here we did not apply randomization to the generated points, so they were deterministic. We would like to note that this situation is not covered by our current theoretical guarantees; the results in Section 4 only apply to random points, and those in Section 5 apply to deterministic points with Sobolev spaces.

The results are shown in Figure 2, where $r\ (=\alpha)$ denotes the assumed smoothness, and $s\ (=\alpha\theta)$ is the (unknown) smoothness of an integrand. The straight lines are (asymptotic) upper-bounds in Theorem 1 (slope $-s$ and intercept fitted for $n\geq 2^{4}$), and the corresponding solid lines are numerical results (both in log-log scales). For $s=4$ with large sample sizes, underflow occurred with our computational environment as the errors were quite small, so we do not report these results. The results indicate the adaptability of the QMC lattice rules for the less smooth functions (i.e. $s=1,2,3$).