98 Learning Theory — Convex Prediction
98.1 Overview
This module develops the convex prediction bridge for the Hedge algorithm. When every expert’s prediction lies in a convex decision set \(S \subseteq \mathbb {R}\) and each round’s loss function is convex on \(S\), Jensen’s inequality shows that the loss of Hedge’s weighted-average prediction is at most Hedge’s abstract expected expert loss; combining this with the abstract Hedge regret theorems yields tight, explicit regret bounds for the real prediction-space problem.
98.2 Declarations
Given a loss function \(\ell : \mathbb {R} \to \Omega \to \mathbb {R}\), expert predictions \(p : \mathrm{Fin}\, T \to \mathrm{Fin}\, N \to \mathbb {R}\), and a sequence of outcomes \(o : \mathrm{Fin}\, T \to \Omega \), the induced loss sequence is the abstract loss table \(L : \mathrm{LossSeq}\, N\, T\) defined by \(L_{t,i} = \ell (p_t(i),\, o_t)\), i.e. expert \(i\) at round \(t\) incurs the loss its own prediction receives under the realized outcome.
At each round \(t \in \mathrm{Fin}\, T\), Hedge’s prediction in the original decision space is the weighted average
where \(w^{(\eta )}_{t,i} = \texttt{hedgeDist}\, \eta \, L\, t\, i\) are the Hedge weights computed from the induced loss table \(L\) up to (but not including) round \(t\), and \(p_t(i)\) is expert \(i\)’s prediction at round \(t\).
The actual cumulative prediction loss of Hedge is
where \(\widehat{x}_t\) is the Hedge weighted-average prediction at round \(t\). This differs from hedgeCumLoss: here the loss is applied to the averaged prediction, not to a weighted average of expert losses.
Let \(S \subseteq \mathbb {R}\) be a convex set, fix any learning rate \(\eta \in \mathbb {R}\), a loss function \(\ell : \mathbb {R}\to \Omega \to \mathbb {R}\), expert predictions \(p_t(i)\), and a sequence of outcomes, and suppose that every expert prediction lies in \(S\), that is \(p_t(i) \in S\) for all rounds \(t\) and all experts \(i\). Then for every round \(t\), Hedge’s weighted-average prediction \(\widehat{x}_t = \sum _{i} w^{(\eta )}_{t,i}\, p_t(i)\) — formed from the Hedge distribution of the loss table induced by \(\ell \), the predictions, and the outcomes up to round \(t\) — again lies in \(S\).
Fix \(N \ge 1\) experts, a horizon of \(T\) rounds, a learning rate \(\eta \in \mathbb {R}\), and a convex set \(S \subseteq \mathbb {R}\). Let \(\ell : \mathbb {R}\times \Omega \to \mathbb {R}\) be a loss function, let \(e_t(i) \in \mathbb {R}\) be expert \(i\)’s prediction at round \(t\), and let \(o_t \in \Omega \) be the outcome at round \(t\); write \(L_{t,i} = \ell (e_t(i), o_t)\) for the induced loss table and let \(q_t(i)\) denote the Hedge distribution over the experts computed from \(L\) at round \(t\). Suppose every prediction \(e_t(i)\) lies in \(S\), and that for each round \(t\) the map \(x \mapsto \ell (x, o_t)\) is convex on \(S\). Then at every round \(t\) the loss of Hedge’s weighted-average prediction \(\widehat{x}_t = \sum _{i} q_t(i)\, e_t(i)\) is at most its expected loss under \(q_t\):
Fix a learning rate \(\eta \in \mathbb {R}\), a loss function \(\ell : \mathbb {R}\to \Omega \to \mathbb {R}\), expert predictions \(p : \mathrm{Fin}\, T \to \mathrm{Fin}\, N \to \mathbb {R}\) (with \(N \ge 1\)), and a sequence of outcomes \(o : \mathrm{Fin}\, T \to \Omega \). Suppose \(S \subseteq \mathbb {R}\) is convex, every expert prediction \(p_t(i)\) lies in \(S\), and for each round \(t\) the map \(x \mapsto \ell (x, o_t)\) is convex on \(S\). Then the cumulative loss of Hedge’s weighted-average predictions is at most the cumulative Hedge loss computed on the induced loss sequence:
where \(\widehat{x}_t = \sum _{i} p_t(i)\, p_t(i)\) is the Hedge weighted-average prediction at round \(t\) and \(p_t\) is the Hedge distribution at that round.
Let \(S \subseteq \mathbb {R}\) be a convex set, let \(\eta \gt 0\) be a learning rate, and consider a prediction problem with \(N \ge 1\) experts over \(T\) rounds, an outcome \(o_t\) at each round \(t\), and a loss function \(\ell (x, o)\). Suppose that every expert prediction \(p_t(i)\) lies in \(S\), that for each round \(t\) the map \(x \mapsto \ell (x, o_t)\) is convex on \(S\), and that the induced loss sequence is valid, so that each expert’s per-round loss \(\ell (p_t(i), o_t)\) lies in \([0,1]\). Then the cumulative loss \(\mathcal{L}^{\mathrm{pred}}_T = \sum _{t} \ell (\widehat{x}_t, o_t)\) of Hedge’s weighted-average predictions \(\widehat{x}_t\) exceeds the best expert loss in hindsight \(L^* = \min _{i} \sum _{t} \ell (p_t(i), o_t)\) by at most
Consider prediction with expert advice using \(N \ge 2\) experts over \(T \ge 1\) rounds, where predictions take values in a convex set \(S \subseteq \mathbb {R}\). Let \(\ell : \mathbb {R}\times \Omega \to \mathbb {R}\) be a loss function, let \(p_t(i) \in S\) be the prediction of expert \(i\) at round \(t\), and let \(o_t \in \Omega \) be the outcome at round \(t\); assume that for every round \(t\) the map \(x \mapsto \ell (x, o_t)\) is convex on \(S\), and that all induced losses \(\ell (p_t(i), o_t)\) lie in \([0,1]\). Run the Hedge algorithm with learning rate \(\eta _{\mathrm{tight}} = \sqrt{8\ln N / T}\), predicting at each round the Hedge weighted average \(\widehat{x}_t = \sum _i p_t(i)\, w_{t}(i) \in S\), where the weights \(w_t\) form the Hedge distribution built from the induced losses through the first \(t\) rounds. Then the cumulative loss of these predictions exceeds the best expert’s loss in hindsight by at most \(\sqrt{\tfrac {T}{2}\ln N}\):