Matrix multiplicative-weights regret bound

Put $Z_t=\mathrm{tr}(e^{-\eta S_t})$ and $m_t=\mathrm{tr}(M_t{\rho }_t)$. By [F5], write $M_t=U\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)U^{\ast }$; the loss bounds imply ${\lambda }_k\in [-1,1]$. The matrix $\sigma =U^{\ast }{\rho }_{t}U$ is positive with trace one by [F1] and [F7]. Thus $q_k={\sigma }_{kk}\ge 0$ and ${\sum }_k{q}_k=1$. Trace cyclicity and the diagonal-sum formula give $m_t={\sum }_k{\lambda }_k{q}_k\in [-1,1]$, consistently with [F6]. Hence $1-\eta m_t+{\eta }^2\ge 1-\eta +{\eta }^2=(\eta -1\mathrm{/}2{)}^2+3\mathrm{/}4>0$. Since $S_t$ is Hermitian, Golden–Thompson [F3] gives $Z_t\le \mathrm{tr}(e^{-\eta S_{t-1}}{e}^{-\eta M_t})$. By [F2], $(I-\eta M_t+{\eta }^{2}I)-e^{-\eta M_t}⪰0$; [F4] compares its trace product with the positive matrix $e^{-\eta S_{t-1}}$, and [F9] expands the result as $Z_t\le Z_{t-1}(1-\eta m_t+{\eta }^2)$. Put $s=-\eta m_t+{\eta }^2$, so $s\ge {\eta }^2-\eta \ge -1\mathrm{/}4$. If $s\ge 0$, the series [F8] gives $\exp (s)\ge 1+s$. If $s=-v$ with $0<v\le 1\mathrm{/}4$, absolute convergence [F8] permits pairing the tail after its linear term as ${\sum }_{j\ge 0}\frac{v^{2j+2}}{(2j+2)!}(1-\frac{v}{2j+3})\ge 0$, so again $\exp (s)\ge 1+s$. Therefore $Z_t\le Z_{t-1}\exp (-\eta m_t+{\eta }^2)$.

Iterating step 1.1 from $Z_0=n$ gives $Z_T\le n\exp (-\eta {\sum }_t{m}_t+{\eta }^{2}T)$. If $S_T$ has eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$, [F5] gives $Z_T={\sum }_k{e}^{-\eta {\lambda }_k}\ge \exp (-\eta {\lambda }_{\min }(S_T))$. Since $n>0$, [F10]–[F11] give $n\exp (-\eta {\sum }_t{m}_t+{\eta }^{2}T)=\exp (\ln n-\eta {\sum }_t{m}_t+{\eta }^{2}T)$. Strict increase of $\exp$ and the inverse relation in [F10] therefore imply $-\eta {\lambda }_{\min }(S_T)\le \ln n-\eta {\sum }_t{m}_t+{\eta }^{2}T$. Rearranging and dividing by $\eta >0$ proves the inequality.