the inference backend in probabilistic programming languages [@advi; @pymc3; @edward].

The main research efforts in variational inference are nowadays geared towards making the approach applicable to a still wider family of models, by constructing even more flexible approximations [@rezende15; @ranganath16; @kingma16] or by generalizing the gradient estimators [@grep; @naesseth]. The question of how exactly the resulting optimization problem is solved has largely remained unattended to – practically all authors are satisfied with standard stochastic gradient descent (SGD) as the underlying optimizer, although some effort has been put into improving convergence by reducing the variance of the gradient estimate near the optimum [@roeder17].

We turn our attention to the optimizer itself, looking into ways of speeding up the computation of gradient-based variational approximation. Practically all of the computational effort during learning goes into evaluating the gradient of the model (or the approximation if using the score-function estimate). Our contribution is in reducing the number of times we need to evaluate the gradient of the model during the optimization process, based on an importance sampling scheme specifically designed for optimization problems where the gradients are computed using Monte Carlo approximation.

The key observation is that the gradient of the objective function with 