# The Lov'asz Hinge: A Novel Convex Surrogate for Submodular Losses

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2015.

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

- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (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)
- [Jaccard Metric Losses: Optimizing the Jaccard Index with Soft Labels](https://mlsanity.com/paper/2302.05666/) (2023)
- [The Structured Abstain Problem and the Lov'asz Hinge](https://mlsanity.com/paper/2203.08645/) (2022)
- [Dice Semimetric Losses: Optimizing the Dice Score with Soft Labels](https://mlsanity.com/paper/2303.16296/) (2023)
- [RMAU-NET: A Residual-Multihead-Attention U-Net Architecture for Landslide Segmentation and Detection from Remote Sensing Images](https://mlsanity.com/paper/2507.11143/) (2025)
- [UNet#: A UNet-like Redesigning Skip Connections for Medical Image Segmentation](https://mlsanity.com/paper/2205.11759/) (2022)
- [Trading off Consistency and Dimensionality of Convex Surrogates for the Mode](https://mlsanity.com/paper/2402.10818/) (2024)
- [Contrasting Cost-Agnostic and Cost-Sensitive Losses under Limited Model Capacity via mathcal H-consistency](https://mlsanity.com/paper/2502.19522/) (2025)
- [RankSEG-RMA: An Efficient Segmentation Algorithm via Reciprocal Moment Approximation](https://mlsanity.com/paper/2510.15362/) (2025)
- [Clay-CNN Hybrids: Leveraging Geospatial Foundation Models as Auxiliary Context for Landslide Detection](https://mlsanity.com/paper/2606.14081/) (2026)
- [Semi-Supervised Segmentation of Functional Tissue Units at the Cellular Level](https://mlsanity.com/paper/2305.02148/) (2023)
- [Active Inference-Based Optimization of Discriminative Neural Network Classifiers](https://mlsanity.com/paper/2306.02447/) (2023)
- [Loss function to optimise signal significance in particle physics](https://mlsanity.com/paper/2412.09500/) (2024)
- [Structured Prediction with Abstention via the Lov'asz Hinge](https://mlsanity.com/paper/2505.06446/) (2025)
- [On the Relaxation of Conditional Independence Assumption for Image Segmentation](https://mlsanity.com/paper/2609.38930/) (2026)

## Abstract (arXiv)

Learning with non-modular losses is an important problem when sets of predictions are made simultaneously. The main tools for constructing convex surrogate loss functions for set prediction are margin rescaling and slack rescaling. In this work, we show that these strategies lead to tight convex surrogates iff the underlying loss function is increasing in the number of incorrect predictions. However, gradient or cutting-plane computation for these functions is NP-hard for non-supermodular loss functions. We propose instead a novel surrogate loss function for submodular losses, the Lov'asz hinge, which leads to O(p log p) complexity with O(p) oracle accesses to the loss function to compute a gradient or cutting-plane. We prove that the Lov'asz hinge is convex and yields an extension. As a result, we have developed the first tractable convex surrogates in the literature for submodular losses. We demonstrate the utility of this novel convex surrogate through several set prediction tasks, including on the PASCAL VOC and Microsoft COCO datasets.