Videos

Convergence of Hamiltonian Monte Carlo and Faster Polytope Volume Computation

Presenter
November 16, 2017
Keywords:
  • Hamiltonian Monte Carlo
  • Sampling
MSC:
  • 68W20
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