Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds

2025/11/19 by Mohri, Mehryar, Zhong, Yutao · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification

paper · doi:10.48550/arxiv.2511.15816

openalex publication_date 2025/11/19 · openalex created_date 2025/11/23 · openalex updated_date 2026/07/28

Abstract

We introduce a new low-noise condition for classification, the Model Margin Noise (MM noise) assumption, and derive enhanced H-consistency bounds under this condition. MM noise is weaker than Tsybakov noise condition: it is implied by Tsybakov noise condition but can hold even when Tsybakov fails, because it depends on the discrepancy between a given hypothesis and the Bayes-classifier rather than on the intrinsic distributional minimal margin (see Figure 1 for an illustration of an explicit example). This hypothesis-dependent assumption yields enhanced H-consistency bounds for both binary and multi-class classification. Our results extend the enhanced H-consistency bounds of Mao, Mohri, and Zhong (2025a) with the same favorable exponents but under a weaker assumption than the Tsybakov noise condition; they interpolate smoothly between linear and square-root regimes for intermediate noise levels. We also instantiate these bounds for common surrogate loss families and provide illustrative tables.

Citations

• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
• Theory and Algorithms for Learning with Multi-Class Abstention and Multi-Expert Deferral
• Fundamental Novel Consistency Theory: H-Consistency Bounds
• Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer
• Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data
• Multi-Label Learning with Stronger Consistency Guarantees
• Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defer
• Cardinality-Aware Set Prediction and Top-k Classification
• A Universal Growth Rate for Learning with Smooth Surrogate Losses
• Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms
• Principled Approaches for Learning to Defer with Multiple Experts
• Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention
• Surrogate Regret Bounds for Polyhedral Losses
• An Embedding Framework for Consistent Polyhedral Surrogates
• Binary Excess Risk for Smooth Convex Surrogates

Cited by

• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
• Adversarial Robustness in One-Stage Learning-to-Defer
• Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer

Related

• Enhanced H-Consistency Bounds
• Fundamental Novel Consistency Theory: H-Consistency Bounds
• Noise-adaptive Margin-based Active Learning and Lower Bounds under Tsybakov Noise Condition
• A Universal Growth Rate for Learning with Smooth Surrogate Losses
• \mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers