← All setups

Accelerated Relative Quasar — Strong Quasar Minimization with Relative Errors

Descriptions may be stale. Consult the linked Lean sources.

Strong Quasar Minimization with Relative Errors · Lean proof

Strong Quasar Minimization with Relative Errors

We consider minimizing a differentiable function f:E→R on a finite-dimensional real Hilbert space E. The function has an L-Lipschitz gradient, with L>0, and is strongly quasar-convex with parameters μ>0 and γ∈(0,1] relative to a global minimizer x⋆. A given point x0∈E satisfies f(x0)−f(x⋆)≤Δ, where Δ≥0. The oracle returns a fixed measurable vector g(x) satisfying ∥g(x)−∇f(x)∥≤δ∥∇f(x)∥, with δ∈[0,1). For ε>0, the goal is an output x¯∈E with integrable objective gap and EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The algorithm receives E, L, x0, μ, γ, δ, Δ, and ε.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Strong quasar-convexity and initial gap). There exists x⋆∈E such that f(x⋆)≤f(x),x∈E,f(x0)−f(x⋆)≤Δ. Relative to this same minimizer, strong quasar-convexity means that, for every x∈E, f(x⋆)≥f(x)+1γ⟨∇f(x),x⋆−x⟩+μ2∥x−x⋆∥2.

Assumption 3 (Relative gradient error). The oracle returns g(x) at any query point x∈E, where g:E→E is a fixed Borel-measurable map satisfying ∥g(x)−∇f(x)∥≤δ∥∇f(x)∥,x∈E.

After the allotted oracle calls, the output must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Proved result

max{1,⌈32⋅Lμ⋅(1−δ)γ+128⋅δ2⋅Lγ2⋅μ⋅(1−δ)⌉+}⋅max{1,clog2(⌈1+2⋅Δγ⋅ε⌉+)}

OracleTemplate.Convergence LongTails.Setups.RelativeGradientStrongQuasar.spec OracleTemplate.RelativeQuasar.budget

Relevant previous results

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