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

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\ge1$ 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.