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

DOI10.1016/J.JAT.2014.04.014zbMATH Open1296.41025arXiv1306.2821OpenAlexW1984820072MaRDI QIDQ2016136FDOQ2016136

Josef Dick, Michael Gnewuch

Publication date: 19 June 2014

Published in: Journal of Approximation Theory (Search for Journal in Brave)

Abstract: We study the numerical integration problem for functions with infinitely many variables. The function spaces of integrands we consider are weighted reproducing kernel Hilbert spaces with norms related to the ANOVA decomposition of the integrands. The weights model the relative importance of different groups of variables. We investigate randomized quadrature algorithms and measure their quality by estimating the randomized worst-case integration error. In particular, we provide lower error bounds for a very general class of randomized algorithms that includes non-linear and adaptive algorithms. Furthermore, we propose new randomized changing dimension algorithms and present favorable upper error bounds. For product weights and finite-intersection weights our lower and upper error bounds match and show that our changing dimension algorithms are optimal in the sense that they achieve convergence rates arbitrarily close to the best possible convergence rate. As more specific examples, we discuss unanchored Sobolev spaces of different degrees of smoothness and randomized changing dimension algorithms that use as building blocks scrambled polynomial lattice rules. Our analysis extends the analysis given in [J. Baldeaux, M. Gnewuch. Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition. arXiv:1209.0882v1 [math.NA], Preprint 2012]. In contrast to the previous article we now investigate a different cost model for algorithms. With respect to that cost model, randomized multilevel algorithms cannot, in general, achieve optimal convergence rates, but, as we prove for important classes of weights, changing dimension algorithms actually can.

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

zbMATH Keywords

numerical integrationrandomized algorithmsANOVA decompositionquasi-Monte Carlo methodmultivariate decomposition methoddimension-wise quadrature method

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Numerical quadrature and cubature formulas (65D32) Analysis of algorithms (68W40) Approximate quadratures (41A55) Integration with respect to measures and other set functions (28A25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Smoothing noisy data with spline functions: Estimating the correct degree of smoothing by the method of generalized cross-validation
• Theory of Reproducing Kernels
• Multilevel Monte Carlo Path Simulation
• Monte Carlo complexity of global solution of integral equations
• A class of generalized Walsh functions
• Quasi-Monte Carlo Finite Element Methods for a Class of Elliptic Partial Differential Equations with Random Coefficients
• Infinite-dimensional quadrature and approximation of distributions
• Deterministic and stochastic error bounds in numerical analysis
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Low-discrepancy point sets obtained by digital constructions over finite fields
• QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach
• Tractability of multivariate problems. Volume I: Linear information
• Toward real-time pricing of complex financial derivatives
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• On decompositions of multivariate functions
• High-dimensional integration: The quasi-Monte Carlo way
• H = W
• Estimating Mean Dimensionality of Analysis of Variance Decompositions
• Good lattice rules in weighted Korobov spaces with general weights
• Liberating the dimension
• Dimension-wise integration of high-dimensional functions with applications to finance
• Infinite-dimensional integration on weighted Hilbert spaces
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
• Monte Carlo Simulation of Stochastic Integrals when the Cost of Function Evaluation Is Dimension Dependent
• Liberating the dimension for \(L_2\)-approximation
• On tractability of path integration
• Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Liberating the dimension for function approximation: standard information
• Liberating the dimension for function approximation
• Tractability of infinite-dimensional integration in the worst case and randomized settings
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• On weighted Hilbert spaces and integration of functions of infinitely many variables
• Lower Error Bounds for Randomized Multilevel and Changing Dimension Algorithms
• Optimal Randomized Multilevel Algorithms for Infinite-Dimensional Integration on Function Spaces with ANOVA-Type Decomposition
• Scrambled Polynomial Lattice Rules for Infinite-Dimensional Integration
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• The smoothing effect of the ANOVA decomposition
• Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
• Randomization for continuous problems
• The smoothing effect of integration in $\mathbb {R}^d$ and the ANOVA decomposition

Cited In (13)

• Some Results on the Complexity of Numerical 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
• Hyperbolic cross approximation in infinite dimensions
• Countable tensor products of Hermite spaces and spaces of Gaussian kernels
• On equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in \(L_1\) or \(L_\infty\)
• MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
• 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
• A note on the periodic \(L_2\)-discrepancy of Korobov's \(p\)-sets
• Infinite-dimensional integration and the multivariate decomposition method
• The ANOVA decomposition of a non-smooth function of infinitely many variables can have every term smooth
• Construction of interlaced scrambled polynomial lattice rules of arbitrary high order

This page was built for publication: Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition

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