Multi-index Monte Carlo: when sparsity meets sampling
From MaRDI portal
Publication:264116
DOI10.1007/S00211-015-0734-5zbMATH Open1339.65009arXiv1405.3757OpenAlexW1595193945MaRDI QIDQ264116FDOQ264116
Authors: Abdul-Lateef Haji-Ali, R. Tempone, F. Nobile 
Publication date: 5 April 2016
Published in: Numerische Mathematik (Search for Journal in Brave)
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...
Full work available at URL: https://arxiv.org/abs/1405.3757
Recommendations
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)
Cites Work
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- Multilevel Monte Carlo Path Simulation
- Title not available (Why is that?)
- Monte Carlo complexity of global solution of integral equations
- A proof of convergence for the combination technique for the Laplace equation using tools of symbolic computation.
- Monte Carlo complexity of parametric integration
- Error analysis of the combination technique
- A continuation multilevel Monte Carlo algorithm
- Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing
- Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation
- Sparse tensor multi-level Monte Carlo finite volume methods for hyperbolic conservation laws with random initial data
- Multilevel hybrid Chernoff tau-leap
- Adaptive multilevel Monte Carlo simulation
- Title not available (Why is that?)
- Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: Application to random elliptic PDEs
- A Multilevel Stochastic Collocation Method for Partial Differential Equations with Random Input Data
- Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients
- Title not available (Why is that?)
- Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients
- Title not available (Why is that?)
- Convergence of the Combination Technique for Second-Order Elliptic Differential Equations
- Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance
- Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients
- Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods
- Optimization of mesh hierarchies in multilevel Monte Carlo samplers
- On the Convergence of the Combination Technique
- Multilevel path simulation for jump-diffusion SDEs
- Implementation and analysis of an adaptive multilevel Monte Carlo algorithm
- Multilevel Accelerated Quadrature for PDEs with Log-Normally Distributed Diffusion Coefficient
- A Stochastic Collocation Method for Elliptic Partial Differential Equations with Random Input Data
- Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients
- The combination technique and some generalisations
Cited In (61)
- A combination technique for optimal control problems constrained by random PDEs
- Multi-index sequential Monte Carlo ratio estimators for Bayesian inverse problems
- Multi-index antithetic stochastic gradient algorithm
- A randomized multi-index sequential Monte Carlo method
- Monte Carlo convergence rates for \(k\)th moments in Banach spaces
- 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
- Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey
- Improved efficiency of multilevel Monte Carlo for stochastic PDE through strong pairwise coupling
- MLMC for Nested Expectations
- Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: Application to random elliptic PDEs
- Modern Monte Carlo Variants for Uncertainty Quantification in Neutron Transport
- A MultiOrder Discontinuous Galerkin Monte Carlo Method for Hyperbolic Problems with Stochastic Parameters
- Sparse polynomial approximations for affine parametric saddle point problems
- A multilevel Monte Carlo method for asymptotic-preserving particle schemes in the diffusive limit
- Improved Efficiency of a Multi-Index FEM for Computational Uncertainty Quantification
- Markov chain simulation for multilevel Monte Carlo
- An Adaptive Multilevel Monte Carlo Method with Stochastic Bounds for Quantities of Interest with Uncertain Data
- Logarithmic gradient transformation and chaos expansion of Itô processes
- Stochastic turbulence modeling in RANS simulations via multilevel Monte Carlo
- On the optimization of approximate control variates with parametrically defined estimators
- Recycling Samples in the Multigrid Multilevel (Quasi-)Monte Carlo Method
- Multi-index ensemble Kalman filtering
- Survey of Multifidelity Methods in Uncertainty Propagation, Inference, and Optimization
- Convergence analysis of multifidelity Monte Carlo estimation
- Multilevel Monte Carlo for Smoothing via Transport Methods
- Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity
- Multilevel Designed Quadrature for Partial Differential Equations with Random Inputs
- Multi-index stochastic collocation for random PDEs
- MFNets: data efficient all-at-once learning of multifidelity surrogates as directed networks of information sources
- Multilevel Monte Carlo estimation of expected information gains
- Meta variance reduction for Monte Carlo estimation of energetic particle confinement during stellarator optimization
- Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
- A Multi-Index Quasi--Monte Carlo Algorithm for Lognormal Diffusion Problems
- Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation
- Continuous Level Monte Carlo and Sample-Adaptive Model Hierarchies
- Sparse Compression of Expected Solution Operators
- Ensemble Approximate Control Variate Estimators: Applications to MultiFidelity Importance Sampling
- Multi-output multilevel best linear unbiased estimators via semidefinite programming
- Multilevel Estimation of Expected Exit Times and Other Functionals of Stopped Diffusions
- Numerical methods for conservation laws with rough flux
- Fuzzy-Stochastic Partial Differential Equations
- Multifidelity approaches for uncertainty quantification
- Multifidelity uncertainty quantification with models based on dissimilar parameters
- Stochastic regularity of a quadratic observable of high-frequency waves
- Multilevel Monte Carlo by using the Halton sequence
- Advanced Multilevel Monte Carlo Methods
- Unbiased multi-index Monte Carlo
- A generalized approximate control variate framework for multifidelity uncertainty quantification
- Multilevel and multi-index Monte Carlo methods for the McKean-Vlasov equation
- Multilevel Markov chain Monte Carlo for Bayesian inverse problem for Navier-Stokes equation
- Analysis of Nested Multilevel Monte Carlo Using Approximate Normal Random Variables
- Comparison of Surrogate-Based Uncertainty Quantification Methods for Computationally Expensive Simulators
- A multi level Monte Carlo method with control variate for elliptic PDEs with log-normal coefficients
- Multilevel Monte Carlo Covariance Estimation for the Computation of Sobol' Indices
- $hp$-Multilevel Monte Carlo Methods for Uncertainty Quantification of Compressible Navier--Stokes Equations
- Analysis of sparse grid multilevel estimators for multi-dimensional Zakai equations
- Computable Error Estimates for Finite Element Approximations of Elliptic Partial Differential Equations with Rough Stochastic Data
Uses Software
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)
