matrix decays very fast. Hence, it is natural to expect to gain a lot from devising preconditioning methods that focus on the stronger directions of the data.

Our contributions are as follows. We develop a relatively cheap preconditioning method that, coupled with SVRG, assures to speed-up the convergence in practical applications while having a computational cost comparable to SVRG alone. In order to approximately extract the stronger directions while incurring a low computational cost, we rely on a variant of the Block Lanczos method due to [@musco2015stronger] in order to compute an approximated truncated SVD (Singular Value Decomposition) of the correlation matrix $C$. Finally, by equipping SVRG with this preconditioner, we obtain our main result.

Main Result {#sec:mainResult}
===========

\[thm:main\] Let $k \in [d]$ be a given parameter and assume that the regularization parameter, $\lambda$, is larger than $\lambda_d$. Our preconditioning process runs in time $O(ndk \log(n))$. By equipping the SVRG of [@xiao2014proximal] with this preconditioner, we find an $\epsilon$-approximate minimizer for (with probability at least $9/10$) in additional runtime of $O ((\tilde{\kappa}  + n + d )d \log(1/\epsilon) )$, where $\tilde{\kappa}=\frac{k \lambda_k+ \sum_{i>k} \lambda_i}{\lambda}$ or $\tilde{\kappa} = \left(\frac{n(k \lambda_k+ \sum_{i>k} \lambda_i)}{\lambda}\right)^{1/2}$ if we use accelerated SVRG.

When the runtimes 