← All setups

Quasar Signed Bias — Quasar-Convex Minimization with Signed Bias

Descriptions may be stale. Consult the linked Lean sources.

Quasar-Convex Minimization with Signed Bias · Lean proof

Quasar-Convex Minimization with Signed Bias

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a real Hilbert space E. Its gradient is bounded by M>0, and it is τ-quasar-convex about a global minimizer x⋆, where τ∈(0,1]. A given point x0∈E satisfies ∥x0−x⋆∥≤R, where R≥0. The oracle returns the exact function value and a gradient perturbed by successive differences of a fixed vector sequence bounded by B≥0 and starting at zero. For ε>0, the goal is an output x¯∈E with f(x¯)−f(x⋆)≤ε almost surely under P, 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. The algorithm receives E, M, B, R, τ, ε, and x0.

Our assumptions:

Assumption 1 (Bounded gradient). The function f is Fréchet differentiable everywhere on E, with ∥∇f(x)∥≤M,x∈E.

Assumption 2 (Quasar-convexity and initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R, and f is τ-quasar-convex about this minimizer: τ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩,x∈E.

Assumption 3 (Signed-bias oracle). There is a fixed deterministic sequence (bk)k≥0 in E satisfying b0=0,∥bk∥≤Bfor every k≥0. On call k+1, for k≥0, a query at any x∈E returns (f(x),∇f(x)+bk+1−bk).

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Proved result

max{1,⌈R2⋅(M2+2⋅M⋅B)τ2⋅ε2⌉+}

OracleTemplate.Convergence LongTails.Setups.QuasarSignedBias.spec OracleTemplate.QuasarSignedBias.budget

Relevant previous results

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