  Doubly intractable distributions arise in many settings, for example in
Markov models for point processes and exponential random graph models for
networks. Bayesian inference for these models is challenging because they
involve intractable normalising "constants" that are actually functions of the
parameters of interest. Although several clever computational methods have been
developed for these models, each method suffers from computational issues that
makes it computationally burdensome or even infeasible for many problems. We
propose a novel algorithm that provides computational gains over existing
methods by replacing Monte Carlo approximations to the normalising function
with a Gaussian process-based approximation. We provide theoretical
justification for this method. We also develop a closely related algorithm that
is applicable more broadly to any likelihood function that is expensive to
evaluate. We illustrate the application of our methods to a variety of
challenging simulated and real data examples, including an exponential random
graph model, a Markov point process, and a model for infectious disease
dynamics. The algorithm shows significant gains in computational efficiency
over existing methods, and has the potential for greater gains for more
challenging problems. For a random graph model example, we show how this gain
in efficiency allows us to carry out accurate Bayesian inference when other
algorithms are computationally impractical.
