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
The optimization problem is
Our assumptions:
Assumption 1 (Regularity and convexity). The
function
Assumption 2 (Third-derivative bound). For every
Assumption 3 (Initial Hessian and minimizer bounds).
At the given starting point,
Queries to either oracle may be made at any point of
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) PointwiseHessianAcceleration
(Ours) |
|||
| (2) Derived bound, (Agafonov et al. 2026), Thm. 4.1, Prop. 2.7, Cor. F.6 | (1): For |
(1) needs |
|
| (3) Accelerated Newton, (Doikov 2023), Thm. 6.2 (unconstrained restriction) | (1) covers non-QSC
examples |
For |
|
| (4) Adaptive MS acceleration, (Carmon et al. 2022), Cor. 3 | (1) extends scope to
|
(1) adds |
Abbr: