Cached Similar Quasar — Similar Finite-Sum Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
Similar Finite-Sum Quasar Minimization · Lean proof
Similar Finite-Sum Quasar
Minimization
We consider minimizing on a real
Hilbert space , where and the functions are differentiable.
The potentially nonconvex objective has a Lipschitz gradient, satisfies
a quadratic lower model, and obeys strong quasar-convexity and quadratic
growth relative to a global minimizer . Component-gradient deviations
from the mean are Lipschitz with a restricted similarity constant. A
given point has bounded
objective gap. The oracle returns at a queried pair . For , the goal is an output
with
almost surely under the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The parameters satisfy The algorithm receives , , , , , , , , and .
Our assumptions:
Assumption 1 (Smoothness and component similarity).
Each is Fréchet differentiable
everywhere on . For every and ,
Assumption 2 (Quadratic lower model). For every
,
Assumption 3 (Strong quasar-convexity and quadratic
growth). There exists a global minimizer such that and, for
every ,
Queries may use any component index and any point . After the allotted
component-gradient calls, the output must satisfy where is the law of the algorithm’s
randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.SimilarFiniteSumQuasar.spec OracleTemplate.SimilarQuasar.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.