SPIDER Stochastic Path-Integrated Differential Estimator for Non-Convex Optimization

SPIDER Stochastic Path-Integrated Differential Estimator for Non-Convex Optimization is a martingale variance-reduction tracking framework and family of stochastic first-order (SPIDER-SFO, SPIDER-SFO+) and zeroth-order (SPIDER-SZO) non-convex optimization algorithms introduced by Fang, Li, Lin, and Zhang (2018) for minimizing smooth possibly non-convex objectives f(x) = E[F(x; zeta)] or f(x) = (1/n) sum_{i=1}^n f_i(x) with averaged L-Lipschitz gradients E||grad f_i(x) - grad f_i(y)||^2 <= L^2 ||x - y||^2. To dynamically track a deterministic quantity Q(x^k) along an iterate sequence x^{0:K}, SPIDER integrates unbiased differential increments xi_k(x^{0:k}) as Q_tilde(x^{0:K}) = Q_tilde(x^0) + sum_{k=1}^K xi_k(x^{0:k}), achieving the exact L^2-martingale variance identity E||Q_tilde(x^{0:K}) - Q(x^K)||^2 = E||Q_tilde(x^0) - Q(x^0)||^2 + sum_{k=1}^K E||xi_k(x^{0:k}) - (Q(x^k) - Q(x^{k-1}))||^2 (Proposition 1) and error bound E||V^k - B(x^k)||^2 <= k L_B^2 epsilon_1^2 / S_* + E||V^0 - B(x^0)||^2 whenever ||x^k - x^{k-1}|| <= epsilon_1 (Lemma 1). SPIDER-SFO (Algorithm 1) hybridizes this path-integrated gradient estimator v^k = grad f_{S_2}(x^k) - grad f_{S_2}(x^{k-1}) + v^{k-1} with Normalized Gradient Descent (NGD), updating x^{k+1} = x^k - eta^k v^k with stepsize eta^k = min(epsilon/(L n_0 ||v^k||), 1/(2 L n_0)) so that the step length is strictly capped at ||x^{k+1} - x^k|| <= epsilon/(L n_0), maintaining E[||v^k - grad f(x^k)||^2] <= epsilon^2 across epochs of length q (Lemma 2) and finding an epsilon-first-order stationary point in O(min(n + n^{1/2} epsilon^{-2}, epsilon^{-3})) stochastic gradient evaluations (Theorems 1-2), matching the Omega(L Delta n^{1/2} epsilon^{-2}) algorithmic lower bound (Theorem 3).