SVRG and SAGA gradient-work and storage ledger

By [F1] and [F3], one full gradient evaluates each of the $n$ component gradients once, and each of the $m$ inner updates evaluates two component gradients, so SVRG uses $n+2m$ evaluations. By [F2], SAGA initializes all $n$ table entries and evaluates one sampled component per update, so its initialized block uses $n+m$ evaluations and a later block uses $m$. Substitution of $n=1000$ and $m=2000$ gives 5000, 3000, and 2000, respectively.

A full gradient sums and scales $n$ vectors with $d$ coordinates, using $O(nd)$ coordinate operations; each update in [F1] has a fixed number of vector operations and therefore costs $O(d)$. SAGA's initialization forms the table mean from $n$ vectors for $O(nd)$ coordinate operations, and each update in [F2] uses a fixed number of vector operations for $O(d)$.

For SVRG, sample the independent uniform output index $J$ before the epoch and save $x_J$ when that index is reached, including $x_0$ if $J=0$. The inner updates do not use $J$, so independence gives the same joint law of $J$ and the trajectory, and hence the same returned-snapshot law as sampling $J$ after the updates. This implementation needs one saved $d$-vector in addition to the fixed update buffers in [F1], uses no extra gradient evaluations, and therefore has $O(d)$ working storage. By [F2], SAGA stores $n$ table vectors and a constant number of additional $d$-vectors, giving $nd+O(d)=O(nd)$ scalars because $n\ge 1$. At the numerical instance the table itself contains $1000\cdot 20=\mathrm{20,000}$ coordinates. The accounting excludes arithmetic within each component-gradient evaluation and makes no total-runtime claim.