Hedge and online gradient descent

Let $N,T\ge 1$ be integers, let $[N]=\{1,\dots ,N\}$ be the expert set, and let $ϵ>0$. At each round $t=1,\dots ,T$, a finite loss vector ${\mathrm{\ell }}_t=({\mathrm{\ell }}_t(1),\dots ,{\mathrm{\ell }}_t(N))\in [0,\mathrm{\infty }{)}^N$ is revealed after the learner's choice. Initialize $W_1(i)=1$ for every $i\in [N]$. At round $t$, set $x_t(i):=\frac{W_t(i)}{{\sum }_{j=1}^N{W}_t(j)},i\in [N],$ Let ${\mathcal{H}}_{t-1}$ be the pre-round history sigma-algebra generated by the previously played choices and all previously revealed loss vectors (any random loss vector is assumed measurable on the protocol's probability space). The weights and $x_t$ are ${\mathcal{H}}_{t-1}$-measurable. Draw a measurable expert choice $I_t\in [N]$ with conditional distribution $\mathbb{P}(I_t=i\mid {\mathcal{H}}_{t-1})=x_t(i)\text{almost surely},i\in [N],$ and play $I_t$. After observing the whole vector ${\mathrm{\ell }}_t$, update $W_{t+1}(i):=W_t(i)\exp (-ϵ{\mathrm{\ell }}_t(i)),i\in [N]\mathrm{.}$ The output is the distributions $x_1,\dots ,x_T$, the sampled choices $I_1,\dots ,I_T$, and the final weights. The protocol assumes a probability space carrying the stated measurable draws; no probability-space construction is claimed.

Online decision protocol: the learner chooses before current-round feedback and its randomized choices are measurable.

Adversary and feedback models: full-information feedback reveals the entire expert-loss vector after the learner's choice.

Random elements and real random variables: each sampled expert is a measurable finite-valued random element.

The real exponential function and the number $e$ by a power series: the update uses the real exponential function.

Hedge's second-order and static-regret bounds ↗: proof step 2.1 establishes positive finite weights and normalizers by induction for every finite nonnegative loss sequence, independently of the fixed-loss assumption used later for expected regret.

Let $d,T\ge 1$ be integers, let $K\subseteq {\mathbb{R}}^d$ be nonempty, closed, and convex, and let $D,G\ge 0$ be finite real bounds such that $\mathrm{\parallel }u-v{\mathrm{\parallel }}_2\le D$ for all $u,v\in K$ and $\mathrm{\parallel }{g}_t{\mathrm{\parallel }}_2\le G$. Supply an initial point $x_1\in K$. At each round $t=1,\dots ,T$, the learner plays $x_t$ and then receives the full loss function $f_t$ or the prescribed vector $g_t$. The smooth branch takes $f_t:U_t\to \mathbb{R}$ differentiable and convex on an open convex set $U_t\supseteq K$, with $g_t=\mathrm{\nabla }{f}_t(x_t)$. The nonsmooth branch takes a convex function $f_t:C_t\to \mathbb{R}$ on a convex set $C_t\supseteq K$ and a supplied $g_t\in \mathrm{\partial }{f}_t(x_t)$, where $\mathrm{\partial }{f}_t(x_t)$ consists of vectors $g$ satisfying $f_t(y)\ge f_t(x_t)+⟨g,y-x_t⟩$ for every $y\in C_t$; require explicitly that this inequality holds for every $u\in K$.

If $D=0$ or $G=0$, set $x_{t+1}=x_t$ at every round. If $D,G>0$, assume the Axiom of Countable Choice for the metric projection. Set ${\eta }_t=D\mathrm{/}(G\sqrt{t})$, put $y_{t+1}=x_t-{\eta }_t{g}_t$, and set $x_{t+1}=P_K(y_{t+1})$, the unique point of $K$ minimizing Euclidean distance to $y_{t+1}$. Return the decisions $x_1,\dots ,x_T$. Equip ${\mathbb{R}}^d$ with its Euclidean Borel $\sigma$-algebra and $K$ with the relative Borel $\sigma$-algebra. For random inputs, require $x_1$ to be a measurable $K$-valued random element and each $g_t$, whether supplied directly or computed as $\mathrm{\nabla }{f}_t(x_t)$ in the smooth branch, to be a measurable ${\mathbb{R}}^d$-valued random element on the protocol's probability space. The vector update is continuous, and the nonexpansive projection is continuous, so each projected update remains measurable.

Online decision protocol: the learner plays before receiving current-round feedback.

Adversary and feedback models: full-information feedback reveals the current loss function after the choice.

Random elements and real random variables: randomized decisions and gradient inputs are measurable random elements.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the inner product and norm on ${\mathbb{R}}^d$ are the standard Euclidean ones.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: open neighborhoods and closed decision sets are taken in the Euclidean metric topology.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: a convex decision set contains the segment between any two of its points.

Convex and strictly convex functions on Euclidean convex sets: convexity of a loss on its domain.

Differentiable convex functions are characterized by the gradient inequality: on an open convex domain, differentiable convex losses satisfy the gradient inequality.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\mathrm{\nabla }{f}_t(x_t)$ is the vector of scalar partial derivatives in the standard Euclidean coordinates.

Subgradients and the subdifferential of a convex function: the nonsmooth subgradient is a vector satisfying the stated supporting inequality on the function's domain.

The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$): Countable Choice is assumed only in the nondegenerate branch that invokes projection existence.

Hilbert space: a real Hilbert space is a complete real inner-product space.

$\mathbb{R}$ and ${\mathbb{R}}^n$ for $n\ge 1$ with the Euclidean metric are complete, componentwise from the Cauchy criterion in $\mathbb{R}$: ${\mathbb{R}}^d$ with its Euclidean metric is complete for $d\ge 1$.

Projection onto a nonempty closed convex set: under Countable Choice, each point of a real Hilbert space has a unique nearest point in a nonempty closed convex set.

The metric projection onto a closed convex set is nonexpansive: the metric projection is nonexpansive and therefore continuous.

Let $N,T\ge 1$ be integers and let $ϵ>0$. Let ${\mathrm{\ell }}_t(i)\ge 0$ be a finite real loss for every $t\in \{1,\dots ,T\}$ and $i\in [N]=\{1,\dots ,N\}$. Run Hedge with $W_1(i)=1$, $x_t(i)=W_t(i)\mathrm{/}{\sum }_{j=1}^N{W}_t(j)$, measurable draws $I_t$ satisfying $\mathbb{P}(I_t=i)=x_t(i)$, and updates $W_{t+1}(i)=W_t(i)\exp (-ϵ{\mathrm{\ell }}_t(i))$. Assume the entire loss-vector sequence is fixed before the learner's random choices. For every fixed expert $i^{\star }\in [N]$, writing ${\mathrm{\ell }}_t^{(2)}(i)={\mathrm{\ell }}_t(i{)}^2$, one has

where $\log$ is the natural logarithm.

If every loss lies in $[0,1]$ and $N\ge 2$, choosing $ϵ=\sqrt{\log N\mathrm{/}T}$ gives expected static regret at most $2\sqrt{T\log N}$:

For $N=1$, the expected static regret is $0$.

Hedge: the initial weights, normalized expert probabilities, sampled actions, and exponential update.

Online decision protocol: the learner chooses before current-round feedback.

Adversary and feedback models: full-information feedback and an oblivious loss sequence.

Static, dynamic, interval, and strongly adaptive regret: realized and expected static regret against a fixed comparator.

Expectation of a nonnegative or integrable random variable: expectation as a Lebesgue integral for bounded sampled losses.

The natural logarithm as the inverse of the exponential function: the natural logarithm is the inverse of the real exponential.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is strictly increasing and $\log 1=0$.

Let $d,T\ge 1$ be integers, let $K\subseteq {\mathbb{R}}^d$ be nonempty, closed, and convex, and let $D,G\ge 0$ be finite bounds such that $\mathrm{\parallel }u-v{\mathrm{\parallel }}_2\le D$ for all $u,v\in K$ and $\mathrm{\parallel }{g}_t{\mathrm{\parallel }}_2\le G$ for every round. Supply $x_1\in K$. On each round, either $f_t$ is differentiable and convex on an open convex neighborhood of $K$ and $g_t=\mathrm{\nabla }{f}_t(x_t)$, or $f_t:C_t\to \mathbb{R}$ is convex on a convex set $C_t\supseteq K$ and a vector $g_t\in \mathrm{\partial }{f}_t(x_t)$ is supplied with $f_t(u)\ge f_t(x_t)+⟨g_t,u-x_t⟩$ explicitly required for every $u\in K$; here $\mathrm{\partial }{f}_t(x_t)$ is the set of vectors satisfying that supporting inequality for every point of $C_t$. Run projected online gradient descent with ${\eta }_t=D\mathrm{/}(G\sqrt{t})$ when $D,G>0$, and with the no-op branch $x_{t+1}=x_t$ if $D=0$ or $G=0$. Assume the Axiom of Countable Choice only when $D,G>0$. For every realization satisfying these hypotheses and every $u\in K$, ${\sum }_{t=1}^T(f_t(x_t)-f_t(u))\le \frac{3}{2}DG\sqrt{T}\mathrm{.}$ If $D=0$ or $G=0$, this sum is nonpositive. Whenever the finite-horizon loss sum attains a finite minimum on $K$, the static regret, defined as ${\sum }_{t=1}^T{f}_t(x_t)-{\min }_{u\in K}{\sum }_{t=1}^T{f}_t(u)$, is therefore at most $\frac{3}{2}DG\sqrt{T}$.

Projected online gradient descent: the projected update and its degenerate branches.

Static, dynamic, interval, and strongly adaptive regret: static regret uses a finite attained minimum.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: open neighborhoods and closed subsets are understood in the Euclidean metric topology.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: convex sets contain the segment between any two points.

Convex and strictly convex functions on Euclidean convex sets: convexity of a real-valued function on its domain.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient is the vector of scalar partial derivatives in Euclidean coordinates.

Subgradients and the subdifferential of a convex function: the subdifferential consists of vectors satisfying the supporting inequality on the function's domain.

The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$): Countable Choice is used only for projection existence in the nondegenerate branch.

Projection onto a nonempty closed convex set: a nonempty closed convex subset of a real Hilbert space has a unique nearest point under Countable Choice.

Metric projection onto a closed convex set satisfies the variational inequality: the metric projection satisfies the Euclidean variational inequality.

The metric projection onto a closed convex set is nonexpansive: the metric projection is continuous.

Differentiable convex functions are characterized by the gradient inequality: the smooth branch satisfies the comparator inequality.