\frac{\sum_{i=1}^d \lambda_i}{nk}~.$$ The ratio between the RHS of and is the ratio given in . Hence, for a given “runtime budget” of order $\tilde{O}(ndk)$, we can set the regularization parameter of the preconditioned SVRG to be smaller by this ratio. Similar interpretation holds for the accelerated versions.

Related Work {#sec:related}
============

#### Existing algorithms and their complexities: 

Since minimizing is equivalent to solving the system $(C+\lambda I)w=\frac{1}{n} \sum_{i=1}^n y_i x_i$, standard numerical linear algebra solvers such as Gaussian elimination can be used to solve the problem in time $O(nd^2)$.

Iterative deterministic methods, such as Gradient Descent (GD), finds an $\epsilon$-approximate minimizer in time $nd \kappa \log(1/\epsilon)$, where $\kappa=\frac{\lambda_1(C+\lambda I)}{\lambda_d(C+\lambda I)}$ is the condition number of $C+\lambda I$ (see Theorem 2.1.15 in [@nesterov2004introductory]). The Kaczmarz algorithm [@kaczmarz1937angenaherte] has an identical complexity. Both the Conjugate Gradient (CG) method [@hestenes1952methods] and the Accelerated Gradient Descent (AGD) algorithm of [@nesterov1983method] enjoy a better runtime of $nd \sqrt{\kappa}\log(1/\epsilon)$. In fact, CG has a more delicate analysis (see Corollary 16.7 in [@vishnoi2012laplacian]): If all but $c \in [d]$ eigenvalues of $C+\lambda I$ are contained in a range $[a,b]$, then the runtime of CG is at most $nd(c+\sqrt{b/a} \log(1/\epsilon))$. In particular, CG’s runtime is at most $O(nd^2)$. 