$r$ can be written in (thin) SVD form as $B = U \Sigma V^\top = \sum_{i=1}^r \sigma_i(B) u_i v_i^\top$. The singular values are ordered in descending order. The spectral norm of $B$ is defined by $\|B\|=\sigma_1(B)$. The spectral norm is submultiplicative, i.e., $\|AB\| \le \|A\|\|B\|$ for all $A$ and $B$. Furthermore, the spectral norm is unitary invariant, i.e., for all $A$ and $U$ such that the columns of $U$ are orthonormal, $\|UA\| = \|A\|$. For any $k \in [r]$, it is well known that the truncated SVD of $B$, $B_k := U_k \Sigma_k V_k =  \sum_{i=1} ^{k} \sigma_i(B) u_i v_i^\top$, is the best rank-$k$ approximation of $B$ w.r.t. the spectral norm [@trefethen1997numerical]. A twice continuously differentiable function $f: \reals^d \rightarrow \reals$ is said to be $\beta$-smooth if $\|\nabla^2 f(w)\| \leq \beta$ for all $w$, where $\nabla^2 f(w)$ is the Hessian of $f$ at $w$. $f$ is said to be $\alpha$-strongly convex if $\lambda_d(\nabla^2 f(w)) \ge \alpha$ for all $w$. If $g$ is convex and $f$ is $\alpha$-strongly convex, then $f+g$ is $\alpha$-strongly convex.

Stochastic Variance Reduced Gradient (SVRG) {#sec:svrg}
-------------------------------------------

We consider a variant of the Stochastic Variance Reduced Gradient (SVRG) algorithm of [@johnson2013accelerating] due to [@xiao2014proximal]. The algorithm is 