Abstract

We formalize and study the natural approach of designing convex surrogate loss functions via embeddings, for problems such as classification, ranking, or structured prediction. In this approach, one embeds each of the finitely many predictions (e.g. rankings) as a point in the d-dimensional reals, assigns the original loss values to these points, and "convexifies" the loss in some way to obtain a surrogate. We establish a strong connection between this approach and polyhedral (piecewise-linear convex) surrogate losses: every discrete loss is embedded by some polyhedral loss, and every polyhedral loss embeds some discrete loss. Moreover, an embedding gives rise to a consistent link function as well as linear surrogate regret bounds. Our results are constructive, as we illustrate with several examples. In particular, our framework gives succinct proofs of consistency or inconsistency for various polyhedral surrogates in the literature, and for inconsistent surrogates, it further reveals the discrete losses for which these surrogates are consistent. We go on to show additional structure of embeddings, such as the equivalence of embedding and matching Bayes risks, and the equivalence of various notions of non-redudancy. Using these results, we establish that indirect elicitation, a necessary condition for consistency, is also sufficient when working with polyhedral surrogates. Based on joint work with Raf Frongillo and Bo Waggoner.

Biography

Jessie Finocchiaro (she/her) is a National Science Foundation Mathematical Sciences Postdoctoral Research Fellow and CRCS Fellow at Harvard University, working with Drs. Yiling Chen and Milind Tambe. She graduated in the CS Theory group at University of Colorado Boulder, advised by Dr. Rafael Frongillo. In general, her research interests intersect Theoretical Machine Learning, Algorithmic Game Theory, and Computational Economics. In particular, she studies how the questions we ask of data, the objectives we optimize affect what we learn and how this information affects people. Previously, she was a 2019 National Science Foundation Graduate Research Fellow.

• Admission

Zoom ID: 864 5710 6044
Passcode: 205973