← All setups

Variance-Only Second-Order Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Variance-Only Second-Order Stationarity

We consider minimizing a possibly nonconvex function f:E→R on a positive-dimensional finite-dimensional real inner product space E. The function is twice continuously differentiable, with L-Lipschitz gradient and ρ-Lipschitz Hessian, where L,ρ>0. A given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with variance at most σ2, where σ≥0. For ε>0 and δ∈(0,1) satisfying ρε≤L2, the goal is a measurable output x¯∈E satisfying ∥∇f(x¯)∥≤ε and ⟨v,∇2f(x¯)v⟩≥−ρε∥v∥2 for every v∈E, with probability at least 1−δ.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The Hessian ∇2f(x):E→E is the derivative of the gradient. The algorithm receives E, the measurable sample space Ω, L, ρ, σ, Δ, ε, δ, and x0.

Our assumptions:

Assumption 1 (Smoothness). The function f belongs to C2(E;R), and, for every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

Assumption 2 (Initial objective gap). The given starting point satisfies f(x0)−f(x)≤Δ,x∈E.

Assumption 3 (Stochastic gradient oracle). There are a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. The samples (ξk)k≥0 are measurable, mutually independent random variables with common law ν under a joint probability law Q on ΩN. At its kth query x∈E, the oracle returns g(x,ξk).

For every fixed x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥2 is integrable under ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. Any algorithm randomness is independent of the sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the algorithm must return a measurable output x¯ such that P(∥∇f(x¯)∥≤ε,⟨v,∇2f(x¯)v⟩≥−ρε∥v∥2for every v∈E)≥1−δ, where P is the joint law of the algorithm randomness and the sample sequence with law Q.

Results

On a real inner-product space of dimension d≥1, f∈C2 has L-Lipschitz gradient, ρ-Lipschitz Hessian, and f(x0)−inff≤Δ. Here L,ρ,ε>0, σ,Δ≥0, 0<δ<1, and ρε≤L2. Fresh IID samples have law p; the jointly measurable oracle satisfies ∫g(x,z)dp(z)=∇f(x) and ∫∥g(x,z)−∇f(x)∥2dp(z)≤σ2. The target is P{∥∇f(x)∥≤ε, ∇2f(x)⪰−ρεI}≥1−δ.

Sufficient oracle budgets for VarianceOnlySecondOrder.
Result Oracle complexity Novelty Limitations
(1) GatedPerturbedEscapeSosp (Ours) (⋆⋆⋆) (review) O(ℓ2D8[A(1+σ2/ε2)+dσ2/ε2+dσ2ρΔ/ε7/2]) gradient calls, including batches and gates. Stopped-point target; tuning uses L,ρ,σ,Δ,ε,δ,d.
(2) PSGD (Jin et al. 2019), Thm. 16 and Remark 14; norm-sub-Gaussian noise, without sample-gradient smoothness O([1+LΔε2(1+dσ2ε2)]ι9) gradient calls. Visits the target with probability 1−δ; random-iterate output has constant success probability. (1): on the norm-sub-Gaussian overlap, Δ≥ε3/2/ρ, σ≥ε: min{d,L/γ} speedup up to polylogs. For d=L/γ, O(dLΔσ2/ε4)→O(LΔσ2/ε4) up to polylogs. Scope: finite variance. Output: stopped-point success 1−δ. (1): certification floor L/γ+dσ2/ε2 can cost more when Δ≪ε3/2/ρ.
(3) SGD (Vlaski and Sayed 2019), Thms. 1–3; relative fourth-moment control, covariance regularity, saddle-noise lower bound Step-size-dependent guarantee; no explicit (ε,γ) oracle budget. Rates are not comparable. (1): finite variance suffices; no fourth-moment control, covariance regularity, or saddle-noise lower bound. (1): injects perturbations; (3) needs none.
(4) (Arjevani et al. 2020), Thm. 4; stochastic gradients and HVPs with almost-sure Hessian-noise bound O(Δσσ¯2ε3+ΔLε2+Δρ(L+σ¯2)2ε5/2log2edLγ) total gradient/HVP calls; success ≥5/8. Requires ε≤min{σ,ΔL}, γ≤σ¯2. Different-oracle rates are not comparable. (1): gradients only; no almost-sure Hessian-noise bound.

Abbr: γ=ρε; A=L/γ+LΔ/ε2; D=1+log⁡d; ℓ=1+log⁡(AD/δ); ι=1+log+(dLΔ(1+dσ2/ε2)/(ρεδ)); log+⁡t=log⁡max{1,t}. HVP: Hessian-vector product; σ¯2 bounds ∥∇2f^−∇2f∥op almost surely. Polylogs denotes logarithmic factors in the displayed parameters.

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. 2020. “Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations.” Proceedings of Thirty Third Conference on Learning Theory, Proceedings of machine learning research, vol. 125: 242–99. https://doi.org/10.48550/arXiv.2006.13476.
Jin, Chi, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. 2019. On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points. https://doi.org/10.48550/arXiv.1902.04811.
Vlaski, Stefan, and Ali H. Sayed. 2019. Second-Order Guarantees of Stochastic Gradient Descent in Non-Convex Optimization. https://doi.org/10.48550/arXiv.1908.07023.

Lean setup