Backtracking Generalized Accelerated — Convex Minimization with Hidden Smoothness
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Hidden Smoothness · Lean proof
Convex Minimization with
Hidden Smoothness
We consider minimizing a convex function on a real Hilbert space
. The function is -smooth with hidden constants
and , and has a differentiable
gradient. A given point
satisfies and
for a
global minimizer and hidden
bounds . 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 only , , and a scalar ; the parameters , and may enter the oracle-call
budget but are not algorithm inputs.
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 (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 satisfy The minimizer is fixed independently of the
algorithm’s randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothParameterFree.spec
OracleTemplate.ParameterFreeGeneralized.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.