The Structured Abstain Problem and the Lov\'asz Hinge

• URL: http://arxiv.org/abs/2203.08645v2
• Date: Thu, 17 Mar 2022 17:02:23 GMT
• Title: The Structured Abstain Problem and the Lov\'asz Hinge
• Authors: Jessie Finocchiaro and Rafael Frongillo and Enrique Nueve
• Abstract summary: 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.
• Score: 0.5156484100374059
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Lov\'asz 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\'asz 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\'asz 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.

Related papers

• Identifying Intervenable and Interpretable Features via Orthogonality Regularization [48.938969291033665]
  We disentangle the decoder matrix into almost orthogonal features.<n>This reduces interference and superposition between the features, while keeping performance on the target dataset essentially unchanged.<n>Our code is available under $texttthttps://github.com/mrtzmllr/sae-icm$.
  arXiv  Detail & Related papers  (2026-02-04T16:29:14Z)
• Fundamental Novel Consistency Theory: $H$-Consistency Bounds [19.493449206135296]
  In machine learning, the loss functions optimized during training often differ from the target loss that defines task performance.<n>We present an in-depth study of the target loss estimation error relative to the surrogate loss estimation error.<n>Our analysis leads to $H$-consistency bounds, which are guarantees accounting for the hypothesis set $H$.
  arXiv  Detail & Related papers  (2025-12-28T11:02:20Z)
• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [64.99236464953032]
  We propose a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.<n>By applying our hinge-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution, we achieve a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.
  arXiv  Detail & Related papers  (2025-06-03T06:31:59Z)
• Structured Prediction with Abstention via the Lovász Hinge [0.24578723416255752]
  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.
  arXiv  Detail & Related papers  (2025-05-09T21:29:22Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems. Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• Control of the von Neumann Entropy for an Open Two-Qubit System Using Coherent and Incoherent Drives [50.24983453990065]
  This article is devoted to developing an approach for manipulating the von Neumann entropy $S(rho(t))$ of an open two-qubit system with coherent control and incoherent control inducing time-dependent decoherence rates. The following goals are considered: (a) minimizing or maximizing the final entropy $S(rho(T))$; (b) steering $S(rho(T))$ to a given target value; (c) steering $S(rho(T))$ to a target value and satisfying the pointwise state constraint $S(
  arXiv  Detail & Related papers  (2024-05-10T10:01:10Z)
• A Contrastive Variational Graph Auto-Encoder for Node Clustering [10.52321770126932]
  State-of-the-art clustering methods have numerous challenges. Existing VGAEs do not account for the discrepancy between the inference and generative models. Our solution has two mechanisms to control the trade-off between Feature Randomness and Feature Drift.
  arXiv  Detail & Related papers  (2023-12-28T05:07:57Z)
• Optimization of Time-Dependent Decoherence Rates and Coherent Control for a Qutrit System [77.34726150561087]
  Incoherent control makes the decoherence rates depending on time in a specific controlled manner. We consider the problem of maximizing the Hilbert-Schmidt overlap between the system's final state $rho(T)$ and a given target state $rho_rm target.
  arXiv  Detail & Related papers  (2023-08-08T01:28:50Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Constrained Optimization of Rank-One Functions with Indicator Variables [0.0]
  optimization problems involving a rank-one convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine learning applications. We propose a constructive approach that exploits a hidden conic structure induced by perspective functions. This enables us to systematically give perspective formulations for the convex hull descriptions of sets with nonlinear separable or non-separable objective functions, sign constraints on continuous variables, and constraints on indicator variables.
  arXiv  Detail & Related papers  (2023-03-31T15:51:56Z)
• Adaptive Bandit Convex Optimization with Heterogeneous Curvature [40.368893108265056]
  We study a heterogeneous setting where each function has its own curvature that is only revealed after the learner makes a decision. We develop an efficient algorithm that is able to adapt to the curvature on the fly.
  arXiv  Detail & Related papers  (2022-02-12T21:55:42Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  We propose a simple strategy for universal online convex optimization. The key idea is to construct a set of experts to process the original online functions, and deploy a meta-algorithm over the linearized losses. In this way, we can plug in off-the-shelf online solvers as black-box experts to deliver problem-dependent regret bounds.
  arXiv  Detail & Related papers  (2021-05-08T11:43:49Z)
• Submodular Maximization Through Barrier Functions [32.41824379833395]
  We introduce a novel technique for constrained submodular, inspired by barrier functions in continuous optimization. We extensively evaluate our proposed algorithm over several real-world applications.
  arXiv  Detail & Related papers  (2020-02-10T03:32:49Z)

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.