Finite-sum SVRG

Let n,d>=1 and let f_1,...,f_n:R^d->R be continuously differentiable convex functions. Define the finite-sum objective

$$F(x)=\frac{1}{n}\sum _{i=1}^n{f}_i(x),\mathrm{\nabla }F(x)=\frac{1}{n}\sum _{i=1}^n\mathrm{\nabla }{f}_i(x),$$

where the gradient identity follows from Gradient of a finite sum is the finite sum of gradients and the sums use Finite sums and finite products, by recursion. Suppose each component gradient is L-Lipschitz for a common L>0. An SVRG epoch with snapshot \tilde x and inner length m>=1 is:

1. Compute the full gradient \nabla F(\tilde x), set x_0=\tilde x.
2. For t=0,...,m-1, draw I_t uniformly from {1,...,n}, independently of the past, and set $$v_t=\mathrm{\nabla }{f}_{I_t}(x_t)-\mathrm{\nabla }{f}_{I_t}(\tilde{x})+\mathrm{\nabla }F(\tilde{x}),x_{t+1}=x_t-\eta v_t$$ for a selected step size \eta>0.
3. Independently draw J uniformly from {0,...,m-1} and return x_J as the next snapshot.

The displayed procedure evaluates the snapshot component gradient at every inner update rather than caching those values. Coordinatewise at a fixed pre-update history, its correction has the one-sample scalar form of Control-variate estimators: the uniform index is the production draw, the integrand is the current component-gradient coordinate, the control is its snapshot coordinate, the known control mean is the corresponding full snapshot-gradient coordinate, and the coefficient is one; the conditional properties needed here are proved in local results on this page. Conditional-expectation notation inherits the The Axiom of Choice assumption from Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates.