Embedded Files
This page acts as a syllabus for a course on couplings and their use in Monte Carlo, both in theory and in methods.
Update: In Spring 2023 and in Spring 2024 the course was used for the material of Optimization-Conscious Econometrics Summer School (June 5-8, 2023, and June 3-6, 2024 University of Chicago): you can find slides here on MCMC and couplings.
Update: in Spring 2021 the course was turned into STAT 248 at Harvard University. The lecture notes are available in this folder. You will also find exercises, R scripts, and the support for the video lectures. The videos are available on Youtube. You can skip the first 11:30 minutes of the first video to get right into the material.
The description below corresponds to an earlier version of the course and is kept here only for reference. I suggest learning from the most recent version of the course, of course.
--
The course was given in Université Paris-Dauphine as part of the M.Sc. in Applied Mathematics in February 2020 over 12 hours (thanks Robin Ryder and Christian P. Robert), at the University of Bristol in March 2020 over 4 hours (thanks Anthony Lee) and at the University of Torino, as part of the M.Sc. in Stochastics and Data Science, remotely over 16 hours in May 2020 (thanks Matteo Ruggiero). I am grateful to these people and these institutions for supporting this course, and to the students of these universities for the helpful feedback.
The course is about the method of coupling in probability and its use in Monte Carlo methods, which refer to algorithms generating samples from probability distributions of interest. The course includes an introduction to Monte Carlo methods (rejection sampling, importance sampling, MCMC), followed by an introduction to the coupling method. This includes the celebrated "coupling inequality" and various coupling interpretations of notions of distances between probability distributions, such as total variation and Wasserstein. The course then focuses on Markov chain methods and describes how couplings of Markov chains can be employed to quantify their convergence. The last part of the course covers various Monte Carlo methods that rely on explicit coupling constructions in their implementations, such as Coupling From The Past (Propp & Wilson 1996), debiasing techniques (Glynn & Rhee 2014) and some convergence diagnostics for MCMC (Johnson 1996).
Outline of the course
The course is made of two main components: a more conceptual/theoretical component, and a more algorithmic/methodological component. The lectures might alternate with topics from both components, i.e. we won't do all of the theory, and then all of the methods.
Introduction on Monte Carlo methods, rejection sampling, importance sampling, some MCMC methods
Couplings of random variables, the celebrated "coupling inequality". Some examples of using couplings to derive some non-trivial results in probability (Thórisson 1995). Some connections to optimal transport (as in Monge/Kantorovich/Wasserstein distances, see Peyré & Cuturi).
Coupling of Markov chains, geometric ergodicity of MCMC algorithms (Jerrum 1998, Roberts & Rosenthal 2004, Jones & Hobert 2004)
Monte Carlo methods employing coupled Markov chains, including Coupling From The Past (Propp & Wilson 1996), debiasing techniques (Glynn & Rhee 2014, Jacob, O'Leary & Atchadé 2017), diagnostics of convergence (Johnson 1996, Biswas et al 2019), etc.
Videos
The course can be followed with videos.
A youtube playlist can be found here. It gathers 16 videos, each around 40-45 minutes long.
The videos were made for the students of the M.Sc. in Stochastics and Data Science of the University of Torino, at the generous invitation of Matteo Ruggiero. These were made rather quickly, in the strange circumstances of the lockdown, so please be forgiving.
To contact me, send an email to: pjacob at g dot harvard dot edu.
Lecture notes
The lecture notes are available as pdf files in that folder.
Chapter 3: convergence of Markov chains
Chapter 4: methods using coupled Markov chains
All of these lecture notes are still work in progress, please be forgiving. Any feedback would be much appreciated.
Code
... eventually the repository will contain scripts that produce figures of the lecture notes, and perhaps the source code for the lecture notes themselves.
Exercises
A good exercise would be to try to understand and reproduce each figure of the lecture notes.
For possible projects (if you need one): prepare a 15 minute presentation including your own simulations, relating to either one of the papers:
Pinto & Neal (2001) "Improving Markov chain Monte Carlo estimators by coupling to an approximating chain'' [link]
Piponi, Hoffman, Sountsov (2020) "Hamiltonian Monte Carlo Swindles" [link]
Devroye (1990) "Coupled samples in simulations" [link]
Johnson (1996) "Studying Convergence of Markov Chain Monte Carlo Algorithms Using Coupled Sample Paths" [link].
Nicholls, Fox, Watt (2012) "Coupled MCMC with a randomized acceptance probability" [link]
For bibliographic references, please see the lecture notes.
Google Sites
Report abuse