arXiv:1705.07224v2 [stat.ML] 4 Nov 2017

AIDE: An algorithm for measuring the accuracy of
probabilistic inference algorithms

Marco F. Cusumano-Towner
Probabilistic Computing Project
Massachusetts Institute of Technology
marcoct@mit.edu

Vikash K. Mansinghka
Probabilistic Computing Project
Massachusetts Institute of Technology
vkm@mit.edu

Abstract
Approximate probabilistic inference algorithms are central to many fields. Examples include sequential Monte Carlo inference in robotics, variational inference
in machine learning, and Markov chain Monte Carlo inference in statistics. A
key problem faced by practitioners is measuring the accuracy of an approximate
inference algorithm on a specific data set. This paper introduces the auxiliary
inference divergence estimator (AIDE), an algorithm for measuring the accuracy of
approximate inference algorithms. AIDE is based on the observation that inference
algorithms can be treated as probabilistic models and the random variables used
within the inference algorithm can be viewed as auxiliary variables. This view leads
to a new estimator for the symmetric KL divergence between the approximating
distributions of two inference algorithms. The paper illustrates application of AIDE
to algorithms for inference in regression, hidden Markov, and Dirichlet process
mixture models. The experiments show that AIDE captures the qualitative behavior
of a broad class of inference algorithms and can detect failure modes of inference
algorithms that are missed by standard heuristics.

1

Introduction

Approximate probabilistic inference algorithms are central to diverse disciplines, including statistics,
robotics, machine learning, and artificial intelligence. Popular approaches to approximate inference
include sequential Monte Carlo, variational inference, and Markov chain Monte Carlo. A key problem
faced by practitioners is measuring the accuracy of an approximate inference algorithm on a specific
data set. The accuracy is influenced by complex interactions between the specific data set in question,
the model family, the algorithm tuning parameters such as the number of iterations, and any associated
proposal distributions and/or approximating variational family. Unfortunately, practitioners assessing
the accuracy of inference have to rely on heuristics that are either brittle or specialized for one type
of algorithm [1], or both. For example, log marginal likelihood estimates can be used to assess
the accuracy of sequential Monte Carlo and variational inference, but these estimates can fail to
significantly penalize an algorithm for missing a posterior mode. Expectations of probe functions do
not assess the full approximating distribution, and they require design specific to each model.
This paper introduces an algorithm for estimating the symmetrized KL divergence between the output
distributions of a broad class of exact and approximate inference algorithms. The key idea is that
inference algorithms can be treated as probabilistic models and the random variables used within
the inference algorithm can be viewed as latent variables. We show how sequential Monte Carlo,
Markov chain Monte Carlo, rejection sampling, and variational inference can be represented in a
common mathematical formalism based on two new concepts: generative inference models and
meta-inference algorithms. Using this framework, we introduce the Auxiliary Inference Divergence
Estimator (AIDE), which estimates the symmetrized KL divergence between the output distributions
of two inference algorithms that have both been endowed with a meta-inference algorithm. We also

Gold standard
inference algorithm

Number of gold-standard N
g
inference runs

Target inference algorithm
(the algorithm being measured)

Nt Number of target
inference runs

AIDE
Auxiliary Inference
Divergence Estimator

Number of meta-inference
Mg
runs for gold-standard

Mt

Number of meta-inference
runs for target

Symmetrized KL divergence estimate D̂
D̂ ≈ DKL (gold-standard||target) + DKL (target||gold-standard)

Figure 1: Using AIDE to estimate the accuracy of a target inference algorithm relative to a goldstandard inference algorithm. AIDE is a Monte Carlo estimator of the symmetrized Kullback-Leibler
(KL) divergence between the output distributions of two inference algorithms. AIDE uses metainference: inference over the internal random choices made by an inference algorithm.

8
6
4
2
0

100

101
Number of particles

102

Metropolis-Hastings
8
6
4
2
0

Variational Inference
AIDE estimate (nats)

Mt = 100
Mt = 101
Mt = 103

AIDE estimate (nats)

AIDE estimate (nats)

Sequential Monte Carlo

100

101
102
1 + Number of transitions

8
6
4
2
0
100

101
104
102
103
Number of gradient steps

Figure 2: AIDE applies to SMC, variational, and MCMC algorithms. Left: AIDE estimates for
SMC converge to zero, as expected. Right: AIDE estimates for variational inference converge to
a nonzero asymptote that depends on the variational family. Middle: The symmetrized divergence
between MH and the posterior converges to zero, but AIDE over-estimates the divergence in expectation. Although increasing the number of meta-inference runs Mt reduces the bias of AIDE, AIDE is
not yet practical for measuring MH accuracy due to inaccurate meta-inference for MH.
show that the conditional SMC update of Andrieu et al. [2] and the reverse AIS Markov chain of
Grosse et al. [3] are both special cases of a ‘generalized conditional SMC update’, which we use as a
canonical meta-inference algorithm for SMC. AIDE is a practical tool for measuring the accuracy
of SMC and variational inference algorithms relative to gold-standard inference algorithms. Note
that this paper does not provide a practical solution to the MCMC convergence diagnosis problem.
Although in principle AIDE can be applied to MCMC, to do so in practice will require more accurate
meta-inference algorithms for MCMC to be developed.

2

Background

Consider a generative probabilistic model with latent variables X and observed variables Y . We
denote assignments to these variables by x ∈ X and y ∈ Y. Let p(x, y) denote the joint
R density of
the generative model. The posterior density is p(x|y) := p(x, y)/p(y) where p(y) = p(x, y)dx is
the marginal likelihood, or ‘evidence’.
Sampling-based approximate inference strategies including Markov chain Monte Carlo (MCMC,
[4, 5]), sequential Monte Carlo (SMC, [6]), annealed importance sampling (AIS, [7]) and importance
sampling with resampling (SIR, [8, 9]), generate samples of the latent variables that are approximately
distributed according to p(x|y). Use of a sampling-based inference algorithm is often motivated by
theoretical guarantees of exact convergence to the posterior in the limit of infinite computation (e.g.
2

number of transitions in a Markov chain, number of importance samples in SIR). However, how well
the sampling distribution approximates the posterior distribution for finite computation is typically
difficult to analyze theoretically or estimate empirically with confidence.
Variational inference [10] explicitly minimizes the approximation error of the approximating distribution qθ (x) over parameters θ of a variational family. The error is usually quantified using the
Kullback-Leibler (KL) divergence from the approximation qθ (x) to the posterior p(x|y), denoted
DKL (qθ (x) k p(x|y)). Unlike sampling-based approaches, variational inference does not generally
give exact results for infinite computation because the variational family does not include the posterior.
Minimizing the KL divergence is performed by maximizing the ‘evidence lower bound’ (ELBO)
L = log p(y) − DKL (qθ (x) k p(x|y)) over θ. Since log p(y) is usually unknown, the actual error
(the KL divergence) of a variational approximation is also unknown.

3

Estimating the symmetrized KL divergence between inference algorithms

This section defines our mathematical formalism for analyzing inference algorithms; shows how
to represent SMC, MCMC, rejection sampling, and variational inference in this formalism; and
introduces the Auxiliary Inference Divergence Estimator (AIDE), an algorithm for estimating the
symmetrized KL divergence between two inference algorithms.
3.1

Generative inference models and meta-inference algorithms

We define an inference algorithm as a procedure that produces a single approximate posterior sample.
Repeated runs of the algorithm give independent samples. For each inference algorithm, there is
an ‘output density’ q(x) that represents the probability that the algorithm returns a given sample
x on any given run of the algorithm. Note that q(x) depends on the observations y that define the
inference problem, but we suppress that in the notation. The inference algorithm is accurate when
q(x) ≈ p(x|y) for all x. We denote a sample produced by running the algorithm by x ∼ q(x).
A naive simple Monte Carlo estimator of the KL divergence between the output distributions of
two inference algorithms requires the output densities of both algorithms. However, it is typically
intractable to compute the output densities of sampling-based inference algorithms like MCMC and
SMC, because that would require marginalizing over all possible values that the random variables
drawn during the algorithm could possibly take. A similar difficulty arises when computing the
marginal likelihood p(y) of a generative probabilistic model p(x, y). This suggests that we treat the
inference algorithm as a probabilistic model, estimate its output density using ideas from marginal
likelihood estimation, and use these estimates in a Monte Carlo estimator of the divergence. We begin
by making the analogy between an inference algorithm and a probabilistic model explicit:
Definition 3.1 (Generative inference model). A generative inference model is a tuple (U, X , q) where
q(u, x) is a joint density defined on U × X . A generative inference model models an inference
algoR
rithm if the output density of the inference algorithm is the marginal likelihood q(x) = q(u, x)du
of the model for all x. An element u ∈ U represents a complete assignment to the internal random
variables within the inference algorithm, and is called a ‘trace’. The ability to simulate from q(u, x) is
required, but the ability to compute the density q(u, x) is not. A simulation, denoted u, x ∼ q(u, x),
may be obtained by running the inference algorithm and recording the resulting trace u and output x.1
A generative inference model can be understood as a generative probabilistic model where the u are
the latent variables and the x are the observations. Note that two different generative inference models
may use different representations for the internal random variables of the same inference algorithm. In
practice, constructing a generative inference model from an inference algorithm amounts to defining
the set of internal random variables. For marginal likelihood estimation in a generative inference
model, we use a ‘meta-inference’ algorithm:
Definition 3.2 (Meta-inference algorithm). For a given generative inference model (U, X , q), a
meta-inference algorithm is a tuple (r, ξ) where r(u; x) is a density on traces u ∈ U of the inference
algorithm, indexed by outputs x ∈ X of the inference algorithm, and where ξ(u, x) is the following
1

The trace data structure could in principle be obtained by writing the inference algorithm in a probabilistic
programming language like Church [11], but the computational overhead would be high.

3

function of u and x for some Z > 0:
ξ(u, x) := Z

q(u, x)
r(u; x)

(1)

We require the ability to sample u ∼ r(u; x) given a value for x, and the ability to evaluate ξ(u, x)
given u and x. We call a procedure for sampling from r(u; x) a ‘meta-inference sampler’. We do not
require the ability to evaluate the density r(u; x).
A meta-inference algorithm is considered accurate for a given x if r(u; x) ≈ q(u|x) for all u.
Conceptually, a meta-inference sampler tries to answer the question ‘how could my inference
algorithm have produced this output x?’ Note that if it is tractable to evaluate the marginal likelihood
q(x) of the generative inference model up to a normalizing constant, then it is not necessary to
represent internal random variables for the inference algorithm, and a generative inference model can
define the trace as an empty token u = () with U = {()}. In this case, the meta-inference algorithm
has r(u; x) = 1 for all x and ξ(u, x) = Zq(x).
3.2

Examples

We now show how to construct generative inference models and corresponding meta-inference
algorithms for SMC, AIS, MCMC, SIR, rejection sampling, and variational inference. The metainference algorithms for AIS, MCMC, and SIR are derived as special cases of a generic SMC
meta-inference algorithm.
Sequential Monte Carlo. We consider a general class of SMC samplers introduced by Del Moral
et al. [6], which can be used for approximate inference in both sequential state space and nonsequential models. We briefly summarize a slightly restricted variant of the algorithm here, and refer
the reader to the supplement and Del Moral et al. [6] for full details. The SMC algorithm propagates
P weighted particles through T steps, using proposal kernels kt and multinomial resampling based
on weight functions w1 (x1 ) and wt (xt−1 , xt ) for t > 1 that are defined in terms of ‘backwards
kernels’ `t for t = 2 . . . T . Let xit , wti and Wti denote the value, unnormalized weight, and normalized
weight of particle i at time t, respectively. We define the output sample x of SMC as a single draw
from the particle approximation at the final time step, which is obtained by sampling a particle
index IT ∼ Categorical(WT1:P ) where WT1:P denotes the vector of weights (WT1 , . . . , WTP ), and then
setting x ← xITT . The generative inference model uses traces of the form u = (x, a, IT ), where x
contains the values of all particles at all time steps and where a (for ‘ancestor’) contains the index
ait ∈ {1 . . . P } of the parent of particle xit+1 for each particle i and each time step t = 1 . . . T − 1.
Algorithm 1 defines a canonical meta-inference sampler for this generative inference model that takes
as input a latent sample x and generates an SMC trace u ∼ r(u; x) as output. The meta-inference
sampler first generates an ancestral trajectory of particles (xI11 , xI22 , . . . , xITT ) that terminates in the
output sample x, by sampling sequentially from the backward kernels `t , starting from xITT = x.
Next, it runs a conditional SMC update [2] conditioned on the ancestral trajectory. For this choice of
d
r(u; x) and for Z = 1, the function ξ(u, x) is closely related to the marginal likelihood estimate p(y)
d See supplement for derivation.
produced by the SMC scheme:2 ξ(u, x) = p(x, y)/p(y).
Annealed importance sampling. When a single particle is used (P = 1), and when each forward
kernel kt satisfies detailed balance for some intermediate density, the SMC algorithm simplifies
to annealed importance sampling (AIS, [7]), and the canonical SMC meta-inference inference
(Algorithm 1) consists of running the forward kernels in reverse order, as in the reverse annealing
algorithm of Grosse et al. [3, 12]. The canonical meta-inference algorithm is accurate (r(u; x) ≈
q(u; x)) if the AIS Markov chain is kept close to equilibrium at all times. This is achieved if the
intermediate densities form a sufficiently fine-grained sequence. See supplement for analysis.
Markov chain Monte Carlo. We define each run of an MCMC algorithm as producing a single
output sample x that is the iterate of the Markov chain produced after a predetermined number of burnin steps has passed. We also assume that each MCMC transition operator satisfies detailed balance
2

AIDE also applies to approximate inference algorithms for undirected probabilistic models; the marginal
likelihood estimate is replaced with the estimate of the partition function.

4

Algorithm 1 Generalized conditional SMC (a canonical meta-inference sampler for SMC)
Require: Latent sample x, SMC parameters
IT ∼ Uniform(1 . . . P )
xITT ← x
for t ← T − 1 . . . 1 do
It ∼ Uniform(1 . . . P )
. Sample from backward kernel
It+1
xIt t ∼ `t+1 (·; xt+1
)
for i ← 1 . . . P do
if i 6= I1 then xi1 ∼ k1 (·)
w1i ← w1 (xi1 )
for t ← 2 . . . T do P
i
1:P
1:P
Wt−1
← wt−1
/( P
i=1 wt−1 )
for i ← 1 . . . P do
if i = It then ait−1 ← It−1
else
1:P
ait−1 ∼ Categorical(Wt−1
)

δ
x13

x23

x33

x43

I3 = 2

x22

x32

x42

I2 = 3

x21

x31

x41

I1 = 1

`3
x12
`2
x11

T =3

ait−1
xit ∼ kt (·; xt−1
)
ait−1
i
i
wt ← wt (xt−1 , xt )

u ← (x, a, IT )
return u

Latent sample
(input to meta-inference sampler)

x

xit

Member of ancestral
trajectory

. Return an SMC trace

with respect to the posterior p(x|y). Then, this is formally a special case of AIS. However, unless the
Markov chain was initialized near the posterior p(x|y), the chain will be far from equilibrium during
the burn-in period, and the AIS meta-inference algorithm will be inaccurate.
Importance sampling with resampling. Importance sampling with resampling, or SIR [8] can be
seen as a special case of SMC if we set the number of steps to one (T = 1). The trace of the SIR
algorithm is then the set of particles xi1 for i ∈ {1, . . . , P } and output particle index I1 . Given output
sample x, the canonical SMC meta-inference sampler then simply samples I1 ∼ Uniform(1 . . . P ),
sets xI11 ← x, and samples the other P − 1 particles from the importance distribution k1 (x).
Rejection sampling. To model a rejection sampler for a posterior distribution p(x|y), we assume it
is tractable to evaluate the unnormalized posterior density p(x, y). We define U = {()} as described
in Section 3.1. For meta-inference, we define Z = p(y) so that ξ(u, x) = p(y)p(x|y) = p(x, y). It is
not necessary to represent the internal random variables of the rejection sampler.
Variational inference. We suppose a variational approximation qθ (x) has been computed through
optimization over the variational parameters θ. We assume that it is possible to sample from the
variational approximation, and evaluate its normalized density. Then, we use U = {()} and Z = 1
and ξ(u, x) = qθ (x). Note that this formulation also applies to amortized variational inference
algorithms, which reuse the parameters θ for inference across different observation contexts y.
3.3

The auxiliary inference divergence estimator

Consider a probabilistic model p(x, y), a set of observations y, and two inference algorithms that
approximate p(x|y). One of the two inference algorithms is considered the ‘gold-standard’, and has a
generative inference model (U, X , qg ) and a meta-inference algorithm (rg , ξg ). The second algorithm
is considered the ‘target’ algorithm, with a generative inference model (V, X , qt ) (we denote a trace
of the target algorithm by v ∈ V), and a meta-inference algorithm (rt , ξt ). This section shows how to
estimate an upper bound on the symmetrized KL divergence between qg (x) and qt (x), which is:




qg (x)
qt (x)
DKL (qg (x) k qt (x)) + DKL (qt (x) k qg (x)) = Ex∼qg (x) log
+ Ex∼qt (x) log
(2)
qt (x)
qg (x)
We take a Monte Carlo approach. Simple Monte Carlo applied to the Equation (2) requires that qg (x)
and qt (x) can be evaluated, which would prevent the estimator from being used when either inference
algorithm is sampling-based. Algorithm 2 gives the Auxiliary Inference Divergence Estimator
5

(AIDE), an estimator of the symmetrized KL divergence that only requires evaluation of ξg (u, x) and
ξt (v, x) and not qg (x) or qt (x), permitting its use with sampling-based inference algorithms.
Algorithm 2 Auxiliary Inference Divergence Estimator (AIDE)
Gold-standard inference model and meta-inference algorithm (U, X , qg ) and (rg , ξg )
Target inference model and meta-inference algorithm
(V, X , qt ) and (rt , ξt )
Number of runs of gold-standard algorithm
Ng
Number of runs of meta-inference sampler for gold-standard
Mg
Number of runs of target algorithm
Nt
Number of runs of meta-inference sampler for target
Mt
for n ← 1 . . . Ng do
un,1 , xn ∼ qg (u, x) . Run gold-standard algorithm, record trace un,1 and output xn
for m ← 2 . . . Mg do
un,m ∼ rg (u; xn ) . Run meta-inference sampler for gold-standard algorithm, on input xn
for m ← 1 . . . Mt do
vn,m ∼ rt (v; xn ) . Run meta-inference sampler for target algorithm, on input xn
for n ← 1 . . . Nt do
0
0
vn,1
, x0n ∼ qt (v, x)
. Run target algorithm, record trace vn,1
and output x0n
for m ← 2 . . . Mt do
0
vn,m
∼ rt (v; x0n ) . Run meta-inference sampler for target algorithm, on input x0n
for m ← 1 . . . Mg do
u0n,m ∼ rg (u; x0n ) . Run meta-inference sampler for gold-standard algorithm, on input x0n




PMg
PMt
Ng
1
0
0
Nt
1
X
m=1 ξg (un,m , xn )
m=1 ξt (vn,m , xn )
Mg
1 X
1
Mt

+
D̂ ←
log 
log 
PMt
PMg
1
1
Ng n=1
Nt n=1
0
0 )
ξ
(u
,
x
g
n,m
n
m=1 ξt (vn,m , xn )
m=1
Mt
Mg

Require:

return D̂

. D̂ is an estimate of DKL (qg (x)||qt (x)) + DKL (qt (x)||qg (x))

The generic AIDE algorithm above is defined in terms of abstract generative inference models and
meta-inference algorithms. For concreteness, the supplement contains the AIDE algorithm specialized
to the case when the gold-standard is AIS and the target is a variational approximation.
Theorem 1. The estimate D̂ produced by AIDE is an upper bound on the symmetrized KL divergence
in expectation, and the expectation is nonincreasing in AIDE parameters Mg and Mt .
See supplement for proof. Briefly, AIDE estimates an upper bound on the symmetrized divergence in
expectation because it uses unbiased estimates of qt (xn ) and qg (xn )−1 for xn ∼ qg (x), and unbiased
estimates of qg (x0n ) and qt (x0n )−1 for x0n ∼ qt (x). For Mg = 1 and Mt = 1, AIDE over-estimates
the true symmetrized divergence by:
E[D̂] − (DKL (qg (x) k qt (x)) + DKL (qt (x) k qg (x))) =

 Bias of AIDE
Ex∼qg (x) [DKL (qg (u|x) k rg (u; x)) + DKL (rt (v; x) k qt (v|x))]
for Mg =Mt =1
+ Ex∼qt (x) [DKL (qt (v|x) k rt (v; x)) + DKL (rg (u; x) k qg (u|x))]

(3)

Note that this expression involves KL divergences between the meta-inference sampling densities
(rg (u; x) and rt (v; x)) and the posteriors in their respective generative inference models (qg (u|x) and
qt (v|x)). Therefore, the approximation error of meta-inference determines the bias of AIDE. When
both meta-inference algorithms are exact (rg (u; x) = qg (u|x) for all u and x and rt (v; x) = qt (v|x)
for all v and x), AIDE is unbiased. As Mg or Mt are increased, the bias decreases (see Figure 2 and
Figure 4 for examples). If the generative inference model for one of the algorithms does not use a
trace (i.e. U = {()} or V = {()}), then that algorithm does not contribute a KL divergence term to
the bias of Equation (3). The analysis of AIDE is equivalent to that of Grosse et al. [12] when the
target algorithm is AIS and Mt = Mg = 1 and the gold-standard inference algorithm is a rejection
sampler.

4

Related Work

Diagnosing the convergence of approximate inference is a long-standing problem. Most existing work
is either tailored to specific inference algorithms [13], designed to detect lack of exact convergence
[1], or both. Estimators of the non-asymptotic approximation error of general approximate inference
6

Number of particles

AIDE estimate
(nats)

100
101

60

102

40

Offset proposal
Broad proposal

Large penalty for
missing mode

20

103

posterior

L
2

R density
0

2

0

4

0

Log marginal
likelihood (nats)

20

Small penalty

40

Offset proposal
Broad proposal
Gold-standard

60
100

101

102

Number of particles

103

100

101

102

Number of particles

103

Figure 3: AIDE detects when an inference algorithm misses a posterior mode. Left: A bimodal
posterior density, with kernel estimates of the output densities of importance sampling with resampling
(SIR) using two proposals. The ‘broad’ proposal (blue) covers both modes, and the ‘offset’ proposal
(pink) misses the ‘L’ mode. Middle: AIDE detects the missing mode in offset-proposal SIR. Right:
Log marginal likelihood estimates suggest that the offset-proposal SIR is nearly converged.

algorithms have received less attention. Gorham and Mackey [14] propose an approach that applies
to arbitrary sampling algorithms but relies on special properties of the posterior density such as
log-concavity. Our approach does not rely on special properties of the posterior distribution.
Our work is most closely related to Bounding Divergences with REverse Annealing (BREAD, [12])
which also estimates upper bounds on the symmetric KL divergence between the output distribution
of a sampling algorithm and the posterior distribution. AIDE differs from BREAD in two ways: First,
whereas BREAD handles single-particle SMC samplers and annealed importance sampling (AIS),
AIDE handles a substantially broader family of inference algorithms including SMC samplers with
both resampling and rejuvenation steps, AIS, variational inference, and rejection samplers. Second,
BREAD estimates divergences between the target algorithm’s sampling distribution and the posterior
distribution, but the exact posterior samples necessary for BREAD’s theoretical properties are only
readily available when the observations y that define the inference problem are simulated from the
generative model. Instead, AIDE estimates divergences against an exact or approximate gold-standard
sampler on real (non-simulated) inference problems. Unlike BREAD, AIDE can be used to evaluate
inference in both generative and undirected models.
AIDE estimates the error of sampling-based inference using a mathematical framework with roots
in variational inference. Several recent works have treated sampling-based inference algorithms as
variational approximations. The Monte Carlo Objective (MCO) formalism of Maddison et al. [15]
is closely related to our formalism of generative inference models and meta-inference algorithms—
indeed a generative inference model and a meta-inference algorithm with Z = 1 give an MCO defined
by: L(y, p) = Eu,x∼q(u,x) [log(p(x, y)/ξ(u, x))], where y denotes observed data. In independent
and concurrent work to our own, Naesseth et al. [16], Maddison et al. [15] and Le et al. [17] treat
SMC as a variational approximation using constructions similar to ours. In earlier work, Salimans
et al. [18] recognized that MCMC samplers can be treated as variational approximations. However,
these works are concerned with optimization of variational objective functions instead of estimation
of KL divergences, and do not involve generating a trace of a sampler from its output.

5
5.1

Experiments
Comparing the bias of AIDE for different types of inference algorithms

We used a Bayesian linear regression inference problem where exact posterior sampling is tractable
to characterize the bias of AIDE when applied to three different types of target inference algorithms:
sequential Monte Carlo (SMC), Metropolis-Hastings (MH), and variational inference. For the goldstandard algorithm we used a posterior sampler with a tractable output density qg (x), which does not
introduce bias into AIDE, so that the AIDE’s bias could be completely attributed to the approximation
error of meta-inference for each target algorithm. Figure 2 shows the results. The bias of AIDE
is acceptable for SMC, and AIDE is unbiased for variational inference, but better meta-inference
algorithms for MCMC are needed to make AIDE practical for estimating the accuracy of MH.
7

5.2

Evaluating approximate inference in a Hidden Markov model

We applied AIDE to measure the approximation error of SMC algorithms for posterior inference in
a Hidden Markov model (HMM). Because exact posterior inference in this HMM is tractable via
dynamic programming, we used this opportunity to compare AIDE estimates obtained using the exact
posterior as the gold-standard with AIDE estimates obtained using a ‘best-in-class’ SMC algorithm as
the gold-standard. Figure 4 shows the results, which indicate AIDE estimates using an approximate
gold-standard algorithm can be nearly identical to AIDE estimates obtained with an exact posterior
gold-standard.
Target algorithms

50

1

state

20

time
Posterior marginals

1

50

1

state

20

time

1

50

SMC optimal proposal
1000 particles
(SMC gold standard)

80

80

50

60
40
20
0
100

C

20

state

1

time
SMC prior proposal
10 particles

1

Measuring accuracy
of target algorithms using
SMC gold-standard

50

B

20

state

1

time
SMC prior proposal
1 particle

1

Measuring accuracy
of target algorithms using
posterior as gold-standard

A

B

C

101

102

Number of particles

AIDE estimate (nats)

time
Ground truth states

1

state

state
1

A

20

AIDE estimate (nats)

20

60
40
20
0
100

A

B

C

101

Number of particles

102

SMC, prior proposal, 1 meta-inference run (Mt = 1)
SMC, prior proposal, 100 meta-inference runs (Mt = 100)
SMC, optimal proposal, 1 meta-inference run (Mt = 1)
SMC, optimal proposal, 100 meta-inference runs (Mt = 100)

1

time
1
50
SMC optimal proposal
100 particles

Figure 4: Comparing use of an exact posterior as the gold-standard and a ‘best-in-class’ approximate
algorithm as the gold-standard, when measuring accuracy of target inference algorithms with AIDE.
We consider inference in an HMM, so that exact posterior sampling is tractable using dynamic
programming. Left: Ground truth latent states, posterior marginals, and marginals of the the output
of a gold-standard and three target SMC algorithms (A,B,C) for a particular observation sequence.
Right: AIDE estimates using the exact gold-standard and using the SMC gold-standard are nearly
identical. The estimated divergence bounds decrease as the number of particles in the target sampler
increases. The optimal proposal outperforms the prior proposal. Increasing Mt tightens the estimated
divergence bounds. We used Mg = 1.

25
20
15
10
5
0

Likelihood weighting
with 1 particle appears
least accurate

100

101
Number of particles

Heuristic diagnostic
Average number
of clusters

nats

AIDE estimates

102

Appears accurate

4.0
3.5

SMC, prior proposal
0 rejuvenation sweeps
SMC, optimal proposal
0 rejuvenation sweeps

3.0

SMC, optimal proposal
4 rejuvenation sweeps

2.5

Gold-standard

100

101
Number of particles

102

Likelihood-weighting
(1 particle)

Figure 5: Contrasting AIDE against a heuristic convergence diagnostic for evaluating the accuracy of
approximate inference in a Dirichlet process mixture model (DPMM). The heuristic compares the
expected number of clusters under the target algorithm to the expectation under the gold-standard
algorithm [19]. White circles identify single-particle likelihood-weighting, which samples from the
prior. AIDE clearly indicates that single-particle likelihood-weighting is inaccurate, but the heuristic
suggests it is accurate. Probe functions like the expected number of clusters can be error prone
measures of convergence because they only track convergence along a specific projection of the
distribution. In contrast, AIDE estimates a joint KL divergence. Shaded areas in both plots show the
standard error. The amount of target inference computation used is the same for the two techniques,
although AIDE performs a gold-standard meta-inference run for each target inference run.

8

5.3

Comparing AIDE to alternative inference evaluation techniques

A key feature of AIDE is that it applies to different types of inference algorithms. We compared AIDE
to two existing techniques for evaluating the accuracy of inference algorithms that share this feature:
(1) comparing log marginal likelihood (LML) estimates made by a target algorithm against LML
estimates made by a gold-standard algorithm, and (2) comparing the expectation of a probe function
under the approximating distribution to the same expectation under the gold-standard distribution
[19]. Figure 3 shows a comparison of AIDE to LML, on a inference problem where the posterior
is bimodal. Figure 5 shows a comparison of AIDE to a ‘number of clusters’ probe function in a
Dirichlet process mixture model inference problem for a synthetic data set. We also used AIDE to
evaluate the accuracy of several SMC algorithms for DPMM inference on a real data set of galaxy
velocities [20] relative to an SMC gold-standard. This experiment is described in the supplement due
to space constraints.

6

Discussion

AIDE makes it practical to estimate bounds on the error of a broad class of approximate inference
algorithms including sequential Monte Carlo (SMC), annealed importance sampling (AIS), sampling
importance resampling (SIR), and variational inference. AIDE’s reliance on a gold-standard inference
algorithm raises two questions that merit discussion:
If we already had an acceptable gold-standard, why would we want to evaluate other inference
algorithms? Gold-standard algorithms such as very long MCMC runs, SMC runs with hundreds of
thousands of particles, or AIS runs with a very fine annealing schedule, are often too slow to use
in production. AIDE make it possible to use gold-standard algorithms during an offline design and
evaluation phase to quantitatively answer questions like “how few particles or rejuvenation steps
or samples can I get away with?” or “is my fast variational approximation good enough?”. AIDE
can thus help practitioners confidently apply Monte Carlo techniques in challenging, performance
constrained applications, such as probabilistic robotics or web-scale machine learning. In future
work we think it will be valuable to build probabilistic models of AIDE estimates, conditioned on
features of the data set, to learn offline what problem instances are easy or hard for different inference
algorithms. This may help practitioners bridge the gap between offline evaluation and production
more rigorously.
How do we ensure that the gold-standard is accurate enough for the comparison with it to be
meaningful? This is an intrinsically hard problem—we are not sure that near-exact posterior inference
is really feasible, for most interesting classes of models. In practice, we think that gold-standard
inference algorithms will be calibrated based on a mix of subjective assumptions and heuristic
testing—much like models themselves are tested. For example, users could initially build confidence
in a gold-standard algorithm by estimating the symmetric KL divergence from the posterior on
simulated data sets (following the approach of Grosse et al. [12]), and then use AIDE with the trusted
gold-standard for a focused evaluation of target algorithms on real data sets of interest. We do not
think the subjectivity of the gold-standard assumption is a unique limitation of AIDE.
A limitation of AIDE is that its bias depends on the accuracy of meta-inference, i.e. inference
over the auxiliary random variables used by an inference algorithm. We currently lack an accurate
meta-inference algorithm for MCMC samplers that do not employ annealing, and therefore AIDE is
not yet suitable for use as a general MCMC convergence diagnostic. Research on new meta-inference
algorithms for MCMC and comparisons to standard convergence diagnostics [21, 22] are needed.
Other areas for future work include understanding how the accuracy of meta-inference depends
on parameters of an inference algorithm, and more generally what makes an inference algorithm
amenable to efficient meta-inference.
Note that AIDE does not rely on asymptotic exactness of the inference algorithm being evaluated.
An interesting area of future work is in using AIDE to study the non-asymptotic error of scalable but
asymptotically biased sampling algorithms [23]. It also seems fruitful to connect AIDE to results
from theoretical computer science, including the computability [24] and complexity [25–28] of
probabilistic inference. It should be possible to study the computational tractability of approximate
inference empirically using AIDE estimates, as well as theoretically using a careful treatment of the
variance of these estimates. It also seems promising to use ideas from AIDE to develop Monte Carlo
program analyses for samplers written in probabilistic programming languages.
9

Acknowledgments
This research was supported by DARPA (PPAML program, contract number FA8750-14-2-0004),
IARPA (under research contract 2015-15061000003), the Office of Naval Research (under research
contract N000141310333), the Army Research Office (under agreement number W911NF-13-10212), and gifts from Analog Devices and Google. This research was conducted with Government
support under and awarded by DoD, Air Force Office of Scientific Research, National Defense
Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a.

References
[1] Mary Kathryn Cowles and Bradley P Carlin. Markov chain monte carlo convergence diagnostics:
a comparative review. Journal of the American Statistical Association, 91(434):883–904, 1996.
[2] Christophe Andrieu, Arnaud Doucet, and Roman Holenstein. Particle markov chain monte
carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72
(3):269–342, 2010.
[3] Roger B Grosse, Zoubin Ghahramani, and Ryan P Adams. Sandwiching the marginal likelihood
using bidirectional monte carlo. arXiv preprint arXiv:1511.02543, 2015.
[4] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and
Edward Teller. Equation of state calculations by fast computing machines. The journal of
chemical physics, 21(6):1087–1092, 1953.
[5] W Keith Hastings. Monte carlo sampling methods using markov chains and their applications.
Biometrika, 57(1):97–109, 1970.
[6] Pierre Del Moral, Arnaud Doucet, and Ajay Jasra. Sequential monte carlo samplers. Journal of
the Royal Statistical Society: Series B (Statistical Methodology), 68(3):411–436, 2006.
[7] Radford M Neal. Annealed importance sampling. Statistics and computing, 11(2):125–139,
2001.
[8] Donald B Rubin et al. Using the sir algorithm to simulate posterior distributions. Bayesian
statistics, 3(1):395–402, 1988.
[9] Adrian FM Smith and Alan E Gelfand. Bayesian statistics without tears: a sampling–resampling
perspective. The American Statistician, 46(2):84–88, 1992.
[10] Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. An introduction to variational methods for graphical models. Machine learning, 37(2):183–233,
1999.
[11] Noah Goodman, Vikash Mansinghka, Daniel M Roy, Keith Bonawitz, and Joshua Tenenbaum.
Church: a language for generative models with non-parametric memoization and approximate
inference. In Uncertainty in Artificial Intelligence, 2008.
[12] Roger B Grosse, Siddharth Ancha, and Daniel M Roy. Measuring the reliability of mcmc
inference with bidirectional monte carlo. In Advances in Neural Information Processing
Systems, pages 2451–2459, 2016.
[13] Augustine Kong. A note on importance sampling using standardized weights. University of
Chicago, Dept. of Statistics, Tech. Rep, 348, 1992.
[14] Jackson Gorham and Lester Mackey. Measuring sample quality with stein’s method. In
Advances in Neural Information Processing Systems, pages 226–234, 2015.
[15] Chris J Maddison, Dieterich Lawson, George Tucker, Nicolas Heess, Mohammad Norouzi,
Andriy Mnih, Arnaud Doucet, and Yee Whye Teh. Filtering variational objectives. arXiv
preprint arXiv:1705.09279, 2017.
[16] Christian A Naesseth, Scott W Linderman, Rajesh Ranganath, and David M Blei. Variational
sequential monte carlo. arXiv preprint arXiv:1705.11140, 2017.
10

[17] Tuan Anh Le, Maximilian Igl, Tom Jin, Tom Rainforth, and Frank Wood. Auto-encoding
sequential monte carlo. arXiv preprint arXiv:1705.10306, 2017.
[18] Tim Salimans, Diederik Kingma, and Max Welling. Markov chain monte carlo and variational
inference: Bridging the gap. In Proceedings of the 32nd International Conference on Machine
Learning (ICML-15), pages 1218–1226, 2015.
[19] Yener Ulker, Bilge Günsel, and Taylan Cemgil. Sequential monte carlo samplers for dirichlet
process mixtures. In Proceedings of the Thirteenth International Conference on Artificial
Intelligence and Statistics, pages 876–883, 2010.
[20] Michael J Drinkwater, Quentin A Parker, Dominique Proust, Eric Slezak, and Hernán Quintana. The large scale distribution of galaxies in the shapley supercluster. Publications of the
Astronomical Society of Australia, 21(1):89–96, 2004.
[21] Andrew Gelman and Donald B Rubin. Inference from iterative simulation using multiple
sequences. Statistical science, pages 457–472, 1992.
[22] John Geweke. Getting it right: Joint distribution tests of posterior simulators. Journal of the
American Statistical Association, 99(467):799–804, 2004.
[23] Elaine Angelino, Matthew James Johnson, Ryan P Adams, et al. Patterns of scalable bayesian
inference. Foundations and Trends R in Machine Learning, 9(2-3):119–247, 2016.
[24] Nathanael L Ackerman, Cameron E Freer, and Daniel M Roy. On the computability of
conditional probability. arXiv preprint arXiv:1005.3014, 2010.
[25] Cameron E Freer, Vikash K Mansinghka, and Daniel M Roy. When are probabilistic programs
probably computationally tractable? In NIPS Workshop on Advanced Monte Carlo Methods
with Applications, 2010.
[26] Jonathan H Huggins and Daniel M Roy. Convergence of sequential monte carlo-based sampling
methods. arXiv preprint arXiv:1503.00966, 2015.
[27] Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling. arXiv
preprint arXiv:1511.01437, 2015.
[28] S Agapiou, Omiros Papaspiliopoulos, D Sanz-Alonso, AM Stuart, et al. Importance sampling:
Intrinsic dimension and computational cost. Statistical Science, 32(3):405–431, 2017.
[29] Neil J Gordon, David J Salmond, and Adrian FM Smith. Novel approach to nonlinear/nongaussian bayesian state estimation. In IEE Proceedings F (Radar and Signal Processing),
volume 140, pages 107–113. IET, 1993.

11

A

Sequential Monte Carlo

An SMC sampler template based on [6] is reproduced in Algorithm 3. The algorithm evolves a set
of P particles to approximate a sequence of target distributions using a combination of proposal
kernels, weighting, and resampling steps. The final target distribution in the sequence is typically
the posterior p(x|y). In our version, the algorithm resamples once from the final weighted particle
approximation and returns this particle as its output sample x. Specifically, the algorithm uses a
sequence of unnormalized target densities p̃t defined on spaces Xt for t = 1 . . . T , with XT = X (the
original space of latent variables in the generative model) and p̃T (x) := p(x, y). The algorithm also
makes use of an initialization kernel k1 defined on X1 , proposal kernels kt defined on Xt and indexed
by Xt−1 for t = 2 . . . T , and backward kernels `t defined on Xt−1 and indexed by Xt for t = 2 . . . T .
For simplicity of analysis we assume that resampling occurs at every step in the sequence. The weight
functions used in the algorithm are:


p̃t (xit )`t xjt−1 ; xit
i
p̃
(x
)
1 1

 

(4)
wt (xjt−1 , xit ) :=
w1 (xi1 ) :=
k1 (xi1 )
kt xi ; xj
p̃t−1 xj
t−1

t

t−1

Note that Algorithm 3 does
Qt not sample from the backward kernels, which serve to define the extended
target densities p̃t (xt ) s=2 `s (xs−1 ; xs ) that justify the SMC sampler as a sequential importance
sampler [6]. When P = 1, Xt = X for all t, kt (xt ; xt−1 ) is a detailed balance transition operator for
pt−1 , and `t = kt , the algorithm reduces to AIS.3 The particle filter without rejuvenation [29] is also
a special case of Algorithm 3. A variety of other SMC variants can also be seen to be special cases of
d is computed from the weights wi
this formulation [6]. The SMC marginal likelihood estimate p(y)
t
Algorithm 3 Sequential Monte Carlo
for i ← 1 . . . P do
xi1 ∼ k1 (·)
w1i ← w1 (xi1 )
for t ← 2 . . . T do P
P
1:P
1:P
i
Wt−1
← wt−1
/( i=1 wt−1
)
for i ← 1 . . . P do
1:P
ait−1 ∼ Categorical(W

 t−1 )
xit

∼ kt

. Initialize particle i
. Initial weight for particle i
1:P
1
P
. Normalize weights wt−1
= (wt−1
, . . . , wt−1
)

. Sample index of parent for particle i

ait−1
·; xt−1

. Sample value for new particle i

ai

t−1
, xit )
wti ← wt (xt−1
IT ∼ Categorical(WT1:P )
x ← xITT
return x

. Compute weight for particle i
. Sample particle index for output sample
. Return the output sample

generated during the SMC algorithm according to:
d =
p(y)

T
P
Y
1 X i
w
P i=1 t
t=1

(5)

Note that an SMC marginal likelihood estimate can also be computed from the weights wti generated
d a function of the SMC trace u. To
during the generalized conditional SMC algorithm. Note that p(y)
d we write the joint density of the generative inference model for SMC:
relate ξ(u, x) to p(y),
"
"P
# T P
#
ait−1
IT
Y
Y Y wt−1
i
w
at−1
i
i
T
q(u, x) :=
k1 (x1 ) 
kt (xt ; xt−1 ) PP
δ(x, xITT ) (6)
PP
j
j
t=2 i=1
j=1 wt−1
j=1 wT
i=1
3
More generally, the proposal kernel kt needs to have stationary distribution pt−1 . The backward kernel `t is
the ‘reversal’ of kt as defined in [7]. When the proposal kernel satisfies detailed balance, it is its own reversal,
and therefore sampling from the backward kernel is identical to sampling from the forward kernel.

12

The the canonical meta-inference sampler (Algorithm 1) for SMC takes as input a latent sample x
and returns a trace u = (x, a, IT ) of Algorithm 3, containing all particles at all time steps x, all
parent indices a, and the final output particle index IT . The density on outputs of the meta-inference
sampler is given by:



# P
"T
ait−1
T Y
P
Y
Y
Y
i
wt−1
1
at−1 


It−1
; xIt t ) 
`t (xt−1
k1 (xi1 ) 
kt (xit ; xt−1
)
r(u; x) := δ(xITT , x) T
PP
j
P
t=2 i=1
t=2
j=1 wt−1
i=1
i6=I1

i6=It

(7)
d Therefore, the quantity
Taking the ratio q(u, x)/r(u; x) and simplifying gives p(x, y)/p(y).
ξ(u, x) = q(u, x)/r(u; x) can be computed from an SMC trace u, in terms of the SMC marginal
likelihood estimate and the unnormalized posterior density p(x, y).

B

AIDE specialized for evaluating variational inference using AIS

To make AIDE more concrete for the reader, we provide the AIDE algorithm when specialized to
measure the symmetrized KL divergence between a variational approximation qθ (x) and an annealed
importance sampler (AIS). For variational inference, there is no meta-inference sampler necessary
because we can evaluate the variational approximation density as discussed in the main text. The
meta-inference sampler for AIS consists of running the AIS chain in reverse, starting from a latent
sample. The trace u that is generated is the vector of intermediate states x = (x1 , . . . , xT ) in
d can be computed from a trace u of the AIS
the chain. The AIS marginal likelihood estimate p(y)
algorithm in terms of the weights (which are themselves deterministic functions of the trace):
T
Y
p̃t (xt )
d = p̃1 (x1 )
p(y)
k1 (x1 ) t=2 p̃t−1 (xt )

(8)

d can be computed from a trace u that is generated either by a ‘forward’ run of AIS, or
Note that p(y)
a reverse run of AIS. Algorithm 4 gives a concrete instantiation of AIDE (Algorithm 2) simplified
for the case when the gold-standard algorithm is an AIS sampler, and the target algorithm being
evaluated is a variational approximation. We further simplify the algorithm by fixing Mg = 1, where
AIS is the gold-standard. The AIS algorithm must support two primitives: AIS.FORWARD(), which
runs AIS forward and returns the resulting output sample x and the resulting marginal likelihood
d and AIS.REVERSE(x), which takes as input a sample x and runs the same AIS chain
estimate p(y),
d
in reverse order, returning the resulting marginal likelihood estimate p(y).

C

Proofs

Theorem 2. The estimate D̂ produced by AIDE is an upper bound on the symmetrized KL divergence
in expectation, and the expectation is nonincreasing in AIDE parameters Mg and Mt .
Proof. We consider the general case of two inference algorithms a and b with generative inference
models (U, X , qa ) and (V, X , qb ), and meta-inference algorithms (ra , ξa ) and (rb , ξb ) with normalizing constants Za and Zb respectively. For example a may be ‘target’ inference algorithm and b may
be the ‘gold standard’ inference algorithm. Note that the analysis of AIDE is symmetric in a and b.
First, we define the following quantity relating a and b:


Zb qb (x)
Zb
Lab := Ex∼qa (x) log
= log
− DKL (qa (x) k qb (x))
(9)
Za qa (x)
Za
When Za = 1 and when b is a rejection sampler for the posterior p(x|y), we have that Zb = p(x, y),
and Lab is the ‘ELBO’ of inference algorithm a with respect to the posterior. We also define the
quantity:
Uab := −Lba = log

Zb
+ DKL (qb (x) k qa (x))
Za
13

(10)

Algorithm 4 AIDE specialized for measuring divergence between variational inference and AIS
Require:

AIS algorithm
Trained variational approximation
Number of AIS forward samples
Number of variational samples

AIS. FORWARD () and AIS. REVERSE (x)
qθ (x)
Ng
Nt

for n ← 1 . . . Ng do
d and the final state in chain xn
.
record the marginal likelihood estimate p(y)
n
 Run AIS forward,

d , xn ∼ AIS.FORWARD()
p(y)
n

for n ← 1 . . . Nt do
. Generate sample x0n from the variational approximation
x0n ∼ qθ (x)

0

d
. Run AIS in reverse, starting from x0n , and record resulting marginal likelihood estimate p(y)
n
0
0
d
p(y) ∼ AIS.REVERSE(xn )
n

. Compute AIDE estimate
!
Ng
Nt
p(xn , y)
1 X
1 X
D̂ ←
log
log
−
d
Ng n=1
Nt n=1
qθ (xn )p(y)
n
return D̂

p(x0n , y)
d0
qθ (x0n )p(y)
n

!

Note that Uab − Lab = Uba − Lba is the symmetrized KL divergence between qa (x) and qb (x).
The AIDE estimate can be understood as a difference of an estimate of Uab and an estimate of Lab .
Specifically, we define the following estimator of Lab :
!
PMb
Na
1
1 X
k=1 ξb (vn,k , xn )
Mb
Na ,Ma ,Mb
log
L̂ab
:=
(11)
PMa
1
Na n=1
k=1 ξa (un,k , xn )
Ma


PMb
qb (vn,k ,xn )
1
Na
X
Z
b
1
k=1
M
rb (vn,k ;xn )

=
(12)
log  b PM
qa (un,k ,xn )
a
1
Na n=1
Z
a
k=1
Ma
ra (un,k ;xn )
xn ∼ qa (x) for n = 1 . . . Na
u |x ∼ qa (u|x) for n = 1 . . . Na
where: n,1 n
un,k |xn ∼ ra (u; x) for n = 1 . . . Na and k = 2 . . . Ma
vn,k |xn ∼ rb (v; x) for n = 1 . . . Na and k = 1 . . . Mb
a ,Mb
We now analyze the expectation E[L̂1,M
] and how it depends on Ma and Mb . We use the notation
ab
ui:j = (ui , . . . , uj ). First, note that:


Zb
qb (x)
1,Ma ,Mb
E[L̂ab
] = log
+ Ex∼qa (x) log
Za
qa (x)
"
#
Mb
1 X
qb (vk |x)
+ Ex∼qa (x)
log
Mb
rb (vk ; x)
iid
k=1
v1:Mb |x ∼ rb (v;x)
"
#
Ma
1 X
qa (uk |x)
(13)
− Ex∼qa (x)
log
Ma
ra (uk ; x)
u1 |x∼qa (u|x)

k=1

iid

u2:Ma |x ∼ ra (u;x)

#
Mb
1 X
qb (vk |x)
log
Mb
rb (vk ; x)
k=1
"
#
Ma
qa (uk |x)
1 X
log
Ma
ra (uk ; x)

"
= Lab + Ex∼qa (x)
iid

v1:Mb |x ∼ rb (v;x)

− Ex∼qa (x)
u1 ∼qa (u|x)

k=1

iid

u2:Ma |x ∼ ra (u;x)

14

(14)

We define the following families of densities on v1:Mb , indexed by x:
ηbMb (v1:Mb ; x) =

Mb
Mb
Y
1 X
qb (vk |x)
rb (v` ; x)
Mb
k=1

b
λM
b (v1:Mb ; x) =

Mb
Y

(15)

`=1
`6=k

rb (vk ; x)

(16)

k=1

and similarly for u1:Ma :
ηaMa (v1:Ma ; x) =

Ma
Ma
Y
1 X
qa (uk |x)
ra (u` ; x)
Ma
k=1

a
λM
a (u1:Ma ; x) =

Ma
Y

(17)

`=1
`6=k

ra (uk ; x)

(18)

k=1

Taking the first expectation in Equation (14):
#
Mb
1 X
qb (vk |x)
Ex∼qa (x)
log
Mb
rb (vk ; x)
iid
k=1
v1:Mb ∼ rb (v;x)


PMb
QMb
1
`=1 rb (v` ; x)
k=1 qb (vk |x)
Mb


`6=k
= Ex∼qa (x)
log

QMb
iid
k=1 rb (vk ; x)
v1:Mb ∼ rb (v;x)
"
#
ηbMb (v1:Mb ; x)
= Ex∼qa (x)
log Mb
M
λb (v1:Mb ; x)
v1:Mb ∼λb b (v1:Mb ;x)
h
i
Mb
b
= −Ex∼qa (x) DKL (λM
(v
;
x)
k
η
(v
;
x))
1:M
1:M
b
b
b
b
"

(19)

(20)

(21)
(22)

Taking the second expectation in Equation (14):
#
"
Ma
qa (uk |x)
1 X
log
Ex∼qa (x)
Ma
ra (uk ; x)
u1 ∼qa (u|x)

(23)

k=1

iid

u2:Ma ∼ ra (u;x)


= Ex∼qa (x)
u1 ∼qa (u|x)


log

1
Ma

QMa



k=1 ra (uk ; x)



PMa

k=1 qa (uk |x)

QMa

`=1 ra (u` ; x)

`6=k

(24)

iid

u2:Ma ∼ ra (u;x)

= Ex∼qa (x)
u1 ∼qa (u|x)



ηaMa (u1:Ma ; x)
log Ma
λa (u1:Ma ; x)

(25)

iid

u2:Ma ∼ ra (u;x)



ηaMa (u1:Ma ; x)
= Ex∼qa (x)
log Ma
Ma
λa (u1:Ma ; x)
u1:Ma ∼ηa
(u1:Ma ;x)


Ma
a
= Ex∼qa (x) DKL (ηa (u1:Ma ; x) k λM
a (u1:Ma ; x))

(26)
(27)

a
where to obtain Equation (26) we used the fact that log(ηaMa (u1:Ma ; x)/λM
a (u1:Ma ; x)) is invariant
to permutation of its arguments u1:Ma . Substituting the expression given by Equation (22) and the
expression given by Equation (27) into Equation (14), we have:
h
i
Mb
Mb
a ,Mb
E[L̂1,M
]
=
L
−
E
D
(λ
(v
;
x)
k
η
(v
;
x))
(28)
ab
KL
1:M
1:M
x∼q
(x)
b
b
a
ab
b
b


a
− Ex∼qa (x) DKL (ηaMa (u1:Ma ; x) k λM
(29)
a (u1:Ma ; x))

15

From non-negativity of KL divergence:
a ,Mb
E[L̂1,M
] ≤ Lab
ab

(30)

a ,Mb
Next, we show that E[L̂1,M
] is nondecreasing in both Ma and Mb . First, we show this for Ma .
ab
We introduce the notation u1:k−1:k+1:Ma := (u1 , . . . , uk−1 , uk+1 , . . . , Ma ) to denote the subvector
of length Ma − 1 obtained by removing element k from vector u1:Ma , where u1:0:2:Ma := u2:Ma and
u1:Ma −1:Ma +1:Ma := u1:Ma −1 . Note that:

ηaMa (u1:Ma ; x) =

Ma
1 X
ηaMa −1 (u1:k−1:k+1:Ma ; x)ra (uk ; x)
Ma

(31)

k=1

By convexity of KL divergence, we have:
a
DKL (ηaMa (u1:Ma ; x) k λM
a (u1:Ma ; x))

≤

=
=

1
Ma

Ma
X

(32)

a
DKL (ηaMa −1 (u1:k−1:k+1:Ma ; x)ra (uk ; x) k λM
a (u1:Ma ; x))

(33)

k=1

Ma
1 X
DKL (ηaMa −1 (u1:Ma −1 ; x) k λaMa −1 (u1:Ma −1 ; x))
Ma

k=1
DKL (ηaMa −1 (u1:Ma −1 ; x)

a −1
k λM
(u1:Ma −1 ; x))
a

(34)
(35)

A similar argument can be used to show that:
Mb
b
DKL (λM
b (v1:Mb ; x) k ηb (v1:Mb ; x))

≤

b −1
DKL (λM
(v1:Mb −1 ; x)
b

k

ηbMb −1 (v1:Mb −1 ; x))

(36)
(37)

Applying these inequalities to Equation (29), we have:
a ,Mb
a −1,Mb
Lab ≥ E[L̂1,M
] ≥ E[L̂1,M
]
ab
ab

(38)

a ,Mb −1
E[L̂1,M
]
ab

(39)

Lab ≥

a ,Mb
E[L̂1,M
]
ab

≥

To conclude the proof we apply these inequalities to the expectation of the AIDE estimate:
a ,Ma ,Mb
b ,Mb ,Ma
D̂Na ,Nb ,Ma ,Mb = −L̂N
− L̂N
ab
ba

E[D̂

Na ,Nb ,Ma ,Mb

a ,Mb
E[−L̂1,M
]
ab

b ,Ma
E[−L̂1,M
]
ba

]=
+
≥ −Lab − Lba
= DKL (qa (x) k qb (x)) + DKL (qb (x) k qa (x))

E[D̂Na ,Nb ,Ma ,Mb ] ≤ E[D̂Na ,Nb ,Ma −1,Mb ]
E[D̂

D

Na ,Nb ,Ma ,Mb

] ≤ E[D̂

Na ,Nb ,Ma ,Mb −1

]

(40)
(41)
(42)
(43)
(44)
(45)

Bias of AIDE for AIS and MH

When the generic SMC algorithm (Algorithm 3) is used with a single particle (P = 1), the algorithm
becomes a Markov chain that samples from transition kernels kt , and the canonical SMC metainference algorithm also becomes a Markov chain that samples from transition kernels `t in reverse
order. For this analysis we assume that kt = `t and that kt satisfies detailed balance with respect to
intermediate distribution pt−1 for t = 2 . . . T . Then, the incremental weight simplifies to:
p̃t (xt )kt (xt−1 ; xt )
p̃t−1 (xt−1 )kt (xt ; xt−1 )
p̃t (xt ) p̃t−1 (xt−1 )
=
p̃t−1 (xt−1 ) p̃t−1 (xt )
p̃t (xt )
=
p̃t−1 (xt )

wt (xt−1 , xt ) =

16

(46)
(47)
(48)

Under the limiting assumption that kt (xt ; xt−1 ) = pt−1 (xt ), the approximation error of the canonical
meta-inference algorithm becomes:
DKL (q(u|x) k r(u; x)) =

T
X

DKL (pt−1 (x) k pt (x))

(49)

t=2

where p0 is defined to be the initialization distribution k1 , and where pT (x) = p(x|y). A similar
result can be obtained for the other direction of divergence. If the intermediate distributions are
sufficiently fine-grained, then empirically this divergence converges to zero (as demonstrated in e.g.
[12]). However, in standard Markov chain Monte Carlo practice, without annealing, the intermediate
distributions are pt = pT for all t > 0. In this case, the approximation error of meta-inference is the
divergence between the initializing distribution and the posterior, which is generally large. Better
meta-inference algorithms that do not rely on the AIS assumption that the chain is near equilibrium at
all times are needed in order for AIDE to be a practical tool for measuring the accuracy of standard,
non-annealed Markov chain Monte Carlo.

E

Evaluating SMC inference in DPMM for galaxy velocity data

We obtained a data set of galaxy velocities based on redshift [20], and randomly subsampled down to
forty of the galaxies for analysis. A histogram of the data set is shown in Figure 6(a). We consider
the task of inference in a collapsed normal-inverse-gamma DPMM. We used SMC with 100 particles,
optimal (Gibbs) proposal for cluster assignments, and Metropolis-Hastings rejuvenation kernels over
hyperparameters and Gibbs kernels over cluster assignments as the gold-standard inference algorithm.
Using this gold-standard, we evaluated the accuracy of SMC inference with the prior proposal, and
without rejuvenation kernels using AIDE and using an alternative diagnostic based on comparing
the average number of clusters in the sampling distribution relative to the average number under the
gold-standard sampling distribution. Results are shown in Figure 6(b) and Figure 6(c).

17

800
600
400
200
0

SMC, prior proposal
0 rejuvenation sweep(s)
SMC, prior proposal
1 rejuvenation sweep(s)
0

10000
20000
30000
40000
Recessional velocity (redshift, km/s)

AIDE estimates

(a)

Average number
of clusters

nats

101
100
100

101
102
Number of particles
(b)

Heuristic diagnostic

8

102

50000

SMC, prior proposal
4 rejuvenation sweep(s)
SMC, optimal proposal
0 rejuvenation sweep(s)
SMC, optimal proposal
1 rejuvenation sweep(s)

6

SMC, optimal proposal
4 rejuvenation sweep(s)

4
100

101
102
Number of particles

Gold-standard

(c)

Figure 6: (a) shows a histogram of velocities of galaxies from [20]. We model this data set using
a Dirichlet process mixture, and evaluate the accuracy of SMC inference algorithms relative to a
gold-standard, using AIDE and using a heuristic diagnostic based on measuring the average number
of clusters in the approximating distribution and the gold-standard distribution. (b) shows results of
AIDE. (c) shows result of the heuristic diagnostic. Both techniques indicate that rejuvenation kernels
are important for fast convergence. Unlike the heuristic diagnostic, AIDE does not require custom
design of a probe function for each model. We envision AIDE being used in concert with heuristic
diagnostics like (c). In our experience, AIDE provides more conservative quantification of accuracy
than heuristic diagnostics. The experiment was performed on a subsampled set of 40 data points from
the data set in (a).

18

