Generalized Mixability via Entropic Duality
This work provides a theoretical extension for online learning algorithms, potentially broadening applicability but is incremental in nature.
The paper generalizes the concept of mixability in prediction with expert advice by introducing Φ-mixability based on any convex entropy function, showing that constant regret is achievable with a natural algorithm derived from this framework.
Mixability is a property of a loss which characterizes when fast convergence is possible in the game of prediction with expert advice. We show that a key property of mixability generalizes, and the exp and log operations present in the usual theory are not as special as one might have thought. In doing this we introduce a more general notion of $Φ$-mixability where $Φ$ is a general entropy (\ie, any convex function on probabilities). We show how a property shared by the convex dual of any such entropy yields a natural algorithm (the minimizer of a regret bound) which, analogous to the classical aggregating algorithm, is guaranteed a constant regret when used with $Φ$-mixable losses. We characterize precisely which $Φ$ have $Φ$-mixable losses and put forward a number of conjectures about the optimality and relationships between different choices of entropy.