# Structured Prediction with Abstention via the Lov'asz Hinge

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 9 May 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Encoder-Decoder with Atrous Separable Convolution for Semantic Image Segmentation](https://mlsanity.com/paper/1802.02611/) (2018)
- [STEm-Seg: Spatio-temporal Embeddings for Instance Segmentation in Videos](https://mlsanity.com/paper/2003.08429/) (2020)
- [Instance Segmentation by Jointly Optimizing Spatial Embeddings and Clustering Bandwidth](https://mlsanity.com/paper/1906.11109/) (2019)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [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)
- [The Lov'asz Hinge: A Novel Convex Surrogate for Submodular Losses](https://mlsanity.com/paper/1512.07797/) (2015)
- [Performance measures for classification systems with rejection](https://mlsanity.com/paper/1504.02763/) (2015)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Yes, IoU loss is submodular - as a function of the mispredictions](https://mlsanity.com/paper/1809.01845/) (2018)

## Abstract (arXiv)

The Lov'asz hinge is a convex loss function proposed for binary structured classification, in which k related binary predictions jointly evaluated by a submodular function. Despite its prevalence in image segmentation and related tasks, the consistency of the Lov'asz hinge has remained open. We show that the Lov'asz hinge is inconsistent with its desired target unless the set function used for evaluation is modular. Leveraging the embedding framework of Finocchiaro et al. (2024), we find the target loss for which the Lov'asz hinge is consistent. This target, which we call the structured abstain problem, is a variant of selective classification for structured prediction that allows one to abstain on any subset of the k binary predictions. We derive a family of link functions, each of which is simultaneously consistent for all polymatroids, a subset of submodular set functions. We then give sufficient conditions on the polymatroid for the structured abstain problem to be tightly embedded by the Lov'asz hinge, meaning no target prediction is redundant. We experimentally demonstrate the potential of the structured abstain problem for interpretability in structured classification tasks. Finally, for the multiclass setting, we show that one can combine the binary encoding construction of Ramaswamy et al. (2018) with our link construction to achieve an efficient consistent surrogate for a natural multiclass generalization of the structured abstain problem.