Convergence of Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Location: MSRI: Simons Auditorium
Hamiltonian Monte Carlo
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
Please report video problems to email@example.com.
See more of our Streaming videos on our main VMath Videos page.