of both the (accelerated) SVRG and our preconditioned (accelerated) SVRG are controlled by the average condition number (and both runtimes dominate $ndk$), then ignoring logarithmic dependencies, we obtain a speed-up of order $$\label{eq:ratioRidge}
\textrm{ratio} = \frac{\sum_{i=1}^d \lambda_i}{k\,\lambda_k+\sum_{i>k}\lambda_i}
= \frac{\sum_{i=1}^k \lambda_i +\sum_{i>k}\lambda_i }{k\,\lambda_k ~~~~+\sum_{i>k}\lambda_i}~.$$ (or $\sqrt{\sum_{i=1}^d \lambda_i/(\lambda_k k+\sum_{i>k}\lambda_i)}$ if acceleration is used) over SVRG. If the spectrum decays fast then $k \, \lambda_k \ll \sum_{i=1}^k \lambda_i$ and $\sum_{i>k}\lambda_i \ll k \, \lambda_k$. In this case, the ratio will be large. Indeed, as we show in the experimental section, this ratio is often *huge* for relatively small $k$.

Main challenges and perspective
-------------------------------

While the idea of developing a preconditioner that focuses on the stronger directions of the data matrix sounds plausible, there are several difficulties that have to be solved.

-   First, since a preconditioner must correspond to an invertible transformation, it is not clear how to form a preconditioner based on a low rank approximation and, in particular, how should we treat the non-leading components.

-   One of the main technical challenges in our work is to translate the approximation guarantees of the Lanczos method into a guarantee on the resulted average condition number. The standard measures of success for 