← All setups

Minimization with Minimizer-Anchored Hessian Regularity

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a real Hilbert space of finite dimension d≥1, f and ∇f are differentiable, f is μ-strongly convex and L-smooth, and a minimizer x⋆ satisfies ∥x0−x⋆∥≤R and ∥∇2f(x)−∇2f(x⋆)∥≤M∥x−x⋆∥ for every x. Parameters 0<μ≤L, M≥0, R>0, and ε>0 are known. Exact gradients may be queried at arbitrary points; the setup imposes no algorithm restriction. Target: f(xout)−f(x⋆)≤ε, deterministically for the constructed algorithms.

Gradient-oracle comparison for MinimizerRegularHessian.
Result Oracle complexity Novelty Limitations
(1) SpectralGradientQuadraticConvergence (Ours) (review) O(κlog(2+d2(2κ)2dΘ)+dlog(2+log⁡(1+κT)))
(2) Derived bound: AGD warmup (Bubeck 2015, Thm. 3.18) + forward-difference Newton O(κlog(2+dκMR/μ)+dlog(2+log⁡(1+κT)))
Same anchored Hessian condition; d+1 gradient calls per Newton step.
(1): matches the quadratic-phase order using scalar gradient steps and quadratic windows; no established problem-class improvement. (1): warmup bound at least a κ factor larger; still needs matrix fitting and eigendecomposition. (2) uses off-iterate gradients and linear solves; for M=0, one Newton step is exact.
(3) AGD (Bubeck 2015, Thm. 3.18) O(1+κlog⁡(1+T)) (1): for fixed d,κ,Θ as T→∞, O(log⁡log⁡T) instead of O(log⁡T); a scalar-step guarantee, not improved problem-class complexity. (1) needs anchored Hessian regularity, finite dimension, and known M,R; its warmup can dominate at moderate accuracy or large d,κ.
(4) Silver stepsizes (Altschuler and Parrilo 2023, Thm. 1.1) O(1+κlog1+2⁡2log⁡(1+T)) (1): for fixed d,κ,Θ as T→∞, O(log⁡log⁡T) instead of O(log⁡T) within scalar-gradient methods. (1) needs anchored Hessian regularity, finite dimension, and known M,R; no uniform cost saving.

Abbr: κ=L/μ, Θ=MLR/μ2, T=LR2/ε; d=dim⁡E. AGD: accelerated gradient descent. Costs count all exact gradient calls, including probing and finite differences; matrix operations are not oracle calls. Logarithms are natural unless a base is shown.

Altschuler, Jason M., and Pablo A. Parrilo. 2023. Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule. https://doi.org/10.48550/arXiv.2309.07879.
Bubeck, Sébastien. 2015. “Convex Optimization: Algorithms and Complexity.” Foundations and Trends in Machine Learning 8 (3–4): 231–358. https://doi.org/10.1561/2200000050.

Lean setup