1$ for some $m$; we never encountered this in practice, but a safe choice is to proceed to the next batch if that happens.

For a practical illustration of the algorithm, see Figure \[fig:normalcontour\] that approximates the posterior over the mean and precision of a normal model. Here $t=0.9$ and hence we take on average $9$ importance-sampled gradient steps for each mini-batch. The I-SGD algorithm reaches the optimum in roughly as many steps as conventional SGD but achieves it almost ten times faster.

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

Stochastic average gradients [@sage] stores the batch gradient and iteratively updates it for the samples in a given mini-batch. In the following we derive a variant of SAG (Algorithm \[alg:isag\]) that uses importance sampling to both re-weight and update the gradients for the historical mini-batches using , helping to detect and avoid using stale gradients whose parameter values have changed so much since computing them.

When visiting a new mini-batch we compute the gradient using . For all previously visited mini-batches we compute the importance weights and modify the gradient according to . The whole gradient is formed by summing up the terms for all mini-batches. It is important to note that 