Convergence of Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Geometric functional analysis and applications November 13, 2017 - November 17, 2017
Location: SLMath: Eisenbud Auditorium
Tags/Keywords
Hamiltonian Monte Carlo
Sampling
15-Lee
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
Lee Notes
|
Download |
15-Lee
H.264 Video |
15-Lee.mp4
|
Download |
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.