  Variational inference is computationally challenging in models that contain
both conjugate and non-conjugate terms. Methods specifically designed for
conjugate models, even though computationally efficient, find it difficult to
deal with non-conjugate terms. On the other hand, stochastic-gradient methods
can handle the non-conjugate terms but they usually ignore the conjugate
structure of the model which might result in slow convergence. In this paper,
we propose a new algorithm called Conjugate-computation Variational Inference
(CVI) which brings the best of the two worlds together -- it uses conjugate
computations for the conjugate terms and employs stochastic gradients for the
rest. We derive this algorithm by using a stochastic mirror-descent method in
the mean-parameter space, and then expressing each gradient step as a
variational inference in a conjugate model. We demonstrate our algorithm's
applicability to a large class of models and establish its convergence. Our
experimental results show that our method converges much faster than the
methods that ignore the conjugate structure of the model.
