← All setups

Gradient-Only Third-Order Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Gradient-Only Third-Order Nonconvex Optimization

We consider minimizing a possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The function is three times continuously differentiable, with L1-Lipschitz gradient and L3-Lipschitz third derivative in the induced operator norm, where L1,L3>0. A given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ>0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈E satisfying ∥∇f(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm, including for multilinear forms. In particular, ∇3f(x) is a trilinear form on E. The algorithm receives E, x0, L1, L3, Δ, and ε.

Our assumptions:

Assumption 1 (Smoothness). The function f belongs to C3(E;R), and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L1∥x−y∥,x,y∈E.

Assumption 2 (Third-derivative regularity). The third derivative satisfies ∥∇3f(x)−∇3f(y)∥op≤L3∥x−y∥,x,y∈E.

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

Queries may be made at any point of E. After the allotted gradient calls, the output must satisfy the first-order stationarity criterion ∥∇f(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, f∈C3 has L1-Lipschitz gradient and L3-Lipschitz third derivative in operator norm, with f(x0)−inff≤Δ and L1,L3,Δ,ε>0. The setup provides exact gradients and requires ∥∇f(x^)∥≤ε almost surely; the constructed method is deterministic.

Gradient-only nonconvex stationarity under third-order smoothness: GradientOnlyThirdOrderNonconvex.
Result Oracle complexity Novelty Limitations
(1) GradientOnlyThirdOrderAcceleration (Ours) (⋆⋆⋆) (review) O((1+ΔL31/3ε−4/3)⋅[1+1+q⋅log(1+(L1+L31/3ε2/3)Δε2)]) gradient calls, all positive parameters.
(2) (Carmon et al. 2017, Theorem 2) O(ΔL11/2L31/6ε−5/3ℓ) total value and gradient calls. Requires ε4/3≤ΔL31/3 and q≥8. (1): Matches the rate on this range using gradients alone; removes all function-value calls. (1) has a much larger leading constant and needs Δ in addition.
(3) Restarted AGD (Li and Lin 2023, Theorem 1) Derived bound: O(ΔL15/8L31/8ε−7/4) gradient calls, using ρ=2L1L3 and rescaled accuracy. Displayed on ε4/3≤ΔL31/3, q≥8. (1): Rate gain q1/8/ℓ when q≫ℓ8. For L1=L3=Δ=1, O(ε−5/3ℓ) instead of O(ε−7/4) as ε→0. (1) needs Lipschitz third derivatives and L3,Δ; (3) needs only Lipschitz Hessians. Cost ratio ℓ/q1/8 favors (3) when q≪ℓ8 within the displayed range.
(4) (Zhou et al. 2026, Theorem 1.3; precise Theorem 5.2, p=3) O(d2+d4/3ε−4/3) gradient calls. Normalized comparison: L1=L3=Δ=1, 0<ε≤1; (4) assumes a known global lower bound. (1): Dimension-free O(ε−5/3ℓ) in this normalization; smaller total bound when d≫ε−1/4ℓ3/4. (1) is slower for fixed small d as ε→0: O(ε−5/3ℓ) versus O(ε−4/3).

Abbr: d=dim⁡E; q=L1/(L31/3ε2/3); ℓ=log⁡(1+L1Δ/ε2); ρ is a Lipschitz constant for ∇2f; AGD denotes accelerated gradient descent. Complexity counts every primitive oracle call; O hides universal factors.

Carmon, Yair, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2017. “‘Convex Until Proven Guilty’: Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions.” Proceedings of the 34th International Conference on Machine Learning, Proceedings of machine learning research, vol. 70: 654–63. https://proceedings.mlr.press/v70/carmon17a.html.
Li, Huan, and Zhouchen Lin. 2023. “Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ϵ−7/4) Complexity.” Journal of Machine Learning Research 24 (157): 1–37. https://www.jmlr.org/papers/v24/22-0522.html.
Zhou, Huanjian, Masashi Sugiyama, and Taiji Suzuki. 2026. Finding Stationary Points Under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds. https://doi.org/10.48550/arXiv.2610.02791.

Lean setup