Timezone: »
We formalize and study the natural approach of designing convex surrogate loss functions via embeddings for problems such as classification or ranking. In this approach, one embeds each of the finitely many predictions (e.g. classes) as a point in \reals^d, assigns the original loss values to these points, and convexifies the loss in some way to obtain a surrogate. We prove that this approach is equivalent, in a strong sense, to working with polyhedral (piecewise linear convex) losses. Moreover, given any polyhedral loss L, we give a construction of a link function through which L is a consistent surrogate for the loss it embeds. We go on to illustrate the power of this embedding framework with succinct proofs of consistency or inconsistency of various polyhedral surrogates in the literature.
Author Information
Jessica Finocchiaro (University of Colorado Boulder)
Rafael Frongillo (CU Boulder)
Bo Waggoner (U. Colorado, Boulder)
More from the Same Authors
-
2021 : Efficient Competitions and Online Learning with Strategic Forecasters »
Anish Thilagar · Rafael Frongillo · Bo Waggoner · Robert Gomez -
2021 : Learning in Matrix Games can be Arbitrarily Complex »
Gabriel Andrade · Rafael Frongillo · Georgios Piliouras -
2021 : Efficient Competitions and Online Learning with Strategic Forecasters »
Anish Thilagar · Rafael Frongillo · Bo Waggoner · Robert Gomez -
2021 : Learning in Matrix Games can be Arbitrarily Complex »
Gabriel Andrade · Rafael Frongillo · Georgios Piliouras -
2021 : Spotlight 3: Efficient Competitions and Online Learning with Strategic Forecasters »
Anish Thilagar · Rafael Frongillo · Bo Waggoner · Robert Gomez -
2021 Poster: Surrogate Regret Bounds for Polyhedral Losses »
Rafael Frongillo · Bo Waggoner -
2021 Poster: Unifying lower bounds on prediction dimension of convex surrogates »
Jessica Finocchiaro · Rafael Frongillo · Bo Waggoner -
2019 Poster: Equal Opportunity in Online Classification with Partial Feedback »
Yahav Bechavod · Katrina Ligett · Aaron Roth · Bo Waggoner · Steven Wu -
2019 Poster: Toward a Characterization of Loss Functions for Distribution Learning »
Nika Haghtalab · Cameron Musco · Bo Waggoner -
2018 Poster: Convex Elicitation of Continuous Properties »
Jessica Finocchiaro · Rafael Frongillo -
2018 Spotlight: Convex Elicitation of Continuous Properties »
Jessica Finocchiaro · Rafael Frongillo -
2018 Poster: Bounded-Loss Private Prediction Markets »
Rafael Frongillo · Bo Waggoner -
2018 Spotlight: Bounded-Loss Private Prediction Markets »
Rafael Frongillo · Bo Waggoner