Learning Submodular Losses with the Lovasz Hinge
[edit]
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:16231631, 2015.
Abstract
Learning with nonmodular 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 cuttingplane computation for these functions is NPhard for nonsupermodular loss functions. We propose instead a novel convex surrogate loss function for submodular losses, the Lovasz hinge, which leads to O(p log p) complexity with O(p) oracle accesses to the loss function to compute a gradient or cuttingplane. 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 a real world image labeling task.
Related Material



