Timezone: »
Surrogate risk minimization is an ubiquitous paradigm in supervised machine learning, wherein a target problem is solved by minimizing a surrogate loss on a dataset. Surrogate regret bounds, also called excess risk bounds, are a common tool to prove generalization rates for surrogate risk minimization. While surrogate regret bounds have been developed for certain classes of loss functions, such as proper losses, general results are relatively sparse. We provide two general results. The first gives a linear surrogate regret bound for any polyhedral (piecewise-linear and convex) surrogate, meaning that surrogate generalization rates translate directly to target rates. The second shows that for sufficiently non-polyhedral surrogates, the regret bound is a square root, meaning fast surrogate generalization rates translate to slow rates for the target. Together, these results suggest polyhedral surrogates are optimal in many cases.
Author Information
Rafael Frongillo (University of Colorado Boulder)
Bo Waggoner
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: Unifying lower bounds on prediction dimension of convex surrogates »
Jessica Finocchiaro · Rafael Frongillo · Bo Waggoner -
2019 Poster: An Embedding Framework for Consistent Polyhedral Surrogates »
Jessica Finocchiaro · Rafael Frongillo · 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 -
2017 Poster: Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM »
Katrina Ligett · Seth Neel · Aaron Roth · Bo Waggoner · Steven Wu