101 Learning Theory — Convex Prediction
101.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.
101.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 and suppose every expert prediction satisfies \(p_t(i) \in S\) for all \(t\) and \(i\). Then Hedge’s weighted-average prediction \(\widehat{x}_t \in S\) for every round \(t\). The result follows because the Hedge weights are nonnegative and sum to one, so the weighted average is a convex combination of points in \(S\).
Under the same hypotheses as above, assume additionally that for each round \(t\) the map \(x \mapsto \ell (x, o_t)\) is convex on \(S\). Then Jensen’s inequality gives, for every \(t\),
That is, the loss of the averaged prediction is at most the Hedge-weighted average of the individual expert losses.
Summing the per-round Jensen bound over all \(T\) rounds, we obtain
i.e. the actual cumulative loss of Hedge’s convex-combination predictions is at most the abstract cumulative Hedge loss on the induced expert loss table.
Let \(S \subseteq \mathbb {R}\) be convex, \(\eta \gt 0\), and suppose all expert predictions lie in \(S\), each round loss is convex on \(S\), and the induced loss table is valid. Then the regret of Hedge’s actual weighted-average predictions satisfies
The proof combines the cumulative Jensen bound with the abstract tight Hedge regret theorem hedge_regret_bound_tight.
Under the same convexity hypotheses, with \(T \gt 0\), \(N \gt 1\), and the learning rate set to \(\eta ^* = \texttt{optimalEtaTight}\, N\, T\), the regret satisfies