arXiv (Cornell University) · 2019 · 17 citations · 16 references
Natural SciencesPhysicsComputational PhysicsOptimizationStochastic ProcessesApproximation AlgorithmsApproximation MethodsConvex OptimizationMonte Carlo MethodsMonte Carlo SimulationNumerical ConvergenceCondition Number AnalysisConvex RelaxationsHamiltonian Monte CarloMonte Carlo SamplingOptimal Convergence Rates
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to $e^{-f}$ where $f:\mathbb{R}^d \to \mathbb{R}$ is $μ$-strongly convex and $L$-smooth (the condition number is $κ= L/μ$). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is $O(κ)$, improving on the previous best bound of $O(κ^{1.5})$; we complement this with an example where the relaxation time is $Ω(κ)$. When implemented using a nearly optimal ODE solver, HMC returns an $\varepsilon$-approximate point in $2$-Wasserstein distance using $\widetilde{O}((κd)^{0.5} \varepsilon^{-1})$ gradient evaluations per step and $\widetilde{O}((κd)^{1.5}\varepsilon^{-1})$ total time.
16
Sampling and integration of near log-concave functions
David Applegate, Ravi Kannan · 1991 · 146 citations · Full text
Underdamped Langevin MCMC: A non-asymptotic analysis
Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett et al. · arXiv (Cornell University) · 2017 · 98 citations · Full text