Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps
- URL: http://arxiv.org/abs/2209.12771v1
- Date: Mon, 26 Sep 2022 15:29:29 GMT
- Title: Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps
- Authors: Simon Apers, Sander Gribling, D\'aniel Szil\'agyi
- Abstract summary: Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density $e-f(x)$.
We show that HMC can sample from a distribution that is $varepsilon$-close in total variation distance using $widetildeO(sqrtkappa d1/4 log(1/varepsilon)$ gradient queries.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a
high-dimensional distribution with density $e^{-f(x)}$, given access to the
gradient of $f$. A particular case of interest is that of a $d$-dimensional
Gaussian distribution with covariance matrix $\Sigma$, in which case $f(x) =
x^\top \Sigma^{-1} x$. We show that HMC can sample from a distribution that is
$\varepsilon$-close in total variation distance using
$\widetilde{O}(\sqrt{\kappa} d^{1/4} \log(1/\varepsilon))$ gradient queries,
where $\kappa$ is the condition number of $\Sigma$. Our algorithm uses long and
random integration times for the Hamiltonian dynamics. This contrasts with (and
was motivated by) recent results that give an $\widetilde\Omega(\kappa
d^{1/2})$ query lower bound for HMC with fixed integration times, even for the
Gaussian case.
Related papers
- Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
This paper deals with the problem of efficient sampling from a differential equation, given the drift function and the diffusion matrix.
It is possible to obtain independent and identically distributed (i.i.d.) samples at precision $varepsilon$ with a cost that is $m2 d log (1/varepsilon)$
Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
arXiv Detail & Related papers (2023-03-30T02:50:49Z) - Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration [0.0]
Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $Delta$ compered to classical counterparts.
We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference.
In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $ell$ scales on $Delta$, the required accuracy $epsilon$ and the standard deviation $sigma$ of $ell$ as $tildeO(sigma/epsilon
arXiv Detail & Related papers (2023-03-10T01:05:16Z) - Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration [0.0]
A novel unadjusted Hamiltonian Monte Carlo (uHMC) algorithm is suggested.
It uses a stratified Monte Carlo (SMC) time integrator for the underlying Hamiltonian dynamics.
The complexity of the uHMC algorithm with Verlet time integration is in general $Oleft((d/K)1/2 (L/K)2 varepsilon-1 log( boldsymbolmathcalW2(mu, nu) / varepsilon-1 log( boldsymbolmathcalW
arXiv Detail & Related papers (2022-11-20T15:45:26Z) - Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time [13.427128424538502]
Hamiltonian Monte Carlo (HMC) is a popular method in sampling.
We propose a scheme of time-varying integration time based on the roots of Chebyshevs.
arXiv Detail & Related papers (2022-07-05T17:42:22Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$.
We propose a novel random technique, called Ternary Random Feature (TRF)
The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
arXiv Detail & Related papers (2021-10-05T09:33:49Z) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
We give algorithms for sampling several structured logconcave families to high accuracy.
We further develop a reduction framework, inspired by proximal point methods in convex optimization.
arXiv Detail & Related papers (2020-10-07T01:43:07Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
We show that a method with an overall computational cost of $mathcalO(log N)2D(loglog N)2)$ can be used to perform inference.
arXiv Detail & Related papers (2020-08-01T19:23:34Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
We show that extending the smoothing technique to defend against other attack models can be challenging.
We present experimental results on CIFAR to validate our theory.
arXiv Detail & Related papers (2020-02-08T22:02:14Z)
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.