The Structured Abstain Problem and the Lovász Hinge

Jessica J Finocchiaro, Rafael Frongillo, Enrique B Nueve
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3718-3740, 2022.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-nueve22a, title = {The Structured Abstain Problem and the Lovász Hinge}, author = {Finocchiaro, Jessica J and Frongillo, Rafael and Nueve, Enrique B}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3718--3740}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/nueve22a/nueve22a.pdf}, url = {https://proceedings.mlr.press/v178/nueve22a.html}, abstract = {The Lovász 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ász 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ász 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.} }
Endnote
%0 Conference Paper %T The Structured Abstain Problem and the Lovász Hinge %A Jessica J Finocchiaro %A Rafael Frongillo %A Enrique B Nueve %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-nueve22a %I PMLR %P 3718--3740 %U https://proceedings.mlr.press/v178/nueve22a.html %V 178 %X The Lovász 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ász 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ász 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.
APA
Finocchiaro, J.J., Frongillo, R. & Nueve, E.B.. (2022). The Structured Abstain Problem and the Lovász Hinge. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3718-3740 Available from https://proceedings.mlr.press/v178/nueve22a.html.

Related Material