The Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions and relies on a bound on the average KL divergence along Hamiltonian dynamics.
Abstract
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.
We study exact simulation of diffusions via rejection sampling on path space using unbiased estimators of the density ratio obtained from Girsanov's theorem. When applied to the underdamped Langevin diffusion, it yields an algorithm for sampling from a strongly log-concave and log-smooth distribution with condition number $\kappa$, in dimension $d$, to accuracy $\varepsilon$ in R\'enyi divergence, in $\widetilde O(\kappa^{2/3} d^{1/3}\,\mathrm{polylog}(1/\varepsilon))$ queries. Under a third derivative bound, the dimension dependence improves to $d^{1/5}$. This improves substantially over the prior state-of-the-art complexity of $\widetilde O(\kappa d^{1/2}\,\mathrm{polylog}(1/\varepsilon))$ for the Metropolis-adjusted Langevin algorithm, and over the $d^{1/4}$ dimension dependence of Metropolized Hamiltonian Monte Carlo under the same third derivative bound. We also present applications to the mirror Langevin diffusion, and for obtaining Fisher information bounds in the non-log-concave case.
Fan Chen, Sinho Chewi, Alexander Rakhlin et al.· 1 citation
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.
We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable $A$ at time $t$. By analyzing the convergence of the perturbative expansion in the interaction strength $\lambda$ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime $\lambda |t|^{2D+1}=\mathcal{O}(1)$, when the Hamiltonian is geometrically local on a $D$-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to $\lambda |t|=\mathcal{O}(1)$ with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to $\lambda |t|=\mathcal{O}(1)$, modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.
We consider beta-Dyson Brownian motion, with $\beta>= 1$, started from a deterministic configuration with uniformly bounded support. Let $\mu_t$ be the semicircular free-convolution flow issued from the initial empirical measure, and set $S_t = supp(\mu_t)$. For every fixed $T, \epsilon>0$, with probability at least $1 - C \exp(-(log n)^2)$, every particle remains within an epsilon-neighborhood of $S_t$ for all $0<= t<= T$. The result holds from time zero, requires no regularity assumption at the initial spectral edges, and applies to multi-cut supports with macroscopic interior gaps. A key ingredient is a deterministic local resolvent exclusion principle: an $o((n \eta)^(-1))$ comparison of Stieltjes transforms on a complex disc above a real point separated from the reference support excludes eigenvalues from the corresponding real interval. This gives a model-independent mechanism for converting local resolvent estimates into spectral confinement.
Quasi-Monte Carlo sampling is a numerical integration method that uses points with a space-filling property in $[0,1]^s$ designed to give better estimates than plain Monte Carlo methods do. For integrands of bounded variation in the sense of Hardy and Krause, errors of $O(n^{-1+\epsilon})$ for any $\epsilon>0$ are obtained from $n$ sample points. Randomized quasi-Monte Carlo (RQMC) points are individually uniformly distributed but collectively space-filling and then independent replications provide variance estimates. For smooth enough integrands the randomization can give a root mean squared error of $O(n^{-3/2+\epsilon})$. This article explains RQMC for a statistical readership recounting some history and presenting some current directions.
We study a variant of the Thompson Sampling (TS) algorithm, called $\alpha$-TS, for solving stochastic generalized linear bandit problems. Existing analyses of TS require inflating the posterior variance to derive near-optimal regret guarantees. We formalize the idea of variance inflation by introducing $\alpha$-TS that uses a fractional or $\alpha$-posterior instead of the standard posterior. Our main contribution is to identify general regularity conditions on the prior and reward distributions that enable a regret analysis of $\alpha$-TS without assuming any tractable approximation of the posterior distribution, unlike previous works. For a specific choice of $\alpha \propto d^{-1}$, our general regret bound yields the best known regret bound of $O(d^{3/2}\sqrt{T}\log T)$ for both the exponential and sub-Gaussian families of reward distributions. We further provide an $\alpha$-dependent lower bound showing that the regret constant depends on the product $\alpha d$, and that when $\alpha \propto d^{-1}$ the regret scales as $\Omega(d^{3/2}\sqrt{T})$, explaining the origin of the $d^{3/2}$ factor in the upper bound. Our proof technique adapts and combines recent advancements in the analysis of linear bandit problems with first- and second-order posterior concentration theory from the Bayesian statistics literature.
Prateek Jaiswal, D. Pati, A. Bhattacharya et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
