proportional to $\beta_i$. As a result, the convergence rate depends on the maximal smoothness, $\max \{\beta_i\}$, rather than the average, $\hat{\beta}$. It will be apparent from our analysis (see ) that in our case, $\max \{\beta_i\}$ is proportional to the maximum norm of any preconditioned $x_i$. Since we rely on the improved variant of [@xiao2014proximal], our bound depends on the average of the $\beta_i$’s, which scale with the average norm of the preconditioned $x_i$’s. To simplify the presentation, in the sequel we refer to as SVRG.

Randomized Block Lanczos
------------------------

A randomized variant of the Block Lanczos method due to [@musco2015stronger] is detailed[^4] in . Note that the matrix ${\tilde{U}}_k {\tilde{\Sigma}}_k {\tilde{V}}_k^\top$ forms an SVD of the matrix ${\tilde{A}}_k := Q(Q^\top A)_k = {\tilde{U}}_k {\tilde{U}}_k^\top A$.

**Input:** $A \in \reals^{d \times n}, k \le d, \epsilon' \in (0,1)$ $q= \Theta \left(\frac{\log(n)}{\sqrt{\epsilon}} \right)$, $p=qk$, $\Pi \sim \cN(0,1)^{n \times k}$ Compute $K = [A \Pi,(AA^\top) A \Pi,\ldots, (AA^\top)^{q-1} A \Pi]$Orthonormalize $K$’s columns to obtain $Q \in \reals^{d \times qk}$ Compute the truncated SVD $(Q^\top A)_k = {\tilde{W}}_k {\tilde{\Sigma}}_k {\tilde{V}}_k^\top$ Compute ${\tilde{U}}_k = Q {\tilde{W}}_k$ **Output:** the matrices ${\tilde{U}}_k,{\tilde{\Sigma}}_k,{\tilde{V}}_k$

\[thm:musco\] **[@musco2015stronger]** Consider the run of and denote ${\tilde{A}}_k = {\tilde{U}}_k {\tilde{\Sigma}}_k {\tilde{V}}_k = 