sketched preconditioner , we obtain the Sketched Preconditioned SVRG (see ).

**(of )** The theorem follows from and .

**Input:** $x_1,\ldots, x_n \in \reals^d, y_1,\ldots,y_n \in \reals, \epsilon>0$ **Parameters:** $\lambda>0, k \in [d]$ Let $\bar{X} \in \reals^{d,n}$ be the matrix whose $i$’th column is $(1/n) x_i$ Run the Block Lanczos method () with the input $\bar{X}, k, \epsilon'=1/2$ to obtain ${\tilde{X}}_k = {\tilde{U}}_k {\tilde{\Sigma}}_k {\tilde{V}}_k$ Let ${\tilde{u}}_i$ be the columns of ${\tilde{U}}_k$ and $\tilde{\sigma}_i$ be the diagonal elements of ${\tilde{\Sigma}}_k$ Form the preconditioner $P^{-1/2}$ according to Compute ${\tilde{x}}_i = P^{-1/2} x_i, b_i = P^{-1/2} e_i$ Let $\ell_i(w) = \frac{n+d}{n} \frac{1}{2} (w^\top {\tilde{x}}_i-y_i)^2$ for $i=1,\ldots,n$ and $\ell_i(w) = \lambda(n+d) (w^\top b_i)^2$ for $i=n+1,\ldots,n+d$ Let $\beta_i = \frac{n+d}{n} \|{\tilde{x}}_i\|^2$ for $i=1,\ldots,n$ and $\beta_i  = \lambda(n+d) \|b_i\|$ for $i=n+1,\ldots,n+d$. Let $\hat{\beta} = \frac{1}{n} \sum_{i=1}^{n+d} \beta_i$ Run SVRG () Return $\hat{w} = P^{1/2} \tilde{w}$

The Empirical Gain of Sketched Preconditioning {#sec:empirical}
==============================================

\[b\] [0.23 ]{}

\[b\] [0.23]{}

\[b\] [0.23]{}

\[b\] [0.23]{}

[0.23 ]{}

[0.23 ]{}

[0.23 ]{}

[0.23 ]{}

[0.23 ]{}

[0.23 ]{}

In this section we empirically demonstrate the gain of our method. We consider both regression problems and binary classifications tasks, where the square loss serves as a surrogate for the zero-one 