Timezone: »
Poster
Unifying lower bounds on prediction dimension of convex surrogates
Jessica Finocchiaro · Rafael Frongillo · Bo Waggoner
The convex consistency dimension of a supervised learning task is the lowest prediction dimension $d$ such that there exists a convex surrogate $L : \mathbb{R}^d \times \mathcal Y \to \mathbb R$ that is consistent for the given task. We present a new tool based on property elicitation, $d$-flats, for lower-bounding convex consistency dimension. This tool unifies approaches from a variety of domains, including continuous and discrete prediction problems. We use $d$-flats to obtain a new lower bound on the convex consistency dimension of risk measures, resolving an open question due to Frongillo and Kash (NeurIPS 2015). In discrete prediction settings, we show that the $d$-flats approach recovers and even tightens previous lower bounds using feasible subspace dimension.
Author Information
Jessica Finocchiaro (University of Colorado Boulder)
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: Surrogate Regret Bounds for Polyhedral Losses »
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