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
on a real Hilbert
space . Its gradient is bounded by
, and it is -quasar-convex about a global
minimizer , where . A given point satisfies , where . The oracle returns the exact
function value and a gradient perturbed by successive differences of a
fixed vector sequence bounded by and starting at zero. For , the goal is an output
with
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives , , , , , , and .
Our assumptions:
Assumption 1 (Bounded gradient). The function is Fréchet differentiable everywhere on
, with
Assumption 2 (Quasar-convexity and initial
distance). There exists such that and is
-quasar-convex about this
minimizer:
Assumption 3 (Signed-bias oracle). There is a fixed
deterministic sequence in satisfying On call , for
, a query at any returns
After the allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.QuasarSignedBias.spec OracleTemplate.QuasarSignedBias.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.