Movement 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 possibly nonconvex objective
has an -Lipschitz gradient and is
strongly quasar-convex with parameters and relative to a global
minimizer .
Component-gradient deviations from satisfy a mean-square Lipschitz bound with constant . A given point satisfies , where . At , the oracle returns . For , the goal is an output
with integrable
objective gap and ,
where is 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 (Differentiability and smoothness).
Each is Fréchet differentiable
everywhere on . The average
gradient satisfies
Assumption 2 (Mean-square gradient similarity).
Define . For every ,
Assumption 3 (Strong quasar-convexity and initial
gap). There exists
such that For this same minimizer and every ,
Queries may use any component and any point . After the allotted
component-gradient calls, the output must have an integrable objective
gap and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.ContinuizedSimilarQuasar.spec
OracleTemplate.ContinuizedSimilarQuasar.Movement.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.