Gap Generalized Smooth Convex Lower Bound — Gap-Constrained Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Gap-Constrained Generalized Smooth Convex Minimization · Lean proof
Gap-Constrained
Generalized Smooth Convex Minimization
We consider minimizing a convex function in a
prescribed high-dimensional regime. The function is -smooth, with and , and has a differentiable
gradient. A given point satisfies and for a global
minimizer , where . The oracle returns at . Given , 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, and denotes its
induced operator norm. The parameters satisfy The algorithm receives , and .
Our assumptions:
Assumption 1 (Convexity). For every and ,
Assumption 2 (Generalized smoothness). The function
is Fréchet differentiable
everywhere, its gradient is Fréchet differentiable everywhere, and
Assumption 3 (Initial distance and objective gap).
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 and satisfy
The minimizer is fixed
independently of the algorithm’s randomness; all global minimizers have
the same objective value.
Proved result
OracleTemplate.NonConvergence LongTails.Setups.GapGeneralizedSmoothConvex.spec
LongTails.Theorems.GapGeneralizedSmoothConvexLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.