Descriptions may be stale. Consult the linked Lean sources.
Online Convex
Optimization
We consider online convex optimization on a nonempty compact convex
set , where
is an integer. The set has
diameter at most , and a
point is given. Each loss
is
convex on and differentiable at
every point of , with gradient
norm at most . At round , the oracle returns at the chosen point . Over rounds, the goal is
for every and every
realization of algorithm randomness, where is the target regret
bound.
The comparison is with the best fixed decision in hindsight, whose
cumulative loss is Throughout, denotes the Euclidean norm. The
algorithm receives , , , , , and the integer horizon ; the loss sequence is accessed through
the oracle.
Our assumptions:
Assumption 1 (Feasible set). The set is compact and convex, contains the
given point , and satisfies
Assumption 2 (Convex losses and bounded gradients).
For every integer , the
function is differentiable in
the ambient space at every .
For every and ,
At each round ,
the algorithm chooses
using its randomness and previous oracle replies. The oracle returns
at . Thus there are exactly gradient queries, one for each
successive loss. The given point is available to the algorithm; its
first decision is chosen by the
algorithm.
The required performance concerns the decisions themselves. For a
target bound , which may depend on
, and , they must satisfy for every realization of the
algorithm’s randomness and every loss sequence satisfying the
assumptions.