Known Gap Generalized Smooth Upper Bound — Known-Gap Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Known-Gap Generalized Smooth Convex Minimization · Lean proof
Known-Gap
Generalized Smooth Convex Minimization
We consider minimizing a differentiable convex function , where is a positive integer. The function
is -smooth, with and : its differentiable gradient
satisfies everywhere. A
given point satisfies and for a global
minimizer , with . 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 norm on and
its induced operator norm on linear maps. The algorithm receives , and .
Our assumptions:
Assumption 1 (Parameter regime and dimension). The
parameters satisfy and
Assumption 2 (Convexity and generalized smoothness).
The function is differentiable
everywhere, and, for every and , Its
gradient is Fréchet differentiable everywhere and satisfies Here is a linear operator from
to .
Assumption 3 (Initial distance and objective gap).
There exists a global minimizer such that
Queries may be made at any point of . After the allotted gradient
calls, the output must have an
integrable objective gap under
and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothConvexKnownGapPolynomialDimension.spec
LongTails.Theorems.KnownGapGeneralizedSmoothUpperBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.