an epoch-based iterative method for minimizing an average, $F(w) = \frac{1}{N} \sum_{i=1}^N f_i(w)$, of smooth functions. It is assumed that each $f_i:\reals^d \rightarrow \reals$ is convex and $\beta_i$-smooth. The entire function $F$ is assumed to be $\alpha$-strongly convex. The algorithm is detailed in . Its convergence rate depends on the averaged smoothness of the individual functions and the average condition number of $F$, defined as $$\label{eq:conditionSVRG}
\hat{\beta} = \frac{1}{N} \sum_{i=1}^N \beta_i ~~~;~~~ {\hat{\kappa}}_F = \frac{\hat{\beta}}{\alpha} ~.$$

**[@xiao2014proximal]** \[thm:svrg\] Fix $\epsilon>0$. Running SVRG () with any $w_0$, $S \ge \log((F(w_0) - \min_{w \in \reals^d} F(w))/\epsilon)$, $m = \lceil {\hat{\kappa}}_F \rceil$, and $\eta = 0.1/\hat{\beta}$ yields an $\epsilon$-approximate minimizer of $F$. Furthermore, assuming that each single gradient $\nabla f_i(w)$ can be computed in time $O(d)$, the overall runtime is $O(({\hat{\kappa}}_F+N)d \log(\epsilon_0/\epsilon))$.

**Input:** Functions $f_1,\ldots,f_n, \beta_1,\ldots,\beta_n$ **Parameters:** $\bar{w}_0 \in \reals^d$, $m$, $\eta$, $S \in \mathbb{N}$ $\bar{w} = \bar{w}_{s-1}$ $\bar{v} = \nabla F(\bar{w})$ $w_0 = \bar{w}$ Pick $i_t \in [N]$ with probability $q_{i_t}=\beta_{i_t}/\sum \beta_j$ $v_t = (\nabla f_{i_t}(w_{t-1}) -\nabla f_{i_t}(\bar{w}))/q_{i_t}+\bar{v}$ $w_t = w_{t-1} - \eta v_t$ $\bar{w}_s = \frac{1}{m} \sum_{t=1}^m w_t$ **Output:** the vector $\bar{w}_S$

In the original definition of SVRG [@johnson2013accelerating], the indices $i_t$ are chosen uniformly at random from $[n]$, rather than 