In machine learning, we rarely optimize what we actually care about. We care about minimizing discrete errors—like whether a classification is right or wrong, or if a structured prediction matches a complex ground truth. However, these discrete "target" losses are usually non-differentiable and computationally intractable to optimize directly.
To solve this, we use surrogate losses: smooth, convex functions like the hinge loss or log-loss that act as proxies for the target. We hope that by minimizing the surrogate, we are effectively minimizing the target. But this hope relies on a critical theoretical property called Fisher consistency.
A surrogate loss is Fisher consistent if, in the limit of infinite data, minimizing the surrogate is guaranteed to yield the optimal solution for the original target loss. Without this property, a model might remain suboptimal forever, no matter how much data you feed it.
The Hidden Inconsistency of Popular Models
It is a common misconception that a "good" surrogate for binary classification will naturally remain good when extended to more complex tasks. Research has shown that many standard tools are fundamentally inconsistent.
For example, while Support Vector Machines (SVMs) are the gold standard for binary tasks, Yufeng Liu demonstrated in Fisher Consistency of Multicategory Support Vector Machines that many popular multicategory extensions of SVMs are Fisher inconsistent. This means that even with an infinite number of samples, these models may never converge to the true Bayes optimal decision boundary.
This gap isn't limited to simple classification. In structured prediction—where we predict complex objects like graphs or sequences—the problem is even more acute. James Petterson and Tibério S. Caetano point out that max-margin estimators, despite their popularity, often suffer from statistical inconsistency in graph matching and ranking tasks Exponential Family Graph Matching and Ranking.
Why Consistency Fails
The intuition behind inconsistency is often a "misalignment" between the geometry of the surrogate and the target.
Consider the Lovász hinge, a popular loss in computer vision. Enrique B. Nueve, Rafael Frongillo, and Jessica Finocchiaro discovered that this loss is actually inconsistent for its intended task of structured binary classification The Structured Abstain Problem and the Lovász Hinge. The surrogate's optimization landscape implicitly favors "abstaining" from a prediction when uncertain, which conflicts with the requirement to provide a definitive label for every bit.
Similarly, in "Predict-then-Optimize" scenarios—where a model predicts parameters for a downstream optimization task—Andrew Perrault and Bryan Wilder found that treating loss parameters as independent instance-level variables leads to inconsistency Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize. The surrogate fails to capture how features globally influence the decision quality.
Designing Consistent Frameworks
To bridge this gap, researchers are moving away from ad-hoc surrogates toward principled "recipes" for consistency.
- Adversarial Frameworks: Instead of picking a fixed surrogate, Rizal Fathony and Xinhua Zhang propose framing learning as a minimax game against an adversary Consistent Robust Adversarial Prediction for General Multiclass Classification. This automatically generates a convex surrogate that is guaranteed to be Fisher consistent for any multiclass task.
- Polyhedral Embeddings: Jessica Finocchiaro and colleagues developed a framework to "embed" discrete losses into piecewise-linear convex functions An Embedding Framework for Consistent Polyhedral Surrogates. This provides a mathematical guarantee that the surrogate's minimum aligns with the target's minimum.
- Logit Adjustment: For long-tailed datasets, Aditya Krishna Menon and Sanjiv Kumar showed that standard loss modifications often break consistency. They introduced "logit adjustment" Long-tail learning via logit adjustment, a simple additive fix that restores Fisher consistency for balanced error.
Beyond Asymptotics: H-Consistency
While Fisher consistency focuses on the "infinite data" limit, recent work by Anqi Mao and Mehryar Mohri pushes toward H-consistency Structured Prediction with Stronger Consistency Guarantees. This is a stronger guarantee that accounts for the specific hypothesis set (the model architecture) being used. They argue that traditional methods like StructSVM and CRFs lack these strong bounds, and propose new families of "comp-sum" losses to ensure that minimizing the surrogate translates to minimizing the target even under finite data and restricted model capacities.