Log Free Generalized Smooth Lower Bound — Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Generalized Smooth Convex Minimization · Lean proof
Generalized Smooth Convex
Minimization
We consider minimizing a convex function in dimension
. The function is -smooth, meaning its
differentiable gradient satisfies everywhere,
with and . A given point lies within distance
of a global minimizer . The oracle returns at . For a tolerance , the goal is an output
with
integrable objective gap and ,
where is the law of the
algorithm’s randomness.
The optimization problem is We use the
Euclidean norm and its induced operator norm. The parameters obey The algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Convexity). For every and ,
Assumption 2 (Generalized smoothness). The function
is differentiable everywhere, its
gradient is Fréchet differentiable everywhere, and Here
is the derivative of the gradient.
Assumption 3 (Initial distance). There exists such that
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.GeneralizedSmoothConvexFull.spec
LongTails.Theorems.LogFreeGeneralizedSmoothLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.