Lower error bounds for randomized multilevel and changing dimension algorithms

DOI10.1007/978-3-642-41095-6_18MaRDI QIDQ2926226zbMATH OpenOpenAlexFDO

Authors Michael Gnewuch

Publication date 31 October 2014

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.1808

zbMATH Keywords

randomized worst case errorinfinite-dimensional integration problemweighted Hilbert spacemultilevel algorithmlower error boundquadrature methodMonte Carlo methodrandomized algorithm

Mathematics Subject Classification ID

Monte Carlo methods (65C05)

Abstract: We provide lower error bounds for randomized algorithms that approximate integrals of functions depending on an unrestricted or even infinite number of variables. More precisely, we consider the infinite-dimensional integration problem on weighted Hilbert spaces with an underlying anchored decomposition and arbitrary weights. We focus on randomized algorithms and the randomized worst case error. We study two cost models for function evaluation which depend on the number of active variables of the chosen sample points. Multilevel algorithms behave very well with respect to the first cost model, while changing dimension algorithms and also dimension-wise quadrature methods, which are based on a similar idea, can take advantage of the more generous second cost model. We prove the first non-trivial lower error bounds for randomized algorithms in these cost models and demonstrate their quality in the case of product weights. In particular, we show that the randomized changing dimension algorithms provided in [L. Plaskota, G. W. Wasilkowski, J. Complexity 27 (2011), 505--518] achieve convergence rates arbitrarily close to the optimal convergence rate.

Recommendations

• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Exact Error Estimates and Optimal Randomized Algorithms for Integration
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Cited in

(11)

• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• On weighted Hilbert spaces and integration of functions of infinitely many variables
• Exact Error Estimates and Optimal Randomized Algorithms for Integration
• Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• On tractability of linear tensor product problems for \(\infty \)-variate classes of functions
• Efficient algorithms for multivariate and \(\infty\)-variate integration with exponential weight
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
• Infinite-dimensional integration and the multivariate decomposition method
• Some results on the complexity of numerical integration

This page was built for publication: Lower error bounds for randomized multilevel and changing dimension algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2926226)