On ranking via sorting by estimated expected utility

Clément Calauzènes, Nicolas UsunierNeurIPS 2020 · OpenReview

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.

Visualization of ranking regions over a probability simplex, illustrating the topological connectedness required for consistent score-and-sort approaches.

"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.

Distribution of sub-optimality of local minima for Expected Reciprocal Rank (ERR) with n=5.

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:

  1. 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.
  2. Structured Prediction: Treating the entire ranking as a single object to be predicted, rather than a sorted list of independent scores.
  3. Direct Loss Minimization: Developing better non-convex optimization techniques that can navigate the inevitable "bad local valleys" identified in this work.

Summary updated

Abstract

Ranking and selection tasks appear in different contexts with specific desiderata, such as the maximizaton of average relevance on the top of the list, the requirement of diverse rankings, or, relatedly, the focus on providing at least one relevant items to as many users as possible. This paper addresses the question of which of these tasks are asymptotically solved by sorting by decreasing order of expected utility, for some suitable notion of utility, or, equivalently, \emph{when is square loss regression consistent for ranking \emph{via} score-and-sort?}. We provide an answer to this question in the form of a structural characterization of ranking losses for which a suitable regression is consistent. This result has two fundamental corollaries. First, whenever there exists a consistent approach based on convex risk minimization, there also is a consistent approach based on regression. Second, when regression is not consistent, there are data distributions for which consistent surrogate approaches necessarily have non-trivial local minima, and optimal scoring function are necessarily discontinuous, even when the underlying data distribution is regular. In addition to providing a better understanding of surrogate approaches for ranking, these results illustrate the intrinsic difficulty of solving general ranking problems with the score-and-sort approach.
BibTeX
@inproceedings{calauzenes2020ranking,
  author = {Clément Calauzènes and Nicolas Usunier},
  title = {{On ranking via sorting by estimated expected utility}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=2jnQdjkp-p},
}
Figure