Multilevel Monte Carlo method

Summary

Multilevel Monte Carlo (MLMC) methods in numerical analysis are algorithms for computing expectations that arise in stochastic simulations. Just as Monte Carlo methods, they rely on repeated random sampling, but these samples are taken on different levels of accuracy. MLMC methods can greatly reduce the computational cost of standard Monte Carlo methods by taking most samples with a low accuracy and corresponding low cost, and only very few samples are taken at high accuracy and corresponding high cost. Goal The goal of a multilevel Monte Carlo method is to approximate the expected value \operatorname{E}[G] of the random variable G that is the output of a stochastic simulation. Suppose this random variable cannot be simulated exactly, but there is a sequence of approximations G_0, G_1, \ldots, G_L with increasing accuracy, but also increasing cost, that converges to G as L\rightarrow\infty. The basis of the mu

Official source

https://en.wikipedia.org/wiki/Multilevel_Monte_Carlo_method

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (35)

Related publications

Related people (7)

, , , , , ,

Related people

Related units (6)

Related units

Related concepts

Related courses (1)

Related courses

Related lectures

In this work, we tackle the problem of minimising the Conditional-Value-at-Risk (CVaR) of output quantities of complex differential models with random input data, using gradient-based approaches in combination with the Multi-Level Monte Carlo (MLMC) method. In particular, we consider the framework of multi-level Monte Carlo for parametric expectations and propose modifications of the MLMC estimator, error estimation procedure, and adaptive MLMC parameter selection to ensure the estimation of the CVaR and sensitivities for a given design with a prescribed accuracy. We then propose combining the MLMC framework with an alternating inexact minimisation-gradient descent algorithm, for which we prove exponential convergence in the optimisation iterations under the assumptions of strong convexity and Lipschitz continuity of the gradient of the objective function. We demonstrate the performance of our approach on two numerical examples of practical relevance, which evidence the same optimal asymptotic cost-tolerance behaviour as standard MLMC methods for fixed design computations of output expectations.

2022

MATHICSE Technical Report : Optimization of mesh hierarchies in multilevel Monte Carlo samplers

Fabio Nobile, Erik Gustaf Bogislaw Von Schwerin

We perform a general optimization of the parameters in the Multilevel Monte Carlo (MLMC) discretization hierarchy based on uniform discretization methods with general approximation orders and computational costs. Moreover, we discuss extensions to non-uniform discretizations based on a priori renements and the effect of imposing constraints on the largest and/or smallest mesh sizes. We optimize geometric and non-geometric hierarchies and compare them to each other, concluding that the geometric hierarchies, when optimized, are nearly optimal and have the same asymptotic computational complexity. We discuss how enforcing domain constraints on parameters of MLMC hierarchies affects the opti- mality of these hierarchies. These domain constraints include an upper and lower bound on the mesh size or enforcing that the number of samples and the number of discretization elements are integers. We also discuss the optimal tolerance splitting between the bias and the statistical error contributions and its asymp- totic behavior. To provide numerical grounds for our theoretical results, we apply these optimized hierarchies together with the Continuation MLMC Algorithm [13] that we recently developed, to several examples. These include the approxima- tion of three-dimensional elliptic partial differential equations with random inputs based on FEM with either direct or iterative solvers and It^o stochastic differential equations based on the Milstein scheme.

MATHICSE2014

MATHICSE Technical Report : Multilevel weighted least squares polynomial approximation

Fabio Nobile

Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. It has been shown that, using an optimal distribution of sample locations, the number of samples required to achieve quasi-optimal approximation in a given polynomial subspace scales, up to a logarithmic factor, linearly in the dimension of this space. However, in many applications, the computation of samples includes a numerical discretization error. Thus, obtaining polynomial approximations with a single level method can become prohibitively expensive, as it requires a sufficiently large number of samples, each computed with a sufficiently small discretization error. As a solution to this problem, we propose a multilevel method that utilizes samples computed with different accuracies and is able to match the accuracy of single-level approximations with reduced computational cost. We derive complexity bounds under certain assumptions about polynomial approximability and sample work. Furthermore, we propose an adaptive algorithm for situations where such assumptions cannot be verified a priori. Finally, we provide an efficient algorithm for the sampling from optimal distributions and an analysis of computationally favorable alternative distributions. Numerical experiments underscore the practical applicability of our method.

MATHICSE2017