\|{\tilde{U}}(({\tilde{\Sigma}}^2+\lambda I)^{1/2}- {\tilde{\Sigma}}) {\tilde{V}}^\top\|~.\end{aligned}$$ By using unitary invariance together with the inequality $\sqrt{{\tilde{\sigma}}_i^2+\lambda} - {\tilde{\sigma}}_i \le \sqrt{\lambda}$ (which holds for every $i$), we get $$\|{\tilde{U}}(({\tilde{\Sigma}}^2+\lambda I)^{1/2}- {\tilde{\Sigma}}) {\tilde{V}}^\top\| = \|({\tilde{\Sigma}}^2+\lambda I)^{1/2}- {\tilde{\Sigma}}\| \le \sqrt{\lambda}~.$$ Hence, using the inequality $(x+y)^2 \le 2x^2 + 2y^2$, we obtain $$\begin{aligned}
  \|{\tilde{Z}}- \bar{X}\|^2 &\le  2 \|{\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top - \bar{X}\|^2 + 2\lambda ~.\end{aligned}$$ We next derive an upper bound on $\|{\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top - \bar{X}\|$. Since ${\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top = \tilde{X}_k + {\tilde{\sigma}}_k \sum_{i=k+1}^d {\tilde{u}}_i {\tilde{v}}_i^\top$, $$\|{\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top-\bar{X}\| \le \|\tilde{X}_k - \bar{X}\|+{\tilde{\sigma}}_k \left\|\sum_{i=k+1}^d {\tilde{u}}_i {\tilde{v}}_i^\top\right\| ~.$$ Using we know that $\|\tilde{X}_k - \bar{X}\| \le 1.5 \, \sigma_k$ and that ${\tilde{\sigma}}_k \le \sqrt{\sigma_k^2+0.5 \, \sigma_{k+1}^2} \le  1.5 \, \sigma_k$. Combining this with the fact that $\|\sum_{i=k+1}^d {\tilde{u}}_i {\tilde{v}}_i^\top\| = 1$, we obtain $$\begin{aligned}
 \|{\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top-\bar{X}\| \le 3\,\sigma_k ~.\end{aligned}$$ Combining the above inequalities, we obtain $$\begin{aligned}
\|P^{1/2} (C+\lambda I)^{-1} P^{1/2}\| 
&\le  1 + \frac{2 \cdot(3 \sigma_k)^2+2\lambda}{\lambda_d+\lambda} \\
&\le \frac{19(\lambda_k+\lambda)}{\lambda} ~,\end{aligned}$$ and using we conclude our proof.

**(of )** The three last lemmas imply that the inequalities derived during the proof of remain intact up to a multiplicative constant. Therefore, the bound on the condition number also holds up to a multiplicative constant. This completes the proof.

Sketched Preconditioned SVRG
----------------------------

By equipping SVRG with the 