Quasar Accelerated Cubic Newton — Quasar-Convex Minimization with Lipschitz Hessian
Descriptions may be stale. Consult the linked Lean sources.
Quasar-Convex Minimization with Lipschitz Hessian · Lean proof
Quasar-Convex
Minimization with Lipschitz Hessian
We consider minimizing a twice continuously differentiable function
on a
finite-dimensional real inner product space . For , the function is -quasar-convex relative to a global
minimizer , with for a given
starting point and radius
. Its Hessian is -Lipschitz, where , and has operator norm at most
at . The oracle returns , , and at
. For , 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 norm. The Hessian is the derivative of the gradient at . The algorithm receives , , , , , , and .
Our assumptions:
Assumption 1 (Hessian regularity). The function
is twice continuously Fréchet
differentiable on , and
Assumption 2 (Quasar convexity and initial
distance). There exists such that, for every , and .
Queries may be made at any point of , and each oracle reply is the exact
triple After the allotted oracle calls, the output must
satisfy Here is a fixed global minimizer; all
global minimizers have the same objective value.
Proved result
OracleTemplate.Convergence LongTails.Setups.QuasarConvexHessianLipschitz.spec
LongTails.Theorems.QuasarAcceleratedCubicNewton.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.