low-rank approximation are based on either Frobenius norm or spectral norm errors. As will be apparent from the analysis (see ), such bounds do not suffice for our needs. Our analysis relies on stronger per vector error guarantees due to [@musco2015stronger].

It should be emphasized that while we use a variant of SVRG due to [@xiao2014proximal], we could equally use a variant of SDCA [@shalev2016sdca] or develop such a variant for SAG or SAGA. Furthermore, while we focus on the quadratic case, we believe that our ideas can be lifted to more general setting. For example, when applied to self-concordant functions, each step of Newton’s method requires the minimization of a quadratic objective. Therefore, it is natural to ask if we can benefit from applying our method for approximating the Newton step.

Bias-complexity tradeoff {#sec:reduceReg}
------------------------

As we mentioned above, $\lambda$ controls a tradeoff between underfitting and overfitting. In this view, we can interpret our result as follows. Assuming for simplicity that $n \ge d$ and ignoring logarithmic dependencies, we note that if $$\label{eq:decay}
\lambda = \frac{k \lambda_k+\sum_{i>k}\lambda_i}{nk}~,$$ then the runtime of our preconditioned SVRG is $\tilde{O}(ndk)$. For comparison, the runtime of (unconditioned) SVRG is $\tilde{O}(ndk)$ if $$\label{eq:decaySVRG}
\lambda = 