(f) mini-batch. The variational approximations used were the same as the priors. For the sub-plots (d) and (e) evaluating the log-probability takes long compared to evaluating the gradient of the approximation because of a large mini-batch size, and hence I-SGD is faster. With a smaller mini-batch size (f) the advantage is lost because evaluating the gradient of the approximation starts to dominate. We used $M =
100$ samples and did not consider variance reduction techniques for simplicity.

IMPORTANCE SAMPLED SAG {#sec:isage}
----------------------

Figure \[fig:sag\] compares the I-SAG algorithm (Algorithm \[alg:isag\]) against naive implementation of SAG [@sage]. Both algorithms are initialized by passing once through the data with I-SGD, to provide the initial estimate for the full batch gradient.

While SAG eventually converges to the right solution, the progress is slow and erratic due to stale mini-batch gradients being accumulated into the full gradient. I-SAG fixes the issue by not only down-weighting gradients corresponding to mini-batches visited several updates ago, but also by transforming the gradients to match the current approximation. The additional computation required for adapting the gradients for other mini-batches results in a computational overhead of, here, roughly 30% per iteration, but the improved accuracy of the batch gradient 