Mathematical Sciences Research Institute

Home » Workshop » Schedules » Convergence of Hamiltonian Monte Carlo and Faster Polytope Volume Computation

Convergence of Hamiltonian Monte Carlo and Faster Polytope Volume Computation

Geometric functional analysis and applications November 13, 2017 - November 17, 2017

November 16, 2017 (02:45 PM PST - 03:45 PM PST)
Speaker(s): Yin Tat Lee (University of Washington)
Location: MSRI: Simons Auditorium
  • Hamiltonian Monte Carlo

  • Sampling

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification No Secondary AMS MSC



We explain the Hamiltonian Monte Carlo method and apply it to the problem of 1) generating uniform random points from polytopes, 2) computing the volume of polytopes. For polytopes in R^n specified by O(n) inequalities, the resulting algorithm for both problems takes merely O*(n^1.667) steps. For volume computation, this is a huge improvement over the previous best algorithm that requires O(n^4) steps. The key idea is to prove certain isoperimetric inequalities on manifolds defined by log barrier functions. Joint work with Santosh Vempala

30102?type=thumb Lee Notes 2.11 MB application/pdf Download
Video/Audio Files


H.264 Video 15-Lee.mp4 116 MB video/mp4 rtsp://videos.msri.org/data/000/030/024/original/15-Lee.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath Videos page.