On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation

Abstract:

We study the maximal rate of convergence (mrc) of algorithms for (multivariate) integration and approximation of $d$-variate functions from reproducing kernel Hilbert spaces $H(K_{d})$. Here $K_{d}$ is an arbitrary kernel all of whose partial derivatives up to order $r$ satisfy a Hölder-type condition with exponent $2\beta$. Algorithms use $n$ function values and we analyze their rate of convergence as $n$ tends to infinity. We focus on universal algorithms which depend on $d$, $r$, and $\beta$ but not on the specific kernel $K_d$, and nonuniversal algorithms which may depend additionally on $K_d$. For universal algorithms the mrc is $(r+\beta )/d$ for both integration and approximation, and for nonuniversal algorithms it is $1/2+ (r+\beta )/d$ for integration and $a+(r+\beta )/d$ with $a\in [1/(4+4(r+\beta )/d),1/2]$ for approximation. Hence, the mrc for universal algorithms suffers from the curse of dimensionality if $d$ is large relative to $r+\beta$, whereas the mrc for nonuniversal algorithms does not since it is always at least $1/2$ for integration, and $1/4$ for approximation. This is the price we have to pay for using universal algorithms. On the other hand, if $r+\beta$ is large relative to $d$, then the mrc for universal and nonuniversal algorithms is approximately the same. We also consider the case when we have the additional knowledge that the kernel $K_d$ has product structure, $K_{d,r,\beta }=\bigotimes _{j=1}^dK_{r_j,\beta _j}$. Here $K_{r_j,\beta _j}$ are some univariate kernels whose all derivatives up to order $r_j$ satisfy a Hölder-type condition with exponent $2\beta _j$. Then the mrc for universal algorithms is $q:=\min _{j=1,2,\dots ,d }(r_j+\beta _j)$ for both integration and approximation, and for nonuniversal algorithms it is $1/2 +q$ for integration and $a+q$ with $a\in [1/(4+4q),1/2]$ for approximation. If $r_j\ge 1$ or $\beta _j\ge \beta >0$ for all $j$, then the mrc is at least $\min (1,\beta )$, and the curse of dimensionality is not present. Hence, the product form of reproducing kernels breaks the curse of dimensionality even for universal algorithms.