Descriptions may be stale. Consult the linked Lean sources.
We consider minimizing a convex function over a compact uniformly
convex set in a
finite-dimensional real inner-product space , starting from a given . The gradient is -Lipschitz on , with , and distance to the minimizer set
satisfies a Hölder error bound. The oracle returns at or a minimizer of a queried linear
functional over . We analyze
short-step Frank–Wolfe. For , the goal is a feasible
output with
almost surely, where
minimizes on and the randomness comes from oracle
tie-breaking.
The optimization problem is Write for the inner
product and for its
induced norm. The parameters satisfy The algorithm receives only , , and ; the parameters may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Uniformly convex feasible set). The
set is compact, contains , and satisfies For every
, , and with ,
Assumption 2 (Convexity and smoothness). The
function is Fréchet
differentiable at every point of .
For all and ,
Assumption 3 (Hölder error bound). There exists
minimizing over . For every , there exists a minimizer such that
There are two query types. The gradient oracle returns at . A linear minimization query
accepts any and returns an
atom satisfying Every reply must satisfy its stated condition;
selection among minimizing atoms may depend on previous queries and
oracle randomness. Both query types count toward a single total
oracle-call budget.
Our result is algorithm-specific: we analyze short-step Frank–Wolfe
initialized at the given point .
Each iteration first queries the gradient and then a minimizing atom,
and updates according to When , the quotient is defined to be
zero, so . Each completed
iteration uses two oracle calls. After a total budget of calls, with an integer, the output is the last
completed iterate . If is odd,
the final gradient query leaves this output unchanged.
The required accuracy is where is the law of the oracle
randomness.