Beyond Tsybakov: Model Margin Noise and $\mathcal{H}$-Consistency Bounds
This work addresses the challenge of deriving tighter consistency bounds in classification theory, offering a more flexible noise assumption that can improve theoretical guarantees for machine learning practitioners, though it is incremental as it builds on existing bounds.
The paper tackles the problem of classification by introducing a new low-noise condition called Model Margin Noise (MM noise), which is weaker than the Tsybakov noise condition, and derives enhanced H-consistency bounds under this condition, achieving the same favorable exponents as prior work but with a less restrictive assumption.
We introduce a new low-noise condition for classification, the Model Margin Noise (MM noise) assumption, and derive enhanced $\mathcal{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 $\mathcal{H}$-consistency bounds for both binary and multi-class classification. Our results extend the enhanced $\mathcal{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.