Math @ Duke

Publications [#354088] of Holden Lee
Papers Published
 Ge, R; Lee, H; Lu, J, Estimating normalizing constants for logconcave distributions: Algorithms and lower bounds,
Proceedings of the Annual Acm Symposium on Theory of Computing
(June, 2020),
pp. 579586 [doi]
(last updated on 2022/01/28)
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=gg.,d ef(x) dx to within a multiplication factor of 1 ± ϵ for a μstrongly convex and Lsmooth function f, given query access to f(x) and g‡ 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 O(d4/3κ + d7/6κ7/6/ϵ2) queries to g‡ f are sufficient, where κ= L / μ is the condition number. Moreover, we provide an information theoretic lowerbound, showing that at least d1o(1)/ϵ2o(1) queries are necessary. This provides a first nontrivial lowerbound for the problem.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

