# The Structured Abstain Problem and the Lov'asz Hinge

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 16 Mar 2022.

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

- [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)

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [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)
- [RankSEG-RMA: An Efficient Segmentation Algorithm via Reciprocal Moment Approximation](https://mlsanity.com/paper/2510.15362/) (2025)
- [Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure](https://mlsanity.com/paper/2608.13549/) (2026)
- [On the Relaxation of Conditional Independence Assumption for Image Segmentation](https://mlsanity.com/paper/2609.38930/) (2026)

## Abstract (arXiv)

The Lov'asz hinge is a convex surrogate recently proposed for structured binary classification, in which k binary predictions are made simultaneously and the error is judged by a submodular set function. Despite its wide usage in image segmentation and related problems, its consistency has remained open. We resolve this open question, showing that the Lov'asz hinge is inconsistent for its desired target unless the set function is modular. Leveraging a recent embedding framework, we instead derive the target loss for which the Lov'asz hinge is consistent. This target, which we call the structured abstain problem, allows one to abstain on any subset of the k predictions. We derive two link functions, each of which are consistent for all submodular set functions simultaneously.