MCMC Recent developments and new connections " September 14 to 25 2020 organized
Francis Bach (INRIA and ENS Paris) Optimization for machine learning Abstract: In these lectures, I will present recent results relating optimization and machine learning, with a particular focus on exponentially convergent stochastic algorithms for convex problems and global convergence of gradient descent for specific non convex problems. In these lectures, I will present recent results relating optimization and machine learning, with a particular focus on exponentially convergent stochastic algorithms for convex problems and global convergence of gradient descent for specific non convex problems. Arnaud Doucet (Oxford) Non reversible Parallel Tempering Abstract: Parallel tempering (PT) methods are a popular class of Markov chain Monte Carlo schemes used to sample complex high dimensional probability distributions. They rely on a collection of N interacting auxiliary chains targeting tempered versions of the target distribution to improve the exploration of the state space. We provide here a new perspective on these algorithms and their tuning by identifying and formalizing a sharp divide in the behaviour and performance of reversible versus non reversible PT schemes. By analyzing the behaviour of PT algorithms using a novel asymptotic regime in which N goes to infinity, we show indeed that a class of non reversible PT methods dominates its reversible counterparts and identify distinct scaling limits for the non reversible and reversible schemes, the former being a piecewise deterministic Markov process and the latter a diffusion. These theoretical results are exploited to develop an adaptive non reversible PT scheme approximating the optimal annealing schedule. Parallel tempering (PT) methods are a popular class of Markov chain Monte Carlo schemes used to sample complex high dimensional probability distributions. They rely on a collection of N interacting auxiliary chains targeting tempered versions of the target distribution to improve the exploration of the state space. We provide here a new perspective on these algorithms and their tuning by identifying and formalizing a sharp divide in the behaviour and performance of reversible versus non reversible PT schemes. By analyzing the behaviour of PT algorithms using a novel asymptotic regime in which N goes to infinity, we show indeed that a class of non reversible PT methods dominates its reversible counterparts and identify distinct scaling limits for the non reversible and reversible schemes, the former being a piecewise deterministic Markov process and the latter a diffusion. These theoretical results are exploited to develop an adaptive non reversible PT scheme approximating the optimal annealing schedule. Arnaud Doucet (Oxford) Controlled Sequential Monte Carlo Abstract: Sequential Monte Carlo methods, also known as particle methods, are a popular set of techniques for approximating high dimensional probability distributions and their normalizing constants. These methods have found numerous applications in statistics and related fields; e.g. for inference in non linear non Gaussian state space models, and in complex static models. Like many Sequential Monte Carlo methods, also known as particle methods, are a popular set of techniques for approximating high dimensional probability distributions and their normalizing constants. These methods have found numerous applications in statistics and related fields; e.g. for inference in non linear non Gaussian state space models, and in complex static models. Like many Hausdorff School page 1 Monte Carlo sampling schemes, they rely on proposal distributions which crucially impact their performance. We introduce here a class of controlled sequential Monte Carlo algorithms, where the proposal distributions are determined by approximating the solution to an associated optimal control problem using an iterative scheme. This method builds upon a number of existing algorithms in econometrics, physics, and statistics for inference in state space models, and generalizes these methods so as to accommodate complex static models. We demonstrate significant gains over state of the art methods at a fixed computational complexity on a variety of applications. Arnaud Doucet (Oxford) Unbiased Markov chain Monte Carlo Abstract: MCMC methods provide consistent estimators of integrals as the number of iterations goes to infinity but typically exhibit a bias after any fixed number of iterations. We will review two approaches that have been recently proposed by Glynn and Rhee (2014) and Jacob, O'Leary and Atchade (2019) to remove the bias using random truncations and coupling ideas. We will illustrate how these methods can be applied to complex algorithms. We will present conditions under which the resulting unbiased estimators can be computed in expected finite time and exhibit finite variance. Finally, we will illustrate the benefits and limitations of such ideas. Tony Lelievre (CERMICS and Ecole des Ponts Paris) Sampling problems in computational statistical physics Abstract: Computational statistical physics is typically a domain where efficient sampling methods are crucial. The objective is indeed to obtain macroscopic properties of materials starting from a microscopic description at the molecular level, using ensemble averages (thermodynamic properties) or averages over paths (dynamical properties) Applications are numerous in very different scientific fields such as molecular biology, chemistry or materials science. The objective of these lectures will be, starting from some prototypical sampling problems raised in statistical physics, to introduce general purpose algorithms which are useful to sample multimodal distributions, distributions supported on manifolds and metastable trajectories. More precisely, the first lecture will be devoted to free energy adaptive biasing techniques, and their analysis using entropy techniques or techniques useful to prove the convergence of stochastic algorithms. In the second lecture, we will present Hamiltonian Monte Carlo methods to sample measures on submanifolds of R. Finally, the third lecture will be devoted to a discussion of the link between metastable dynamics and jump Markov processes, using the notion of quasi stationary distribution. Jesus Maria Sanz Serna (Madrid) Numerical integrators for the Hamiltonian Monte Carlo method Abstract: When using the Hamiltonian Monte Carlo (HMC) method and its variants, most computational effort goes into the numerical simulation of the Hamiltonian dynamics. In practice, that simulation is (almost) always performed by means of the Leapfrog/Verlet/Stormer integrator. In my talks I will first explain why the demands that HMC imposes on the integrator have a number of peculiar features not present in other uses of numerical methods for ordinary differential equations. I will then explain the reasons why Leapfrog is so successful in some settings. Finally I will argue that, nevertheless, Leapfrog is not in general the optimal integrator and discuss alternative algorithms that afford an enhanced performance. Hausdorff School page 2 Aaron Smith (Ottawa) Methods for Bounding MCMC Error: Recent Advances and Comparisons Abstract: One of the main questions in the theory of Markov chains is to bound or estimate the rate at which a chain, or its ergodic averages, converges to a stationary measure. In the context of MCMC or computer science, this rate determines the efficiency of an algorithm; in statistical physics this might determine the qualitative behaviour of a system being modeled, while in other areas of probability a rapidly mixing chain might be used to prove efficient concentration inequalities. Although the different communities studying Markov chain convergence are aware of each other, methods have not always traveled quickly between them. One major difficulty has been the different systems being studied in particular, many probabilists and statistical physicists work on finite state spaces, while statisticians tend to be interested in continuous state spaces. The primary goal of this lecture series is to discuss some recent advances in estimating convergence of Markov chains that may be relevant to statisticians interested in MCMC. We will start with an overview of important parts of the classical theory of Markov chain convergence. This will include the mainstays of MCMC analysis (drift and minorization and its frequent companion, contraction) and some methods that are much more popular in other communities (conductance and canonical path approaches) From there, we will explore the relevance of various spectral methods to MCMC analysis. This will include some recent work on basic path bounds, the extension of the spectral profile method to continuous state spaces, and the sharpness of the spectral profile. We will also explore some recent breakthroughs involving the conductance method. This will include some work on both new methods for proving conductance inequalities and using profile based methods to obtain sharp bounds. Throughout, there will be an emphasis on illustrative examples and and comparison of these methods to classical methods. Finally, we will devote some time to survey (de )coupling methods that have been developed in the statistics community. We will emphasize the distinction between coupling methods for analyzing the convergence of chains and those for analyzing the convergence of ergodic averages. Hausdorff School page 3 Joris Bierkens (TU Delft) Spectral theory and asymptotic variance of piecewise deterministic samplers Abstract: Markov Chain Monte Carlo (MCMC) is an essential computational tool in quantitative fields such as Bayesian statistics, physics and machine learning. In recent years piecewise deterministic Markov processes (PDMPs) have emerged as a promising alternative to classical MCMC algorithms. In this talk PDMP based algorithms such as the Zig Zag Sampler and the Bouncy Particle Sampler will be introdu