On the consistency of top-k surrogate losses

Forest Yang, Sanmi Koyejo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The top-k error is often employed to evaluate performance for challenging classification tasks in computer vision as it is designed to compensate for ambiguity in ground truth labels. This practical success motivates our theoretical analysis of consistent top-k classification. Surprisingly, it is not rigorously understood when taking the k-argmax of a vector is guaranteed to return the k-argmax of another vector, though doing so is crucial to describe Bayes optimality; we do both tasks. Then, we define top-k calibration and show it is necessary and sufficient for consistency. Based on the top-k calibration analysis, we propose a class of top-k calibrated Bregman divergence surrogates. Our analysis continues by showing previously proposed hinge-like top-k surrogate losses are not top-k calibrated and suggests no convex hinge loss is top-k calibrated. On the other hand, we propose a new hinge loss which is consistent. We explore further, showing our hinge loss remains consistent under a restriction to linear functions, while cross entropy does not. Finally, we exhibit a differentiable, convex loss function which is top-k calibrated for specific k.

Original languageEnglish (US)
Title of host publication37th International Conference on Machine Learning, ICML 2020
EditorsHal Daume, Aarti Singh
PublisherInternational Machine Learning Society (IMLS)
Pages10658-10666
Number of pages9
ISBN (Electronic)9781713821120
StatePublished - 2020
Event37th International Conference on Machine Learning, ICML 2020 - Virtual, Online
Duration: Jul 13 2020Jul 18 2020

Publication series

Name37th International Conference on Machine Learning, ICML 2020
VolumePartF168147-14

Conference

Conference37th International Conference on Machine Learning, ICML 2020
CityVirtual, Online
Period7/13/207/18/20

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Fingerprint

Dive into the research topics of 'On the consistency of top-k surrogate losses'. Together they form a unique fingerprint.

Cite this