the ratio between the trace of the Hessian of $L$ and its minimal eigenvalue: $$\label{eq:initialCondition}
{\hat{\kappa}}:={\hat{\kappa}}(C+\lambda I) = \frac{\tr(C+\lambda I)}{\lambda_d(C+\lambda I)} = \sum_{i=1}^d \frac{\lambda_i+\lambda}{\lambda_d+\lambda}  ~.$$ The mentioned variant of SVRG finds an $\epsilon$-approximate minimizer of $L$ in time $\tilde{O}(({\hat{\kappa}}+n)d \log(1/\epsilon))$. Namely, the output of the algorithm, denoted $\hat{w}$, satisfies $\bE[L(\hat{w})]-L(w^\star) \le \epsilon$, where the expectation is over the randomness of the algorithm. For an accelerated version of the algorithm, we can replace ${\hat{\kappa}}$ by $\sqrt{n {\hat{\kappa}}}$ [@shalev2014accelerated; @lin2015universal].

The regularization parameter, $\lambda$, increases the smallest eigenvalue of $C+\lambda I$ to be at least $\lambda$, thus improves the condition number and makes the optimization problem easier. However, to control the under/over fitting tradeoff, $\lambda$ has to decrease as $n$ increases [@shalev2014understanding]. Moreover, in many machine learning applications $\lambda_d$ approaches zero and it is usually smaller than the value of $\lambda$. Overall, this yields a large condition number in most of the interesting cases.

A well-known approach for reducing the average condition number is *preconditioning*. Concretely, for a (symmetric) positive definite (pd) matrix $P \in \reals^{d \times d}$, we define the preconditioned optimization problem as $$\label{eq:condRidge}
\min_{{\tilde{w}}\in \reals^d} {\tilde{L}}({\tilde{w}}):= L(P^{-1/2} {\tilde{w}}) ~.$$ Note that ${\tilde{w}}$ is an $\epsilon$-approximate minimizer of ${\tilde{L}}$ if 