in standard SGD. However, we have taken considerably more gradient steps, possibly by a factor of ten. Alternatively, we can think of it as performing more updates given a constant number of model gradient evaluations.

A practical detail concerns the choice of how many steps to take for each mini-batch. This choice is governed by two aspects. On one hand we should not use the importance sampled estimate if the approximation has changed too much since computing the $\nabla_z \log p(x, z_m)$ terms, recognized typically as $w_m$ tending to zero. On the other hand, we should not take too many steps even if the approximation does not change dramatically, since the gradient is still based on just a single mini-batch.

The empirical experiments in this paper are run with a simple heuristic that randomly determines whether to take another step with the current mini-batch or to proceed to the next one. This introduces a single tuning parameter $t$ that controls the expected number of steps per mini-batch. The algorithm is robust for this choice; we obtain practical speedups with values ranging from $t = 0.5$ to $t=0.9$. Finally, importance-sampling could in principle result in very large gradients if $w_m \gg 