TY - JOUR
T1 - Generalized mixability via entropic duality
AU - Reid, Mark D.
AU - Frongillo, Rafael M.
AU - Williamson, Robert C.
AU - Mehta, Nishant
N1 - Publisher Copyright:
© 2015 M.D. Reid, R.M. Frongillo, R.C. Williamson & N. Mehta.
PY - 2015
Y1 - 2015
N2 - 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 φ-mixability where φ is a general entropy (i.e., 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 which φ have non-trivial φ-mixable losses and relate φ-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.
AB - 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 φ-mixability where φ is a general entropy (i.e., 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 which φ have non-trivial φ-mixable losses and relate φ-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.
KW - Aggregating Algorithm
KW - Convex Analysis
KW - Online Learning
KW - Prediction With Expert Advice
UR - http://www.scopus.com/inward/record.url?scp=84984674681&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:84984674681
SN - 1532-4435
VL - 40
JO - Journal of Machine Learning Research
JF - Journal of Machine Learning Research
IS - 2015
T2 - 28th Conference on Learning Theory, COLT 2015
Y2 - 2 July 2015 through 6 July 2015
ER -