← All setups

Hessian-Lipschitz Second-Order Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Hessian-Lipschitz Second-Order Stationarity

We consider minimizing a possibly nonconvex, twice continuously differentiable function f:E→R on a finite-dimensional real inner product space E, with induced norm ∥⋅∥. Its Hessian is H-Lipschitz for H>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ for Δ≥0. Two exact oracles return (f(x),∇f(x)) and ∇2f(x), respectively. For ε>0 and ρ∈(0,1), the goal is an output x¯∈E satisfying both ∥∇f(x¯)∥≤ε and ⟨v,∇2f(x¯)v⟩≥−Hε∥v∥2 for every v∈E, with probability at least 1−ρ over the algorithm’s randomness.

The optimization problem is infx∈Ef(x). The Hessian ∇2f(x):E→E is a linear operator, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, H, Δ, ε, ρ, and an additional real parameter m≥1; the setup imposes no further condition involving m.

Our assumptions:

Assumption 1 (Hessian regularity). The function f is twice continuously Fréchet differentiable on E, and ∥∇2f(x)−∇2f(y)∥op≤H∥x−y∥,x,y∈E.

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

Queries to either oracle may be made at any point of E. The first oracle returns the exact function value and gradient together; the second returns the exact Hessian. Calls to these two oracles are counted separately.

After the allotted calls, the output must satisfy P({∥∇f(x¯)∥≤ε,⟨v,∇2f(x¯)v⟩≥−Hε∥v∥2for every v∈E})≥1−ρ, where P is the law of the algorithm’s randomness.

Results

On a finite-dimensional real inner-product space, f∈C2, ∥∇2f(x)−∇2f(y)∥≤H∥x−y∥, and f(x0)−f(x)≤Δ for every x. Here H,ϵ>0, Δ≥0, m≥1, and 0<ρ<1. Oracles return exact (f,∇f) and full Hessians. The target is P{∥∇f(y)∥≤ϵ, ∇2f(y)⪰−HϵI}≥1−ρ.

Comparison for HessianLipschitzSecondOrder.
Result Oracle complexity Novelty Limitations
(1) MonotoneHessianSecondOrder (Ours) (⋆⋆⋆) (review) O(m+m1/3(1+S)ℓ2)
(2) Cubic regularization (Nesterov and Polyak 2006), Thm. 1 O(m(1+S)) (1): cheaper for S≥1, ℓ2≪m2/3. For d=S=m, ρ=1/m, costs O(m4/3log2⁡m) versus O(m2). (1): probabilistic instead of deterministic; ℓ2 overhead when m=O(1).
(3) Lazy cubic Newton (Doikov et al. 2023), Cor. 3.7 O(m+mS); separate minima: gradient O(ϵ), negative curvature O(mHϵ). (1): one point satisfies the gradient and curvature targets; removes the m curvature inflation in (3). (1): probabilistic instead of deterministic; additional dimension- and confidence-dependent logarithms.
(4) Derived bound (Doikov et al. 2023), Thm. 3.1, (15) O(m2(1+S)); reuse period ⌈m⌉, separate minima at tolerances ϵ, Hϵ. (1): same-point certificate; for S≥1, ℓ2≪m2/3, lowers cost to O(m+m1/3Sℓ2) while strengthening (4)’s output. (1): probabilistic instead of deterministic.
(5) (Adil et al. 2025), Cor. 2 O(m+m1/3Slog18⁡(2+S)); S≥1, first-order target only. (1): adds the second-order certificate with matching polynomial powers; logarithmic overhead becomes ℓ2 instead of log18⁡(2+S), smaller when ℓ2≪log18⁡(2+S). (1): probabilistic instead of deterministic.
(6) NALEN (Chen et al. 2026), Thm. 4.1 O(m+m1/3S); first-order target only. (1): extends the m1/3S polynomial dependence to a same-point second-order certificate. (1): extra ℓ2 overhead; probabilistic instead of deterministic.

Abbr: d=dim⁡E, S=ΔH/ϵ3/2, ℓ=log(2+(d+1)m(1+S)/ρ). Costs are G+mJ, where G counts ordinary oracle calls and J counts full-Hessian calls; m is the assigned Hessian cost. First-order target: ∥∇f(y)∥≤ϵ. Negative curvature: max{0,−λmin(∇2f)}. Separate minima may occur at different iterates.

Adil, Deeksha, Brian Bullins, Aaron Sidford, and Chenyi Zhang. 2025. “Balancing Gradient and Hessian Queries in Non-Convex Optimization.” Advances in Neural Information Processing Systems 38. https://doi.org/10.52202/085713-1441.
Chen, Lesi, Chengchang Liu, Luo Luo, and Jingzhao Zhang. 2026. “Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity.” Proceedings of Thirty Ninth Conference on Learning Theory, Proceedings of machine learning research, vol. 336: 1088–112. https://proceedings.mlr.press/v336/chen26a.html.
Doikov, Nikita, El Mahdi Chayti, and Martin Jaggi. 2023. “Second-Order Optimization with Lazy Hessians.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 8138–61. https://proceedings.mlr.press/v202/doikov23a.html.
Nesterov, Yurii, and Boris T. Polyak. 2006. “Cubic Regularization of Newton Method and Its Global Performance.” Mathematical Programming 108 (1): 177–205. https://doi.org/10.1007/s10107-006-0706-8.

Lean setup