Generalized Self Normalized Convex — 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 on a real Hilbert space
. The function is -smooth, with and , and has an everywhere
differentiable gradient. A given point satisfies and for a global
minimizer , where . 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 The norm is induced by the inner product
on , and denotes the
induced operator norm. The algorithm receives , , , , , and ; the tolerance may enter the oracle-call
budget but is not an algorithm input.
Our assumptions:
Assumption 1 (Convexity). For every and ,
Assumption 2 (Generalized smoothness). The function
is Fréchet differentiable
everywhere on , and its gradient
is Fréchet
differentiable everywhere. Its Hessian satisfies
Assumption 3 (Minimizer and initialization). There
exists such that
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothAndConvex.spec
OracleTemplate.GeneralizedAccelerated.SelfNormalized.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.