English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the optimal rate of convergence of algorithms for integrating and approximating d-variate functions. We consider functions that belong to reproducing kernel Hilbert spaces H(Kd). Here Kd is an arbitrary kernel all of whose partial derivatives up to order r satisfy a Holder-type condition with exponent 2 . We discuss algorithms using n function values and analyze their rate of convergence as n tends to innit y. Without loss of generality it is enough to consider linear algorithms. We focus on universal algorithms, whose weights and sample points depend only on d, r and but not on the specic kernel Kd, and non-universal algorithms whose weights and sample points may depend additionally on the specic kernel Kd. We prove that the optimal (largest possible) rate of convergence of universal algorithms is (r + )=d. This holds for both multivariate integration and approximation. Furthermore, we prove that the optimal rate of convergence of non-universal algorithms is 1=2 + (r + )=d for multivariate integration and a + (r + )=d with a 2 (1=(4 + 4(r + )=d); 1=2) for multivariate approximation. Hence, universal algorithms suer from the curse of dimensionality if d is large relative to r + . Indeed, the computation of an "-approximation requires then of order " d=(r+ ) function values which is exponential in d. On the other hand, non-universal algorithms require of order " p function values with p 2 for multivariate integration and p 4 for multivariate approximation. Hence, the curse of dimensionality is not present for non-universal algorithms in the exponent of " 1. Thus, the curse of dimension is the price we have to pay for using universal algorithms. On the other hand, if r + is large relative to d then the optimal rates of convergence for universal and non-universal algorithms are approximately the same. We also consider the case when we have additional knowledge that the kernel Kd has product structure, Kd;r; = d j=1Krj ; j . Here Krj ; j are arbitrary univariate kernels that are rj times continuously dieren tiable and whose deriva- tives up to order rj satisfy a Holder-type condition with exponent 2 j. In this case, the optimal order of convergence of universal algorithms is q := minj=1;2;:::;d(rj + j) for both multivariate integration and approximation. For non-universal algorithms the optimal rate of convergence is 1=2 + q for multivariate integration and a + q with a 2 (1=(4 + 4q); 1=2) for multivariate approximation. The optimal rate of convergence of universal algorithms for product kernels depends on d only through the minimum of the local regularities rj + j. For example, if we assume that rj 1 or j > 0 for all j, then the optimal rate is at least minf1; g. Hence, the computation of an "-approximation requires of order " minf1; g function values, and the curse of dimensionality is not present in the exponent of " 1. This shows the power of the product form of reproducing kernels in breaking the curse of dimensionality, even for universal algorithms.

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