Polynomial Dimension Generalized Smooth Lower Bound — Generalized Smoothness in Polynomial Dimension
Descriptions may be stale. Consult the linked Lean sources.
Generalized Smoothness in Polynomial Dimension · Lean proof
Generalized
Smoothness in Polynomial Dimension
We consider minimizing a convex function in a
dimension subject to
a polynomial lower bound. The function is -smooth, with : its differentiable gradient
satisfies at every . A given point lies within distance of a global minimizer . The oracle returns at . For , the goal is an output
with ,
where is the law of the
algorithm’s randomness.
The optimization problem is We use the
Euclidean norm, and denotes the
induced operator norm. The algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Parameter regime). The positive
parameters satisfy
Assumption 2 (Convexity). For every and ,
Assumption 3 (Generalized smoothness). The function
is Fréchet differentiable
everywhere, its gradient is Fréchet differentiable everywhere, and Here is a linear operator from
to .
Assumption 4 (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 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.GeneralizedSmoothConvexPolynomialDimension.spec
LongTails.Theorems.PolynomialDimensionGeneralizedSmoothLowerBound.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.