Unbiased constrained sampling with Self-Concordant Barrier Hamiltonian Monte Carlo

• URL: http://arxiv.org/abs/2210.11925v3
• Date: Sat, 28 Oct 2023 14:40:43 GMT
• Title: Unbiased constrained sampling with Self-Concordant Barrier Hamiltonian Monte Carlo
• Authors: Maxence Noble, Valentin De Bortoli, Alain Durmus
• Abstract summary: Barrier Hamiltonian Monte Carlo (BHMC) is a version of the HMC algorithm which aims at sampling from a Gibbs distribution $pi$ on a manifold $mathrmM$. We propose a new filter step, called "involution checking step", to address this problem. Our main results establish that these two new algorithms generate reversible Markov chains with respect to $pi$ and do not suffer from any bias in comparison to previous implementations.
• Score: 18.14591309607824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose Barrier Hamiltonian Monte Carlo (BHMC), a version of the HMC algorithm which aims at sampling from a Gibbs distribution $\pi$ on a manifold $\mathrm{M}$, endowed with a Hessian metric $\mathfrak{g}$ derived from a self-concordant barrier. Our method relies on Hamiltonian dynamics which comprises $\mathfrak{g}$. Therefore, it incorporates the constraints defining $\mathrm{M}$ and is able to exploit its underlying geometry. However, the corresponding Hamiltonian dynamics is defined via non separable Ordinary Differential Equations (ODEs) in contrast to the Euclidean case. It implies unavoidable bias in existing generalization of HMC to Riemannian manifolds. In this paper, we propose a new filter step, called "involution checking step", to address this problem. This step is implemented in two versions of BHMC, coined continuous BHMC (c-BHMC) and numerical BHMC (n-BHMC) respectively. Our main results establish that these two new algorithms generate reversible Markov chains with respect to $\pi$ and do not suffer from any bias in comparison to previous implementations. Our conclusions are supported by numerical experiments where we consider target distributions defined on polytopes.

Related papers

• Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
  We establish an oracle complexity of $widetildeOleft(fracdbeta2cal A2varepsilon6right)$ for simple annealed Langevin Monte Carlo algorithm. We show that $cal A$ represents the action of a curve of probability measures interpolating the target distribution $pi$ and a readily sampleable distribution.
  arXiv  Detail & Related papers  (2024-07-24T02:15:48Z)
• A Symplectic Analysis of Alternating Mirror Descent [11.117320730408272]
  We study the discretization of continuous-time Hamiltonian flow via the symplectic Euler method. We derive new error bounds on the modified Hamiltonian when truncated at orders in the stepsize. We propose a conjecture which, if true, would imply that the total regret for AMD scales as $mathcalOleft(K-1+varepsilonright)$ and the duality gap of the average iterates as $mathcalOleft(K-1+varepsilonright)$ for any $varepsilon>0$
  arXiv  Detail & Related papers  (2024-05-06T13:47:09Z)
• Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
  We study the task efficiently sampling from a Gibbs distribution $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC. Our results apply to general settings where $pi*$ can be non exponential and $Mh$ can have negative Ricci curvature.
  arXiv  Detail & Related papers  (2024-02-15T22:59:14Z)
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? [4.657614491309671]
  We analyze the mixing time of Metropolized Hamiltonian Monte Carlo (HMC) with the leapfrog integrator. We show that the joint distribution of the location and velocity variables of the discretization of the continuous HMC dynamics stays approximately invariant.
  arXiv  Detail & Related papers  (2023-04-10T17:35:57Z)
• Sampling with Barriers: Faster Mixing via Lewis Weights [8.701566919381223]
  We analyze a polytope defined by $m$ inequalities in $Rn$ endowed with the metric defined by the Hessian of a convex barrier function. The advantage of RHMC over Euclidean methods such as the ball walk, hit-and-run and the Dikin walk is in its ability to take longer steps.
  arXiv  Detail & Related papers  (2023-03-01T13:09:47Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• An Introduction to Hamiltonian Monte Carlo Method for Sampling [26.555110725656963]
  Hamiltonian Monte Carlo (HMC) is a Hamiltonian dynamics-inspired algorithm for sampling from a Gibbs density $pi(x) propto e-f(x)$. We show that idealized HMC preserves $pi$ and we establish its convergence when $f$ is strongly convex and smooth.
  arXiv  Detail & Related papers  (2021-08-27T03:28:20Z)
• Orbital MCMC [82.54438698903775]
  We propose two practical algorithms for constructing periodic orbits from any diffeomorphism. We also perform an empirical study demonstrating the practical advantages of both kernels.
  arXiv  Detail & Related papers  (2020-10-15T22:25:52Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• A diffusion approach to Stein's method on Riemannian manifolds [65.36007959755302]
  We exploit the relationship between the generator of a diffusion on $mathbf M$ with target invariant measure and its characterising Stein operator. We derive Stein factors, which bound the solution to the Stein equation and its derivatives. We imply that the bounds for $mathbb Rm$ remain valid when $mathbf M$ is a flat manifold.
  arXiv  Detail & Related papers  (2020-03-25T17:03:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.