Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds

Abstract

Estimating the normalizing constant of an unnormalized probability distribution has important applications in computer science, statistical physics, machine learning, and statistics. In this work, we consider the problem of estimating the normalizing constant $Z={\int }_{{\mathbb{R}}^d}{e}^{-f(x)}\mathrm{d}x$ to within a multiplication factor of $1\pm \epsilon$ for a $\mu$-strongly convex and $L$-smooth function $f$, given query access to $f(x)$ and $\nabla f(x)$. We give both algorithms and lowerbounds for this problem. Using an annealing algorithm combined with a multilevel Monte Carlo method based on underdamped Langevin dynamics, we show that $\tilde{\mathcal{O}}\left(\frac{d^{4/3}\kappa +d^{7/6}{\kappa }^{7/6}}{{\epsilon }^2}\right)$ queries to $\nabla f$ are sufficient, where $\kappa =L/\mu$ is the condition number. Moreover, we provide an information theoretic lowerbound, showing that at least $\frac{d^{1-o(1)}}{{\epsilon }^{2-o(1)}}$ queries are necessary. This provides a first nontrivial lowerbound for the problem.

arXiv comment46 pages

References in corpus (15)

• A nonequilibrium equality for free energy differences
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Geometric integrators and the Hamiltonian Monte Carlo method
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Is There an Analog of Nesterov Acceleration for MCMC?
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Multilevel Monte Carlo for Scalable Bayesian Computations
• Sampling normalizing constants in high dimensions using inhomogeneous diffusions
• Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume

Cited by in corpus (2)

• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Advances in deep learning methods for pavement surface crack detection and identification with visible light visual images