Goda Takashi (University of Tokyo)

Multilevel Monte Carlo methods for efficient nested simulations

Nested simulation problem arises in a number of different applications, such as financial risk estimation, medical decision making, and construction of Bayesian experimental designs. Probably the most standard approach to tackle this problem is to consider naive Monte Carlo estimator for each of inner and outer loops, and then ``nest" them. However, it is well-known that the total computational cost required for such a nested Monte Carlo estimator to achieve the root-mean-squared error $\epsilon$ is typically of order $\epsilon^{-3}$ and even increases up to order $\epsilon^{-4}$ in the worse cases.

In this talk, we discuss applying multilevel Monte Carlo (MLMC) methods to reduce this cost significantly. In particular, motivated by applications to medical decision making, we focus on estimating what is called the expected value of information, and prove under some assumptions that the total computational cost for our MLMC estimator is of order $\epsilon^{-2}$. We also present some results of numerical experiments, which confirm the considerable computational savings achieved by our MLMC estimator as compared to the nested Monte Carlo estimator.

Xin Tong (National University of Singapore)

Can Algorithms Collaborate? The Replica Exchange Method and Its Spectral Gap

Abstract: Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minima. On the other hand, Langevin dynamics (LD) can explore the state space and find global minima, but in order to give accurate estimates, LD needs to run with a small discretization step size and weak stochastic force, which in general slows down its convergence. This paper shows that these two algorithms can “collaborate” through a simple exchange mechanism, in which they swap their current positions if LD yields a lower objective function. This idea can be seen as the singular limit of the replica-exchange technique from the sampling literature. We show that this new algorithm converges to the global minimum linearly with high probability, assuming the objective function is strongly convex in a neighborhood of the unique global minimum. By replacing gradients with stochastic gradients, and adding a proper threshold to the exchange mechanism, our algorithm can also be used in online settings. We further verify our theoretical results through some numerical experiments, and observe superior performance of the proposed algorithm over running GD or LD alone. We will further explain how does replica exchange method improve LD’s spectral gap using Poincare type of inequality.

Alexandre H. Thiery (National University of Singapore)

Exploiting geometry for walking larger steps in Bayesian Inverse Problems

Scaling limit analysis of some piecewise deterministic Markov processes

Recently, piecewise deterministic Markov processes have gained interest in the Monte Carlo community in the context of scalable Monte Carlo integration methods. In this talk, we will discuss scaling limits for some piecewise deterministic Markov processes. We will describe these results using multiscale analysis, which is a useful technique for this purpose.

This is joint work with J. Bierkens (TU Delft) and G. O. Roberts (Warwick).

Björn Sprungk (TU Bergakademie Freiberg)

Robust sampling methods for Bayesian inverse problems with small observational noise

The Bayesian approach to inverse problems provides a rigorous framework for the incorporation and quantification of uncertainties in measurements, parameters and models. We are interested in designing numerical methods which are robust w.r.t. the size of the observational noise, i.e., methods which behave well in case of concentrated posterior measures. The concentration of the posterior is a highly desirable situation in practice, since it relates to informative or large data. However, it can pose a computational challenge for numerical methods based on the prior as reference measure. We propose to employ the Laplace approximation of the posterior as the base measure for numerical integration in this context. The Laplace approximation is a Gaussian measure centered at the maximum a-posteriori estimate and with a covariance matrix depending on the Hessian of the log posterior density. We discuss the convergence of the Laplace approximation to the posterior measure in the Hellinger distance and analyze the efficiency of Monte Carlo methods based on it. In particular, we show that Laplace-based importance sampling and Laplace-based Markov chain Monte Carlo methods are robust w.r.t. the concentration of the posterior for large classes of posterior distributions and integrands whereas prior-based sampling methods are not.

This is joint work together with Claudia Schillings (U Mannheim), Daniel Rudolf (U Göttingen), and Philipp Wacker (U Erlangen-Nürnberg).

Tony Lelièvre (Ecole des Ponts ParisTech)

Adaptive importance sampling methods

We will present the general strategy of free energy adaptive importance sampling methods. These are very efficient algorithms to sample multimodal distributions with an information on the modes given by a so-called collective variable which indexes the modes. We will also discuss recent techniques to build this collective variable.

References:

- T. Lelièvre, M. Rousset and G. Stoltz, Long-time convergence of an Adaptive Biasing Force method, Nonlinearity, 21, 1155-1181 (2008).

- G. Fort, B. Jourdain, T. Lelièvre and G. Stoltz, Convergence and efficiency of adaptive importance sampling techniques with partial biasing, Journal of Statistical Physics, 171(2), 220-268 (2018).

- B. Jourdain, T. Lelièvre and P.A. Zitt, Convergence of metadynamics: discussion of the adiabatic hypothesis, to appear in Annals of Applied Probability.

- Z. Belkacemi, P. Gkeka, T. Lelièvre and G. Stoltz, Chasing Collective Variables using Autoencoders and biased trajectories, https://arxiv.org/abs/2104.11061 .

Alexandros Beskos (University College London)

Manifold Markov chain Monte Carlo methods for Bayesian inference in diffusion models