be combined with several optimization algorithms. In this work, we derive practical algorithms extending standard SGD and stochastic average gradients [@sage]. We demonstrate them in learning a variational approximation for several probabilistic models, showing how they improve the convergence speed in a model-independent manner.

In the following we first give a brief overview of the state-of-the-art in gradient-based variational approximation, covering both the gradient estimates and stochastic optimization algorithms in Section 2. We then proceed to describe the importance sampling estimate for the gradient in Section 3, followed by practical optimization algorithms outlined in Section 4. Empirical experiments and illustrations are provided in Section 5.

BACKGROUND
==========

VARIATIONAL APPROXIMATION
-------------------------

Variational inference refers to approximating the posterior distribution $p(z|x)$ of a probabilistic model $p(x,z)$ using a distribution $q_\lambda(z)$ parameterized by $\lambda$. Usually this is achieved by maximizing a lower bound $\mathcal{L}(\lambda)$ for the evidence (also called the marginal likelihood) $p(x)$: $$\mathcal{L}(\lambda) = \int q_\lambda(z) \log \frac{p(x, z)} {q_\lambda(z)}\ \delta z \le p(x).
  \label{eq:ELBO}$$ Traditionally, the problem has been made tractable by assuming a factorized mean-field approximation and models with conjugate priors, resulting in closed-form coordinate ascent algorithms specific for individual models – for a full derivation and examples, see, [*e.g.*]{}, 