Generalised Mixability, Constant Regret, and Bayesian Updating
This work provides a theoretical extension for prediction algorithms, but it is incremental as it builds on existing mixability and aggregating algorithm frameworks.
The paper tackles the problem of achieving constant regret bounds in prediction with expert advice by generalizing the concept of mixability through convex analysis, replacing the Kullback-Leibler divergence with Bregman divergences, and proves that this generalization maintains constant regret bounds.
Mixability of a loss is known to characterise when constant regret bounds are achievable in games of prediction with expert advice through the use of Vovk's aggregating algorithm. We provide a new interpretation of mixability via convex analysis that highlights the role of the Kullback-Leibler divergence in its definition. This naturally generalises to what we call $Φ$-mixability where the Bregman divergence $D_Φ$ replaces the KL divergence. We prove that losses that are $Φ$-mixable also enjoy constant regret bounds via a generalised aggregating algorithm that is similar to mirror descent.