mlsanityData to 14 Oct 2026

Enhanced H-Consistency Bounds

arXiv 2407.13722 ↗First posted 18 Jul 2024cs.LG stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 42 of its 112 references that are in the map. First posted on arXiv 18 Jul 2024.

Builds on

42 of 112 references.

References · 42

  1. 2018Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labelscited by 997
  2. 2017Robust Loss Functions under Label Noise for Deep Neural Networkscited by 443
  3. 2020Consistent Estimators for Learning to Defer to an Expertcited by 271
  4. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 210
  5. 2019Peer Loss Functions: Learning from Noisy Labels without Knowing Noise Ratescited by 142
  6. 2022Calibrated Learning to Defer with One-vs-All Classifierscited by 69
  7. 2013Classification with Asymmetric Label Noise: Consistency and Maximal Denoisingcited by 68
  8. 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
  9. 2019On the Calibration of Multiclass Classification with Rejectioncited by 41
  10. 2023Principled Approaches for Learning to Defer with Multiple Expertscited by 38
  11. 2023Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithmscited by 36
  12. 2019On the Consistency of Top-k Surrogate Lossescited by 35
30 more
  1. 2016A Consistent Regularization Approach for Structured Predictioncited by 33
  2. 2023Learning to Reject with a Fixed Predictor: Application to Decontextualizationcited by 32
  3. 2023Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstentioncited by 32
  4. 2022Learning from Label Proportions by Learning with Label Noisecited by 30
  5. 2023Revisiting Discriminative vs. Generative Classifiers: Theory and Implicationscited by 29
  6. 2024Regression with Multi-Expert Deferralcited by 29
  7. 2015Top-k Multiclass SVMcited by 28
  8. 2023Ranking with Abstentioncited by 27
  9. 2021A Finer Calibration Analysis for Adversarial Robustnesscited by 26
  10. 2023In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defercited by 26
  11. 2014On the Consistency of Ordinal Regression Methodscited by 24
  12. 2016Loss factorization, weakly supervised learning and label noise robustnesscited by 24
  13. 2024A Universal Growth Rate for Learning with Smooth Surrogate Lossescited by 24
  14. 2017On Structured Prediction Theory with Calibrated Convex Surrogate Lossescited by 23
  15. 2024Cardinality-Aware Set Prediction and Top-k Classificationcited by 23
  16. 2014Convex Calibration Dimension for Multiclass Loss Matricescited by 21
  17. 2019Structured Prediction with Projection Oraclescited by 21
  18. 2024H-Consistency Guarantees for Regressioncited by 21
  19. 2020Convex Calibrated Surrogates for the Multi-Label F-Measurecited by 18
  20. 2021Surrogate Regret Bounds for Polyhedral Lossescited by 15
  21. 2022An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogatescited by 14
  22. 2016Multiclass Classification Calibration Functionscited by 13
  23. 2020Weston-Watkins Hinge Loss and Ordered Partitionscited by 9
  24. 2022Consistent Polyhedral Surrogates for Top-k Classification and Variantscited by 8
  25. 2023Unified Binary and Multiclass Margin-Based Classificationcited by 8
  26. 2015Consistent Algorithms for Multiclass Classification with a Reject Optioncited by 7
  27. 2023On Classification-Calibration of Gamma-Phi Lossescited by 6
  28. 2021Unifying Lower Bounds on Prediction Dimension of Consistent Convex Surrogatescited by 4
  29. 2024Multiclass Learning from Noisy Labels for Non-decomposable Performance Measurescited by 3
  30. 2024Trading off Consistency and Dimensionality of Convex Surrogates for the Modecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 11; 2026: 5.

18 papers.

Sort:

By area:

  1. 2024A Two-Stage Learning-to-Defer Approach for Multi-Task Learningcited by 17
  2. 2025Adversarial Robustness in Two-Stage Learning-to-Defer: Algorithms and Guaranteescited by 16
  3. 2025Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defercited by 16
  4. 2024Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guaranteescited by 15
  5. 2025Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Datacited by 15
  6. 2025Budgeted Multiple-Expert Deferralcited by 13
  7. 2025Improved Balanced Classification with Theoretically Grounded Loss Functionscited by 9
  8. 2025Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Expertscited by 7
  9. 2025To Ask or Not to Ask: Learning to Require Human Feedbackcited by 6
  10. 2025Principled Algorithms for Optimizing Generalized Metrics in Binary Classificationcited by 6
  11. 2025Adversarial Robustness in One-Stage Learning-to-Defercited by 5
  12. 2026A Theoretical Framework for Modular Learning of Robust Generative Modelscited by 4
6 more
  1. 2025Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Lossescited by 2
  2. 2026Optimized Deferral for Imbalanced Settingscited by 2
  3. 2026Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Predictioncited by 2
  4. 2026Online Learning-to-Defer with Varying Expertscited by 1
  5. 2025Some Robustness Properties of Label Cleaningcited by 0
  6. 2026Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learningcited by 0