Hamiltonian Monte Carlo with boundary reflections, and application to polytope volume calculations
Hamiltonian Monte Carlo avec réflexions, et application au calcul du volume de polytopes
Résumé
This paper studies HMC with reflections on the boundary of a domain, providing an
enhanced alternative to Hit-and-run (HAR) to sample a target distribution in a bounded domain.
We make three contributions. First, we provide a convergence bound, paving the way to more
precise mixing time analysis. Second, we present a robust implementation based on multi-precision
arithmetic – a mandatory ingredient to guarantee exact predicates and robust constructions. Third,
we use our HMC random walk to perform polytope volume calculations, using it as an alternative to
HAR within the volume algorithm by Cousins and Vempala. The tests, conducted up to dimension
50, show that the HMC RW outperforms HAR.
Ce papier étudie HMC avec réflexions au bord du domaine, donnant une meilleure
alternative a Hit-and-Run (HAR) pour échantillonner une distribution cible dans un domaine
borné. Nous apportons trois contributions. Premièrement, nous prouvons une borne de convergence,
préparant le terrain pour une analyse plus précise du mixing time. Deuxièmement, nous
produisons une implémentation robuste basée sur l’arithmétique multi-precision. Troisièmement,
nous utilisons HMC avec réflexions comme une alternative à HAR pour calculer le volume de
polytopes pour l’algorithme de Cousins et Vempala. Les tests, conduits jusqu’en dimension 50
montrent que HMC avec réflexions est plus performant que HAR.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...