The Lovász Hinge: A Convex Surrogate for Submodular Losses

Jiaqian Yu, Matthew B. BlaschkoarXiv 2015 · arXiv · OpenReview

Abstract

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ász 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ász 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.

Introduction

In many structured prediction tasks, such as image segmentation or multi-label classification, performance is evaluated using non-modular loss functions like the Jaccard index (Intersection over Union). Unlike standard modular losses (e.g., Hamming loss), where the total error is a simple sum of individual errors, non-modular losses account for dependencies between predictions. Specifically, submodular losses exhibit "diminishing returns," where the marginal cost of an additional error decreases as the total number of errors increases.

While submodular losses better align with human evaluation metrics, they present significant optimization challenges. Traditional convex surrogates, such as margin and slack rescaling used in Structured Support Vector Machines (SSVMs), often result in NP-hard optimization problems when applied to submodular functions. This tractability gap frequently forces researchers to use simpler, less representative proxies during training.

The Tractability Gap in Structured Prediction

The standard approach to optimizing non-smooth discrete losses is to find a convex surrogate. Margin and slack rescaling are the primary tools for this. However, the authors demonstrate that for submodular losses, finding the "most violated constraint"—a necessary step for gradient-based optimization—is generally NP-hard. This makes these traditional surrogates computationally prohibitive for complex set prediction tasks.

The Lovász Hinge Surrogate

To address these limitations, the authors introduce the Lovász Hinge. This novel surrogate leverages the Lovász extension, a fundamental tool in submodular analysis that extends a set function defined on the vertices of a hypercube to a continuous, convex function on the entire cube.

Comparison of Lovász hinge, margin-rescaling, and slack-rescaling surfaces under various loss properties.

The Lovász Hinge is the first tractable convex surrogate specifically designed for submodular losses. Its key properties include:

  • Convexity: It provides a guaranteed convex upper bound on the discrete loss.
  • Efficiency: Computing a gradient or a cutting-plane for the Lovász Hinge requires only $O(p \log p)$ time, where $p$ is the number of predictions. This efficiency stems from a "sorting trick": the optimization problem can be solved by simply sorting the prediction scores.
  • Tightness: The surrogate is shown to be a tight extension of the underlying discrete loss.

Optimization via Cutting-Plane

The Lovász Hinge can be optimized using a cutting-plane method, similar to standard SSVMs but with significantly lower per-iteration complexity. Because the subgradient can be computed via sorting, the algorithm scales well to large datasets.

The cutting-plane algorithm for optimizing the Lovász hinge.

Experimental Evaluation

The authors validated the Lovász Hinge on several benchmarks:

  1. Synthetic Task: In an "early detection" task designed to penalize early errors, the Lovász Hinge achieved an average loss of 0.100, significantly outperforming approximate margin (0.154) and slack (0.144) rescaling methods.
  2. Computer Vision Benchmarks: On the PASCAL VOC and Microsoft COCO datasets, the Lovász Hinge consistently outperformed standard linear SVMs and traditional rescaled surrogates when evaluated on the Jaccard loss. The authors also provided a formal proof that the Jaccard loss is indeed submodular, justifying the use of their method.

Conclusion

The Lovász Hinge provides a mathematically principled and computationally efficient way to optimize submodular losses. By bridging the gap between discrete submodular optimization and continuous convex optimization, it enables the direct training of models on complex metrics like IoU without resorting to NP-hard approximations or oversimplified proxies.

Summary updated

Abstract

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.
BibTeX
@misc{yu2015lovasz,
  author = {Jiaqian Yu and Matthew B. Blaschko},
  title = {{The Lovász Hinge: A Convex Surrogate for Submodular Losses}},
  year = {2015},
  eprint = {1512.07797},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1512.07797},
}
Figure