Related papers: Enhanced $H$-Consistency Bounds

Enhanced $H$-Consistency Bounds

URL: http://arxiv.org/abs/2407.13722v1
Date: Thu, 18 Jul 2024 17:22:40 GMT
Title: Enhanced $H$-Consistency Bounds
Authors: Anqi Mao, Mehryar Mohri, Yutao Zhong,
Abstract summary: We present a framework for establishing enhanced $H$-consistency bounds based on more general inequalities relating conditional regrets. Our theorems subsume existing results as special cases but also enable the derivation of more favorable bounds in various scenarios. These include standard multi-class classification, binary and multi-class classification under Tsybakov noise conditions, and bipartite ranking.
Score: 30.389055604165222
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Recent research has introduced a key notion of $H$-consistency bounds for surrogate losses. These bounds offer finite-sample guarantees, quantifying the relationship between the zero-one estimation error (or other target loss) and the surrogate loss estimation error for a specific hypothesis set. However, previous bounds were derived under the condition that a lower bound of the surrogate loss conditional regret is given as a convex function of the target conditional regret, without non-constant factors depending on the predictor or input instance. Can we derive finer and more favorable $H$-consistency bounds? In this work, we relax this condition and present a general framework for establishing enhanced $H$-consistency bounds based on more general inequalities relating conditional regrets. Our theorems not only subsume existing results as special cases but also enable the derivation of more favorable bounds in various scenarios. These include standard multi-class classification, binary and multi-class classification under Tsybakov noise conditions, and bipartite ranking.

Related papers

A Universal Growth Rate for Learning with Smooth Surrogate Losses [30.389055604165222]
We prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification. We extend this analysis to multi-class classification with a series of novel results.
arXiv Detail & Related papers (2024-05-09T17:59:55Z)
Top-$k$ Classification and Cardinality-Aware Prediction [30.389055604165222]
We show that comp-sum and constrained losses are supported by $H$-consistency bounds with respect to the top-$k$ loss. We introduce cardinality-aware loss functions through instance-dependent cost-sensitive learning. Minimizing these losses leads to new cardinality-aware algorithms for top-$k$ classification.
arXiv Detail & Related papers (2024-03-28T17:45:03Z)
Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
arXiv Detail & Related papers (2024-01-17T09:23:25Z)
Ranking with Abstention [27.3569897539488]
We introduce a novel framework of ranking with abstention, where the learner can abstain from making prediction at some limited cost $c$. We present a series of $H$-consistency bounds for both the family of linear functions and that of neural networks with one hidden-layer.
arXiv Detail & Related papers (2023-07-05T05:37:13Z)
A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $O(frac1sqrtK)$ when the operator is $L$-Lipschitz and monotone.
arXiv Detail & Related papers (2022-10-27T17:59:09Z)
On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
arXiv Detail & Related papers (2022-10-12T12:49:20Z)
$\mathscr{H}$-Consistency Estimation Error of Surrogate Loss Minimizers [38.56401704010528]
We present a detailed study of estimation errors in terms of surrogate loss estimation errors. We refer to such guarantees as $mathscrH$-consistency estimation error bounds.
arXiv Detail & Related papers (2022-05-16T23:13:36Z)
Sequential prediction under log-loss and misspecification [47.66467420098395]
We consider the question of sequential prediction under the log-loss in terms of cumulative regret. We show that cumulative regrets in the well-specified and misspecified cases coincideally. We provide an $o(1)$ characterization of the distribution-free or PAC regret.
arXiv Detail & Related papers (2021-01-29T20:28:23Z)
On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
arXiv Detail & Related papers (2020-08-20T03:48:14Z)
Relative Deviation Margin Bounds [55.22251993239944]
We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
arXiv Detail & Related papers (2020-06-26T12:37:17Z)

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