Expected Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Expected
Smooth Convex Minimization
We consider minimizing a differentiable convex function with -Lipschitz gradient, where is a nonnegative integer and . A given point lies within Euclidean
distance of a global
minimizer . The oracle
returns at . For a tolerance , the goal is a random
output with
integrable objective gap and ,
where is the law of the
algorithm’s randomness. The parameters satisfy the accuracy and
dimension restrictions specified below.
The optimization problem is
Throughout, denotes the
Euclidean norm. The algorithm receives , , , , and .
Our assumptions:
Assumption 1 (Parameter regime). The parameters
satisfy and
, with
Assumption 2 (Convexity and smoothness). The
function is differentiable
everywhere on . For
every and ,
Assumption 3 (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 under
and satisfy
Results
Lean setup