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

Cong Fang; Chris Junchi Li; Zhouchen Lin; Tong Zhang

Source-linked AI summary

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

Cong Fang, Chris Junchi Li, Zhouchen Lin, Tong Zhang

arXiv:1807.01695v2Jul 4, 2018math.OCcs.LGstat.ML

TL;DR

The paper addresses the cost of finding stationary points in non-convex stochastic optimization. It introduces SPIDER and combines it with normalized gradient descent and negative-curvature search, obtaining sharp first- and second-order rates and reduced zeroth-order function-access costs. In the finite-sum setting, SPIDER-SFO nearly matches an algorithmic lower bound for first-order stationarity.

Problem
Finding approximate first- and second-order stationary points in non-convex stochastic optimization requires reducing stochastic-gradient cost while avoiding saddle points and local maximizers.
Method
The paper introduces SPIDER for tracking deterministic quantities and combines it with normalized gradient descent, negative-curvature search, and zeroth-order variance reduction.
Results
SPIDER-SFO achieves O(min(n^1/2 ε^-2, ε^-3)) first-order gradient cost, SPIDER-SFO+ achieves Õ(min(n^1/2 ε^-2 + ε^-2.5, ε^-3)) second-order cost, and zeroth-order access costs are O(min(dn^1/2 ε^-2, dε^-3)).
Takeaways & Limitations
In the finite-sum case, SPIDER-SFO’s first-order gradient-cost upper bound matches the algorithmic lower bound in at least one case.
Takeaways & Limitations
For finite sums with n ≤ ε^-1, Spider-SFO+ is slower than existing accelerated methods, while its advantage appears only when n = Ω(ε^-1).

Abstract

from arXiv · show

In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order methods. For stochastic first-order method, combining SPIDER with normalized gradient descent, we propose two new algorithms, namely SPIDER-SFO and SPIDER-SFO\textsuperscript{+}, that solve non-convex stochastic optimization problems using stochastic gradients only. We provide sharp error-bound results on their convergence rates. In special, we prove that the SPIDER-SFO and SPIDER-SFO\textsuperscript{+} algorithms achieve a record-breaking gradient computation cost of $\mathcal{O}\left( \min( n^{1/2} ε^{-2}, ε^{-3} ) \right)$ for finding an $ε$-approximate first-order and $\tilde{\mathcal{O}}\left( \min( n^{1/2} ε^{-2}+ε^{-2.5}, ε^{-3} ) \right)$ for finding an $(ε, \mathcal{O}(ε^{0.5}))$-approximate second-order stationary point, respectively. In addition, we prove that SPIDER-SFO nearly matches the algorithmic lower bound for finding approximate first-order stationary points under the gradient Lipschitz assumption in the finite-sum setting. For stochastic zeroth-order method, we prove a cost of $\mathcal{O}( d \min( n^{1/2} ε^{-2}, ε^{-3}) )$ which outperforms all existing results.

1 Introduction

The paper introduces SPIDER, a stochastic estimator for tracking deterministic quantities with lower sampling cost, and applies it to non-convex first-order, second-order, and zeroth-order optimization.

First-order optimization: SPIDER-SFO combines SPIDER with normalized gradient descent to find approximate first-order stationary points using stochastic gradients.Normalized gradient descent uses steps inversely proportional to the full-gradient norm, while SPIDER estimates the gradient and its norm.
Second-order optimization: SPIDER-SFO+ uses negative-curvature search to find approximate second-order stationary points at Õ(min(n^1/2 ε^-2 + ε^-2.5, ε^-3)) gradient cost.This result uses an additional Hessian-Lipschitz assumption.
SPIDER technique: SPIDER tracks deterministic quantities using stochastic path-integrated differential estimates, reducing excessive stochastic-oracle access.The technique is presented as broadly applicable to stochastic estimation problems.
First-order optimization: O(min(n^1/2 ε^-2, ε^-3)) gradient cost is achieved for first-order stationarity, with matching upper and lower bounds in the finite-sum setting.The lower-bound match applies for at least one case under the paper’s stated smoothness setting.
Zeroth-order optimization: O(min(dn^1/2 ε^-2, dε^-3)) individual function accesses are obtained for non-convex zeroth-order optimization.The paper applies SPIDER to reduce function accesses through variance reduction.
Analysis: The paper also develops a simpler convergence analysis for proving convergence to a stationary point.This is listed as a separate contribution alongside the optimization applications.

2 Stochastic Path-Integrated Differential Estimator: Core Idea

SPIDER tracks a deterministic quantity along an observed sequence by integrating unbiased stochastic estimates of successive changes. Its error can be bounded in expectation and with high probability, while applications use it to track stochastic and zeroth-order gradients and related quantities with reduced oracle access.

Core estimator: The technique is designed to avoid excessive stochastic-oracle access and reduce computational complexity.The paper presents this reduction as independently interesting and potentially applicable to many stochastic estimation problems.
Core estimator: SPIDER integrates unbiased stochastic estimates of Q(x_k) − Q(x_{k−1}) from an initial estimate to track Q(x_k) along a sequence.The tracked quantity is an arbitrary deterministic vector quantity, and the estimator is defined over the observed path.
Error control: Its error bound controls the deviation between the path-integrated estimator and the target quantity in expectation and with high probability.The high-probability statement is obtained using an Azuma-Hoeffding-type concentration inequality.
Estimator construction: The construction uses stochastic estimates B_i(x) and subsampled estimators formed from samples drawn with replacement.The sequence is conditioned on the observed iterates, and the subsample size determines the estimator used at each step.
Applications: SPIDER-based algorithms apply the framework to stochastic gradients, zeroth-order gradient estimates, function values, and functionals of Hessian matrices.In the proposed algorithms, B_i is instantiated as either a stochastic gradient or a zeroth-order estimate gradient.

3 SPIDER for Stochastic First-Order Method

SPIDER is applied to first- and second-order stationarity in non-convex stochastic optimization, using gradient estimates maintained at low error under limited gradient budgets. The resulting bounds include near-optimal finite-sum first-order complexity and improved second-order complexity under Hessian-Lipschitz assumptions.

First-order method: SPIDER-SFO applies SPIDER to estimate gradients while maintaining an O(ϵ) estimation error for first-order stationarity.The method combines SPIDER gradient tracking with normalized-gradient updates under the stated smoothness assumptions.
First-order method: O(n + n^1/2ϵ^-2) stochastic gradients suffice in the finite-sum setting when treating ∆, L, and σ as constants.Theorem 2 uses a full gradient in Line 3 and permits n0 ∈ [1, n^1/2].
First-order method: The finite-sum lower bound requires at least Ω(n^1/2ϵ^-2) stochastic gradient accesses for an algorithm finding ∥∇f(˜x)∥ ≤ ϵ.The construction generalizes a deterministic counterexample to the finite-sum setting.
Second-order method: ˜O(ϵ^-3) gradient cost finds an (ϵ, δ)-approximate second-order stationary point online when δ = O(ϵ^0.5).More generally, the online bound is ˜O(ϵ^-3 + δ^-2ϵ^-2 + δ^-5) under Hessian-Lipschitz assumptions.
First-order method: O(min(ϵ^-3, n^1/2ϵ^-2)) gradient cost supersedes previous stochastic-optimization convergence results and reaches the finite-sum algorithmic lower bound.The near-optimality claim is established for finding approximate first-order stationary points in the finite-sum case.

4 SPIDER for Stochastic Zeroth-Order Method

This section applies SPIDER to stochastic zeroth-order optimization, using two-point feedback and integrated estimators to reduce oracle complexity for finding stationary points.

Oracle model: The method uses an Incremental Zeroth-Order Oracle that returns fi(x) for a sampled function index and point.The stochastic zeroth-order algorithms therefore access function values rather than true gradients.
Estimator: Gaussian two-point feedback estimates the gradient of a smoothed objective, whose properties support the zeroth-order convergence analysis.The analysis assumes Lipschitz-continuous gradients and uses u sampled from a standard Gaussian distribution.
Complexity: O(d min(n^1/2 ε^-2, ε^-3)) IZO calls improve the best known non-convex zeroth-order result O(dε^-4).The improvement is attributed to applying SPIDER directly to the incremental zeroth-order oracle.
Estimator: Algorithm 3 integrates two-point feedback across iterations to track the smoothed gradient, while vk estimates its norm accurately.The estimator is constructed using sampled function indices and Gaussian directions.
Convergence: Choosing a smaller smoothing parameter makes the smoothed gradient approximate the true gradient and supports sufficient descent per iteration.The resulting expectation guarantee is stated in Theorem 8 for the infinite case under the listed assumptions.

5 Summary and Future Directions

The paper concludes that SPIDER provides strong first- and zeroth-order convergence results while leaving the optimality of its second-order complexity unresolved.

Future directions: The optimality of the second-order gradient-cost upper bounds remains open under both Lipschitz-gradient and Lipschitz-Hessian assumptions.The unresolved cases include the online rate Õ(ε^-3) and the finite-sum rate Õ(n^1/2ε^-2) when n ≥ Ω(ε^-1).
Summary: SPIDER-type first- and zeroth-order algorithms use simple update rules and achieve strong convergence properties for non-convex optimization.The conclusion presents these properties as the paper’s central contribution.
Analysis: The technical analysis uses conditional expectations, vector-valued martingale concentration, and a dimension-free bound for Euclidean norms.The cited concentration result is an Azuma-Hoeffding-type inequality for vector-valued martingale differences.

A.1 Proof of Proposition 1

The proof establishes the auxiliary proposition by verifying that the constructed quantity is a martingale and invoking the L2 martingale property.

Martingale argument: The constructed quantity ˜Q is shown to be a martingale directly from its definition.This verification supplies the structural premise for the proposition.
Martingale argument: The proposition then follows from the L2 martingale property.The proof uses this property rather than deriving the result from a separate concentration argument.

A.2 Proof of Lemma 1

The proof of Lemma 1 starts from Proposition 1, combines bounds for randomly sampled indices, and concludes through telescoping and iterated expectation.

Proof setup: For k > 0, the proof applies Proposition 1 with ˜Q = V.This connects the lemma’s quantity to the previously established proposition.
Sampling: The proof combines inequalities for samples drawn from [n] with replacement.The sampled indices are incorporated into the bound before the final aggregation.
Aggregation: Telescoping over k′ = k − 1, …, 0 and using iterated expectation completes the argument.The telescoping step aggregates the preceding per-iteration relations.

B Deferred Proofs

The deferred proof begins by invoking Algorithm 1 and selecting parameters for Lemma 1.

Algorithm 1 supplies the iteration relation used in the deferred proof.
Lemma 1 is applied with ϵ1 = ϵ/(Ln0), S2 = 2σ/(ϵn0), and K − k0 ≤ σn0/ϵ.
The selected parameters connect the iteration range to the stochastic-gradient batch size S2.

B.2 Proof of Expectation Results for FSP

This section establishes expectation results through lemmas, Lipschitz-gradient assumptions, telescoping arguments, and gradient-cost accounting.

The proof develops Theorems 1 and 2 from a sequence of lemmas under the stated assumptions.
L-Lipschitz continuity of the gradient is used as a foundational assumption in the analysis.
The analysis uses Jensen’s inequality and the triangle inequality to control intermediate quantities.
Expectation bounds are obtained by taking full expectations and telescoping results across iterations.
Theorem 1’s gradient cost is computed from one batch of S1 stochastic gradients and q batches of S2 stochastic gradients per q iterations.
Theorem 2’s analysis concludes a gradient cost of n + 8(L∆) · n^1/2ϵ^-2 + 2n^-1.

B.3 Proof of High Probability Results for FSP

The high-probability proof analyzes a stopping-time algorithm, controls SPIDER estimation errors, and derives approximate stationarity with probability at least 1 − p.

Algorithm 1 stops when the estimator norm falls below 2ϵ, with K defined as a random stopping time.
The proof defines a high-probability event HK0 and establishes that it occurs with probability at least 1 − p.
The proof controls estimator deviations across iterations using filtration-based randomness and component-function sampling.
Before stopping, normalized updates have fixed length η = ϵ/(Ln0).
On HK0, the analysis bounds the estimator and gradient at termination by ∥vK∥ ≤ 2˜ϵ and ∥∇f(xK)∥ ≤ 3˜ϵ.
The high-probability argument combines descent over iterations with gradient-cost analysis inherited from Theorem 2.

B.4 Proof of Theorem 6 for SSP

The SSP proof combines SPIDER maintenance with Neon-based negative-curvature search and analyzes first- and second-order updates through filtration and event arguments.

The proof restates Neon2’s NC-search result under the paper’s assumptions before analyzing Theorem 6.
Successful NC-search identifies a unit direction w satisfying w^T∇²f(x0)w ≤ δ/2 when w is not ⊥.
Algorithm 2 draws randomness from SPIDER maintenance, NC-search, and random directions for first-order updates.
The proof uses nested events to track whether the algorithm has stopped and whether estimator and NC-search guarantees hold.
With probability at least 1 − 1/(16(K0 + 1)), estimator-control events hold uniformly through K0 iterations.
With probability 1/2, the algorithm terminates before KJ iterations and outputs an xk satisfying (3.12).
Total stochastic-gradient complexity includes both SPIDER maintenance and NC-search costs.

B.5 Proof for SZO

Under Assumption 2, the proof establishes an ε^2 bound for the estimator error at checkpoint-aligned iterations and derives Theorem 8 by taking expectations and applying auxiliary lemmas. The argument separately considers online and finite-sum cases and uses Lipschitz-gradient assumptions.

Assumptions and bounds: The proof invokes L-Lipschitz continuous gradients for the component functions and moment bounds involving the dimension d.
Estimator-error bound: ε^2 bounds the expected estimator error at checkpoint-aligned iterations under Assumption 2, including condition (ii’).The bound is stated for k0 = ⌊k/q⌋·q.
Estimator-error bound: The proof initializes the result from Lemma 10 when k equals the checkpoint k0, then extends it to later iterations using Lemma 3.
Theorem 8: The analysis treats online and finite-sum settings separately through Proposition 1.
Theorem 8: Theorem 8 follows by taking full expectation of Lemma 11 and combining Lemma 4 with intermediate bounds and Jensen’s inequality.

B.6 Proof of Theorem 3 for Lower Bound

The lower-bound proof extends a hard-instance construction to account for the number of individual functions n. It combines orthogonal randomization and zero-chain structure to show that algorithms recover limited information per iteration and require repeated calls to resolve component functions.

Hard-instance construction: The construction extends Carmon et al. (2017b)’s hard instance to incorporate the number n of individual functions.
Information-recovery limitation: The zero-chain structure limits deterministic algorithms to recovering one dimension per iteration, with the randomized construction extending this one-coordinate recovery property with probability 1 − p.
Hard-instance properties: The component function ˜fK,BK has a constant l-Lipschitz continuous gradient independent of K and d.
Hard-instance construction: The hard instance uses randomly chosen orthogonal matrices and parameters K and b constrained by n, Δ, L, and ε.
Query complexity: K calls to an individual function are required before that function can be solved, creating a lower-bound mechanism based on repeated component queries.
Probability argument: The proof establishes the recovery limitation through a hard event, projection arguments, rotational symmetry, and a union-bound probability guarantee.