Multi-index Monte Carlo: when sparsity meets sampling
From MaRDI portal
PDEs of infinite order (35R50) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Monte Carlo methods (65C05) Probabilistic models, generic numerical methods in probability and statistics (65C20) Numerical solutions to stochastic differential and integral equations (65C30)
Abstract: We propose and analyze a novel Multi-Index Monte Carlo (MIMC) method for weak approximation of stochastic models that are described in terms of differential equations either driven by random measures or with random coefficients. The MIMC method is both a stochastic version of the combination technique introduced by Zenger, Griebel and collaborators and an extension of the Multilevel Monte Carlo (MLMC) method first described by Heinrich and Giles. Inspired by Giles's seminal work, we use in MIMC high-order mixed differences instead of using first-order differences as in MLMC to reduce the variance of the hierarchical differences dramatically. This in turn yields new and improved complexity results, which are natural generalizations of Giles's MLMC analysis and which increase the domain of the problem parameters for which we achieve the optimal convergence, Moreover, in MIMC, the rate of increase of required memory with respect to is independent of the number of directions up to a logarithmic term which allows far more accurate solutions to be calculated for higher dimensions than what is possible when using MLMC. We motivate the setting of MIMC by first focusing on a simple full tensor index set. We then propose a systematic construction of optimal sets of indices for MIMC based on properly defined profits that in turn depend on the average cost per sample and the corresponding weak error and variance. Under standard assumptions on the convergence rates of the weak error, variance and work per sample, the optimal index set turns out to be the total degree (TD) type. In some cases, using optimal index sets, MIMC achieves a better rate for the computational complexity than the corresponding rate when using full tensor index sets...
Recommendations
Cites work
- A continuation multilevel Monte Carlo algorithm
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A multilevel stochastic collocation method for partial differential equations with random input data
- A proof of convergence for the combination technique for the Laplace equation using tools of symbolic computation.
- A Stochastic Collocation Method for Elliptic Partial Differential Equations with Random Input Data
- Adaptive multilevel Monte Carlo simulation
- Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation
- Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: Application to random elliptic PDEs
- Convergence of the Combination Technique for Second-Order Elliptic Differential Equations
- Error analysis of the combination technique
- Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods
- Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients
- scientific article; zbMATH DE number 440658 (Why is no real title available?)
- scientific article; zbMATH DE number 48363 (Why is no real title available?)
- scientific article; zbMATH DE number 66109 (Why is no real title available?)
- scientific article; zbMATH DE number 653220 (Why is no real title available?)
- Implementation and analysis of an adaptive multilevel Monte Carlo algorithm
- Monte Carlo complexity of global solution of integral equations
- Monte Carlo complexity of parametric integration
- Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients
- Multilevel accelerated quadrature for PDEs with log-normally distributed diffusion coefficient
- Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients
- Multilevel Monte Carlo Path Simulation
- Multilevel path simulation for jump-diffusion SDEs
- On the convergence of the combination technique
- Optimization of mesh hierarchies in multilevel Monte Carlo samplers
- Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients
- Sparse tensor multi-level Monte Carlo finite volume methods for hyperbolic conservation laws with random initial data
- Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing
- Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance
- The combination technique and some generalisations
Cited in
(75)- Convergence analysis of multifidelity Monte Carlo estimation
- Multilevel and multi-index Monte Carlo methods for the McKean-Vlasov equation
- A dimension-adaptive multi-index Monte Carlo method applied to a model of a heat exchanger
- Toeplitz Monte Carlo
- A multilevel Monte Carlo method for asymptotic-preserving particle schemes in the diffusive limit
- Markov chain simulation for multilevel Monte Carlo
- Multi-index ensemble Kalman filtering
- Analysis of sparse grid multilevel estimators for multi-dimensional Zakai equations
- Improved efficiency of multilevel Monte Carlo for stochastic PDE through strong pairwise coupling
- A generalized approximate control variate framework for multifidelity uncertainty quantification
- On the optimization of approximate control variates with parametrically defined estimators
- Logarithmic gradient transformation and chaos expansion of Itô processes
- Stochastic turbulence modeling in RANS simulations via multilevel Monte Carlo
- Multilevel Monte Carlo by using the Halton sequence
- Numerical methods for conservation laws with rough flux
- Multi-index stochastic collocation for random PDEs
- MFNets: data efficient all-at-once learning of multifidelity surrogates as directed networks of information sources
- Sparse polynomial approximations for affine parametric saddle point problems
- Multilevel Markov chain Monte Carlo for Bayesian inverse problem for Navier-Stokes equation
- Multi-level stochastic approximation algorithms
- Computable error estimates for finite element approximations of elliptic partial differential equations with rough stochastic data
- Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: Application to random elliptic PDEs
- An adaptive multilevel Monte Carlo method with stochastic bounds for quantities of interest with uncertain data
- Multilevel Monte Carlo estimation of expected information gains
- Multilevel Monte Carlo for smoothing via transport methods
- Survey of multifidelity methods in uncertainty propagation, inference, and optimization
- A multiorder discontinuous Galerkin Monte Carlo method for hyperbolic problems with stochastic parameters
- Multilevel estimation of expected exit times and other functionals of stopped diffusions
- Continuous Level Monte Carlo and Sample-Adaptive Model Hierarchies
- MLMC for nested expectations
- Modern Monte Carlo variants for uncertainty quantification in neutron transport
- Unbiased multi-index Monte Carlo
- Analysis of multi-index Monte Carlo estimators for a Zakai SPDE
- Multilevel Monte Carlo Covariance Estimation for the Computation of Sobol' Indices
- Multilevel Designed Quadrature for Partial Differential Equations with Random Inputs
- Enhanced multi‐index Monte Carlo by means of multiple semicoarsened multigrid for anisotropic diffusion problems
- Stochastic regularity of a quadratic observable of high-frequency waves
- Ensemble approximate control variate estimators: applications to multifidelity importance sampling
- Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity
- Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation
- $hp$-Multilevel Monte Carlo Methods for Uncertainty Quantification of Compressible Navier--Stokes Equations
- Sparse Compression of Expected Solution Operators
- Improved Efficiency of a Multi-Index FEM for Computational Uncertainty Quantification
- Fuzzy-stochastic partial differential equations
- Recycling samples in the multigrid multilevel (quasi-)Monte Carlo method
- Comparison of Surrogate-Based Uncertainty Quantification Methods for Computationally Expensive Simulators
- A multi-index quasi-Monte Carlo algorithm for lognormal diffusion problems
- Analysis of nested multilevel Monte Carlo using approximate normal random variables
- Advanced Multilevel Monte Carlo Methods
- Meta variance reduction for Monte Carlo estimation of energetic particle confinement during stellarator optimization
- Multifidelity approaches for uncertainty quantification
- Multifidelity uncertainty quantification with models based on dissimilar parameters
- Multi-output multilevel best linear unbiased estimators via semidefinite programming
- Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
- Multi-index antithetic stochastic gradient algorithm
- A randomized multi-index sequential Monte Carlo method
- Monte Carlo convergence rates for kth moments in Banach spaces
- A combination technique for optimal control problems constrained by random PDEs
- Multi-index sequential Monte Carlo ratio estimators for Bayesian inverse problems
- Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey
- A multilevel Monte Carlo algorithm for stochastic differential equations driven by countably dimensional Wiener process and Poisson random measure
- A fully parallelized and budgeted multilevel Monte Carlo method and the application to acoustic waves
- Efficient estimation of expected information gain in Bayesian experimental design with multi-index Monte Carlo
- Multilevel importance sampling for rare events associated with the McKean-Vlasov equation
- Complexity analysis of quasi continuous level Monte Carlo
- Lasso Monte Carlo, a variation on multi fidelity methods for high-dimensional uncertainty quantification
- Covariance-free bifidelity control variates importance sampling for rare event reliability analysis
- Multilevel Monte Carlo metamodeling for variance function estimation
- Bayesian deep learning with multilevel trace-class neural networks
- Fixed-budget optimal designs for multi-fidelity computer experiments
- Boosting efficiency and reducing graph reliance: basis adaptation integration in Bayesian multi-fidelity networks
- Residual multi-fidelity neural network computing
- Multifidelity uncertainty quantification for ice sheet simulations
- Multi-index importance sampling for McKean-Vlasov stochastic differential equations
- A multi level Monte Carlo method with control variate for elliptic PDEs with log-normal coefficients
This page was built for publication: Multi-index Monte Carlo: when sparsity meets sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q264116)
