In modern search and recommendation systems, the standard recipe for Learning to Rank (LTR) is straightforward: assign a predicted score to every item (a document, a product, a video) and sort them in descending order. This "score-and-sort" approach is mathematically grounded in the Probability Ranking Principle, which suggests sorting by the probability of relevance.
However, modern ranking is rarely just about simple relevance. Systems increasingly need to account for complex trade-offs like diversity. For instance, if a user searches for "Jaguar," the optimal ranking should likely show both the car and the animal. When moving from simple relevance to these complex requirements, defining the "utility" of an item becomes challenging.
This NeurIPS 2020 paper by Clément Calauzènes and Nicolas Usunier asks a fundamental question: When is the score-and-sort approach actually consistent? In other words, for which ranking loss functions does minimizing a surrogate (like square loss regression) actually lead to an optimal ranking? The authors prove that the common practice of sorting items by a predicted score is fundamentally limited, particularly for complex tasks requiring diversity.
The "Connectedness" Litmus Test
The authors employ a rigorous mathematical framework to analyze consistency and calibration, defining a class of ranking losses called CEU (Consistent with Expected Utility). These are ranking losses that can be solved by predicting a single utility value for each item and sorting.
The paper's most elegant contribution is a novel topological condition for CEU. The authors show that a ranking loss is CEU if and only if its "sublevel sets" (the sets of rankings that are "good enough") are connected in the space of permutations.
"Connected" in this context means you can move from one good ranking to another by repeatedly swapping adjacent items without ever passing through a "bad" ranking. If a ranking task is "fragmented"—meaning there are two very different ways to provide a good ranking but no safe "path" of good rankings between them (as is often the case with diversity tasks)—then a simple scoring function will fail to capture the complexity.
Convexity is Not a Silver Bullet
A common response to difficult machine learning problems is to employ more sophisticated convex surrogate losses, such as those used in SVMs or Boosted Trees. However, the authors prove a "ceiling" effect: if any convex surrogate approach is consistent for a ranking loss, then simple square-loss regression is also consistent.
This means that for "hard" ranking problems, switching to a different convex loss won't help. You are hitting a fundamental limit of the score-and-sort paradigm itself.
The Inevitability of Local Minima
To study losses that are not CEU, the authors use a smoothed surrogate based on the Plackett-Luce model. They demonstrate that for non-CEU losses, any surrogate loss that is actually consistent must be non-convex. Furthermore, these non-convex surrogates are guaranteed to have "bad" local valleys that can trap gradient-based optimization.
The empirical evidence of this hardness is striking. By sampling probability distributions over rankings for small sets of items, they found that optimization landscapes for non-CEU metrics are minefields for standard algorithms. As illustrated above for $n=5$, local minima frequently exhibit significant sub-optimality. When scaling up to 8 items for the Expected Reciprocal Rank (ERR) metric, the authors found that nearly 70% of data distributions result in multiple local minima.
Additionally, in these difficult tasks, the optimal scoring function might need to be discontinuous. A tiny change in the input data could require a massive "jump" in the assigned scores to maintain an optimal ranking.
Key Theoretical Results
The paper formalizes these insights into two major theorems:
- Theorem 6: Establishes the equivalence between a loss being CEU and its sublevel sets being topologically connected.
- Theorem 10: Proves that a ranking loss has a convex calibrated surrogate if and only if it is CEU. This effectively categorizes which ranking problems are "easy" (convex-solvable) and which are "hard."
Limitations and Future Directions
While the score-and-sort approach is the industry standard, this paper's theoretical results suggest it might be the wrong tool for diversity-heavy tasks. To overcome these fundamental limits, the authors point toward several future directions:
- Higher-Dimensional Scoring: Moving beyond a single score per item (e.g., predicting a vector of scores) might restore consistency, though this increases computational complexity.
- Structured Prediction: Treating the entire ranking as a single object to be predicted, rather than a sorted list of independent scores.
- Direct Loss Minimization: Developing better non-convex optimization techniques that can navigate the inevitable "bad local valleys" identified in this work.
Summary updated