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 on
a finite-dimensional real inner product space . We assume a gradient-dependent
third-derivative bound, a hidden bound on the Hessian at a given
starting point , and bounds
on its distance and objective gap to a global minimizer . Two exact oracles return
and at , respectively. For a tolerance
, the goal is an
output satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator and multilinear norms. We regard as a linear operator from
to and as a trilinear form on
. The parameters satisfy The algorithm receives , , , , , , and ; the hidden parameter may enter only the oracle-call
budget.
Our assumptions:
Assumption 1 (Regularity and convexity). The
function belongs to and, for every and ,
Assumption 2 (Third-derivative bound). For every
,
Assumption 3 (Initial Hessian and minimizer bounds).
At the given starting point, There exists such that
Queries to either oracle may be made at any point of . Gradient calls and Hessian calls are
counted separately. After the allotted calls, the output must satisfy
Proved result
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: exact Hessian calls and exact
gradient calls, including initialization and backtracking, for
deterministic using adaptive
damped A-NPE. Here ,
,
,
, , , and . Initialize regularization at ; return immediately if . Stated here for , , and global
; the gradient logarithmic term is absent when
.