Fix \(N \ge 1\) experts, a horizon \(T\), and a loss sequence \(\ell \) over these experts and rounds, and let \(\eta \in \mathbb {R}\) be a learning rate. At time \(0\) every expert has zero cumulative loss, so each unnormalized Hedge weight equals \(1\), and the potential is

Fix a learning rate \(\eta \in \mathbb {R}\), a loss sequence \(\ell \) for \(N\) experts over \(T\) rounds, a time \(t\), and an expert \(i\). Then the unnormalized Hedge weight \(w_t(i) = \exp \! \bigl(-\eta \cdot L_t(i)\bigr)\), where \(L_t(i) = \sum _{s \lt t} \ell _s(i)\) is the cumulative loss of expert \(i\) through the first \(t\) rounds, is strictly positive.

Fix a learning rate \(\eta \in \mathbb {R}\), a loss sequence \(\ell \) for \(N \ge 1\) experts over \(T\) rounds, and a time \(t\). Then the potential at time \(t\) is strictly positive:

where \(L_t(i) = \sum _{s \lt t} \ell _s(i)\) is the cumulative loss of expert \(i\) through the first \(t\) rounds.

For every \(\eta \gt 0\) and every \(x \in [0,1]\), the value \(e^{-\eta x}\) lies below the chord joining the endpoints of the graph of \(t \mapsto e^{-\eta t}\) over \([0,1]\); that is, the inequality

holds, the right-hand side being the affine function equal to \(1\) at \(x = 0\) and to \(e^{-\eta }\) at \(x = 1\).

Let \(\ell \) be a loss sequence for \(N\) experts over \(T\) rounds, and write \(L_t(i) = \sum _{s \lt t} \ell _s(i)\) for the cumulative loss of expert \(i\) through the first \(t\) rounds. Then for every round \(t \lt T\) and every expert \(i\),

Fix \(N\) experts and a horizon \(T\), and let \(\ell \) be a loss sequence assigning to each round \(t\) and expert \(i\) a real loss \(\ell _t(i)\). For every expert \(i\), the cumulative loss through the first \(T\) rounds equals the total loss over all rounds: \(L_T(i) = \sum _{t} \ell _t(i)\), where \(t\) ranges over all \(T\) rounds.

Fix a learning rate \(\eta \in \mathbb {R}\) and a loss sequence \(\ell \) for \(N\) experts over \(T\) rounds. For every round \(t \in \mathrm{Fin}\, T\) and every expert \(i \in \mathrm{Fin}\, N\), the unnormalized Hedge weights satisfy

Fix a number of experts \(N \ge 1\), a horizon \(T\), a learning rate \(\eta \in \mathbb {R}\), a loss sequence \(\ell \) for \(N\) experts over \(T\) rounds, and a round \(t\). Then the Hedge distribution at round \(t\) sums to one over all experts,

so it is a probability distribution on the \(N\) experts.

Fix \(N \ge 1\) experts, a horizon of \(T\) rounds, a learning rate \(\eta \gt 0\), and a valid loss sequence \(\ell \). Then for every round \(t\) with \(t \lt T\), the consecutive potentials satisfy

where \(\widehat{\ell }_t = \sum _{i=1}^{N} p_t(i)\, \ell _t(i)\) is the expected loss of the learner under the Hedge distribution at round \(t\).

Fix \(N \ge 1\) experts and \(T\) rounds, a learning rate \(\eta \gt 0\), and a valid loss sequence \(\ell \), so that \(0 \le \ell _t(i) \le 1\) for every round \(t\) and expert \(i\). Writing \(W_t = \sum _{i=1}^N \exp \! \bigl(-\eta L_t(i)\bigr)\) for the Hedge potential and \(\widehat{\ell }_t = \sum _{i=1}^N p_t(i)\, \ell _t(i)\) for the expected loss under the Hedge distribution, the one-round change in log-potential is controlled by the expected loss: for each round \(t\),

For every real number \(t \ge 0\), the value \(e^{-t}\) is at most the second-order Taylor polynomial \(1 - t + t^2/2\); that is,

For every real number \(\eta \gt 0\), the quantity \(1 - e^{-\eta }\) is bounded below by its second-order Taylor expansion at the origin:

Fix \(N \ge 1\) experts and \(T\) rounds, a loss sequence \(\ell \), and a learning rate \(\eta \gt 0\). Then the final potential is at least the unnormalized Hedge weight of the best expert in hindsight:

where \(L^* = \min _{i} L_T(i)\) is the smallest cumulative loss over the full horizon \(T\).

Fix \(N \ge 1\) experts and \(T\) rounds, a learning rate \(\eta \in \mathbb {R}\), and a loss sequence \(\ell \). For every time \(t\) and every expert \(i\), the Hedge distribution is nonnegative, that is, \(p_t(i) \ge 0\).

Fix a learning rate \(\eta \in \mathbb {R}\), and let \(\ell \) be a valid loss sequence for \(N \ge 1\) experts over \(T\) rounds, so that \(0 \le \ell _t(i) \le 1\) for every round \(t\) and expert \(i\). Then at each round \(t\) the expected loss of the learner under the Hedge distribution satisfies \(\widehat{\ell }_t \le 1\).

Let \(\ell \) be a valid loss sequence for \(N \ge 1\) experts over \(T\) rounds, fix any learning rate \(\eta \in \mathbb {R}\), and let \(t\) be one of the rounds. Then the learner’s expected loss \(\widehat{\ell }_t = \sum _{i=1}^{N} p_t(i)\, \ell _t(i)\) under the Hedge distribution is nonnegative, \(\widehat{\ell }_t \ge 0\).

Let \(p \in [0,1]\) and let \(h \in \mathbb {R}\) be arbitrary. Then

Fix \(N \ge 1\) experts and a learning rate \(\eta \gt 0\), and let \(\ell \) be a valid loss sequence over \(T\) rounds, so that every individual loss satisfies \(0 \le \ell _t(i) \le 1\). Write \(W_t = \sum _{i=1}^{N} \exp (-\eta L_t(i))\) for the Hedge potential after \(t\) rounds, and \(\widehat{\ell }_t\) for the expected loss of the learner at round \(t\) under the Hedge distribution. Then for every round \(t\) (with \(0 \le t \lt T\)),