When training machine learning models to rank items—whether for search engines, recommendation systems, or multi-label classification—we face a fundamental mismatch between what we care about and what we can optimize.
The evaluation metrics we care about, such as Average Precision (AP), Expected Reciprocal Rank (ERR), or multi-label ranking loss, are discrete and combinatorial. They depend on sorting and counting item permutations. Because these metrics are discontinuous, their gradients are zero almost everywhere, making them impossible to optimize directly using gradient descent.
To get around this, the standard recipe in machine learning is to replace the discrete target metric with a smooth, convex surrogate loss (such as exponential, logistic, or hinge loss) that acts as a differentiable proxy. We trust that by minimizing this proxy over a large enough dataset, our model will naturally converge to the optimal ranking. This guarantee is known as asymptotic consistency or calibration.
However, a deep body of theoretical work reveals that for many of our most important ranking metrics, this recipe is mathematically broken. For these metrics, no convex surrogate loss can ever be consistent. Even with infinite data and perfect optimization, minimizing a convex proxy will fail to find the true optimal ranking.
Understanding why this barrier exists requires looking at the geometric and structural friction between convexity and the nature of sorting.
The Geometry of Incompatibility
Why do convex surrogates fail to align with ranking metrics? The root of the problem lies in how convex functions handle trade-offs compared to how ranking metrics evaluate permutations.
A ranking metric is inherently indifferent to certain changes in model scores as long as those changes do not alter the relative order of the items. Furthermore, for many metrics, swapping the positions of two items at the bottom of a ranked list has zero impact on the final score, whereas swapping two items at the very top drastically alters it.
In On the (Non-)existence of Convex, Calibrated Surrogate Losses for Ranking, Clément Calauzènes et al. demonstrate that this "item-swapping indifference" creates a geometric conflict with convexity. Convex functions have a rigid, global curvature. They cannot easily create flat regions where the loss is indifferent to score changes in one context but highly sensitive in another, without violating the definition of convexity itself. As a result, standard ranking algorithms based on convex surrogates are asymptotically inconsistent for metrics like pairwise disagreement; more data does not guarantee a convergence to the optimal ranking.
This phenomenon is not unique to information retrieval; it also plagues multi-label learning. When evaluating models on multi-label ranking metrics, Wei Gao et al. showed that standard convex surrogate losses are fundamentally incapable of achieving Bayes consistency. The target ranking loss functions contain flat regions where multiple different score vectors yield the exact same ranking penalty. Convex surrogates, by virtue of their strict geometry, cannot align with these flat regions, preventing the model from converging to the Bayes optimal solution.
Discrete Ranking Metric (Permutation-based)
Loss
▲
│ ┌──────┐ <- Discontinuous steps, flat regions
│ ─────┘ └─────
└──────────────────► Scores
Convex Surrogate Proxy (Smooth)
Loss
▲ .
│ / . <- Rigid, continuous curvature
│ _/ \.
└──────────────────► Scores
The Limits of "Score-and-Sort"
Most modern ranking systems rely on a paradigm called score-and-sort: a model outputs a single scalar score for each item independently, and the items are then sorted by those scores. To train these models, practitioners use order-preserving losses, which penalize the model when the relative order of scores mismatches the target labels.
This approach works beautifully for some metrics, but fails completely for others. In Learning Scoring Functions with Order-Preserving Losses and Standardized Supervision, David Buffoni et al. established a fundamental divide between ranking objectives:
- Standardizable Metrics: Metrics like Normalized Discounted Cumulative Gain (NDCG) can be consistently optimized using order-preserving losses.
- Non-Standardizable Metrics: Metrics like Average Precision (AP) and Expected Reciprocal Rank (ERR) lack the mathematical structure required to be standardized into a pairwise, order-preserving framework.
In a companion analysis published in Machine Learning, Clément Calauzènes et al. proved that order-preserving surrogate losses are fundamentally incapable of being calibrated for MAP or ERR. Because these top-heavy metrics possess complex, non-linear dependencies across the entire ranked list, a simple independent scoring mechanism cannot capture the contextual value of an item's position. The common practice of scoring items in isolation and sorting them is theoretically ill-suited for these objectives.
The Regression Ceiling
If complex convex surrogates fail, can we design a more sophisticated, higher-dimensional convex loss to fix the issue?
A remarkable result by Clément Calauzènes et al. places a hard ceiling on what convex surrogates can achieve. They proved a sweeping equivalence theorem: for any ranking loss, if a consistent convex surrogate loss exists, then simple square-loss regression is also a consistent surrogate.
This means that if a ranking problem is too complex to be solved by predicting expected utilities via simple least-squares regression, switching to a more intricate convex surrogate will not save you. If regression fails to achieve consistency for a specific metric, every possible convex surrogate approach is guaranteed to fail as well. This establishes a clear boundary for researchers: to achieve consistency on sophisticated ranking tasks, one must abandon convex approximations entirely and explore non-convex or structural alternatives.
Broader Implications across Machine Learning
The limits of convex calibration ripple across several adjacent domains in machine learning, exposing similar structural bottlenecks:
- Property Elicitation: In Arpit Agarwal et al., the authors connect surrogate risk minimization to probability forecasting. They show that a calibrated surrogate loss function is essentially estimating a specific summary statistic (or "property") of the data distribution. Many complex target properties in supervised learning simply cannot be elicited using convex scoring rules, restricting the availability of easily optimizable losses.
- Low-Rank Constraints: When dealing with subset ranking losses, Harish G. Ramaswamy et al. demonstrated that no low-dimensional, score-based surrogate loss can be calibrated across all possible data distributions, forcing a trade-off between computational dimensionality and theoretical consistency.
- Adversarial Attacks: The failure of convex surrogates even impacts adversarial machine learning. In Thomas Paniagua et al., the authors found that traditional heuristic surrogates (like modified cross-entropy) become highly inconsistent when trying to force a neural network to predict a specific sequence of multiple target classes. Because these surrogates lack the mathematical rigor to maintain precise relative rankings as the number of constraints grows, the authors had to pivot to quadratic programming to guarantee the target sequence order.
Moving Beyond Convexity
The collective evidence from these papers shows that the convenience of convexity comes at a steep theoretical cost. When our evaluation metrics depend on the intricate, non-linear combinatorial structure of a ranked list, convex proxies eventually lose their alignment with the true objective.
To bypass this limit, the field has evolved toward alternative paradigms. This includes exploring non-convex surrogates, leveraging automated loss function searches bounded by combinatorial constraints like the "Strong Ranking Property" (Boshi Wang et al.), or designing frameworks that optimize structural, non-order-preserving objectives. Recognizing the inherent boundaries of convex surrogates allows practitioners to stop fighting the geometry of convexity and instead build optimization frameworks designed for the discrete reality of ranking.
Key Foundational Work
"On the (Non-)existence of Convex, Calibrated Surrogate Losses for Ranking" (2012) — contributed 5 concept elements to this direction.
On the Consistency of Multi-Label Learning (2011) — contributed 4 concept elements to this direction.
Learning Scoring Functions with Order-Preserving Losses and Standardized Supervision (2011) — contributed 3 concept elements to this direction.