CIFAR-10 the ratio is large for small values of $k$, in RCV1 and real-sim the ratio increases very slowly (note that for the former two datasets we use logarithmic scale).

Empirical advantage of Sketched Preconditioned SVRG {#sec:emp}
---------------------------------------------------

We now evaluate and compare it to the SVRG algorithm of [@xiao2014proximal]. To minimally affect the inherent condition number, we added only a slight amount of regularization, namely, $\lambda=10^{-8}$. The loss used is the square loss. The step size, $\eta$, is optimally tuned for each method. Similarly to previous work on SVRG [@xiao2014proximal; @johnson2013accelerating], the size of each epoch, $m$, is proportional to the number of points, $n$. We minimally preprocessed the data by average normalization: each instance vector is divided by the average $\ell_2$-norm of the instances. The number of epochs is up to $60$. Note that in all cases we choose a small preconditioning parameter, namely $k=30$, so that the preprocessing time of is negligible. There is a clear correspondence between the ratios depicted in and the actual speedup. In other words, the empirical results strongly affirm our theoretical results.

Acknowledgments {#acknowledgments .unnumbered}
===============

We thank Edo Liberty for helpful discussions. The work is supported by ICRI-CI and by the 