When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

DOI10.1006/jcom.1997.0463zbMath1032.65011OpenAlexW1981743146MaRDI QIDQ1265135

Publication date: 3 December 2003

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

Full work available at URL: https://semanticscholar.org/paper/054a203422d121cd4464d953846f53576a41c573

zbMATH Keywords

multivariate integration quasi-Monte Carlo algorithms worst case error bounds

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Pseudo-random numbers; Monte Carlo methods (11K45)

Related Items

Generalized maximum entropy estimation, Scaled lattice rules for integration on ℝ^{𝕕} achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces, Strong tractability of multivariate integration using quasi–Monte Carlo algorithms, EC-tractability of multivariate approximation in Hermite spaces for the standard information class, On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}, On strong tractability of weighted multivariate integration, Reducing the construction cost of the component-by-component construction of good lattice rules, Strong tractability of integration using scrambled Niederreiter points, Construction algorithms for polynomial lattice rules for multivariate integration, Entropy, Randomization, Derandomization, and Discrepancy, On Figures of Merit for Randomly-Shifted Lattice Rules, A Global Adaptive Quasi-Monte Carlo Algorithm for Functions of Low Truncation Dimension Applied to Problems from Finance, Construction-Free Median Quasi-Monte Carlo Rules for Function Spaces with Unspecified Smoothness and General Weights, Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate, The curse of dimensionality for the $L_p$-discrepancy with finite $p$, FDM-PINN: Physics-informed neural network based on fictitious domain method, Bypassing the quadrature exactness assumption of hyperinterpolation on the sphere, Higher-Order Monte Carlo through Cubic Stratification, Numerical smoothing with hierarchical adaptive sparse grids and quasi-Monte Carlo methods for efficient option pricing, Sequentially weighted uniform designs, Tractability of $L_2$-approximation and integration in weighted Hermite spaces of finite smoothness, On a reduced component-by-component digit-by-digit construction of lattice point sets, Quasi--Monte Carlo Integration for Affine-Parametric, Elliptic PDEs: Local Supports and Product Weights, A Universal Median Quasi-Monte Carlo Integration, A Measure Approximation for Distributionally Robust PDE-Constrained Optimization Problems, Discrepancy of Digital Sequences: New Results on a Classical QMC Topic, Multilevel QMC with Product Weights for Affine-Parametric, Elliptic PDEs, Modern Monte Carlo Variants for Uncertainty Quantification in Neutron Transport, Ian Sloan and Lattice Rules, Truncation Dimension for Function Approximation, The Analysis of Vertex Modified Lattice Rules in a Non-periodic Sobolev Space, Effective Dimension of Some Weighted Pre-Sobolev Spaces with Dominating Mixed Partial Derivatives, Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights, Richardson Extrapolation of Polynomial Lattice Rules, On the existence of low‐diaphony sequences made of digital sequences and lattice point sets, Better Approximations of High Dimensional Smooth Functions by Deep Neural Networks with Rectified Power Units, Analysis and Application of Single Level, Multi-Level Monte Carlo and Quasi-Monte Carlo Finite Element Methods for Time-Dependent Maxwell's Equations with Random Inputs, Worst-case errors in a Sobolev space setting for cubature over the sphere S², Handling Discontinuities in Financial Engineering: Good Path Simulation and Smoothing, Multilevel Accelerated Quadrature for PDEs with Log-Normally Distributed Diffusion Coefficient, Approximation methods for piecewise deterministic Markov processes and their costs, Statistical properties of generalized discrepancies, The construction of extensible polynomial lattice rules with small weighted star discrepancy, Intractability results for integration and discrepancy, What is the complexity of surface integration?, Uniform distribution, discrepancy, and reproducing kernel Hilbert spaces, Constructions of general polynomial lattices for multivariate integration, Hyperbolic cross approximation in infinite dimensions, Open type quasi-Monte Carlo integration based on Halton sequences in weighted Sobolev spaces, Equivalence of anchored and ANOVA spaces via interpolation, Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls, Reconstruction and collocation of a class of non-periodic functions by sampling along tent-transformed rank-1 lattices, Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions. Error bounds and tractability, A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy, Weighted discrepancy of Faure-Niederreiter nets for a certain sequence of weights, On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation, A Taylor space for multivariate integration, Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters, On quasi-Monte Carlo methods in weighted ANOVA spaces, Discrepancy Theory and Quasi-Monte Carlo Integration, Calculation of Discrepancy Measures and Applications, Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration, Fast convergence of quasi-Monte Carlo for a class of isotropic integrals, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, Quasi-Monte Carlo integration using digital nets with antithetics, Finite-order weights imply tractability of linear multivariate problems, Finite-order weights imply tractability of multivariate integration, The acceptance-rejection method for low-discrepancy sequences, $I$-binomial scrambling of digital nets and sequences, Liberating the weights, On polynomial-time property for a class of randomized quadratures, Construction algorithms for good extensible lattice rules, Spline methods using integration lattices and digital nets, QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach, Quasi-regression, The price of pessimism for multidimensional quadrature, Tractability of multivariate integration for periodic functions, Tractability of multivariate integration for weighted Korobov classes, Quasi-random simulation of linear kinetic equations, The exact exponent of sparse grid quadratures in the weighted case, Integration and approximation based on scramble sampling in arbitrary dimensions, A comment on ``Computational complexity of stochastic programming problems, Multi-element probabilistic collocation method in high dimensions, Degradation-based maintenance decision using stochastic filtering for systems under imperfect maintenance, Conditional quasi-Monte Carlo methods and dimension reduction for option pricing and hedging with discontinuous functions, On the mean square weighted $\mathcal {L}_2$ discrepancy of randomized digital nets in prime base, Randomly shifted lattice rules for unbounded integrands, Exact cubature for a class of functions of maximum effective dimension, Consistent inference in fixed-effects stochastic frontier models, Highly efficient numerical algorithm based on random trees for accelerating parallel Vlasov-Poisson simulations, The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets, A note on equivalence of anchored and ANOVA spaces; lower bounds, A component-by-component approach to efficient numerical integration over products of spheres, The construction of good extensible Korobov rules, The $p$-adic diaphony of the Halton sequence, On the convergence rate of the component-by-component construction of good lattice rules, Tractability of quasilinear problems. I: General results, Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information, Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, Quasi-Monte Carlo tractability of high dimensional integration over products of simplices, Construction of scrambled polynomial lattice rules over $\mathbb{F}_{2}$ with small mean square weighted $\mathcal{L}_{2}$ discrepancy, On equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in $L_1$ or $L_\infty$, On a projection-corrected component-by-component construction, How do path generation methods affect the accuracy of quasi-Monte Carlo methods for problems in finance?, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, Sufficient conditions for fast quasi-Monte Carlo convergence, My dream quadrature rule, Open problems for tractability of multivariate integration., Tractability of approximating multivariate linear functionals, Variance bounds and existence results for randomly shifted lattice rules, Adaptive ANOVA decomposition of stochastic incompressible and compressible flows, An efficient dimension-adaptive uncertainty propagation approach, Bayesian model selection for complex geological structures using polynomial chaos proxy, A construction of polynomial lattice rules with small gain coefficients, Tractability properties of the weighted star discrepancy of the Halton sequence, Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm, A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights, Truncation dimension for linear problems on multivariate function spaces, Monte Carlo finite volume element methods for the convection-diffusion equation with a random diffusion coefficient, Lattice rules in non-periodic subspaces of Sobolev spaces, On the tractability of the Brownian bridge algorithm, Bounds for the weighted $L^p$ discrepancy and tractability of integration, Integration error for multivariate functions from anisotropic classes, Estimation and detection of high-variable functions from Sloan-Woźniakowski space, Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces, Tractability results for weighted Banach spaces of smooth functions, Koksma-Hlawka type inequalities of fractional order, Quasi-Monte Carlo for highly structured generalised response models, Tractability using periodized generalized Faure sequences, Hilbert space with reproducing kernel and uniform distribution preserving maps. I, Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules, Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence, Lattice rules with random $n$ achieve nearly the optimal $\mathcal{O}(n^{-\alpha-1/2})$ error independently of the dimension, Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients, A fast Monte-Carlo method with a reduced basis of control variates applied to uncertainty propagation and Bayesian estimation, Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation, Tractability properties of the weighted star discrepancy of regular grids, Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions, Quasi-Monte Carlo methods for lattice systems: a first look, Quasi-Monte Carlo methods with applications in finance, Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands, Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces, Construction algorithms for higher order polynomial lattice rules, Quasi-Monte Carlo methods for elliptic PDEs with random coefficients and applications, Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights, Liberating the dimension, Dimension-wise integration of high-dimensional functions with applications to finance, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, Quasi-Monte Carlo methods can be efficient for integration over products of spheres, Computational complexity of the integration problem for anisotropic classes, Introduction to convex optimization in financial markets, Efficient deterministic numerical simulation of stochastic asset-liability management models in life insurance, New averaging technique for approximating weighted integrals, Scrambling Sobol' and Niederreiter-Xing points, Learning a function from noisy samples at a finite sparse set of points, On the approximation of smooth functions using generalized digital nets, Tractability of the Helmholtz equation with non-homogeneous Neumann boundary conditions: the relation to the $L_{2}$-approximation, Assessing linearity in high dimensions., On stochastic formalisms in transition state theory, Randomized Halton sequences, The Brownian bridge does not offer a consistent advantage in quasi-Monte Carlo integration, A new measure of irregularity of distribution and quasi-Monte Carlo methods for global optimization, The effective dimension and quasi-Monte Carlo integration, QUASI-MONTE CARLO METHODS FOR HIGH-DIMENSIONAL INTEGRATION: THE STANDARD (WEIGHTED HILBERT SPACE) SETTING AND BEYOND, Exponential convergence and tractability of multivariate integration for Korobov spaces, On the root mean square weighted $L_{2}$ discrepancy of scrambled nets, Countable tensor products of Hermite spaces and spaces of Gaussian kernels, The weighted star discrepancy of Korobov’s $p$-sets, Are quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?, Effective discrepancy and numerical experiments, Numerical Integration in Multiple Dimensions with Designed Quadrature, A note on concatenation of quasi-Monte Carlo and plain Monte Carlo rules in high dimensions, Constructing lattice rules based on weighted degree of exactness and worst case error, Non-linear approximation of functions with mixed smoothness by sets of finite pseudo-dimension, Construction Schemes for Weighted Lattice Rules, On the effective dimension and multilevel Monte Carlo, ANOVA Decomposition of Convex Piecewise Linear Functions, QMC Galerkin Discretization of Parametric Operator Equations, On the Choice of Weights in a Function Space for Quasi-Monte Carlo Methods for a Class of Generalised Response Models in Statistics, Equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in $L_p$, Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces, Small superposition dimension and active set construction for multivariate integration under modest error demand, Construction of good polynomial lattice rules in weighted Walsh spaces by an alternative component-by-component construction, The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers, A note on the periodic $L_2$-discrepancy of Korobov's $p$-sets, On the quasi-Monte Carlo method with Halton points for elliptic PDEs with log-normal diffusion, ABC on IBC, Some Results on the Complexity of Numerical Integration, Random weights, robust lattice rules and the geometry of the $cbcrc$ algorithm, Constructive representation of functions in low-rank tensor formats, Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm, A note on the CBC-DBD construction of lattice rules with general positive weights, A GPU compatible quasi-Monte Carlo integrator interfaced to pySecDec, Minimax goodness-of-fit testing in multivariate nonparametric regression, On efficient weighted integration via a change of variables, Estimation and detection of functions from weighted tensor product spaces, On weighted Hilbert spaces and integration of functions of infinitely many variables, Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials, Weighted tensor product algorithms for linear multivariate problems, Numerical solution of the Stratonovich- and Ito-Euler equations: application to the stochastic piston problem, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, Adaptive detection of a high-variable function, Anchor Points Matter in ANOVA Decomposition, Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness, A note on $(s,t)$-weak tractability of the weighted star discrepancy of regular grids, Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules, On the existence of higher order polynomial lattices based on a generalized figure of merit, A note on EC-tractability of multivariate approximation in weighted Korobov spaces for the standard information class, Constructions of general polynomial lattice rules based on the weighted star discrepancy, A note on tools for prediction under uncertainty and identifiability of SIR-like dynamical systems for epidemiology, Periodization strategy may fail in high dimensions, Robust Optimizers for Nonlinear Programming in Approximate Dynamic Programming, Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals, Quasi-Monte Carlo and $\varepsilon$-truncation dimension in ANOVA spaces, Instances of computational optimal recovery: refined approximability models, How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings, Hiding the weights -- CBC black box algorithms with a guaranteed error bound, Tractability results for the weighted star-discrepancy, Fast CBC construction of randomly shifted lattice rules achieving $\mathcal{O}(n^{- 1 + \delta})$ convergence for unbounded integrands over $\mathbb{R}^s$ in weighted spaces with POD weights, Low discrepancy sequences in high dimensions: how well are their projections distributed?, High-dimensional integration on $\mathbb{R}^d$, weighted Hermite spaces, and orthogonal transforms, Constructing good higher order polynomial lattice rules with modulus of reduced degree, New Brownian bridge construction in quasi-Monte Carlo methods for computational finance, Tractability properties of the weighted star discrepancy, Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points, Randomly shifted lattice rules on the unit cube for unbounded integrands in high dimensions, Infinite-dimensional integration and the multivariate decomposition method, Good lattice rules in weighted Korobov spaces with general weights, Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition, Weighted integration over a hyperrectangle based on digital nets and sequences, Embeddings for infinite-dimensional integration and $L_2$-approximation with increasing smoothness, The construction of good extensible rank-1 lattices, Optimized general sparse grid approximation spaces for operator equations, Toeplitz Monte Carlo, The weighted $b$-adic diaphony, Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration, Convergence analysis of deterministic kernel-based quadrature rules in misspecified settings, Theory of generalized discrepancies on a ball of arbitrary finite dimensions and algorithms for finding low-discrepancy point sets, An algorithm to compute the $t$-value of a digital net and of its projections, An iterative algorithm to determine the number of time steps in path generation methods, $ \varepsilon $-superposition and truncation dimensions in average and probabilistic settings for $\infty $-variate linear problems, Information based complexity for high dimensional sparse functions, Multilevel Higher Order QMC Petrov--Galerkin Discretization for Affine Parametric Operator Equations, Calibration of financial models using quasi-Monte Carlo, On the Scenario-Tree Optimal-Value Error for Stochastic Programming Problems, Analysis of quasi-Monte Carlo methods for elliptic eigenvalue problems with stochastic coefficients, Physics-informed neural networks: a deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations, Infinite-dimensional integration on weighted Hilbert spaces, Tractability of quasilinear problems II: Second-order elliptic problems, Good lattice rules based on the general weighted star discrepancy, Dyadic diaphony of digital nets over $\mathbb Z_2$, Diaphony, discrepancy, spectral test and worst-case error, On the necessity of low-effective dimension, The $b$-adic tent transformation for quasi-Monte Carlo integration using digital nets, Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces, Integration in Hermite spaces of analytic functions, On embeddings of weighted tensor product Hilbert spaces, Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets, Quasi-Monte Carlo methods for linear two-stage stochastic programming problems, Advances and applications of chance-constrained approaches to systems optimisation under uncertainty, Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces, Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients, The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Cites Work