  Variance reduced stochastic gradient (SGD) methods converge significantly
faster than the vanilla SGD counterpart. However, these methods are not very
practical on large scale problems, as they either i) require frequent passes
over the full data to recompute gradients---without making any progress during
this time (like for SVRG), or ii)~they require additional memory that can
surpass the size of the input problem (like for SAGA). In this work, we propose
$k$-SVRG that addresses these issues by making best use of the \emph{available}
memory and minimizes the stalling phases without progress. We prove linear
convergence of $k$-SVRG on strongly convex problems and convergence to
stationary points on non-convex problems. Numerical experiments show the
effectiveness of our method.
