10:00-12:00: Mike Giles, Multilevel Monte Carlo methods. Monte Carlo methods are a very general and useful approach for the estimation of expectations arising from stochastic simulation. However, they can be computationally expensive, particularly when the cost of generating individual stochastic samples is very high, as in the case of stochastic PDEs. Multilevel Monte Carlo is a recently developed approach which greatly reduces the computational cost by performing most simulations with low accuracy at a correspondingly low cost, with relatively few simulations being performed at high accuracy and a high cost. This lecture, based on a new Acta Numerica review article, is aimed at non-specialists, and will present the ideas behind the multilevel Monte Carlo method, and discuss a range of applications in areas such as computational finance, engineering, and biochemical reactions. We will also give an overview of various recent generalisations and extensions, and the challenges in developing more efficient implementations with a faster rate of convergence of the multilevel correction variance.
13:30-14:15: Gilles Pages, Multilevel Richardson-Romberg extrapolation for Monte Carlo and Langevin Monte Carlo simulation. This is a joint work with V. Lemaire (LPMA-UPMC). We propose and analyze a Multilevel Richardson-Romberg (MLRR) estimator which combines the higher order bias cancellation of the Multistep Richardson-Romberg extrapolation introduced in~[Pag�s 07] and the variance control resulting from the stratification in the Multilevel Monte Carlo (MLMC) method (see [Giles ’08]). The ML2R estimator appears as a weighted version of the MLMC, with universal weights. Thus we show that in standard frameworks like discretization schemes of diffusion processes, an assigned quadratic error epsilon can be obtained with our MLRR estimator with a global complexity of log(1/epsilon)* epsilon^(-2) instead of (log(1/epsilon))^2*epsilon^(-2) with the standard MLMC method, at least when the weak error E(Y_h)-E(Y_0) induced by the biased implemented estimator Y_h can be expanded at any order in h.This is half-way between MLMC and a virtual unbiased simulation. More generally, the slower the quadratic strong error ||Y_h-Y_0||_2 is, the higher the complexity gain is. We analyze and compare these estimators on several numerical problems: option pricing (vanilla or exotic) using Monte Carlo simulation and the less classical Nested Monte Carlo simulation (see~[Gordy & Juneja 2010]). In a second step, we adapt similar ideas to Langevin Monte Carlo simulation for the recursive computation of invariant distributions of diffusions with applications to stationary stochastic volatility models.
14:15-15:00: Denis Belomestny, Multilevel Monte Carlo for multidimensional Levy type processes. Abstract TBA.
15:30-16:15: Steffen Dereich,
Multilevel stochastic approximation: a complexity theorem. Stochastic approximation algorithms are a standard tool for the numerical computation of zeroes of functions $f:mathbb R^dtomathbb R^d$ of the form $$ f(theta)=mathbb E[F(theta,U)] $$ with $U$ denoting a random variable and $F$ an appropriate measurable function. Robbins and Monro introduced in 1951 a dynamical system that converges to solutions and is based on independent realisations of $U$ (under appropriate assumptions). Research on this topic remained active and resulted in a variety of results. A natural question was whether the approach can be combined with the recently discovered multilevel paradigm in the case where $F(theta,U)$ is not simulatable. Indeed, as shown by N. Frikha the combination bears potential and leads to new efficient schemes in the context of SDEs. In this talk we provide new multilevel stochastic approximation algorithms and present complexity theorems on $L^p$-errors in the spirit of the original work of M. Giles on multilevel Monte Carlo. In contrast to previous work, our error analysis requires significantly weaker assumptions which makes it applicable in a wide variety of examples.
16:15-17:00: Des Higham, Efficiency of Multilevel Monte Carlo for Large-Scale Markov Chain Simulations. I will analyze and compare the computational complexity of different simulation strategies for continuous time Markov chains. I consider the task of approximating the expected value of some functional of the state of the system over a compact time interval. This task is a bottleneck in many large-scale computations arising in biochemical kinetics and cell biology. In this context, the terms ‘Gillespie’s method’, ‘The Stochastic Simulation Algorithm’ and ‘The Next Reaction Method’ are widely used to describe exact simulation methods. For example, Google Scholar records more than 5,500 citations to Gillespie’s seminal 1977 paper. I will look at the use of standard Monte Carlo when samples are produced by exact simulation and by approximation with tau-leaping or an Euler-Maruyama discretization of a diffusion approximation. In particular, I will point out some possible pitfalls when computational complexity is analysed. Appropriate modifications of recently proposed multilevel Monte Carlo algorithms will then be studied for the tau-leaping and Euler-Maruyama approaches. I will pay particular attention to a parameterization of the problem that, in the mass action chemical kinetics setting, corresponds to the classical system size scaling. This is joint work with David Anderson and Yu Sun at Wisconsin.
17:00-17:45: Mike Giles, Multilevel Monte Carlo for the simulation of dilute polymers. Abstract TBA.