In machine learning, we rarely optimize the metric we actually care about. We want to minimize the target loss—such as the 0/1 classification error—but because these functions are often non-convex and mathematically "stubborn," we optimize a surrogate loss (like logistic, hinge, or cross-entropy loss) instead.
For decades, the standard theoretical justification for this swap was "Bayes consistency." If a surrogate is Bayes consistent, minimizing it over the set of all possible measurable functions eventually minimizes the target loss. However, Anqi Mao, Mehryar Mohri, and Yutao Zhong argue that this is a dangerous oversimplification. In practice, we don't use "all functions"; we use a restricted hypothesis set $\mathcal{H}$, such as linear models or specific neural network architectures.
The Failure of Universal Consistency
Traditional consistency is an asymptotic property that assumes infinite model capacity. As Anqi Mao and colleagues point out in H-Consistency Bounds: Characterization and Extensions, a surrogate loss might be consistent in the limit of all functions but fail miserably when restricted to a specific class $\mathcal{H}$.
If your model architecture cannot represent the optimal function for a surrogate loss, the "approximation gap" doesn't just make the surrogate error higher—it can fundamentally decouple the surrogate loss from the target loss. You might find yourself successfully lowering the cross-entropy on your training set while the actual classification error remains stagnant or even increases.
The Minimizability Gap
To bridge this divide, these researchers introduced the minimizability gap. This concept serves as a critical correction factor that quantifies the discrepancy between the best possible error achievable within a specific hypothesis set $\mathcal{H}$ and the absolute theoretical minimum across all functions.
In H-Consistency Estimation Error of Surrogate Loss Minimizers, the authors demonstrate that the relationship between surrogate and target loss is determined by this gap. It represents the "inherent penalty" of your chosen architecture. By incorporating this gap into error bounds, they provide $\mathcal{H}$-consistency bounds: non-asymptotic guarantees that tell you exactly how much target error you can expect for a given level of surrogate loss, specifically for the model class you are actually using.
Choosing the Right Loss for the Architecture
One of the most surprising insights from this research direction is that the "best" loss function depends on the model. In A Universal Growth Rate for Learning with Smooth Surrogate Losses, Anqi Mao and Mehryar Mohri show that while almost all smooth surrogate losses (like logistic loss) share a universal square-root growth rate ($\sqrt{\epsilon}$), they differ in their minimizability gaps.
The minimizability gap acts as a "tie-breaker." If you have two different surrogate losses, the one that is "easier" for your specific neural network to approximate (i.e., the one with the smaller minimizability gap for that $\mathcal{H}$) will yield better real-world performance. This moves the choice of loss function from a matter of convention to a principled decision based on the representational limits of the model.
Applications: Ranking, Abstention, and Deferral
This framework has been used to fix theoretical holes in several complex learning tasks:
- Ranking: In H-Consistency Bounds for Pairwise Misranking Loss Surrogates, the authors show that standard ranking surrogates often lack guarantees when used with restricted models. They propose "abstention" mechanisms—allowing the model to say "I don't know" when two items are too close to rank—to restore theoretical tightness.
- Learning to Defer: When a model can choose to hand a decision off to a human expert, the surrogate loss must account for both the model's error and the expert's error. Anqi Mao developed a family of surrogate losses in Principled Approaches for Learning to Defer with Multiple Experts that use $\mathcal{H}$-consistency to ensure the system effectively minimizes real-world error even with limited model capacity.
- Robustness: In Cross-Entropy Loss Functions: Theoretical Analysis and Applications, the team used these bounds to create the ADV-COMP-SUM algorithm, which achieves superior adversarial robustness by optimizing a surrogate that is theoretically tighter to the robust target error.
By shifting the focus from "universal" consistency to "hypothesis-specific" consistency, this body of work provides a more realistic and mathematically rigorous foundation for the surrogate losses that power modern machine learning.