Negative entropy gives normalized multiplicative weights

On $U_n$, differentiating $R(q)={\sum }_{i<n}{q}_i\log q_i+p_n\log p_n$ using [F6, F7, F9] gives ${\mathrm{\partial }}_{i}R=\log q_i+1-(\log p_n+1)=\log (q_i\mathrm{/}{p}_n)$ and ${\mathrm{\nabla }}^{2}R(q)=\mathrm{diag}(1\mathrm{/}{q}_1,\dots ,1\mathrm{/}{q}_{n-1})+\frac{1}{p_n}{\mathbf{11}}^{\mathrm{\top }}$. For every nonzero $v$, $v^{\mathrm{\top }}{\mathrm{\nabla }}^{2}R(q)v={\sum }_{i<n}{v}_i^2\mathrm{/}{q}_i+({\sum }_{i<n}{v}_i{)}^2\mathrm{/}{p}_n>0$. Thus the Hessian is positive definite on $U_n$; together with [F2] and [F10], this verifies the mirror-regularizer conditions for $(K_n,U_n)$ and the validity of the uniform initialization.

Fix an interior iterate $p_t$ and write $r_{t+1}$ for the full probability coordinates of a prospective dual point $y_{t+1}\in U_n$. In independent coordinates the linear loss is $f_t(q)={\mathrm{\ell }}_{t,n}+{\sum }_{i<n}{q}_i({\mathrm{\ell }}_{t,i}-{\mathrm{\ell }}_{t,n})$, a differentiable convex function on all of ${\mathbb{R}}^{n-1}$ with gradient $g_{t,i}={\mathrm{\ell }}_{t,i}-{\mathrm{\ell }}_{t,n}$. By step 1.1, the dual equation [F1] becomes $\log (r_{t+1,i}\mathrm{/}{r}_{t+1,n})=\log (p_{t,i}\mathrm{/}{p}_{t,n})-\eta ({\mathrm{\ell }}_{t,i}-{\mathrm{\ell }}_{t,n})$ for $i<n$.

By [F7, F8], $\exp$ is multiplicative: for real $a,b$, $\log (\exp (a)\exp (b))=a+b=\log (\exp (a+b))$, so injectivity of $\log$ gives $\exp (a+b)=\exp (a)\exp (b)$. Also $\exp (0)=1$ by $\log 1=0$ and [F8], hence $\exp (-b)=1\mathrm{/}\exp (b)$. Any positive normalized solution of step 2.1 therefore satisfies $r_{t+1,i}\mathrm{/}{r}_{t+1,n}=(p_{t,i}\mathrm{/}{p}_{t,n})\exp (-\eta {\mathrm{\ell }}_{t,i})\mathrm{/}\exp (-\eta {\mathrm{\ell }}_{t,n})$. Its coordinates must have the form $c_t{p}_{t,i}\exp (-\eta {\mathrm{\ell }}_{t,i})$ for a common $c_t>0$, and normalization forces $c_t=({\sum }_j{p}_{t,j}\exp (-\eta {\mathrm{\ell }}_{t,j}){)}^{-1}$. Conversely, define $r_{t+1,i}=c_t{p}_{t,i}\exp (-\eta {\mathrm{\ell }}_{t,i})$ by this formula. The denominator is a finite sum of positive finite terms by [F8], so $r_{t+1}$ is positive and normalized. Its first $n-1$ coordinates define $y_{t+1}\in U_n$, and [F7, F8] verify the dual equation in step 2.1. Thus this dual point exists uniquely.

For the interior dual point $y_{t+1}$ constructed in step 3.1, [F4] gives $B_R(q\mathrm{\parallel }{y}_{t+1})\ge \frac{1}{2}\mathrm{\parallel }q-y_{t+1}{\mathrm{\parallel }}_2^2$ for every $q\in K_n$, and the defining Bregman formula gives zero at $q=y_{t+1}$. Hence its unique projection [F3] is $x_{t+1}=y_{t+1}$. In full probability coordinates this says $p_{t+1}=r_{t+1}$, proving the displayed update. Starting from the interior uniform point in step 1.1, this construction applies inductively at every round and keeps all iterates in $U_n$.

At initialization, [F2] and [F10] make the uniform distribution a minimizer of $R$ in $U_n$, so it is a valid OMD initial point. If $p_t(i)=W_t(i)\mathrm{/}{\sum }_j{W}_t(j)$ and $ϵ=\eta$, then [F5] gives $W_{t+1}(i)=W_t(i)\exp (-\eta {\mathrm{\ell }}_{t,i})$, whose normalization is exactly the update proved in step 4.1. Induction from $W_1(i)=1$ proves equality of the OMD and Hedge distributions at every round.