  In this paper, we show that SVRG and SARAH can be modified to be
fundamentally faster than all of the other standard algorithms that minimize
the sum of $n$ smooth functions, such as SAGA, SAG, SDCA, and SDCA without
duality. Most finite sum algorithms follow what we call the "span assumption":
Their updates are in the span of a sequence of component gradients chosen in a
random IID fashion. In the big data regime, where the condition number
$\kappa=\mathcal{O}(n)$, the span assumption prevents algorithms from
converging to an approximate solution of accuracy $\epsilon$ in less than
$n\ln(1/\epsilon)$ iterations. SVRG and SARAH do not follow the span assumption
since they are updated with a hybrid of full-gradient and component-gradient
information. We show that because of this, they can be up to
$\Omega(1+(\ln(n/\kappa))_+)$ times faster. In particular, to obtain an
accuracy $\epsilon = 1/n^\alpha$ for $\kappa=n^\beta$ and
$\alpha,\beta\in(0,1)$, modified SVRG requires $\mathcal{O}(n)$ iterations,
whereas algorithms that follow the span assumption require
$\mathcal{O}(n\ln(n))$ iterations. Moreover, we present lower bound results
that show this speedup is optimal, and provide analysis to help explain why
this speedup exists. With the understanding that the span assumption is a point
of weakness of finite sum algorithms, future work may purposefully exploit this
to yield even faster algorithms in the big data regime.
