Sampling Crash Course

on YouTube ↗01h 03m

" summary

Shows that random-walk Metropolis has exponentially small acceptance unless step size scales like O(1/d), uses conductance to turn that into provable lower bounds on mixing time, derives the continuous-time overdamped Langevin SDE with invariant density e^{-U} and characterizes invariant/detailed-balance drifts, proves synchronous coupling yields exponential W_p contraction under K-strong convexity, and introduces reflection coupling to exploit noise and obtain stronger (including total-variation) convergence controls.

AI-written summary · about

" chapters (15)

1. 0:00References
2. 2:54Direct Methods
3. 3:50Acceptance rejection
4. 4:29Creating samples from mu
5. 5:15Running time
6. 7:07Markov chain Monte Carlo
7. 13:05Mixing time
8. 15:10Relaxation times
9. 16:56probabilistic approaches
10. 18:27analytic approaches
11. 23:59Independent sampler
12. 25:03Proposal kernel
13. 27:19Random work metropolis
14. 31:00Conductance
15. 41:23Detailed Balance

" related talks

• 37mCorrelation Decay for Hard Spheres via Markov ChainsSamantha Petti · Computational Phase Transitions (Simons Institute, 2020)
• 31mInterpreting Machine Learning From the Perspective of Nonequilibrium SystemsDavid Limmer · Interpretable Machine Learning in Natural and Social Sciences (2022)
• 01h 02mContinuous Methods 1Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 31mThe Convergence of Hamiltonian Monte CarloSantosh Vempala · Optimization, Statistics and Uncertainty
• 58mTools from Stochastic Calculus 1Ronen Eldan · Analysis and TCS Boot Camp 2023
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 46mRandom Walks on Simplicial Complexes and Isoperimetric InequalitiesSayan Mukherjee · Spectral Algorithms: From Theory to Practice 2014