# Enhanced H-Consistency Bounds

arXiv: https://arxiv.org/abs/2407.13722 · HTML: https://mlsanity.com/paper/2407.13722/

## 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 (most cited first, 30 of 42)

- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Peer Loss Functions: Learning from Noisy Labels without Knowing Noise Rates](https://mlsanity.com/paper/1910.03231/) (2019)
- [Calibrated Learning to Defer with One-vs-All Classifiers](https://mlsanity.com/paper/2202.03673/) (2022)
- [Classification with Asymmetric Label Noise: Consistency and Maximal Denoising](https://mlsanity.com/paper/1303.1208/) (2013)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [On the Calibration of Multiclass Classification with Rejection](https://mlsanity.com/paper/1901.10655/) (2019)
- [Principled Approaches for Learning to Defer with Multiple Experts](https://mlsanity.com/paper/2310.14774/) (2023)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [Learning to Reject with a Fixed Predictor: Application to Decontextualization](https://mlsanity.com/paper/2301.09044/) (2023)
- [Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention](https://mlsanity.com/paper/2310.14770/) (2023)
- [Learning from Label Proportions by Learning with Label Noise](https://mlsanity.com/paper/2203.02496/) (2022)
- [Revisiting Discriminative vs. Generative Classifiers: Theory and Implications](https://mlsanity.com/paper/2302.02334/) (2023)
- [Regression with Multi-Expert Deferral](https://mlsanity.com/paper/2403.19494/) (2024)
- [Top-k Multiclass SVM](https://mlsanity.com/paper/1511.06683/) (2015)
- [Ranking with Abstention](https://mlsanity.com/paper/2307.02035/) (2023)
- [A Finer Calibration Analysis for Adversarial Robustness](https://mlsanity.com/paper/2105.01550/) (2021)
- [In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer](https://mlsanity.com/paper/2311.01106/) (2023)
- [On the Consistency of Ordinal Regression Methods](https://mlsanity.com/paper/1408.2327/) (2014)
- [Loss factorization, weakly supervised learning and label noise robustness](https://mlsanity.com/paper/1602.02450/) (2016)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [Structured Prediction with Projection Oracles](https://mlsanity.com/paper/1910.11369/) (2019)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)

## Built on by (most cited first, 18 of 18)

- [A Two-Stage Learning-to-Defer Approach for Multi-Task Learning](https://mlsanity.com/paper/2410.15729/) (2024)
- [Adversarial Robustness in Two-Stage Learning-to-Defer: Algorithms and Guarantees](https://mlsanity.com/paper/2502.01027/) (2025)
- [Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer](https://mlsanity.com/paper/2506.20650/) (2025)
- [Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guarantees](https://mlsanity.com/paper/2410.15761/) (2024)
- [Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data](https://mlsanity.com/paper/2502.10381/) (2025)
- [Budgeted Multiple-Expert Deferral](https://mlsanity.com/paper/2510.26706/) (2025)
- [Improved Balanced Classification with Theoretically Grounded Loss Functions](https://mlsanity.com/paper/2512.23947/) (2025)
- [Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts](https://mlsanity.com/paper/2504.12988/) (2025)
- [To Ask or Not to Ask: Learning to Require Human Feedback](https://mlsanity.com/paper/2510.08314/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [Adversarial Robustness in One-Stage Learning-to-Defer](https://mlsanity.com/paper/2510.10988/) (2025)
- [A Theoretical Framework for Modular Learning of Robust Generative Models](https://mlsanity.com/paper/2602.17554/) (2026)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Optimized Deferral for Imbalanced Settings](https://mlsanity.com/paper/2604.27723/) (2026)
- [Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction](https://mlsanity.com/paper/2604.27742/) (2026)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Some Robustness Properties of Label Cleaning](https://mlsanity.com/paper/2509.11379/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## 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.