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

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ℝd e-f(x),dx to within a multiplication factor of 1 ± varepsilon for a μ-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 widetildeOBigl(fracd4/3kappa + d7/6kappa7/6varepsilon2Bigr) queries to nabla f are sufficient, where kappa= L / μ is the condition number. Moreover, we provide an information theoretic lowerbound, showing that at least fracd1-o(1)varepsilon2-o(1) queries are necessary. This provides a first nontrivial lowerbound for the problem.