Convex Minimization with Unknown Smoothness
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization
with Unknown Smoothness
We consider minimizing a differentiable convex function on a real Hilbert space
. Its gradient is -Lipschitz for an unknown constant , and a given starting point lies within distance of a global minimizer . The oracle returns at . For a tolerance , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness. Only
and are algorithm inputs.
The optimization problem is The norm is induced by the inner product
on . The parameters , , and may enter the oracle-call
budget but are not supplied to the algorithm.
Our assumptions:
Assumption 1 (Convexity). For every and ,
Assumption 2 (Smoothness). The function is Fréchet differentiable everywhere on
, and its gradient satisfies
Assumption 3 (Initial distance). There exists such that
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy
Results
Lean setup