H Consistency Bounds via Minimizability Gaps

17 concepts8 papers1 proposal

When training a machine learning model, we rarely minimize the true target error (such as the discrete 0-1 classification error or ranking error) directly. Because these target losses are combinatorially hard to optimize, we instead minimize a smooth surrogate loss, such as cross-entropy, logistic loss, or hinge loss.

Classical learning theory reassures us through the concept of asymptotic consistency: if we minimize a proper surrogate loss over all possible measurable functions, we will eventually converge to the optimal target performance.

But there is a major catch. In practice, we never search over all possible measurable functions. We restrict our search to a specific hypothesis set $\mathcal{H}$, such as linear models or deep neural network architectures. Traditional consistency guarantees often fall apart under these constraints, yielding bounds that are either too loose to be useful or entirely vacuous.

To bridge this gap between theory and practice, a series of papers by Anqi Mao et al. introduces a refined framework known as $\mathcal{H}$-consistency. The core insight is that consistency is not an inherent property of a loss function alone; rather, it is a property of the interaction between the loss function and the specific constraints of the model architecture $\mathcal{H}$. The key mechanism driving this framework is the minimizability gap.


Intuition Behind the Minimizability Gap

To understand why the minimizability gap matters, imagine the absolute best possible performance a model could achieve on a given surrogate loss if it had no architectural constraints whatsoever—the theoretical global minimum (or pointwise infimum) over all measurable functions. Now, imagine the best possible performance achievable strictly within your chosen hypothesis set $\mathcal{H}$.

The difference between these two values is the minimizability gap.

$$\text{Minimizability Gap} = \inf_{h \in \mathcal{H}} \mathbb{E}[\text{Loss}(h)] - \mathbb{E}[\inf_{\text{all functions}} \text{Loss}]$$

It quantifies the penalty your model architecture pays for its representational limitations relative to a specific loss function. If a surrogate loss requires a highly complex decision boundary that $\mathcal{H}$ cannot represent, its minimizability gap will be large.


Why the Minimizability Gap Enables Tighter Bounds

Conventional error bounds in machine learning often rely on general approximation errors that do not account for the specific geometric constraints of a model's architecture. This results in theoretical guarantees that fail to predict actual performance on finite datasets.

By incorporating the minimizability gap, the framework developed by Anqi Mao et al. allows for the derivation of tight, non-asymptotic error bounds. Instead of analyzing the loss in a vacuum, the minimizability gap tracks how surrogate loss minimization directly translates to target error within the specific boundaries of $\mathcal{H}$. The true target error of a model is fundamentally bounded by the sum of its empirical surrogate error and this architectural gap.

This approach has allowed the authors to establish the first tight, non-asymptotic bounds for ubiquitous loss families. For instance, in Cross-Entropy Loss Functions: Theoretical Analysis and Applications, the authors used this metric to analyze "comp-sum" losses (a category including cross-entropy), revealing exactly how factors like the number of classes affect theoretical performance under constrained architectures.


The Ultimate Tie-Breaker for Loss Selection

In A Universal Growth Rate for Learning with Smooth Surrogate Losses, Anqi Mao et al. proved a striking unification: for almost all smooth surrogate losses, the error bound grows at a universal square-root rate ($\sqrt{\epsilon}$) relative to the surrogate loss.

If popular smooth losses share the exact same asymptotic growth rate, how should a practitioner choose between them?

The minimizability gap serves as the ultimate tie-breaker. Because different surrogate losses impose different geometric demands on the model, their minimizability gaps will vary even when the hypothesis set $\mathcal{H}$ is held constant. The gap acts as a precise selection criterion: the optimal surrogate loss for a given problem is the one that minimizes the minimizability gap for your specific model architecture.


Application to Complex Learning Paradigms

By anchoring consistency analysis to the minimizability gap, the authors have successfully extended rigorous guarantees to complex domains where traditional theory struggled:

  • Regression: In H-Consistency Guarantees for Regression, the authors established the first rigorous $\mathcal{H}$-consistency framework for regression. Their analysis revealed that while common surrogates like Huber loss are theoretically sound, the standard $\epsilon$-insensitive loss used in Support Vector Regression (SVR) actually lacks consistency guarantees when constrained.
  • Ranking: In pairwise ranking tasks, the best possible model error within a restricted class is frequently non-zero. In $H$-Consistency Bounds for Pairwise Misranking Loss Surrogates and Ranking with Abstention, the authors demonstrated that ignoring this gap leads to an incomplete understanding of ranking performance, and showed how incorporating an "abstention" mechanism can mitigate the gap.
  • Learning to Defer and Abstain: In high-stakes scenarios where an AI must decide whether to predict, abstain, or hand off a decision to human experts, the authors utilized minimizability gaps to derive non-asymptotic guarantees for score-based multi-class abstention (Anqi Mao et al.) and learning to defer to multiple experts (Anqi Mao et al.).

By shifting the focus from abstract, infinite-capacity function spaces to the concrete interaction between losses and architectures, the minimizability gap transforms consistency analysis from a purely theoretical exercise into a practical tool for model and loss function design.

Key Foundational Work

H-Consistency Bounds for Pairwise Misranking Loss Surrogates (2023) — contributed 3 concept elements to this direction.
Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention (2024) — contributed 3 concept elements to this direction.
A Universal Growth Rate for Learning with Smooth Surrogate Losses (2024) — contributed 3 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 8 papers
  2. Version 1 · 2026-10-04 · 16 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_minimizability_gap_e5210641,
  title = {minimizability gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimizability-gap/rdr_e5210641c0764422802c8a83c8effcb0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_minimizability_gap_e5210641_v2,
  title = {minimizability gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimizability-gap/rdr_e5210641c0764422802c8a83c8effcb0/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake