Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition

Abstract

In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of ANOVA-type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first non-trivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or non-linear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Müller-Gronbach, B. Niu, K. Ritter, J. Complexity 26 (2010), 229-254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi-Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.

31 pages, 0 figures

Cited by in corpus (12)

• Approximation of high-dimensional periodic functions with Fourier-based methods
• The Numerical Approximation of Nonlinear Functionals and Functional Differential Equations
• Dynamically orthogonal tensor methods for high-dimensional nonlinear PDEs
• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Dynamic tensor approximation of high-dimensional nonlinear PDEs
• Embeddings of Weighted Hilbert Spaces and Applications to Multivariate and Infinite-Dimensional Integration
• Stability analysis of hierarchical tensor methods for time-dependent PDEs
• Embeddings for Infinite-Dimensional Integration and $L_2$-Approximation with Increasing Smoothness
• Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
• A Generalized Faulhaber Inequality, Improved Bracketing Covers, and Applications to Discrepancy
• Learning multivariate functions with low-dimensional structures using polynomial bases
• Infinite-Variate $L^2$-Approximation with Nested Subspace Sampling