← All setups

Gradient Only Quasar High Probability — Gradient-Only Generalized Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

Gradient-Only Generalized Quasar Minimization · Lean proof

Gradient-Only Generalized Quasar Minimization

We consider minimizing a continuously differentiable function f:E→R on a finite-dimensional real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0, and is γ-quasar-convex relative to a global minimizer x⋆, meaning γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for every x∈E, where 0<γ≤1. A given starting point x0∈E has bounded distance and objective gap to this minimizer. The oracle returns ∇f(x) at x. For ε>0 and δ∈(0,1), the goal is an output x¯∈E with P{f(x¯)−f(x⋆)>ε}≤δ, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. Let R>0 and Δ>0 denote the initial distance and objective-gap bounds. The algorithm receives E, L0, L1, R, Δ, x0, γ, ε, and δ.

Our assumptions:

Assumption 1 (Generalized smoothness). The function f is Fréchet differentiable everywhere, and ∇f:E→E is continuous. For every x,y∈E and M∈R, the segment bound ∥∇f(x+θ(y−x))∥≤Mfor every θ∈[0,1] implies ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

Assumption 2 (Quasar convexity and initialization). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ. Relative to this same minimizer, the quasar-convexity condition is γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩for every x∈E.

Queries may be made at any point of E. After the allotted gradient calls, the output must satisfy the failure-probability bound P{f(x¯)−f(x⋆)>ε}≤δ.

Proved result

⌈65536⋅(1+clog2(⌈4δ⌉+))⋅(1+L0⋅R2ε+L1⋅R⋅(1+clog2(⌈8⋅Δε⌉+)))γ⌉+

OracleTemplate.Convergence LongTails.Setups.GradientOnlyGeneralizedQuasar.spec OracleTemplate.GradientOnlyQuasar.budget

Relevant previous results

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