  Information projections are the key building block of variational inference
algorithms and are used to approximate a target probabilistic model by
projecting it onto a family of tractable distributions. In general, there is no
guarantee on the quality of the approximation obtained. To overcome this issue,
we introduce a new class of random projections to reduce the dimensionality and
hence the complexity of the original model. In the spirit of random
projections, the projection preserves (with high probability) key properties of
the target distribution. We show that information projections can be combined
with random projections to obtain provable guarantees on the quality of the
approximation obtained, regardless of the complexity of the original model. We
demonstrate empirically that augmenting mean field with a random projection
step dramatically improves partition function and marginal probability
estimates, both on synthetic and real world data.
