Structured Prediction with Abstention via the Lovász Hinge

• URL: http://arxiv.org/abs/2505.06446v1
• Date: Fri, 09 May 2025 21:29:22 GMT
• Title: Structured Prediction with Abstention via the Lovász Hinge
• Authors: Jessie Finocchiaro, Rafael Frongillo, Enrique Nueve,
• Abstract summary: We show that the Lov'asz hinge is inconsistent with its desired target unless the set function used for evaluation is modular.<n>We show that one can combine the binary encoding construction of Ramaswamy et al. with our link construction to achieve an efficient consistent surrogate for a natural multiclass of the structured abstain problem.
• Score: 0.24578723416255752
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Lov\'asz hinge is a convex loss function proposed for binary structured classification, in which k related binary predictions jointly evaluated by a submodular function. Despite its prevalence in image segmentation and related tasks, the consistency of the Lov\'asz hinge has remained open. We show that the Lov\'asz hinge is inconsistent with its desired target unless the set function used for evaluation is modular. Leveraging the embedding framework of Finocchiaro et al. (2024), we find the target loss for which the Lov\'asz hinge is consistent. This target, which we call the structured abstain problem, is a variant of selective classification for structured prediction that allows one to abstain on any subset of the k binary predictions. We derive a family of link functions, each of which is simultaneously consistent for all polymatroids, a subset of submodular set functions. We then give sufficient conditions on the polymatroid for the structured abstain problem to be tightly embedded by the Lov\'asz hinge, meaning no target prediction is redundant. We experimentally demonstrate the potential of the structured abstain problem for interpretability in structured classification tasks. Finally, for the multiclass setting, we show that one can combine the binary encoding construction of Ramaswamy et al. (2018) with our link construction to achieve an efficient consistent surrogate for a natural multiclass generalization of the structured abstain problem.

Related papers

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• A Convex Loss Function for Set Prediction with Optimal Trade-offs Between Size and Conditional Coverage [0.554780083433538]
  We consider supervised learning problems in which set predictions provide explicit uncertainty estimates.<n>We propose a convex loss function for nondecreasing subset-valued functions obtained as level sets of a real-valued function.<n>We show how to naturally obtain sets with optimized conditional coverage.
  arXiv  Detail & Related papers  (2025-12-22T08:41:31Z)
• On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models [11.137244714693779]
  We study the robustness of spectral algorithms against semirandom adversaries.<n>We identify classes of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent.
  arXiv  Detail & Related papers  (2024-12-18T20:35:02Z)
• Semiparametric conformal prediction [79.6147286161434]
  We construct a conformal prediction set accounting for the joint correlation structure of the vector-valued non-conformity scores.<n>We flexibly estimate the joint cumulative distribution function (CDF) of the scores.<n>Our method yields desired coverage and competitive efficiency on a range of real-world regression problems.
  arXiv  Detail & Related papers  (2024-11-04T14:29:02Z)
• Understanding and Constructing Latent Modality Structures in Multi-modal Representation Learning [53.68371566336254]
  We argue that the key to better performance lies in meaningful latent modality structures instead of perfect modality alignment. Specifically, we design 1) a deep feature separation loss for intra-modality regularization; 2) a Brownian-bridge loss for inter-modality regularization; and 3) a geometric consistency loss for both intra- and inter-modality regularization.
  arXiv  Detail & Related papers  (2023-03-10T14:38:49Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• The Structured Abstain Problem and the Lov\'asz Hinge [0.5156484100374059]
  We show that the Lov'asz hinge is inconsistent for its desired target unless the set function is modular. We derive two link functions, each of which are consistent for all submodular set functions simultaneously.
  arXiv  Detail & Related papers  (2022-03-16T14:30:25Z)
• Understanding Interlocking Dynamics of Cooperative Rationalization [90.6863969334526]
  Selective rationalization explains the prediction of complex neural networks by finding a small subset of the input that is sufficient to predict the neural model output. We reveal a major problem with such cooperative rationalization paradigm -- model interlocking. We propose a new rationalization framework, called A2R, which introduces a third component into the architecture, a predictor driven by soft attention as opposed to selection.
  arXiv  Detail & Related papers  (2021-10-26T17:39:18Z)
• Inducing Transformer's Compositional Generalization Ability via Auxiliary Sequence Prediction Tasks [86.10875837475783]
  Systematic compositionality is an essential mechanism in human language, allowing the recombination of known parts to create novel expressions. Existing neural models have been shown to lack this basic ability in learning symbolic structures. We propose two auxiliary sequence prediction tasks that track the progress of function and argument semantics.
  arXiv  Detail & Related papers  (2021-09-30T16:41:19Z)
• Taming Adversarial Robustness via Abstaining [7.1975923901054575]
  We consider a binary classification problem where the observations can be perturbed by an adversary. We include an abstaining option, where the classifier abstains from taking a decision when it has low confidence about the prediction. We show that there exist a tradeoff between the two metrics regardless of what method is used to choose the abstaining region.
  arXiv  Detail & Related papers  (2021-04-06T07:36:48Z)
• Predictive Value Generalization Bounds [27.434419027831044]
  We study a bi-criterion framework for assessing scoring functions in the context of binary classification. We study properties of scoring functions with respect to predictive values by deriving new distribution-free large deviation and uniform convergence bounds.
  arXiv  Detail & Related papers  (2020-07-09T21:23:28Z)
• Achieving robustness in classification using optimal transport with hinge regularization [7.780418853571034]
  We propose a new framework for binary classification, based on optimal transport. We learn 1-Lipschitz networks using a new loss that is an hinge regularized version of the Kantorovich-Rubinstein dual formulation for the Wasserstein distance estimation.
  arXiv  Detail & Related papers  (2020-06-11T15:36:23Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.