High Dimensional Strong Quasar Lower Bound — High-Dimensional Strong Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Strong Quasar Minimization · Lean proof
High-Dimensional Strong
Quasar Minimization
We consider minimizing a differentiable, possibly nonconvex function
with an
-Lipschitz gradient, where is the dimension and . The function is strongly
quasar-convex toward a global minimizer , with parameters and . A given starting
point satisfies
, where
. The oracle returns
at . For , the goal is an output
with
integrable objective gap satisfying ,
where is the law of the
algorithm’s randomness.
The optimization problem is We use the
Euclidean inner product and its induced
norm . The algorithm
receives , , , , , , and .
Our assumptions:
Assumption 1 (Parameter and dimension regime). The
dimension is a nonnegative
integer. In addition to the parameter ranges above, define and require
Assumption 2 (Smoothness). The function is Fréchet differentiable everywhere,
and
Assumption 3 (Strong quasar convexity and initial
gap). There exists a global minimizer satisfying the
stated initial objective-gap bound such that, for every ,
Queries may be made at any point of . After the allotted oracle
calls, the output must have an integrable objective gap under and satisfy
Proved result
OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalStrongQuasar.spec
LongTails.Theorems.HighDimensionalStrongQuasarLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.