← All setups

Nonconvex Optimization with Lipschitz Third Derivatives

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Lipschitz Third Derivatives

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 L3-Lipschitz third derivative, where L3>0. A given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ and ∥∇2f(x0)∥op≤H0, where Δ>0 and H0≥0; derivative norms are induced operator norms. Two exact oracles return (f(x),∇f(x)) and ∇2f(x), respectively. 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. The Hessian ∇2f(x) is a linear operator from E to E, and ∇3f(x) is the third derivative viewed as a trilinear form on E. The algorithm receives E, x0, L3, Δ, H0, and ε.

Our assumptions:

Assumption 1 (Third-derivative regularity). The function f belongs to C3(E;R), and ∥∇3f(x)−∇3f(y)∥op≤L3∥x−y∥,x,y∈E.

Assumption 2 (Initial gap and curvature). The given point x0 satisfies f(x0)−f(x)≤Δfor every x∈E,∥∇2f(x0)∥op≤H0.

Both oracles accept queries at any point of E, and their calls are counted separately. After the allotted calls, the output must satisfy ∥∇f(x¯)∥≤εP-a.s.

Results

On a finite-dimensional real inner-product space, f∈C3 has L3-Lipschitz third derivative, f(x0)−inff≤Δ, and ∥∇2f(x0)∥≤H0, where L3,Δ,ε>0 and H0≥0. Exact value/gradient and full-Hessian oracles are available. The target is ∥∇f(xout)∥≤ε almost surely; (1) guarantees it for every seed. No global gradient- or Hessian-Lipschitz bound or algorithm restriction is imposed.

Third-derivative-smooth nonconvex optimization: ThirdDerivativeSmoothNonconvex.
Result Oracle complexity Novelty Limitations
(1) LazyQuarticHessianTradeoff (Ours) (⋆⋆⋆) (review) O((1+S5/4)ℓ+m(1+S3/4)) total; O(1+S3/4) Hessian calls.
(2) (Doikov and Grapiglia 2025), Thm. 3.5, Cor. 3.6 (p=3) O(m[d1/3ΔL¯1/3ε−4/3
+d{1+log+⁡(L3/Linit)}]) total, counting trials and finite differences; Linit>0.
(1): Dimension-free; for S≥1, Linit≍L3, Hessians S3/4 instead of d1/3S+d; total gain when md1/3≫S1/4ℓ.
Example: m=d, H0≤β, Linit≍L3: O(d4/3S+d2) becomes O(S5/4[1+log⁡S]+dS3/4).
(1) needs L3,Δ,H0; (2) adapts to L3. For m=d=1, Linit≍L3, S≥1: O(S) becomes O(S5/4ℓ).
(3) (Hinder 2018), first-order variant after (8); globally L1-Lipschitz gradient O(d(1+S)[1+log+(L13L3ε2)]) expected value/gradient calls; no Hessians. (1): Scope extends beyond global L1; dimension-free. On the overlap, for S≥1, gains when d≫S1/4 and m≪dS1/4, up to logarithms. (1) needs Hessians; larger cost when d≲S1/4, up to logarithms.
(4) (Carmon et al. 2017), Thm. 2; globally L1-Lipschitz gradient O(ΔL11/2L31/6ε5/3[1+log+(L1Δε2)]) value/gradient calls; no Hessians.
Valid for ε2/3≤δ1/2L31/6 and 8L31/3ε2/3≤L1.
(1): Scope extends beyond global L1, including quartic least squares. On the overlap, replaces L1 by (L3Δ)1/4; total gain for L1≫β and m≪Δ1/4L11/2L3−1/12ε−2/3, up to logarithms. (1) needs Hessians and H0; larger gradient prefactor when L1<β within (4)’s admissible accuracy range.
(5) LogFreeSecondOrderThirdSmooth (Ours) (⋆⋆) (review) O((1+m)[1+S+log⁡(2+H0Δ/ε2)]) total; equal-order budgets for value/gradient and Hessian calls.
(6) (He and Zhang 2026), Thm. 4.7; globally LH-Lipschitz Hessian O((1+m)(1+S)[1+log(1+LH(L32ε)1/3)]) total; εg=ε, εH=2(L3ε2)1/3. (5): Removes multiplicative logarithm when LH≫(L32ε)1/3 and S≳log⁡(2+H0Δ/ε2). Scope: no global Hessian-Lipschitz assumption. Saving concerns the shared gradient target. (5) loses second-order stationarity; adds H0 dependence, potentially worse when its additive logarithm dominates (6)’s cost.

Abbr: d=dim⁡E; m≥1 is the cost of one full Hessian in value/gradient-call units; total cost is G+mH, with G,H the respective call counts. S=ΔL31/3ε−4/3; β=L3Δ; ℓ=1+log⁡(1+H0Δ/ε2+L3Δ3/ε4). L1 is a global gradient-Lipschitz constant; Linit is (2)’s initial smoothness estimate and L¯=max{Linit,L3}. δ=f(x0)−inff≤Δ; log+⁡t=max{0,log⁡t}; ≍ denotes equality up to 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.
Doikov, Nikita, and Geovani Nunes Grapiglia. 2025. On the Complexity of Lower-Order Implementations of Higher-Order Methods. https://doi.org/10.48550/arXiv.2510.07992.
He, Chang, and Shuzhong Zhang. 2026. Proximal Point Newton Methods for Nonconvex Optimization. https://doi.org/10.48550/arXiv.2610.36256.
Hinder, Oliver. 2018. “Cutting Plane Methods Can Be Extended into Nonconvex Optimization.” Proceedings of the 31st Conference on Learning Theory, Proceedings of machine learning research, vol. 75: 1451–54. https://doi.org/10.48550/arXiv.1805.08370.

Lean setup