A new class of uniformly ergodic MCMC algorithms, termed Diffeomorphic Contraction Sampler (DCS), is introduced, and fast non-asymptotic mixing guarantees for DCS targeting distributions on $\R^d$ with arbitrarily heavy polynomial tails are provided.
Abstract
We introduce a new class of uniformly ergodic MCMC algorithms, termed Diffeomorphic Contraction Sampler (DCS), and provide fast non-asymptotic mixing guarantees for DCS targeting distributions on $\R^d$ with arbitrarily heavy polynomial tails. DCS provides a solution to a well-known problem for MCMC samplers, which typically struggle with the combination of unbounded high-dimensional state space and vanishing gradients. The DCS pulls back a target on $\R^d$ onto a Euclidean ball $B(R)\subset\R^d$ and then samples from the transformed density on the convex set $B(R)$ via algorithms such as the Ball Walk, Hit-and-Run and others. A radial diffeomorphic contraction is chosen so that the pull-back density on $B(R)$ is bounded, implying uniform ergodicity for \textit{all} targets with a finite polynomial moment. Non-asymptotic bounds for DCS require stronger assumptions such as log-concavity of the pull-back density. In practice, this is achieved approximately by a preconditioned automorphism of the ball $B(R)$, tuned via Variational Inference. Numerical simulation tests demonstrate that the DCS outperforms significantly the No-U-Turns sampler on multi-dimensional heavy-tailed targets arising as real-world posteriors in PosteriorDB benchmark. DCS also numerically outperforms in high-dimensional examples recently developed spherical projection samplers for heavy-tailed target distributions.
Given a strongly convex function $u$, equip $R^d$ with a Riemannian metric given by the Hessian $\nabla^2 u$. This is a so-called Hessian manifold. Given a probability density $\mu$ one may run a Langevin diffusion intrinsic to the manifold with stationary distribution $\mu$. Such (Hessian) manifold-valued Langevin diffusions are called Mirror Langevin diffusions (MLD) which have recently become popular. One of the questions we explore is whether, given $\mu$, one can choose $u$ to get an exponential convergence to equilibrium for the MLD, especially if $\mu$ is not strongly log-concave. Our results are based on Lyapunov function methods and give sufficient conditions for a Poincar\'e or a log-Sobolev inequality to hold for the MLD. These, in turn, imply exponential convergence. We also introduce a Markov chain approximation to the MLD given by a two step Gibbs sampler with stationary distribution $\mu$. This Markov chain is a variant of the Sinkhorn Markov chain introduced in arXiv:2307.16421 that is conjectured to converge to a time-inhomogeneous generalization of the MLD. Under suitable assumptions, we prove that the Markov chain has a guaranteed convergence rate in $\chi^2$ that is consistent with the diffusion time scale. Our proofs are based on ideas from entropic optimal transport and strong data processing inequalities.
Benjamin Capdeville, Young-Heon Kim, Soumik Pal· 0 citations
We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $\alpha$-Talagrand inequality (for example, if the target distribution is $\alpha$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $\Theta(\alpha^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\alpha^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.
Siddharth Mitra, Vishwak Srinivasan, Xiuyuan Wang et al.· 1 citation
We consider a fractional Brownian motion $B$ with Hurst index $0<H<1/2$, and its maximiser $\tau$ on $[0,1]$. We show that the rescaled process $a^H(B_{\tau+\,\cdot\,/a}-B_\tau)$ converges in $C_{\mathrm{loc}}(\mathbb R)$ to a limiting tangent law that is $H$-self-similar, supported on nonpositive paths pinned at zero, and rerooting-rescaling invariant: rerooting the limit process at its maximum on any fixed compact interval separated from zero and rescaling again asymptotically reproduces the same law. We also identify the tangent law as the limit of two-sided finite-grid hard-wall laws as the mesh vanishes and both horizons diverge, which can informally be interpreted as conditioning fractional Brownian motion on a nonpositive path. As an application, we consider persistence probabilities for fractional Brownian motion: a tilted variant of $B$ yields a different tangent law with a finite left horizon and an infinite right horizon and we show that \[ \mathbb P(B_t\leq1\text{ for all }0\leq t\leq T) = \big(C+o(1)\big)\,T^{-(1-H)},\quad \text{as }T\to\infty, \] where the leading order coefficient $C\in(0,\infty)$ has an explicit representation in terms of the expected maximum and the tilted tangent law.
We develop a new uniform drift condition and local minorization that implies a stronger weighted form of uniform ergodicity for Markov chains we call hyper-V uniform ergodicity. The convergence guarantees geometric decay of the bias towards the invariant measure independently of the initialization for all functions controlled by a dominating function V. A key advantage of the approach is that it bypasses the need to establish a global minorization condition, which is often substantially more difficult to verify in practice, while yielding stronger convergence guarantees than global minorization. Optimal convergence bounds in a minimax sense of the framework are established. The utility of the framework is demonstrated through applications to the P'olya-Gamma and Kolmogorov-Gamma Gibbs samplers. We also show qualitative hyper-V uniform ergodicity convergence for two-variable Gibbs samplers can be inferred by the form of the invariant measure, bypassing convergence analysis entirely.
Sampling from multimodal distributions is a longstanding challenge for classical local Markov chain Monte Carlo (MCMC) methods. A popular remedy is to introduce a sequence of intermediate distributions that interpolate between the target and a simpler reference. The classical choice, tempering, raises the density to a power, but distorts the relative weights of asymmetric modes and can lead to poor mixing. We instead propose interpolating along the diffusion path, the marginals of a noising diffusion process that carries the target toward a Gaussian. This path preserves the relative weights of the modes and enjoys favorable mixing properties, which we make precise through a spectral-gap analysis of the corresponding ideal transition kernel. Sampling along the path requires its intermediate scores, which can be estimated from the unnormalized target through variational approaches, yielding only an approximate sampler. To remove the resulting bias, we introduce the Metropolis-adjusted diffusion path (MAD-Path) sampler, which corrects the diffusion-path proposal in an augmented path space and leaves the target invariant regardless of the accuracy of the learned score or the discretization error. We further quantify how these two errors affect the acceptance probability, providing guidance for practical tuning. Experiments on a range of Bayesian posteriors show that MAD-Path improves global exploration and mode-weight estimation relative to tempering-based MCMC methods and unadjusted diffusion samplers.
We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias $O(\tau_{\mathrm{mix}}/T)$ uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under $\sigma^2\mapsto 2\Lambda G_\sigma^2$ and $L^2\mapsto 2\Lambda L^2$, where $\Lambda=O(\tau_{\mathrm{mix}}\log T)$. For positive centered noise, the tuned method achieves expected sample complexity $\widetilde{O}((\tau_{\mathrm{mix}}^2G_\sigma+\tau_{\mathrm{mix}}^{5/2}G_\sigma^2)\varepsilon^{-3}+\tau_{\mathrm{mix}}^5\varepsilon^{-2})$. The exactly noiseless specialization achieves $\widetilde{O}(\varepsilon^{-2})$ with mixing-time-free constants, while a mixing-time-oblivious variant achieves $\widetilde{O}(\tau_{\mathrm{mix}}^6\varepsilon^{-3}+\tau_{\mathrm{mix}}^3\varepsilon^{-2})$. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.