187 Learning Theory — Regret

187.1 Overview

This module proves the no-regret guarantees for the Hedge algorithm in the expert setting via the potential argument of Cesa-Bianchi–Lugosi (Thm. 2.2) and Freund–Schapire: a per-round bound on the change of the log potential \(\log W_{t+1} - \log W_t\) is telescoped over the \(T\) rounds and combined with the lower bound \(W_T \ge e^{-\eta \, \mathrm{bestExpertLoss}}\) to give \(\mathrm{regret} \le (\log N)/\eta + cT/\eta \). It also contains the elementary balancing identity behind the optimized learning rates \(\eta = \sqrt{c \log N / T}\).

187.2 Declarations

Lemma 187.1 Telescoping of the log potential

✓

Let \(\eta \in \mathbb {R}\) and let \(\ell \) be a loss sequence for \(N\) experts over \(T\) rounds, with potential \(W_t = \texttt{potential}\ \eta \ \ell \ t\). Then the one-step changes of the log potential telescope:

\[ \sum _{t=0}^{T-1} \bigl(\log W_{t+1} - \log W_t\bigr) \; =\; \log W_T - \log W_0 . \]

Lemma 187.2 Regret from a per-step log-potential bound

✓

Let \(N \ge 1\), let \(\eta \gt 0\), let \(\ell \) be a loss sequence for \(N\) experts over \(T\) rounds, and let \(c \in \mathbb {R}\). Suppose that for every round \(t \lt T\) the log potential satisfies the one-step bound

\[ \log W_{t+1} - \log W_t \; \le \; -\eta \cdot \mathrm{hedgeLoss}_t + c , \]

where \(\mathrm{hedgeLoss}_t\) is the expected loss of Hedge in round \(t\). Then the regret of Hedge is bounded by

\[ \mathrm{regret}(\eta ,\ell ) \; \le \; \frac{\log N}{\eta } + \frac{c\, T}{\eta } . \]

Lemma 187.3 Balancing the two terms of a Hedge bound

✓

For real numbers \(a, T, c \gt 0\), at the learning rate \(\eta = \sqrt{c a / T}\) the two terms \(a/\eta \) and \(\eta T / c\) sum to \(\sqrt{4 a T / c}\):

\[ \frac{a}{\sqrt{ca/T}} + \frac{\sqrt{ca/T}\; T}{c} \; =\; \sqrt{\frac{4 a T}{c}} . \]