← All setups

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 f:E→R on a finite-dimensional real inner product space E. For γ∈(0,1], the function is γ-quasar-convex relative to a global minimizer x⋆, with ∥x0−x⋆∥≤R for a given starting point x0∈E and radius R>0. Its Hessian is H-Lipschitz, where H>0, and has operator norm at most L0≥0 at x0. The oracle returns f(x), ∇f(x), and ∇2f(x) at x. For ε>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 norm. The Hessian ∇2f(x):E→E is the derivative of the gradient at x. The algorithm receives E, x0, H, γ, R, L0, and ε.

Our assumptions:

Assumption 1 (Hessian regularity). The function f is twice continuously Fréchet differentiable on E, and ∥∇2f(x)−∇2f(y)∥op≤H∥x−y∥for all x,y∈E,∥∇2f(x0)∥op≤L0.

Assumption 2 (Quasar convexity and initial distance). There exists x⋆∈E such that, for every x∈E, f(x⋆)≤f(x),γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩, and ∥x0−x⋆∥≤R.

Queries may be made at any point of E, and each oracle reply is the exact triple (f(x),∇f(x),∇2f(x)). After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. Here x⋆ is a fixed global minimizer; all global minimizers have the same objective value.

Proved result

⌈(8388608⋅H⋅R3γ4⋅ε)38⌉+⋅(log2(⌈27⋅(8388608⋅H⋅R3γ4⋅ε+1)2⋅(L0H⋅R+32768)γ2⌉+)+3)+1

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.