Known Value Nondual Generalized Rate — Known-Value Generalized Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Known-Value Generalized Convex Minimization · Lean proof
Known-Value Generalized
Convex Minimization
We consider minimizing a continuously differentiable convex function
, where
. The function is -smooth in the Euclidean norm,
with . Its minimum
value is
known, and a given point lies within coordinate
distance of a global minimizer. The oracle
returns at . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is We write
for the Euclidean norm
and for
the coordinate norm. The
algorithm receives , , , , , , and .
Our assumptions:
Assumption 1 (Convexity). For every and ,
Assumption 2 (Generalized smoothness). The function
is differentiable everywhere, and
is continuous. For every
,
Assumption 3 (Known minimum and initial distance).
There exists
such that
Queries may be made at any point of , with each query returning
both the exact function value and the exact gradient. After the allotted
oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.KnownValueNondualGeneralizedConvex.spec
LongTails.Theorems.KnownValueNondualGeneralizedRate.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.