← All setups

Convex Minimization with Hessian Access

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Hessian Access

We consider minimizing a three-times continuously differentiable convex function f:E→R on a finite-dimensional real inner product space E. We assume a gradient-dependent third-derivative bound, a hidden bound on the Hessian at a given starting point x0∈E, and bounds on its distance and objective gap to a global minimizer x⋆∈E. Two exact oracles return ∇f(x) and ∇2f(x) at x∈E, respectively. For a tolerance ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator and multilinear norms. We regard ∇2f(x) as a linear operator from E to E and ∇3f(x) as a trilinear form on E. The parameters satisfy M0,M1,H0≥0,R,Δ,ε>0. The algorithm receives E, x0, M0, M1, R, Δ, and ε; the hidden parameter H0 may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Regularity and convexity). The function f belongs to C3(E;R) and, for every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Third-derivative bound). For every x∈E, ∥∇3f(x)∥op≤M0+M1∥∇f(x)∥.

Assumption 3 (Initial Hessian and minimizer bounds). At the given starting point, ∥∇2f(x0)∥op≤H0. There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Queries to either oracle may be made at any point of E. Gradient calls and Hessian calls are counted separately. After the allotted calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

Convex f∈C3(E) on a finite-dimensional real inner-product space, with ∥D3f(x)∥≤M0+M1∥∇f(x)∥ everywhere. An attained minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ; ∥∇2f(x0)∥≤H0. Here M0,M1,H0≥0 and R,Δ,ε>0. Exact gradient and Hessian access; target f(xout)−f(x⋆)≤ε for every seed.

Sufficient oracle budgets for PointwiseHessianConvex.
Result Oracle complexity Novelty Limitations
(1) PointwiseHessianAcceleration (Ours) (⋆⋆) (review) O([1+(M0R3/ε)2/7+M13/2R3]ℓ4) total gradient and Hessian calls.
(2) Derived bound, (Agafonov et al. 2026), Thm. 4.1, Prop. 2.7, Cor. F.6 O((M¯0R3/ε)2/7+δR2/ε+Bρℓρ+Jρ+BρCρℓρ2/3) total gradient and Hessian calls, including rejected trials. Restriction: ∥∇2f∥≤L0+L1∥∇f∥, L0>0, L1≥0; any ρ>0. (1): For δ=M0=0, fixed positive M1,L0,R, ε→0: O(log4⁡(1/ε)) removes the reduction’s (M1L0R4/ε)1/5 term. Scope: pointwise growth alone; no extra Hessian-growth assumption. (1) needs M0,M1,R,Δ,ε; (2) is parameter-free. C3 instead of C2; exact Hessians required. Growth terms: (M1R2)3/2 versus (M1R2)1/3 for M1R2≫1. Same M0-term exponent, with ℓ4 overhead.
(3) Accelerated Newton, (Doikov 2023), Thm. 6.2 (unconstrained restriction) O((MRD)2/3ℓD⋅[1+log+((MRD)2/3RD⋅LDFDℓD2/ε)]) total gradient and Hessian calls, including inner Dual Newton iterations. Restriction: QSC with M>0; relative accuracy converted using d=f(x0)−f⋆>0. (1) covers non-QSC examples 12xTQx+β∥x∥4/4, Q⪰0 singular, β>0. Classes incomparable; no general rate comparison. For f=∑icosh⁡xi+12xTQx, Q⪰0, (1) with M1=1+∥Q∥ has term ((1+∥Q∥)R2)3/2; (3) has M=1, only logarithmic ∥Q∥ dependence and RD2/3 outside logarithms.
(4) Adaptive MS acceleration, (Carmon et al. 2022), Cor. 3 O(1+(M0R3/ε)2/7+log[1+log(2+M0R/λ0+λ0R2/ε)]) total gradient and Hessian calls; same order of linear solves. Special case: M1=0, M0>0; initialization λ0>0. (1) extends scope to M1>0; matches the leading ε−2/7 rate at M1=0. (1) adds ℓ4 overhead at M1=0 and needs M0; (4) adapts without knowing M0.

Abbr: f⋆=f(x⋆); log+⁡t=log⁡(max{1,t}). ℓ=1+log(2+(Δ+H0R2+M0R3+M12R4Δ)/ε+M1R2). H0: analysis-only initial Hessian bound for (1). For (2), M¯0=M0+M1L0ρeL1ρ, M¯1=M1eL1ρ (positive certificates may be used); δ≥0 bounds symmetric Hessian error in operator norm, and comparisons use δ=0. Bρ=1+(M¯1R2)1/3+(R/ρ)2/3, rρ=min{ρ/2,1/(6M¯1)}, with 1/0=+∞; g0=∥∇f(x0)∥, G=max∥x−x⋆∥≤(1+2/3)R∥∇f(x)∥. For arbitrary initial regularization η0>0, τρ=max{4δ,2(M¯0+M¯1g0)g0,2g0/ρ}, ℓρ=1+log+⁡(max{η0,τρ}R2/ε), Jρ=log+⁡(τρ/η0) and Cρ=log+⁡((δ+G/rρ)/(δ+M¯0rρ)). For (3), QSC means |D3f(x)[u,u,v]|≤M⟨∇2f(x)u,u⟩∥v∥; RD=max{R,23/2/M}, ℓD=1+log+⁡(d/ε), LD=max∥x−x⋆∥≤6RD∥∇2f(x)∥, FD=max∥x−x⋆∥≤6RD(f(x)−f⋆); the theorem’s absolute tuning constant is set to 1.

Agafonov, Artem, Aslan Ashabokov, Alexander D’yakonov, Martin Takáč, Alexander Gasnikov, and Dmitry Kamzolov. 2026. Optimal Parameter-Free Second-Order Acceleration with Inexact Hessians Under Generalized Smoothness. https://doi.org/10.48550/arXiv.2609.32977.
Carmon, Yair, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. 2022. Optimal and Adaptive Monteiro–Svaiter Acceleration. https://doi.org/10.48550/arXiv.2205.15371.
Doikov, Nikita. 2023. Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method. https://doi.org/10.48550/arXiv.2308.14742.

Lean setup