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 on a finite-dimensional
real Hilbert space . The function
is -smooth, with and , and is -quasar-convex relative to a global
minimizer , meaning for every , where . A given starting point
has bounded distance and
objective gap to this minimizer. The oracle returns at . For and , the goal is an output
with ,
where is the law of the
algorithm’s randomness.
The optimization problem is Write for the inner
product on and for its induced norm. Let and denote the initial distance
and objective-gap bounds. The algorithm receives , , , , , , , , and .
Our assumptions:
Assumption 1 (Generalized smoothness). The function
is Fréchet differentiable
everywhere, and is
continuous. For every and
, the segment bound
implies
Assumption 2 (Quasar convexity and initialization).
There exists such that
Relative to this same minimizer, the
quasar-convexity condition is
Queries may be made at any point of . After the allotted gradient calls, the
output must satisfy the failure-probability bound
Proved result
OracleTemplate.Convergence LongTails.Setups.GradientOnlyGeneralizedQuasar.spec OracleTemplate.GradientOnlyQuasar.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.