STAT 31512: Analysis of Sampling Algorithms
Instructor: Frederic Koehler
Class Schedule & Location
Monday and Wednesday, 3:00 PM - 4:20 PM
Location: Ryerson 176
Course Description
This is a graduate course on the mathematical analysis of algorithms for sampling from high-dimensional probability distributions. The course mostly focuses on the analysis of Markov-Chain Monte Carlo (MCMC) algorithms via functional inequalities. It aims to equip students with a deep understanding of the mathematical principles underlying these algorithms with a view towards current research questions.
Lecture Schedule
- Monday, March 18 - Intro, Sampling a 1D Ising Model
- Wednesday, March 20 - Laplacian, Counting and Sampling Spanning Trees
-
Monday, March 25 - Complexity theory and counting, limitations of exact formulas
Related reference: Jerrum book (below), chapter 2. Course notes (Sinclair) Vandermonde matrix #P
Scribe: Scribe Notes -
Wednesday, March 27 - Intro to random walks and MCMC. Perron-Frobenius theory
Related reference: Course notes (Sinclair) Perron-Frobenius theorem. Levin et al, Chapters 1 and 4.
Scribe: Scribe Notes - Monday, April 1 - Spectral theory of reversible Markov chains
-
Wednesday, April 3 - Glauber dynamics/Gibbs sampler
Related reference: Levin et al, Chapter 3. van Handel, Chapter 2.
Scribe: Scribe Notes -
Monday, April 8 - Efron-Stein inequality (Poincare for product measure), applications to concentration
Related reference: van Handel, Chapter 2. Levin et al, Chapter 12.4. Bakry et al, Chapter 4.
Scribe: Scribe Notes -
Wednesday, April 10 - SRW on cycle + Mixing and f-divergences
Related reference: Levin et al, Chapter 12.3 (SRW on cycle). Lecture notes (Sinclair). Lecture notes (Wu).
Scribe: Scribe Notes -
Monday, April 15 - Dobrushin's condition
Related reference: Lecture notes (Sinclair) Coupling and TV: Lecture Notes (Daskalakis) Original paper (Wu) Original paper (Hayes)
Scribe: Scribe Notes -
Wednesday, April 17 - Simulated annealing, Curie-Weiss Model
Related reference: Lecture Notes (Sinclair) Lecture Notes (Mei) Chebyshev's correlation inequality
Scribe: Scribe Notes -
Monday, April 22 - Cheeger's inequality, Random Cluster Model
Related references: Levin et al, Chapter 13.2. Grimmett, Chapter 1.4. Original paper (Guo-Jerrum), see also cited paper of Jerrum-Sinclair
Scribe: Scribe Notes - Wednesday, April 24 - Down-Up Walks on Simplicial Complexes
- Monday, April 29 - Log-Concave Polynomials, Spectral Independence, Local-to-Global
-
Wednesday, May 1 (virtual) - Statement of trickle-down, log-concavity for matroids.
Related references: same as above. See email for link to lecture.
Scribe: Scribe Notes -
Monday, May 6 - Proof of trickle-down
Related references: notes (see email). Also slides linked above.
Scribe: Scribe Notes -
Wednesday, May 8 - Langevin dynamics, log-concave measures
Related references: Chewi book, chapter 1. van Handel, chapter 2. Bakry et al, Chapters 1 and 2. Notes on Caffarelli Contraction
Handwritten notes: below. -
Monday, May 12 - Stochastic localization/"diffusion model"
Related references: Time inversion of Brownian motion (Pitman notes) See Section 4 (Klartag-Putterman). (Note: this discusses connection to Follmer drift.) Follmer's paper See Section 3 (El Alaoui-Montanari)
Handwritten notes for last two classes (do not perfectly match class, contains some typos!) Key facts about stochastic localization/diffusion (blackboard photo) -
Wednesday, May 14 - Entropy, Modified Log-Sobolev Inequalities vs. Poincar\'e', etc.
Related references: van Handel, chapter 3. Chewi, chapters 1 and 2. Slides (Anari) Lecture Notes (Liu) KLS up to polylog (Klartag-Lehec) On Chen's work on KLS (Klartag)
Handwritten notes (do not perfectly match class, contain typos)
Scribe Instructions
Every student enrolled for credit should scribe a class. Scribe notes should aim to be high quality, mathematically correct, and intelligible to someone who missed the class. They are due within 9 days of when the class occurred. I might ask for edits to the scribe notes if I observe areas for improvement. They will be posted on the course webpage.
Scribing template: template.tex Please send tex and pdf when completed with scribing.
Some useful references and notes
- Counting, Sampling, and Integrating: Algorithms and Complexity by Jerrum
- Summer school on spectral independence, lecture videos/notes by several people
- Markov Chains and Mixing Times by Levin, Peres, and Wilmer
- Mathematical Aspects of Mixing Times in Markov Chains by Montenegro and Tetali
- Probability in High Dimension by van Handel
- Analysis and Geometry of Markov Diffusion Operators by Bakry, Gentil, Ledoux
- From stochastic calculus to geometric inequalities by Eldan
- Lecture slides by Anari
- Course notes by Liu
- Course notes by Sinclair
- Course notes by Lau
- Draft book (log-concave sampling) by Chewi
- Lecture notes (in progress) by Chen
- Many other references... (try a web search, or look at links from other pages)
Other Logistics
There will be a course project with a written report for all students enrolled for a grade. You may either write a survey of at least 2 papers, or do original research. The main goal is to make a novel intellectual contribution, so do not just reproduce the contents of an existing paper. For example, even if you are doing a survey try to identify important open problems and whether the techniques in the paper have limitations, try to simplify the proofs, etc. Research that seeks to find new domains of application and connect with theory is also valued. Please send a half-page project proposal by end of Friday, April 5. Some papers of interest: Google doc
The final project deadline is Tuesday, May 21.
If you are auditing the class, please email me to ensure you receive relevant announcements.