← All setups

Stationarity with Gradient-Dependent Third Derivatives

Descriptions may be stale. Consult the linked Lean sources.

Stationarity with Gradient-Dependent Third Derivatives

We consider a possibly nonconvex objective f:E→R on a finite-dimensional real inner product space E. The function is three times continuously differentiable, with its third derivative bounded by L0+L1∥∇f(x)∥ at each x∈E, where L0>0 and L1≥0. A given starting point x0∈E has objective gap at most Δ>0 above the infimum and gradient norm at most G0≥0. Two exact oracles return the gradient and Hessian. For ε>0, the goal is an output x¯∈E satisfying ∥∇f(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and derivative norms ∥⋅∥op are the induced operator norms. The algorithm receives E, x0, L0, L1, Δ, G0, ε, and an integer m≥1.

Our assumptions:

Assumption 1 (Third-derivative bound). The function f belongs to C3(E;R) and satisfies ∥∇3f(x)∥op≤L0+L1∥∇f(x)∥,x∈E. Here ∇3f(x) denotes the trilinear third derivative of f, equivalently the second derivative of its gradient under the inner product identification.

Assumption 2 (Initial bounds). The given point x0 satisfies f(x0)−f(x)≤Δfor every x∈E,∥∇f(x0)∥≤G0.

Queries to either oracle may be made at any point of E. The gradient oracle returns ∇f(x) at x. The Hessian oracle returns ∇2f(x) at x, as a linear operator from E to E. Gradient and Hessian calls are counted separately.

After the allotted calls to each oracle, the output must satisfy ∥∇f(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, f∈C3 satisfies ∥∇3f(x)∥≤L0+L1∥∇f(x)∥ and f(x0)−f(x)≤Δ for every x, with ∥∇f(x0)∥≤G0. Here L0,Δ,ε>0, L1,G0≥0, and m∈N, m≥1. Exact gradient and Hessian oracles are available. The target is ∥∇f(xout)∥≤ε; (1) attains it deterministically.

Comparison for GradientDependentHessian.
Result Oracle complexity Novelty Limitations
(1) EnergyHessianReuse (Ours) (⋆⋆⋆) (review) O(mA+mℓ)
(2) Parameter-free CRN (Fang et al. 2026), Cor. 1 O(m[A+J+Δ(L02δ3+L1δ)])
Includes backtracking trials; δ=∞ gives the shared target.
(1): m instead of m in the accuracy cost; factor-m saving when A≥mℓ. For m=104, L0=Δ=1, L1G0≤1, ε≤10−2: O(100A+104) versus O(104(A+J)) at δ=∞. (1) needs L0,L1,Δ,G0,ε for tuning; loses parameter-free updates and, for finite δ, the extra guarantee ∇2f(xout)⪰−δI.
(3) LazyCRN (Doikov et al. 2023), Thm. 3.1, Cor. 3.7 O(m+mL0Δε−3/2)
Special case: L1=0, globally L0-Lipschitz Hessian.
(1): Scope extends Hessian reuse to gradient-dependent third derivatives, including unbounded Hessian variation. Matches known rate at L1=0. (1) needs Δ,ε for tuning in addition to L0,m; lacks the separate curvature guarantee mini[−λmin(∇2f(xi))]+ =O(mL0ε).
(4) NALEN (Chen et al. 2026), Thm. 4.1 O(m+m1/3HΔε−3/2)
Special case: globally H-Lipschitz Hessian; H=L0 when L1=0.
(1): Scope beyond globally Lipschitz Hessians. On the intersection, smaller accuracy term if H≫m1/3(L0+L1ε); initialization can mask this gain. (1) has m1/2 instead of m1/3: an m1/6 loss in the accuracy term when L1=0 and H=L0.

Abbr: Costs are Ng+mNH, with m gradient units per Hessian call; function-value calls in (2) cost one unit each and are included. A=Δ(L0ε−3/2+L1ε−1), ℓ=1+log⁡(1+L1G0/(mL0)). J=1+log+(max{σinit,L1G0}/(L0+L13/2Δ))+log+((L0+L13/2Δ)/σinit), where σinit>0 is the initial cubic regularization in (2). log+⁡t=max{0,log⁡t}, [t]+=max{0,t}; δ is the second-order tolerance and 1/∞=0. H denotes a global Lipschitz constant of ∇2f; Ng,NH count gradient and Hessian evaluations.

Chen, Lesi, Chengchang Liu, Luo Luo, and Jingzhao Zhang. 2026. Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity. https://doi.org/10.48550/arXiv.2501.17488.
Doikov, Nikita, El Mahdi Chayti, and Martin Jaggi. 2023. “Second-Order Optimization with Lazy Hessians.” In Proceedings of the 40th International Conference on Machine Learning, edited by Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, vol. 202. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v202/doikov23a.html.
Fang, Shaoying, Naoki Marumo, and Akiko Takeda. 2026. Parameter-Free Cubic-Regularized Newton Method: Sharp Complexity and Generalized Smoothness. https://doi.org/10.48550/arXiv.2607.10741.

Lean setup