  Recent research has developed several Monte Carlo methods for estimating the
normalization constant (partition function) based on the idea of annealing.
This means sampling successively from a path of distributions that interpolate
between a tractable "proposal" distribution and the unnormalized "target"
distribution. Prominent estimators in this family include annealed importance
sampling and annealed noise-contrastive estimation (NCE). Such methods hinge on
a number of design choices: which estimator to use, which path of distributions
to use and whether to use a path at all; so far, there is no definitive theory
on which choices are efficient. Here, we evaluate each design choice by the
asymptotic estimation error it produces. First, we show that using NCE is more
efficient than the importance sampling estimator, but in the limit of
infinitesimal path steps, the difference vanishes. Second, we find that using
the geometric path brings down the estimation error from an exponential to a
polynomial function of the parameter distance between the target and proposal
distributions. Third, we find that the arithmetic path, while rarely used, can
offer optimality properties over the universally-used geometric path. In fact,
in a particular limit, the optimal path is arithmetic. Based on this theory, we
finally propose a two-step estimator to approximate the optimal path in an
efficient way.

Machine Learning;Machine Learning