provided for a straightforward variant of SGD and for a generalization of stochastic average gradients, but other related algorithms could be instantiated as well.

IMPORTANCE SAMPLED SGD
----------------------

Stochastic gradient descent estimates the gradient based on a mini-batch and then takes a step along the gradient direction, typically using adaptive learning rates such as those by @adam [@adagrad].

The importance sampled SGD (I-SGD; Algorithm \[alg:isgd\]) follows otherwise the same pattern, but for each mini-batch we conduct several gradient steps instead of just one. For the first one we evaluate the gradient directly using . After updating the approximation we apply Algorithm \[alg:impgrad\] to obtain an importance-sampled estimate for the gradient evaluated at the new parameter values, and proceed to take another gradient step using that estimate. For each step we use a proper estimate for the mini-batch gradient that can, after the first evaluation, be computed in a fraction of a time. After taking a few steps we then proceed to analyze a new mini-batch, again needing to compute the gradient from scratch since now $x$ has changed.

After passing through the whole data we have evaluated $\log p(x, z)$ and its gradient once for every data point, just as 