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 on a finite-dimensional
real Hilbert space . The function
has an -Lipschitz gradient, with
, and is strongly
quasar-convex with parameters and relative to a global
minimizer . A given point
satisfies , where . The oracle returns a fixed
measurable vector satisfying
, with . For , the goal is an output
with integrable
objective gap and ,
where is the law of the
algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , , , , , , and .
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 2 (Strong quasar-convexity and initial
gap). There exists
such that Relative to this same minimizer, strong
quasar-convexity means that, for every ,
Assumption 3 (Relative gradient error). The oracle
returns at any query point
, where is a fixed Borel-measurable map
satisfying
After the allotted oracle calls, the output must have an integrable
objective gap under and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.RelativeGradientStrongQuasar.spec OracleTemplate.RelativeQuasar.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.