TY - JOUR
T1 - Exp-concavity of proper composite losses
AU - Kamalaruban, Parameswaran
AU - Williamson, Robert C.
AU - Zhang, Xinhua
N1 - Publisher Copyright:
© 2015 P. Kamalaruban, R.C. Williamson & X. Zhang.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Aggregating Algorithm
KW - Composite Losses
KW - Exp-Concavity
KW - Link Functions
KW - Mixability
KW - Proper Scoring Rules
KW - Regret Bound
KW - Sequential Prediction
KW - Substitution Functions
KW - Weighted Average Algorithm
UR - http://www.scopus.com/inward/record.url?scp=84962312533&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:84962312533
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 -