SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

1.2 Our Contributions

• SPIDER-SFO+ finds an (ε, O(ε^0.5))-approximate second-order stationary point at gradient cost Õ(min(n^1/2 ε^-2 + ε^-2.5, ε^-3)) under an additional Hessian-Lipschitz assumption.The method is based on a Negative-Curvature-Search method.Source: §1 · p. 3, §1.2 · p. 6

1.1 Related Works

• Unlike SARAH (Nguyen et al., 2017a,b), SPIDER hybrids its recursive estimator with stochastic normalized gradient descent and uses a small stepsize proportional to ε.Source: §1.1 · p. 5
• SNVRG independently obtained a first-order gradient complexity of Õ(min(n^1/2 ε^-2, ε^-3)); with third-order smoothness, it reaches second-order stationarity in Õ(ε^-3) gradient costs (Zhou et al., 2018b,a).Source: §1.1 · p. 5

1. Introduction

• The paper proposes SPIDER to reduce stochastic-oracle accesses and time complexity, with potential application to many stochastic estimation problems.Its estimator tracks deterministic quantities with reduced sampling costs.Source: §1 · p. 3, §1.2 · p. 6

1.2 Our Contributions

• SPIDER-SFO finds an ε-approximate first-order stationary point at gradient cost O(min(n^1/2 ε^-2, ε^-3)), with a matching lower bound in the finite-sum case.The paper says this rate was obtained independently of Zhou et al. (2018b,a).Source: §1.2 · p. 6
• O(d min(n^1/2 ε^-2, ε^-3)) individual function accesses are achieved by applying SPIDER to zeroth-order optimization.The paper presents this as the first use of variance reduction to reduce individual function accesses for non-convex problems to this complexity.Source: §1.2 · p. 6
• The paper gives a simpler stationary-point convergence analysis that can also be applied to SGD, SVRG, and SAGA (Defazio et al., 2014).Source: §1.2 · p. 6

Core estimator

• SPIDER starts from an initial estimate of Q(x̂0) and integrates unbiased estimates of successive differences to track Q(x̂k) along the sequence.The estimator is defined over the observed path x̂0:K.Source: §2 · p. 7

Error bounds

• Its error relative to Q(x̂K) is bounded both in expectation and with high probability.The high-probability proof uses an Azuma-Hoeffding-type concentration inequality.Source: §2 · pp. 7–8

Finite-sum estimator

• For finite-sum estimates, the construction samples indices with replacement and Lemma 1 bounds Vk's second-moment error under condition (2.7).The described update uses steps with norm at most ϵ1.Source: §2 · p. 8

Applications

• SPIDER can track stochastic gradients, function values, zeroth-order gradient estimates, and functionals of Hessian matrices.The paper's SPIDER-based algorithms use stochastic gradients and zeroth-order gradient estimates.Source: §2 · p. 8

3.1 Settings and Assumptions

• The analysis assumes finite initial function-value gap and averaged L-Lipschitz component gradients, with bounded stochastic-gradient variance online; second-order results additionally assume ρ-Lipschitz component Hessians.The paper defines approximate first- and second-order stationary points and states stronger assumptions for high-probability results.Source: §3.1 · pp. 9–10

3.2 First-Order Stationary Point

• SPIDER-SFO maintains a higher-accuracy gradient estimate under limited gradient budgets by applying SPIDER within a stochastic normalized-gradient-descent variant.The estimator maintains O(ε) error under the stated assumptions.Source: §3.2 · p. 11

Upper Bound for Finding First-Order Stationary Points, in Expectation

• O(ε^-3) stochastic-gradient complexity is achieved by SPIDER-SFO for finding a first-order stationary point in the online setting.The bound is stated under Assumption 1, treating Δ, L, and σ as constants.Source: Upper Bound for Finding First-Order… · p. 11
• O(n + n^1/2ε^-2) stochastic-gradient complexity is achieved by SPIDER-SFO for finding a first-order stationary point in the finite-sum setting.The bound is stated under Assumption 1, treating Δ, L, and σ as constants.Source: Upper Bound for Finding First-Order… · p. 12
• For n ≤ O(ε^-4), the finite-sum upper bound matches the stated Ω(n^1/2ε^-2) lower bound up to a constant factor, making SPIDER-SFO near-optimal in that regime.The paper notes that this lower-bound construction depends on n, not the online variance σ², and leaves an online lower bound for future work.Source: Upper Bound for Finding First-Order… · pp. 12–13
• ˜O(ε^-3) stochastic-gradient complexity gives a first-order stationary point with probability at least 1−p in the online setting under the stronger Assumption 2.The theorem also states a polylogarithmic factor in the high-probability complexity.Source: Upper Bound for Finding First-Order… · p. 13

3.3 Second-Order Stationary Point

• SPIDER-SFO+ splits a negative-curvature step into equal-length η mini-steps, maintaining the SPIDER gradient estimate; the update decreases the function value by Ω(δ^3) in expectation.The method fuses SPIDER-SFO with negative-curvature search for second-order stationary points.Source: §3.3 · p. 14
• For δ = O(ε^0.5), SPIDER-SFO+ has second-order gradient cost O(min(n^1/2 ε^-2 + ε^-2.5, ε^-3)); the online cost is O(ε^-3), versus O(ε^-3.5) for prior results.The second-order comparison assumes Assumptions 1 and 3; the cited prior-work comparison is reported under similar assumptions.Source: §3.3 · p. 16, §3.4 · p. 18
• Mini-steps in place of a single large Neon step let SPIDER-SFO+ maintain SPIDER estimates and improve the Neon coupling term by a factor of δ.The passage describes this modification as sharpening the coupling term.Source: §3.3 · p. 16
• SPIDER-SFO+ is faster than existing finite-sum methods only when n = Ω(ε^-1); for n = O(ε^-1), momentum-based methods can retain the state-of-the-art cost.The comparison notes Neon+FastCubic/CDHS as unoutperformed in this parameter regime.Source: §3.3 · p. 16, §3.4 · p. 18

3.4 Comparison with Concurrent Works

• The results indicate gradient cost O(min(ε^-3, n^(1/2)ε^-2)), superseding best-known convergence-rate results for stochastic optimization problem (1.2), and achieving the algorithmic lower bound in the finite-sum setting.Source: §3.4 · p. 17

4 SPIDER for Stochastic Zeroth-Order Method

• Because the true gradient is unavailable, the method uses two-point feedback and Gaussian convolution to estimate the gradient of a smoothed objective.The section identifies this as a typical stochastic zeroth-order approach.Source: §4 · p. 19
• O(min(d n^1/2 ε^-2, d ε^-3)) IZO calls improve on the prior O(d ε^-4) non-convex result.The paper attributes the reduction to its SPIDER technique.Source: §4 · p. 20
• SPIDER integrates two-point feedback to track ∇ˆf(x), and Lemma 3 establishes that vk is a high-accuracy estimator of ∥∇ˆf(xk)∥.Source: §4 · p. 20
• Theorem 8 gives an expectation result under Assumption 2, including (ii’), with smoothing and step-size parameters specified for the infinite case.Source: §4 · p. 20

5 Summary and Future Directions

• SPIDER’s first- and zeroth-order algorithms use reasonably simple update rules and achieve excellent convergence properties.The paper proposes the Spider method for non-convex optimization.Source: §5 · p. 21
• Whether the second-order gradient-cost upper bounds are optimal remains open under Lipschitz gradient and Lipschitz Hessian assumptions.The bounds are ˜O(ϵ−3) online and ˜O(n1/2ϵ−2) finite-sum when n ≥Ω(ϵ−1); the paper leaves their optimality or further improvement as future research.Source: §5 · p. 21

A Vector-Martingale Concentration Inequality

• For brevity, Ek[·] denotes E[· | x0:k], the expectation conditional on x0:k, for arbitrary k ≥0.Source: A Vector-Martingale Concentration… · p. 25
• The section applies Pinelis (1994) to obtain Proposition 2, an Azuma-Hoeffding-type concentration inequality.It also points to Kallenberg & Sztencel (1991) and Zhang (2005) for related results.Source: A Vector-Martingale Concentration… · p. 25
• Proposition 2 considers Rd-valued martingale differences with conditional mean zero and Euclidean norm bounded by B2.The sequence is with respect to Fk, with E[ϵk | Fk−1] = 0 for each k = 1, . . . , K.Source: A Vector-Martingale Concentration… · p. 25
• Proposition 2’s right-hand bound is dimension-free, a feature not obtained by a straightforward derivation of one-dimensional Azuma’s inequality.The section connects this feature to the Hilbert-space dimension reduction lemma of Kallenberg & Sztencel (1991).Source: A Vector-Martingale Concentration… · p. 25

A.1 Proof of Proposition 1

• The proof verifies from the definition of ˜Q in (2.1) that it is a martingale, then derives (2.2) using the L2 martingale property.Source: §A.1 · p. 25

A.2 Proof of Lemma 1

• For any k > 0, the proof invokes Proposition 1 with ˜Q = V.Source: §A.2 · p. 25
• The proof combines Eqs. (A.2) and (A.3), with S* sampled uniformly from [n] with replacement.Source: §A.2 · p. 26
• It telescopes the display for k′ = k − 1, …, 0 and applies the iterated law of expectation.Source: §A.2 · p. 26

B.1 Proof of Lemma 2

• For all k ≥ 0, the proof begins from Line 14 of Algorithm 1.Source: §B.1 · p. 26
• Applying Lemma 1 uses ϵ1 = ϵ/(Ln0), S2 = 2σ/(ϵn0), and K = k − k0 ≤ q = σn0/ϵ.Source: §B.1 · p. 26

B.2 Proof of Expectation Results for FSP

• Under Assumption 1, Lemma 4 sets k0 = ⌊k/q⌋·q as a preliminary for the proofs of Theorems 1 and 2.The supplied passage states the lemma’s setup but omits its displayed conclusion.Source: §B.2 · p. 27
• In each q iterations, the Theorem 1 cost analysis counts one access to S1 stochastic gradients and q accesses to S2 stochastic gradients.The proof takes full expectation in Lemma 4 and telescopes from k = 0 to K − 1.Source: §B.2 · pp. 28–29
• n + 8(LΔ)·n^1/2 ε^-2 + 2n^-1 is the gradient cost concluded by the analysis following the proof of Theorem 2.The proof first establishes Lemma 2, then derives (B.2), (5), and (B.15).Source: §B.2 · p. 29

B.3 Proof of High Probability Results for FSP

• If the algorithm has not stopped by K0 while HK0 holds, Lemma 7 ensures sufficient function-value descent at each iteration to rule out that case.The proof sets K0 = ⌊4L∆n0ϵ−2⌋+ 2 and uses the per-iteration descent bound from Lemma 7.Source: §B.3 · pp. 29, 33
• For each k through K0, the proof bounds failure probability by p/(K0 + 1), then obtains the horizon-wide event HK0 with probability at least 1-p.The proof tracks the randomness in maintaining the estimator and applies a union bound across the fixed horizon.Source: §B.3 · pp. 29–30
• With probability at least 1-p, the algorithm stops by K0 and returns an iterate with gradient norm at most 3ε̃.The proof combines the event HK0 with the stopping-time argument; when HK0 holds, the estimator norm at stopping is at most 2ε̃ and its error from the true gradient is at most ε·ε̃.Source: §B.3 · pp. 29, 33
• The proof also extends the same high-probability stopping and gradient guarantees to the setting addressed by Lemma 2.It invokes the same technique as Lemma 7 and Theorem 4.Source: §B.3 · p. 34

• The proof models randomness from SPIDER maintenance, periodic NC-search, and random-direction first-order updates, conditioning on the algorithm’s filtration.Source: §B.4 · p. 35
• With probability 1/2, Algorithm 2 terminates before KJ iterations and outputs an x_k satisfying (3.12).Source: §B.4 · p. 39
• Total stochastic-gradient complexity is bounded by combining SPIDER maintenance and NC-search costs; each NC-search costs tildeC L^2 δ^-2, with tildeC hiding a polylogarithmic factor of d.Source: §B.4 · pp. 39–40

B.5 Proof for SZO

• Under Theorem 8’s setting and Assumption 2 (including (ii’)), the conditional expected estimator error is at most ε^2 at k0 = floor(k/q)·q.The bound is E_{k0}||v_k − ∇hat f(x_k)|| ≤ ε^2, where k0 = floor(k/q)·q.Source: §B.5 · p. 43
• The Lemma 11 proof starts from Lemma 10 at k = k0 and, for later iterations, invokes Lemma 3 and Proposition 1 for online and finite-sum cases.Source: §B.5 · p. 43
• Theorem 8’s proof takes full expectation on Lemma 11, then applies Lemma 4, (B.13), (B.14), and Jensen’s inequality.Source: §B.5 · p. 44

B.6 Proof of Theorem 3 for Lower Bound

• The proof extends Carmon et al. (2017b)’s hard instance using random orthogonal matrices and component functions with Lipschitz continuous gradients.The stated gradient Lipschitz constant l is independent of K and d.Source: §B.6 · pp. 45–46
• Each component function f_i can be solved only after K calls to that component.This per-component requirement contributes to the lower-bound argument for algorithms handling n individual functions.Source: §B.6 · pp. 46–47
• With sufficiently large d, each iterate recovers at most one coordinate with probability 1−p.The proof establishes this for the constructed instance at every iteration through T.Source: §B.6 · p. 47