# On the Consistency of Top-k Surrogate Losses

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2019.

## Built on by (most cited first, 30 of 35)

- [Set-valued classification -- overview via a unified framework](https://mlsanity.com/paper/2102.12318/) (2021)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer](https://mlsanity.com/paper/2311.01106/) (2023)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Sum of Ranked Range Loss for Supervised Learning](https://mlsanity.com/paper/2106.03300/) (2021)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)
- [Learning with Noisy Labels by Efficient Transition Matrix Estimation to Combat Label Miscorrection](https://mlsanity.com/paper/2111.14932/) (2021)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [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)
- [On Learning Latent Models with Multi-Instance Weak Supervision](https://mlsanity.com/paper/2306.13796/) (2023)
- [Label Distributionally Robust Losses for Multi-class Classification: Consistency, Robustness and Adaptivity](https://mlsanity.com/paper/2112.14869/) (2021)
- [Stochastic smoothing of the top-K calibrated hinge loss for deep imbalanced classification](https://mlsanity.com/paper/2202.02193/) (2022)
- [A Reduction to Binary Approach for Debiasing Multiclass Datasets](https://mlsanity.com/paper/2205.15860/) (2022)
- [Optimizing Partial Area Under the Top-k Curve: Theory and Practice](https://mlsanity.com/paper/2209.01398/) (2022)
- [Consistent Polyhedral Surrogates for Top-k Classification and Variants](https://mlsanity.com/paper/2207.08873/) (2022)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts](https://mlsanity.com/paper/2504.12988/) (2025)
- [ε-Softmax: Approximating One-Hot Vectors for Mitigating Label Noise](https://mlsanity.com/paper/2508.02387/) (2025)
- [From Classification Accuracy to Proper Scoring Rules: Elicitability of Probabilistic Top List Predictions](https://mlsanity.com/paper/2301.11797/) (2023)
- [Top-k Classification and Cardinality-Aware Prediction](https://mlsanity.com/paper/2403.19625/) (2024)
- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)
- [Small molecule retrieval from tandem mass spectrometry: what are we optimizing for?](https://mlsanity.com/paper/2602.16507/) (2026)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Classification Under Ambiguity: When Is Average-K Better Than Top-K?](https://mlsanity.com/paper/2112.08851/) (2021)
- [Identify ambiguous tasks combining crowdsourced labels by weighting Areas Under the Margin](https://mlsanity.com/paper/2209.15380/) (2022)
- [Provable Robust Saliency-based Explanations](https://mlsanity.com/paper/2212.14106/) (2022)
- [U-Trustworthy Models.Reliability, Competence, and Confidence in Decision-Making](https://mlsanity.com/paper/2401.02062/) (2024)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)

## Abstract (arXiv)

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.