← All setups

Spectral Gradient Quadratic Convergence — Minimization with Minimizer-Anchored Hessian Regularity

Descriptions may be stale. Consult the linked Lean sources.

Minimization with Minimizer-Anchored Hessian Regularity · Lean proof

Minimization with Minimizer-Anchored Hessian Regularity

We consider minimizing a differentiable function f:E→R on a nonzero finite-dimensional real Hilbert space E. The function is μ-strongly convex with an L-Lipschitz, differentiable gradient, where 0<μ≤L. A given point x0∈E lies within distance R>0 of a global minimizer x⋆, and the Hessian satisfies ∥∇2f(x)−∇2f(x⋆)∥op≤M∥x−x⋆∥ for every x∈E, where M≥0 and the norms are induced by the inner product. The oracle returns ∇f(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 algorithm receives E, L, μ, M, x0, R, and ε. We write ∥⋅∥op for the induced operator norm; each Hessian ∇2f(x) is a linear operator from E to E.

Our assumptions:

Assumption 1 (Strong convexity). For every x,y∈E, f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2.

Assumption 2 (Differentiability and smoothness). Both f and ∇f are Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial distance and Hessian regularity). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R, and the Hessian obeys the minimizer-anchored bound ∥∇2f(x)−∇2f(x⋆)∥op≤M∥x−x⋆∥,x∈E.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Proved result

⌈2⋅Lμ⋅log⁡(2+8⋅(dimR⁡(E)+1)2⋅(4⋅L2μ2)dimR⁡(E)⋅M⋅L⋅Rμ2)⌉++2⋅dimR⁡(E)⋅⌈log⁡(1+log⁡(1+L2⋅R2μ⋅ε))log⁡(2)⌉+

OracleTemplate.Convergence LongTails.Setups.MinimizerRegularHessian.spec OracleTemplate.SpectralGradient.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.