Online Gradient Descent — Online Convex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Online Convex Optimization · Lean proof
Online Convex Optimization
We consider online convex optimization on a nonempty compact convex
set
The comparison is with the best fixed decision in hindsight, whose
cumulative loss is
Our assumptions:
Assumption 1 (Feasible set). The set
Assumption 2 (Convex losses and bounded gradients).
For every integer
At each round
The required performance concerns the decisions themselves. For a
target bound
Proved result
OracleTemplate.OnlineConvergence LongTails.Setups.OnlineConvexBoundedGradient.spec
OracleTemplate.OnlineGradientDescent.boundRelevant previous results
- Martin Zinkevich. Online
Convex Programming and Generalized Infinitesimal Gradient Ascent.
2003 (ICML). Complexity:
exact-gradient oracle calls, one per round, for deterministic regret using Greedy Projection; its proved bound is , giving with . Equivalently, calls suffice for average regret at most .