# Consistent Polyhedral Surrogates for Top-k Classification and Variants

arXiv: https://arxiv.org/abs/2207.08873 · HTML: https://mlsanity.com/paper/2207.08873/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 18 Jul 2022.

## Builds on (most cited first, 11 of 11)

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [A Minimax Approach to Supervised Learning](https://mlsanity.com/paper/1606.02206/) (2016)
- [Stochastic Negative Mining for Learning with Large Output Spaces](https://mlsanity.com/paper/1810.07076/) (2018)
- [Top-k Multiclass SVM](https://mlsanity.com/paper/1511.06683/) (2015)
- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [An Embedding Framework for Consistent Polyhedral Surrogates](https://mlsanity.com/paper/1907.07330/) (2019)
- [Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification](https://mlsanity.com/paper/1612.03663/) (2016)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)

## Built on by (most cited first, 8 of 8)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts](https://mlsanity.com/paper/2504.12988/) (2025)
- [Top-k Classification and Cardinality-Aware Prediction](https://mlsanity.com/paper/2403.19625/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Consistency Conditions for Differentiable Surrogate Losses](https://mlsanity.com/paper/2505.13760/) (2025)

## Abstract (arXiv)

Top-k classification is a generalization of multiclass classification used widely in information retrieval, image classification, and other extreme classification settings. Several hinge-like (piecewise-linear) surrogates have been proposed for the problem, yet all are either non-convex or inconsistent. For the proposed hinge-like surrogates that are convex (i.e., polyhedral), we apply the recent embedding framework of Finocchiaro et al. (2019; 2022) to determine the prediction problem for which the surrogate is consistent. These problems can all be interpreted as variants of top-k classification, which may be better aligned with some applications. We leverage this analysis to derive constraints on the conditional label distributions under which these proposed surrogates become consistent for top-k. It has been further suggested that every convex hinge-like surrogate must be inconsistent for top-k. Yet, we use the same embedding framework to give the first consistent polyhedral surrogate for this problem.