SARAH Stochastic Recursive Gradient for Finite-Sum Optimization

SARAH Stochastic Recursive Gradient for Finite-Sum Optimization is a variance-reduced first-order stochastic optimization algorithm and practical adaptive variant (SARAH+) introduced by Nguyen, Liu, Scheinberg, and Takac (2017) for finite-sum minimization min_{w in R^d} P(w) = (1/n) sum_{i=1}^n f_i(w) with L-smooth component functions. At the start of each outer loop s, SARAH (Algorithm 1) computes the exact full gradient v_0 = grad P(w_0) and takes one gradient step w_1 = w_0 - eta v_0; in each inner iteration t = 1, ..., m-1, it samples i_t uniformly from [n] and updates the stochastic gradient estimate recursively via v_t = grad f_{i_t}(w_t) - grad f_{i_t}(w_{t-1}) + v_{t-1} followed by w_{t+1} = w_t - eta v_t. Unlike SVRG (which anchors its control variate to the static outer snapshot w_0 and is conditionally unbiased), SARAH's recursive estimator v_t is conditionally biased given F_t — E[v_t | F_t] = grad P(w_t) - grad P(w_{t-1}) + v_{t-1} != grad P(w_t) — while remaining unbiased in total expectation E[v_t] = E[grad P(w_t)] and requiring O(d) memory (no O(n d) gradient table as in SAG/SAGA). Lemma 2 proves the exact variance decomposition E[||grad P(w_t) - v_t||^2] = sum_{j=1}^t E[||v_j - v_{j-1}||^2] - sum_{j=1}^t E[||grad P(w_j) - grad P(w_{j-1})||^2], which guarantees that the step norm E[||v_t||^2] converges linearly to zero within a single inner loop under strong convexity (Theorems 1a-1b) and enables the self-tuning practical variant SARAH+ (Algorithm 2) that terminates the inner loop as soon as ||v_{t-1}||^2 <= gamma ||v_0||^2.