Online convex learning and regret

Let K be a nonempty closed convex subset of a finite-dimensional Euclidean space. On round t the learner chooses w_t in K before receiving the current loss function or its subgradient feedback. The revealed loss is convex on K, and the learner incurs its value at w_t. Static regret is cumulative incurred loss minus the smallest cumulative loss of a single fixed comparator in K. The comparator sees the whole realized sequence when selected in hindsight, but it must use one decision for every round.

Regret does not compare to a different optimal point on every round; that stronger dynamic comparator needs additional restrictions on how the environment changes. Nor does a small average regret assert that each individual round has small loss. A pathwise convex-gradient proof can handle adversarially chosen losses, provided the learner’s update uses only available feedback and the stated gradient bounds hold along the actual sequence. An independent-data generalization conclusion is a later, separate step.

Fix a comparator u. Nonexpansiveness of Euclidean projection shows that the next squared distance to u is at most the squared distance before projection. Expand that square and rearrange to bound the gradient inner product by a distance decrease divided by twice eta plus eta times squared gradient norm divided by two. Convexity bounds the current loss difference by that same gradient inner product. Summing over t makes the distance decreases telescope, leaving only the initial distance and the sum of gradient squares.

If K has diameter at most D and each chosen subgradient has norm at most G, the resulting regret is at most D squared over twice eta plus eta G squared T over two. For positive D and G and a known horizon T, choose eta=D/(Gsqrt(T)) to obtain DGsqrt(T). Degenerate zero-diameter or zero-gradient cases are handled directly rather than by dividing by zero. Unknown horizons need an adaptive schedule or a doubling argument; the fixed-horizon choice is not available before T is specified.

Suppose the online losses are generated from iid examples and w_t depends only on earlier observations. Then the current example is independent of w_t, so expected incurred loss equals expected population risk at w_t. If population loss is convex in the decision, averaging the iterates stays in K and Jensen bounds its risk by the average iterate risks. An expected regret bound relative to a fixed population comparator can therefore yield expected excess risk of the averaged decision at most regret divided by T.

This conversion is an expectation statement and needs its own measurability and integrability assumptions. A high-probability online-to-batch guarantee requires an additional concentration argument; an adversarial pathwise regret statement alone is not an iid test-risk theorem. Finally, averaging parameters need not preserve predictions in a nonconvex model or a nonconvex constraint set. The simple interval example below verifies the online arithmetic directly, while keeping these population conclusions conditional on their additional assumptions.