SNVRG (Stochastic Nested Variance Reduction) for Non-Convex Optimization

Because each nested level difference nabla f_{B_l}(x_tilde^{(l)}) - nabla f_{B_l}(x_tilde^{(l-1)}) is conditionally unbiased for nabla F(x_tilde^{(l)}) - nabla F(x_tilde^{(l-1)}) given x_tilde^{(l)} and x_tilde^{(l-1)}, the top-level variance decomposes across the K levels as E||g^{(K)} - nabla F(x_j)||_2^2 <= E||g^{(0)} - nabla F(x_tilde^{(0)})||_2^2 + L^2 * sum_{l=1}^K B_l^{-1} * E||x_tilde^{(l)} - x_tilde^{(l-1)}||_2^2 (Lemma 17); setting s_l = 2, B_l = 68 * 4^l * K (with K = floor(1/2 * log_2 B_0)), and constant step size eta = 1/(6L) bounds the per-step trajectory drift so that One-Epoch-SNVRG (Algorithm 1) achieves E[F(x_S) - F(x_0)] <= -(S/(32*L)) * E||nabla F(x)||_2^2 + (68*S/(32*L)) * I(B_0 < n) * sigma^2 / B_0 using at most 3 * B_0 * (1 + K) stochastic gradient evaluations per epoch of length S = 2^{K+1} (Lemma 4).

For finite-sum and online L-smooth non-convex objectives (Algorithm 2), setting B_0 = min{68*sigma^2/varepsilon^2, n} and S = (B_0/2)^{1/2} yields E||nabla F(x_out)||_2 <= varepsilon in O((Delta_F*L*varepsilon^{-2} * min{sigma/varepsilon, n^{1/2}} + min{sigma^2/varepsilon^2, n}) * log(2 + min{sigma^2/varepsilon^2, n})) = O_tilde(min(n + n^{1/2}*varepsilon^{-2}, varepsilon^{-3})) stochastic gradient evaluations, simultaneously outperforming GD O(n*varepsilon^{-2}), SGD O(varepsilon^{-4}), and SVRG O(min(n + n^{2/3}*varepsilon^{-2}, varepsilon^{-10/3})) with a single parameter-free constant step size eta = 1/(6L) (Theorem 5, Corollary 6, Table 1); furthermore, if F satisfies the local mu-Polyak-Lojasiewicz condition 1/2 * ||nabla F(x)||_2^2 >= mu * (F(x) - F(x^*)), SNVRG (Algorithm 3) achieves F(x_out) - F(x^*) <= varepsilon in O_tilde(min{n + kappa*n^{1/2}, kappa*sigma*varepsilon^{-1/2} + sigma^2*varepsilon^{-1}} * log(1/varepsilon)) where kappa = L/mu, beating SVRG's O((n + kappa*n^{2/3})*log(1/varepsilon)) when kappa >= n^{1/2} without knowing mu inside One-Epoch-SNVRG (Theorem 9, Corollary 10).

Coupling One-Epoch-SNVRG with Neon2 negative-curvature extraction in SNVRG+Neon2 (Algorithm 4.1 / Algorithm 4.2) finds an (varepsilon_g, varepsilon_H)-second-order stationary point (||nabla F(x)||_2 <= varepsilon_g, lambda_min(nabla^2 F(x)) >= -varepsilon_H) in O_tilde(varepsilon_g^{-3} + varepsilon_H^{-5} + varepsilon_g^{-2}*varepsilon_H^{-3}) online and O_tilde(n*varepsilon_H^{-1.5} + n^{3/4}*varepsilon_H^{-3.5} + n^{1/2}*varepsilon_g^{-2} + n + varepsilon_H^{-5}) finite-sum stochastic gradient evaluations (Theorems 13 and 15, Corollaries 14 and 16); applied to non-convex robust linear regression and multi-class neural networks on CIFAR-10/MNIST/SVHN and to variance-reduced Glauber dynamics for Ising models, SNVRG converges faster than SGD, SVRG, and SCSG.