Generalized Mixability via Entropic Duality
Journal of Machine Learning Research , Volume 40 - Issue 28 p. 1- 22
Mixability is a property of a loss which characterizes when constant regret 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 so we introduce a more general notion of $\Phi$-mixability where $\Phi$ 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 $\Phi$-mixable losses. We characterize which $\Phi$ have non-trivial $\Phi$-mixable losses and relate $\Phi$-mixability and its associated Aggregating Algorithm to potential-based methods, a Blackwell-like condition, mirror descent, and risk measures from finance. We also define a notion of ``dominance'' between different entropies in terms of bounds they guarantee and conjecture that classical mixability gives optimal bounds, for which we provide some supporting empirical evidence.
|online learning, prediction with expert advice, convex analysis, aggregating algorithm|
|Information (theme 2)|
|P.D. Grünwald (Peter) , E. Hazan , S. Kale|
|Journal of Machine Learning Research|
|Annual Conference on Learning Theory|
|Organisation||Algorithms and Complexity|
Reid, M.D, Frongillo, R.M, Williamson, R.C, & Mehta, N.A. (2015). Generalized Mixability via Entropic Duality. In P.D Grünwald, E Hazan, & S Kale (Eds.), Journal of Machine Learning Research (Vol. 40, pp. 1–22). MIT Press.