Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)

DOI10.1016/j.jco.2010.02.002zbMath1207.65005OpenAlexW2149958429MaRDI QIDQ983180

Ben Niu, Klaus Ritter, Thomas Müller-Gronbach, Fred J. Hickernell

Publication date: 3 August 2010

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2010.02.002

zbMATH Keywords

reproducing kernel Hilbert spacesMonte Carlo algorithmsrandomized algorithmsmulti-level methodworst-case errortractabilityminimal errorfixed subspace samplinginfinite-dimensional quadraturevariable subspace samplingintegration on sequence spacesworst-case cost

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Monte Carlo methods (65C05) Integration with respect to measures and other set functions (28A25) Multidimensional problems (41A63) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22) Approximate quadratures (41A55) Numerical quadrature and cubature formulas (65D32) Complexity and performance of numerical algorithms (65Y20) Randomized algorithms (68W20)

Related Items

QUASI-MONTE CARLO METHODS FOR HIGH-DIMENSIONAL INTEGRATION: THE STANDARD (WEIGHTED HILBERT SPACE) SETTING AND BEYOND ⋮ Countable tensor products of Hermite spaces and spaces of Gaussian kernels ⋮ Liberating the Dimension for Function Approximation and Integration ⋮ Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration ⋮ Numerical approximations of stochastic differential equations with non-globally Lipschitz continuous coefficients ⋮ Some Results on the Complexity of Numerical Integration ⋮ Liberating the dimension for \(L_2\)-approximation ⋮ The ANOVA decomposition of a non-smooth function of infinitely many variables can have every term smooth ⋮ On tractability of linear tensor product problems for \(\infty \)-variate classes of functions ⋮ On weighted Hilbert spaces and integration of functions of infinitely many variables ⋮ Tractability of approximation of \(\infty\)-variate functions with bounded mixed partial derivatives ⋮ Tractability of infinite-dimensional integration in the worst case and randomized settings ⋮ Efficient algorithms for multivariate and \(\infty\)-variate integration with exponential weight ⋮ Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces ⋮ Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence ⋮ Average case tractability of approximating ∞-variate functions ⋮ Quasi-Monte Carlo and \(\varepsilon\)-truncation dimension in ANOVA spaces ⋮ The cost of deterministic, adaptive, automatic algorithms: cones, not balls ⋮ Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\) ⋮ Infinite-dimensional integration and the multivariate decomposition method ⋮ Liberating the dimension for function approximation: standard information ⋮ Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights ⋮ Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition ⋮ Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness ⋮ Hyperbolic cross approximation in infinite dimensions ⋮ A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy ⋮ Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration ⋮ MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM ⋮ \( \varepsilon \)-superposition and truncation dimensions in average and probabilistic settings for \(\infty \)-variate linear problems ⋮ Infinite-dimensional integration on weighted Hilbert spaces ⋮ Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A multilevel Monte Carlo algorithm for Lévy-driven stochastic differential equations
• Liberating the dimension
• Infinite-dimensional quadrature and approximation of distributions
• Tractability of multivariate problems. Volume I: Linear information
• On irregular functionals of SDEs and the Euler scheme
• Analyzing multi-level Monte Carlo for options with non-globally Lipschitz payoff
• Deterministic and stochastic error bounds in numerical analysis
• Monte Carlo complexity of global solution of integral equations
• Average-case analysis of numerical problems
• On polynomial-time property for a class of randomized quadratures
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
• Multilevel Monte Carlo Path Simulation
• Variable Subspace Sampling and Multi-level Algorithms
• Monte Carlo Variance of Scrambled Net Quadrature
• Strong tractability of integration using scrambled Niederreiter points