\sum_{i=1}^k {\tilde{\sigma}}_i {\tilde{u}}_i {\tilde{v}}_i^\top$. Denote the SVD of $A$ by $A = \sum_{i=1}^d \sigma_i v_i u_i^\top$. The following bounds hold with probability at least $9/10$: $$\|A - {\tilde{A}}_k\| \le (1+\epsilon') \|A-A_k\| \le (1+\epsilon') \sigma_k$$ $$\begin{aligned}
\forall i \in [k],~~|z_i^\top AA^\top z_i - u_i^\top AA^\top u_i| &=  |{\tilde{\sigma}}_i^2-\sigma_i^2 | \notag \\
&\le \epsilon' \sigma_{k+1}^2 ~. \label{eq:perVec}\end{aligned}$$ The runtime of the algorithm is $O\left(\frac{nd k \log(n)}{ \sqrt{\epsilon'}}+ \frac{k^2(n+d)}{\epsilon'} \right)$.

Sketched Conditioned SVRG {#sec:scsvrg}
=========================

In this section we develop our sketched conditioning method. By analyzing the properties of this conditioner and combining it with SVRG, we will conclude .

Recall that we aim at devising cheaper preconditioners that lead to a significant reduction of the condition number. Specifically, given a parameter $k \in [d]$, we will consider only preconditioners $P^{-1/2}$ for which both the computation of $P^{-1/2}$ itself and the computation of the set $\{P^{-1/2}x_i, \ldots, P^{-1/2} x_n\}$ can be carried out in time $\tilde{O}(ndk)$. We will soon elaborate more on the considerations when choosing the preconditioner, but first we would like to address some important implementation issues.

Preconditioned regularization {#sec:regCond}
-----------------------------

In order to implement the preconditioning scheme suggested above, we should be able to find a simple form for the 