Generalized mixability via entropic duality

Mark D. Reid, Rafael M. Frongillo, Robert C. Williamson, Nishant Mehta

    Research output: Contribution to journalConference articlepeer-review

    7 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    JournalJournal of Machine Learning Research
    Volume40
    Issue number2015
    Publication statusPublished - 2015
    Event28th Conference on Learning Theory, COLT 2015 - Paris, France
    Duration: 2 Jul 20156 Jul 2015

    Fingerprint

    Dive into the research topics of 'Generalized mixability via entropic duality'. Together they form a unique fingerprint.

    Cite this