Exp-concavity of proper composite losses

Parameswaran Kamalaruban, Robert C. Williamson, Xinhua Zhang

    Research output: Contribution to journalConference articlepeer-review

    3 Citations (Scopus)

    Abstract

    The goal of online prediction with expert advice is to find a decision strategy which will perform almost as well as the best expert in a given pool of experts, on any sequence of outcomes. This problem has been widely studied and O(√T) and O(log T) regret bounds can be achieved for convex losses (Zinkevich (2003)) and strictly convex losses with bounded first and second derivatives (Hazan et al. (2007)) respectively. In special cases like the Aggregating Algorithm (Vovk (1995)) with mixable losses and the Weighted Average Algorithm (Kivinen and Warmuth (1999)) with exp-concave losses, it is possible to achieve O(1) regret bounds. van Erven (2012) has argued that mixability and exp-concavity are roughly equivalent under certain conditions. Thus by understanding the underlying relationship between these two notions we can gain the best of both algorithms (strong theoretical performance guarantees of the Aggregating Algorithm and the computational efficiency of theWeighted Average Algorithm). In this paper we provide a complete characterization of the exp-concavity of any proper composite loss. Using this characterization and the mixability condition of proper losses (Van Erven et al. (2012)), we show that it is possible to transform (reparameterize) any β-mixable binary proper loss into a β-exp-concave composite loss with the same β. In the multi-class case, we propose an approximation approach for this transformation.

    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 'Exp-concavity of proper composite losses'. Together they form a unique fingerprint.

    Cite this