$\tilde{L}$ as follows: $$\begin{aligned}
 {\tilde{L}}(w) = \frac{1}{n+d} \sum_{i=1}^{n+d} {\tilde{\ell}}_i(w)~,\end{aligned}$$ where ${\tilde{\ell}}_i(w) = \frac{n+d}{n} \frac{1}{2} (w^\top {\tilde{x}}_i-y_i)^2$ for $i=1,\ldots,n$ and ${\tilde{\ell}}_{n+i}(w)=\lambda(n+d) \frac{1}{2}(w^\top b_i)^2$ for $i=1,\ldots,d$. By computing the ${\tilde{x}}_i$’s and the $b_i$’s in advance, we are able to apply SVRG while computing stochastic gradients in time $O(d)$.

The effect of conditioning
--------------------------

We are now in position to address the following fundamental question: How does the choice of the preconditioner, $P^{-1/2}$, affects the resulted average condition number of the function ${\tilde{L}}$ (\[eq:conditionSVRG\])? The following lemma upper bounds ${\hat{\kappa}}_{{\tilde{L}}}$ by the average condition number of the matrix $P^{-1/2}(C+\lambda I)P^{-1/2}$, which we denote by ${\tilde{\kappa}}$ (when the identity of the matrix $P$ is understood).

\[thm:condEffect\] Let $P^{-1/2}$ be a preconditioner. Then, the average condition number of $\tilde{L}$ is upper bounded by $${\hat{\kappa}}_{\tilde{L}} \le {\tilde{\kappa}}= \frac{\tr (P^{-1/2} (C + \lambda I ) P^{-1/2} ) } {\lambda_d(P^{-1/2} (C + \lambda I ) P^{-1/2})} ~.$$

The proof is in the appendix. Note that an optimal bound of $O(d)$ is attained by the whitening matrix $P^{-1/2}  = (C+\lambda I)^{-1/2}$.

Exact sketched conditioning
---------------------------

Our sketched preconditioner is based on a random approximation of the best rank-$k$ approximation of the data matrix. It will be instructive to consider 