← All setups

Pointwise Hessian Acceleration — Convex Minimization with Hessian Access

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Hessian Access · Lean proof

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.

Proved result

Oracle 0:⌈35184372088832⋅(1+(M0⋅R3ε)27+(M1⋅R)3)⋅(1+log⁡(2+Δ+H0⋅R2+M0⋅R3+M12⋅R4⋅Δε+M1⋅R2))4⌉+ Oracle 1:⌈35184372088832⋅(1+(M0⋅R3ε)27+(M1⋅R)3)⋅(1+log⁡(2+Δ+H0⋅R2+M0⋅R3+M12⋅R4⋅Δε+M1⋅R2))4⌉+

OracleTemplate.Convergence LongTails.Setups.PointwiseHessianConvex.spec
  LongTails.Theorems.PointwiseHessianAcceleration.budget

Relevant previous results

  • Artem Agafonov, Aslan Ashabokov, Alexander D’yakonov, Martin Takáč, Alexander Gasnikov, Dmitry Kamzolov. Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness. 2026 preprint, v1. Complexity: O(N) exact Hessian calls and O(N+Blog+⁡(36M1G/M0)L2/3) exact gradient calls, including initialization and backtracking, for deterministic f(w)−f∗≤ε using adaptive damped A-NPE. Here N=1+(M0R3/ε)2/7+B[1+log+⁡(TR2/max{ε,48M0R3/B7/2})], B=max{1,(6M1R)2/3}, L=1+log+⁡(4TR2/ε), T=2(M0+M1g0)g0, g0=∥∇f(x0)∥, G=max∥x−x∗∥≤(1+2/3)R∥∇f(x)∥, and log+⁡t=max{0,log⁡t}. Initialize regularization at T; return immediately if g0=0. Stated here for M0>0, 0<ε≤M0R3, and global ∥∇2f(y)−∇2f(x)∥≤(M0+M1∥∇f(x)∥)∥y−x∥; the gradient logarithmic term is absent when M1=0.