Hedge's second-order and static-regret bounds

For every $z\ge 0$, [F2] gives $\exp (z)\ge 1+z>0$, so [F3] gives $\exp (-z)\le 1\mathrm{/}(1+z)$. Since $(1-z+z^2)(1+z)=1+z^3\ge 1$ and $1+z>0$, one also has $1\mathrm{/}(1+z)\le 1-z+z^2$. Thus $\exp (-z)\le 1-z+z^2$ for all $z\ge 0$.

Put $S_t={\sum }_{i=1}^N{W}_t(i)$, $m_t={\sum }_i{x}_t(i){\mathrm{\ell }}_t(i)$, and $q_t={\sum }_i{x}_t(i){\mathrm{\ell }}_t(i{)}^2$. By [F3], every factor $\exp (-ϵ{\mathrm{\ell }}_t(i))$ is a positive finite real. Starting with $W_1(i)=1$, [F1] therefore gives positive finite weights through round $T+1$ by induction, so $S_t>0$ is finite and $x_t$ is a probability vector. This induction is pointwise and does not require the loss sequence to be fixed before randomization. Applying step 1.1 to $z=ϵ{\mathrm{\ell }}_t(i)$ and summing with weights $x_t(i)$ gives $S_{t+1}=S_t{\sum }_i{x}_t(i)\exp (-ϵ{\mathrm{\ell }}_t(i))\le S_t(1-ϵm_t+{ϵ}^2{q}_t)\le S_t\exp (-ϵm_t+{ϵ}^2{q}_t)$, where the last inequality is [F2].

Dividing the positive ratios from step 2.1 by $S_t$ and multiplying over $t$, then using [F4] and $S_1=N$, gives $S_{T+1}\le N\exp (-ϵ{\sum }_t{m}_t+{ϵ}^2{\sum }_t{q}_t)$. For any fixed $i^{\star }$, [F1] also gives $S_{T+1}\ge W_{T+1}(i^{\star })=\exp (-ϵ{\sum }_t{\mathrm{\ell }}_t(i^{\star }))$. Since $N=\exp (\log N)$ by [F6], combining the bounds and applying [F5] yields $-ϵ{\sum }_t{\mathrm{\ell }}_t(i^{\star })\le \log N-ϵ{\sum }_t{m}_t+{ϵ}^2{\sum }_t{q}_t$.

Rearranging step 3.1 and dividing by $ϵ>0$ gives ${\sum }_t{m}_t\le {\sum }_t{\mathrm{\ell }}_t(i^{\star })+ϵ{\sum }_t{q}_t+\log (N)\mathrm{/}ϵ$, which is the first assertion.

For losses in $[0,1]$, $q_t\le {\sum }_i{x}_t(i)=1$. Since $[N]$ is finite and nonempty, fix $i^{\star }$ attaining ${\min }_i{\sum }_t{\mathrm{\ell }}_t(i)$. If $N\ge 2$, then $N>1$ and [F7] gives $\log N>\log 1=0$, so $ϵ=\sqrt{\log N\mathrm{/}T}$ is positive; step 4.1 now gives the deterministic mixed-loss regret bound $ϵT+\log N\mathrm{/}ϵ=2\sqrt{T\log N}$. If $N=1$, the only sampled expert is the only comparator, so the static regret is zero.

For each $t$, ${\mathrm{\ell }}_t(I_t)={\sum }_{i=1}^N{\mathrm{\ell }}_t(i){\mathbf{1}}_{\{I_t=i\}}$. By [A1], the entire loss sequence is fixed before randomization; [F11] gives the choice-before-feedback order, and [F1] makes every $x_t$ deterministic from the fixed losses and previous updates. Thus [F8]–[F9] give $\mathbb{E}[{\mathrm{\ell }}_t(I_t)]={\sum }_i{\mathrm{\ell }}_t(i)\mathbb{P}(I_t=i)=m_t$ and $\mathbb{E}[{\sum }_t{\mathrm{\ell }}_t(I_t)]={\sum }_t{m}_t$. The bounded losses are measurable by the algorithm's protocol and integrable by [F12]. Subtracting the deterministic best-expert loss proves the expected static-regret assertion from step 5.1 using [F10].