loss. We use the following datasets:

-   *Synthetic*: We draw two random $5000 \times 20000$ matrices, $X^{(1)}$ and $X^{(2)}$, whose singular vectors are drawn uniformly at random and the $q$-th singular value is $1/q$ and $1/q^2$, respectively. We then normalize the columns. For each $X=X^{(j)}$, we consider a regression problem, where the labels are generated as follows: we first draw a vector $w^\star \in \cN(0,1)^{5000}$ and then set $y_i = {w^\star}^\top X_{\cdot,i}+z_i$, where $z_i \sim \cN(0,0.1)$.

-   *MNIST*:[^5] A subset of MNIST, corresponding to the digits $4$ and $7$, where the task is to distinguish between the two digits. Here, $n=12107, d=784$.

-   *RCV1*:[^6] The Reuters RCV1 collection. Here, $n=20242, d=47236$ and we consider a standard binary document classification task.

-   *CIFAR-10*:[^7] Here, $n=50000, d=3072$. Following [@frostig2015regularizing], the classification task is to distinguish between the animal categories to the automotive ones.

-   *real-sim*:[^8] Here, $n=72309, d=20958$, and we consider a standard binary document classification task.

Inspecting our theoretical speed-up {#sec:ratioEmp}
-----------------------------------

Recall that the ratio quantifies our theoretical speedup. Hence, we first empirically inspect the prefixes of the corresponding quantities (as a function of $k$) for each of the datasets (see ). We can see that while in MNIST and 