and only if $w = P^{-1/2} {\tilde{w}}$ forms an $\epsilon$-approximate minimizer of $L$. Hence, we can minimize rather than . As we shall see, the structure of the objective allows us to apply the preconditioning directly to the data (as a preprocessing step) and consequently rewrite the preconditioned objective as a ridge regression problem with respect to the preconditioned data (see ). For a suitable choice of a matrix $P$, the average condition number is significantly reduced. Precisely, as will be apparent from the analysis, the pd matrix that minimizes the average condition number is $P=C+\lambda I$, and the corresponding average condition number is $d$. However, we note that such preconditioning process would require both the computation of $P^{-1/2}$ and the computation of $P^{-1/2} x_i$ for each $i \in [n]$. By first order conditions, computing $(C+\lambda I)^{-1/2}$ is equivalent to solving the original problem in , rendering this “optimal” preconditioner useless. Yet, the optimal preconditioner might not needed in many cases. In fact, a common empirical observation (see ) is that (high-dimensional) machine learning problems tend to have few dominant features, while the other coordinates are strongly correlated with the stronger features. As a result, the spectrum of the correlation 