← All setups

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 K⊆Rd, where d≥0 is an integer. The set has diameter at most D>0, and a point x0∈K is given. Each loss ft:Rd→R is convex on K and differentiable at every point of K, with gradient norm at most G>0. At round t, the oracle returns ∇ft(xt) at the chosen point xt∈K. Over T≥1 rounds, the goal is ∑t=0T−1[ft(xt)−ft(u)]≤B for every u∈K and every realization of algorithm randomness, where B∈R is the target regret bound.

The comparison is with the best fixed decision in hindsight, whose cumulative loss is minu∈K∑t=0T−1ft(u). Throughout, ∥⋅∥ denotes the Euclidean norm. The algorithm receives d, K, x0, D, G, and the integer horizon T; the loss sequence is accessed through the oracle.

Our assumptions:

Assumption 1 (Feasible set). The set K is compact and convex, contains the given point x0, and satisfies ∥x−y∥≤D,x,y∈K.

Assumption 2 (Convex losses and bounded gradients). For every integer t≥0, the function ft is differentiable in the ambient space at every x∈K. For every x,y∈K and λ∈[0,1], ft((1−λ)x+λy)≤(1−λ)ft(x)+λft(y),∥∇ft(x)∥≤G.

At each round t=0,…,T−1, the algorithm chooses xt∈K using its randomness and previous oracle replies. The oracle returns ∇ft(xt) at xt. Thus there are exactly T gradient queries, one for each successive loss. The given point x0 is available to the algorithm; its first decision x0 is chosen by the algorithm.

The required performance concerns the decisions themselves. For a target bound B, which may depend on d,K,x0,D,G, and T, they must satisfy ∑t=0T−1ft(xt)−∑t=0T−1ft(u)≤B,for every u∈K, for every realization of the algorithm’s randomness and every loss sequence satisfying the assumptions.

Proved result

D⋅G⋅T

OracleTemplate.OnlineConvergence LongTails.Setups.OnlineConvexBoundedGradient.spec
  OracleTemplate.OnlineGradientDescent.bound

Relevant previous results

  • Martin Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. 2003 (ICML). Complexity: O(T) exact-gradient oracle calls, one per round, for deterministic regret O(DGT) using Greedy Projection; its proved bound is D2/(2ηT)+(G2/2)∑t=1Tηt, giving DGT with ηt=D/(GT). Equivalently, O(1+D2G2/ε2) calls suffice for average regret at most ε>0.