XuanLong Nguyen, Martin J. Wainwright, Michael Jordan
In this paper, we provide a general theorem that establishes a correspon- dence between surrogate loss functions in classiﬁcation and the family of f-divergences. Moreover, we provide constructive procedures for determining the f-divergence induced by a given surrogate loss, and conversely for ﬁnding all surrogate loss functions that realize a given f-divergence. Next we introduce the notion of universal equivalence among loss functions and corresponding f-divergences, and provide nec- essary and sufﬁcient conditions for universal equivalence to hold. These ideas have applications to classiﬁcation problems that also involve a com- ponent of experiment design; in particular, we leverage our results to prove consistency of a procedure for learning a classiﬁer under decen- tralization requirements.