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: SLMath: Eisenbud Auditorium
Tags/Keywords
  • Hamiltonian Monte Carlo

  • Sampling

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

15-Lee

Abstract

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

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

15-Lee

H.264 Video 15-Lee.mp4 116 MB video/mp4 rtsp://videos.msri.org/15-Lee/15-Lee.mp4 Download
Troubles with video?

Please report video problems to itsupport@slmath.org.

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