Multi-index Monte Carlo: when sparsity meets sampling
From MaRDI portal
(Redirected from Publication:264116)
Monte Carlo methods (65C05) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Probabilistic models, generic numerical methods in probability and statistics (65C20) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Numerical solutions to stochastic differential and integral equations (65C30) PDEs of infinite order (35R50)
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
- 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?)
- A Stochastic Collocation Method for Elliptic Partial Differential Equations with Random Input Data
- 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.
- 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
- 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 Monte Carlo Path Simulation
- Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients
- Multilevel accelerated quadrature for PDEs with log-normally distributed diffusion coefficient
- 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
(65)- Multi-index sequential Monte Carlo ratio estimators for Bayesian inverse problems
- Monte Carlo convergence rates for \(k\)th moments in Banach spaces
- 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
- A fully parallelized and budgeted multilevel Monte Carlo method and the application to acoustic waves
- A combination technique for optimal control problems constrained by random PDEs
- Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
- A multilevel Monte Carlo algorithm for stochastic differential equations driven by countably dimensional Wiener process and Poisson random measure
- Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey
- Multi-index antithetic stochastic gradient algorithm
- A randomized multi-index sequential Monte Carlo method
- Multi-output multilevel best linear unbiased estimators via semidefinite programming
- Complexity analysis of quasi continuous level Monte Carlo
- Multi-index stochastic collocation for random PDEs
- Analysis of multi-index Monte Carlo estimators for a Zakai SPDE
- Sparse Compression of Expected Solution Operators
- Multilevel Monte Carlo estimation of expected information gains
- Advanced Multilevel Monte Carlo Methods
- Multi-level stochastic approximation algorithms
- Numerical methods for conservation laws with rough flux
- Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity
- Continuous Level Monte Carlo and Sample-Adaptive Model Hierarchies
- An adaptive multilevel Monte Carlo method with stochastic bounds for quantities of interest with uncertain data
- Multi-index ensemble Kalman filtering
- Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: Application to random elliptic PDEs
- Markov chain simulation for multilevel Monte Carlo
- A multiorder discontinuous Galerkin Monte Carlo method for hyperbolic problems with stochastic parameters
- Sparse polynomial approximations for affine parametric saddle point problems
- Toeplitz Monte Carlo
- Convergence analysis of multifidelity Monte Carlo estimation
- Comparison of Surrogate-Based Uncertainty Quantification Methods for Computationally Expensive Simulators
- On the optimization of approximate control variates with parametrically defined estimators
- Computable error estimates for finite element approximations of elliptic partial differential equations with rough stochastic data
- Meta variance reduction for Monte Carlo estimation of energetic particle confinement during stellarator optimization
- A multi level Monte Carlo method with control variate for elliptic PDEs with log-normal coefficients
- A multilevel Monte Carlo method for asymptotic-preserving particle schemes in the diffusive limit
- Analysis of nested multilevel Monte Carlo using approximate normal random variables
- Multilevel Monte Carlo Covariance Estimation for the Computation of Sobol' Indices
- Survey of multifidelity methods in uncertainty propagation, inference, and optimization
- Multilevel Monte Carlo for smoothing via transport methods
- Fuzzy-stochastic partial differential equations
- Recycling samples in the multigrid multilevel (quasi-)Monte Carlo method
- Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation
- Stochastic turbulence modeling in RANS simulations via multilevel Monte Carlo
- $hp$-Multilevel Monte Carlo Methods for Uncertainty Quantification of Compressible Navier--Stokes Equations
- Multilevel Markov chain Monte Carlo for Bayesian inverse problem for Navier-Stokes equation
- Improved efficiency of multilevel Monte Carlo for stochastic PDE through strong pairwise coupling
- A generalized approximate control variate framework for multifidelity uncertainty quantification
- Multifidelity approaches for uncertainty quantification
- Unbiased multi-index Monte Carlo
- Multilevel Designed Quadrature for Partial Differential Equations with Random Inputs
- Stochastic regularity of a quadratic observable of high-frequency waves
- A dimension-adaptive multi-index Monte Carlo method applied to a model of a heat exchanger
- Multilevel estimation of expected exit times and other functionals of stopped diffusions
- Multilevel Monte Carlo by using the Halton sequence
- Multifidelity uncertainty quantification with models based on dissimilar parameters
- Ensemble approximate control variate estimators: applications to multifidelity importance sampling
- Improved Efficiency of a Multi-Index FEM for Computational Uncertainty Quantification
- Multilevel and multi-index Monte Carlo methods for the McKean-Vlasov equation
- MLMC for nested expectations
- Logarithmic gradient transformation and chaos expansion of Itô processes
- A multi-index quasi-Monte Carlo algorithm for lognormal diffusion problems
- Modern Monte Carlo variants for uncertainty quantification in neutron transport
- MFNets: data efficient all-at-once learning of multifidelity surrogates as directed networks of information sources
- Analysis of sparse grid multilevel estimators for multi-dimensional Zakai equations
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)
