Finite-sum SAGA

Let n,d>=1, let f_1,...,f_n:R^d->R be continuously differentiable, and set F(x)=n^{-1}sum_i f_i(x), with \nabla F(x)=n^{-1}sum_i\nabla f_i(x) by Gradient of a finite sum is the finite sum of gradients and Finite sums and finite products, by recursion. Given a deterministic initial point x_0 and step size \eta>0, initialize a table \alpha_i^0=\nabla f_i(x_0) and its mean \bar\alpha_0=n^{-1}sum_i\alpha_i^0. At iteration k:

1. Draw I_k uniformly from {1,...,n}, independently of the history \mathcal F_k.
2. Evaluate $g_k=\mathrm{\nabla }{f}_{I_k}(x_k)$ once. Using the old table, form $$v_k=g_k-{\alpha }_{I_k}^k+{\bar{\alpha }}_k,x_{k+1}=x_k-\eta v_k\mathrm{.}$$
3. Replace only the sampled table entry, using the pre-update point: $${\alpha }_{I_k}^{k+1}=g_k,{\alpha }_i^{k+1}={\alpha }_i^k(i\mathrm{\ne }{I}_k),$$ and set $${\bar{\alpha }}_{k+1}={\bar{\alpha }}_k+\frac{1}{n}(g_k-{\alpha }_{I_k}^k)\mathrm{.}$$

The stored state is the current iterate, the component-gradient table, and its running mean. For each fixed history, each coordinate of the correction is a scalar control-variate estimator in Control-variate estimators: take one uniform sample $I$ from $\{1,\dots ,n\}$, integrand $i\mapsto (\mathrm{\nabla }{f}_i(x_k){)}_j$, control $i\mapsto ({\alpha }_i^k{)}_j$, known control mean $({\bar{\alpha }}_k{)}_j$, and coefficient $1$. The conditional claims are proved locally. The conditional-expectation convention inherits The Axiom of Choice from Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates.