PiRank: Scalable Learning To Rank via Differentiable Sorting
Authors: Robin Marcel Edwin Swezey
Aditya Grover
Bruno Charron
Stefano Ermon
Venue: NeurIPS 2021 Poster (2021)
Keywords: learning-to-rank
differentiable sorting
continuous relaxations

Abstract: A key challenge with machine learning approaches for ranking is the gap between the performance metrics of interest and the surrogate loss functions that can be optimized with gradient-based methods. This gap arises because ranking metrics typically involve a sorting operation which is not differentiable w.r.t. the model parameters. Prior works have proposed surrogates that are loosely related to ranking metrics or simple smoothed versions thereof, and often fail to scale to real-world applications. We propose PiRank, a new class of differentiable surrogates for ranking, which employ a continuous, temperature-controlled relaxation to the sorting operator based on NeuralSort [1]. We show that PiRank exactly recovers the desired metrics in the limit of zero temperature and further propose a divide-and-conquer extension that scales favorably to large list sizes, both in theory and practice. Empirically, we demonstrate the role of larger list sizes during training and show that PiRank significantly improves over comparable approaches on publicly available Internet-scale learning-to-rank benchmarks.

PiRank: Scalable Learning To Rank via Differentiable Sorting
Robin Swezey!
Aditya 2
Bruno Charron
Stefano Ermon
Amazon
University of California, Los Angeles
3 Facebook Al Research
*Stanford University
{rswezey, bcharron]@aaer org, adi tyag@cs www.ccclcccc..... edu, ermonêcs. stanford. edu
Abstract
A key challenge with machine learning approaches for ranking is the gap between the performance metrics of interest and the surrogate loss functions that can be optimized with gradient-based methods. This gap arises because ranking metries typically involve sorting operation which is not differentiable w.r.t. the model parameters. Prior works have proposed surrogates that are loosely related to ranking metrics simple smoothed versions thereof, and often fail to scale to real-world applications. We propose PiRank, a new class of differentiable surrogates for ranking, which employ continuous, cemperature-controllee relaxation the sorting operator based on NeuralSort [T]. We show that PiRank exactly recovers the desired metrics in the limit of zero temperature and further propose divide- and-conquer extension that scales favorably to large list sizes, both in theory and practice. Empirically, we demonstrate the role of larger list sizes during training and show that PiRank significantly improves over comparable approaches on publicly available internet-scale carning-to-rant benchmarks.
Introduction
The goal of Searning-To-Rani (LTR) models is to rank set of candidate items for any given search query according preference criterion [2]. The preference over items is specified via relevance labels for each candidate. The fundamental difficulty in LTR is that the downstream metrics of interest such normalized discounted cumulative gain (NDCG) and average relevance position (ARP) depend on the ranks induced by the model. These ranks are not differentiable with respect to the model parameters, so the metrics cannot be optimized directly via gradient-based methods.
To resolve the above challenge, popular class of LTR approaches map items to real-valued scores and then define surrogate loss functions that operate directly these scores. Surrogate loss functions, in turn, can belong to one three types. LTR models optimized via pointwise surrogates 3 O cast ranking as regression/Classficatiio problem, wherein the labels of items are given by their individual relevance labels. Such approaches do not directly account for any inter-dependenccess across item rankings. Pairwise surrogate losses (7-14) be decomposed into terms that involve scores of pairs of items in list and their relative ordering. Finally, listwise surrogate losses [15][99 are defined with respect scores for an entire ranked list. For many prior surrogate losses, especially those used for listwise approaches, the functional form is inspired via downstream ranking metrics, such as NDCG. However, the connection loose heuristically driven. For instance, SoftRank (14 [9 introduces Gaussian distribution over scores, which in turn defines distribution over ranks and the surrogate is the expected NDCG w.r.t. this rank distribution.
TThis work was done prior to joining Amazon.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We propose PiRank, listwise approach where the scores are learned via deep neural networks and the surrogate loss is obtained via differentiable relaxation to the sorting operator. In particular, we choose as building block the comperature-controll commonly used ranking metrics such as NDCG and ARP. The resulting training objective for PiRank reduces to the exact ranking metric optimization in the limit of zero temperature and trades off bias for lower variance in the gradient estimates when the temperature is high. Furthermore, PiRank scales to real-world industrial scenarios where the size of the item lists is very large but the ranking metrics of interest are determined by only a small set of top ranked items. Scaling is enabled by novel divide-and-conuue strategy akin to merge sort, where recursively apply the sorting relaxation to sub-lists of smaller size and propagate only the top items from each sub-list for further sorting.
NouralSort [1] relaxation for sorting and specialize it for
Empirically. we benchmark PiRank against 5 competing methods on two of the largest publicly available L.TR datasets: MSL.R-EEB300 W-R3330 (20) and Yahoo! C14. We find that PiRank superior or competitive on 13 out of 16 ranking metrics and their variants, including on which it is significantly superior to all baselines, and that it is able to scale to very large item lists. We also provide several ablation experiments to understand the impact of various factors performance. To the best of our knowledge, this work the first to analyze the importance of training list size on an LTR benchmark. Finally, we provide an open-source implementation based on TensorFlow Ranking 21
2 Background and Related Work
The LTR setting considers a finite dataset consisting triplets == {g: { fut. 1 Di The i-th triplet consists of query q: E Q, list of L candidate items represented as feature vectors Ri E X, and query-specific relevance labels yt,, for each item j. The relevance labels Yi.j can be binary, ordinal or real-valued for more fine-grained relevance. For generality, we focus on the real-valued setting. Given a training dataset D, our goal is to learn a mapping from queries and itemsets to rankings. A ranking и is a list of unique indices from 21,2..... L}. equivalently permutation, such that πTy is the index of the item ranked in j-th position. Without loss of generality, assume lower ranks (starting from 1) have higher relevance scores. This is typically achieved by learning a scoring function f Q x X -> R that maps a query context and list candidate items to L scores. At test time, the candidate items are ranked by sorting their predicted scores in
descending order. The training of f itself can be done by a suitable differentiable surrogate objective, which we discuss next.
2.1 Surrogate Objectives for LTR
In this section, we briefly summarize prominent LTR approaches with representative loss function for each category of pointwise, pairwise or listwise surrogate losses. We refer the reader to the excellent survey by [2 for more extensive review. Omitting the triplet index, denote the relevance labels vector as y E R and an LTR model's score vector obtained via the scoring function ý R
The simplest pointwise surrogate loss for ranking is the mean-squared error (MSE) between y and ğ:
1 Σ (0:- y:)²
Aase(y. θ)
As the example loss above shows, pointwise LTR approaches convert ranking into a regression problem over the relevance labels and do not account for the relationships between the candidate items. Pairwise approaches seek to remedy this by considering loss terms depending in the predicted scores of pairs of items. For example, the widely used RankNet ( aims minimize the number of inversions, or incorrect relative orderings between pairs of items in the predicted ranking. It does so by modeling the probability P., that the relevance of the i-th item higher than that of the --thh item as a logistic map of their score difference, for all candidate items i, i'. The objective is then the
httpss//gthhbb.co///mmmooooopppp

---

cross-entropy:
I.
@RankNet (3.
(yt > ye log Pi,K"
where (-) denotes the indicator function and Pr,.r is function of ÿ. Pairwise approaches effectively model relationships between pairs of items and generally perform better than pointwise approaches, but still manifest limitations on downstream metrics which consider rankings in the full list and not just pairs. fact, the larger the list of candidate items, the weaker these approaches tend to be: an error between the first and second item on a list weighted the same in the RankNet loss as one between the last two items, despite the top items being of more importance in the LTR setting.
Listwise approaches learn from errors on the complete list. LambdaRank assigning weights to every loss term from Eq 2
B extends RankNet by
L
LaambdaRank (y. 9)
Σ
AÉNDCG log Pt.y'
(3)
(=1 d=1
with AinDOG i') the difference in the downstream metric NDCG (defined below) when swapping items and i'
2.2 Ranking Metries
Downstream metrics operate directly on the predicted ranking म (obtained by sorting ý in descending order) and the true relevance labels y. They differ from conventional metrics used for other supervised learning problems in explicitly weighting the loss for each item by suitably choosen increasing function of its predicted rank. For example, relevance position (RP) [23] multiplies the relevance labels with linearly increasing weights, and normalizes by the total relevance score for the query:
RP +) = EEー V#.J
Σ/ Uj
Averaging RP across the predictions made for all the queries in the test set gives the average relevance position (ARP) metric. Lower ARP signifies better performance.
A very common metric is the discounted cumulative gain (DCG) 24 DCG computes the rescaled relevance of the j-th candidate by exponentiating its relevance label, and further divides it by the assigned log-ranking. This model incentivizes ranking models to focus on elements with higher graded relevance scores:
1.
2 log2 (1 +)
DCG ft)
(5)
more common variant NDCG normalizes DCG by the maximum possible DCG attained via the optimal ranking n* (obtained by sorting y in descending order):
DCG(y,
NDCG #) DCG (y. x*)
(6)
Higher DCG and NDCG signify better performance. Their truncated versions DCG@ k: and NDCG@k defined by replacing with cutoff l in Eq. metrics are computed the top-k items.
3 Scalable and Differentiable Top-k Ranking via PiRank
In PiRank, we seek to design new class of surrogate objectives for ranking that address two key challenges with current LTR approaches. The first challenge is the gap between downstream ranking metric of interest (e.g., NDCG, ARP) that involve non-differentiable sorting operator and the differentiable surrogate function being optimized. The second challenge concerns the scalability w.r.t. the size of the candidate list L for each query item. Larger list sizes standard

---

LambdaRank
PiRank
93
9,-
y:2 85
3/4 0, 94 - 0.3
1.
92 0.2
Yr. 9,= 0.1
Figure I: A set of items, green if relevant and gray otherwise, sorted by their score. Arrows show the sign each item's predicted score for different methods (positive for black, negative for
of the loss derivative green and zero for red dots). Pairwise approaches weighted by differences truncated ranking metrics, LambdaRank with NDCG@k, would put zero weights on the relevant items ranked below k = 2. thus bypassing learning signal. In comparison, PiRank efficiently learns from all items even using k = 2 truncated loss.
as
in industrial applications but present computational and memory challenges for current approaches during both training and test-time inference. Pairwise and listwise methods (or hybrids) typically scale quadratically in the list size L, the number items to rank for each query. Combining surrogates for truncated metrics, such LambdaRank in Eq. 3 with NDCG@A k has a reduced complexity of Okk but comes at the cost of vanishing gradient signal from relevant entries below (see Figure for an illustration). Soft versions of the truncation metrics, such Approximate NDCG Loss (25] can learn from all items but again scale quadratically with L or do not take advantage of GPU acceleration [26].
As defined previously, ranking is list of indices equivalent to permutation of 21, L}. The set of possible rankings can thus be seen as the symmetric group St. size L!. Every permutation i can be equivalently represented as a permutation matrix P,, an L L matrix such that its m;)tt) entry is for all i E 21,2.... ... L} and the remaining entries are all 0. We define the sorting operator map of an L-dimensional input vector the permutation that corresponds to the
sort: R / - Sy descending ordering of the vector components. Prior work in relaxing the sorting operator is based on relaxation of its output, either in the form of rankings [19] 26 27 or permutation matrices [ 30). PiRank first applies the latter kind of relaxations to the ranking problem by introducing new class of relaxed LTR metrics, then introduces
relaxation that is particularly suited these metrics.
3.1 Relaxed Ranking Metries
denote an LTR model by Se (e.g.. deep neural network) with parameters The model outputs vector of L scores ÿ fe (q. Ii...., xt) for query q and L candidate elements {x,)]- We first consider the NDCG target metric. In Eq. 6 the numerator DCG f) involves computing f sort(ÿ) which is non-differentiable w.r.t. 6. Let g denote the column vector of graded relevance scores such that gj = 2 1. We can then rewrite DCG f) as:
Jh
[Pag] log, +
DCG(y,
log
+
To obtain the DCG@ objective, one can replace L with k in the sum. We omit the suffix @k in the following, assuming that has been defined, potentially equal to L which would yield the full metric.
Let P Po (T) denote relaxation the permutation matrix Psort(s) that can be used for differentiable sorting of an input score vector s, for some temperature parameter r > 0 such that the true matrix is recovered as т + 0+. Since sort(ğ) we can obtain a differentiable relaxation to DCG f):
k (sont(i) (T)gl,
DCG(y. ÿ.T)
Σ
log + +j)

---

pr
Shared
PiRank relaxation
NN
PiRank
Loss
Figure 2: Architecture for the computation of the PiRank relaxed NDCG@A loss for L and k: 2. Square cells represent scalars with darker shades indicating higher values. The fourth item has currently the highest score as given by the neural network hut second item has highest relevance. The vector c, with components = 1/ log(1 + j), discounts gains g hased on rankings.
0.9
0.1
0.8
0.2
0
0.5
0.01
0.49
0.2
0.3
0.5
0.5 0.09 0.41
0.25
0.6
0.15
Figure 3: Doubly-stochastic (left) vs. unimodal (right) matrices. Maximum entry in every row in bold. Unlike unimodal matrices, two different items can have the same assignment of most-likely ranks (column indices) for doubly-stochastic matrix relaxations.
Substituting this in the expression for NDCG Eq.
we obtain the following relaxation for NDCG:
NDCG Ú: r) = DCG D.T) DCG(y,
where the normalization in the denominator does not depend on and can be computed exactly via regular sorting. Finally, we define the PiRank surrogate loss for NDCG as follows:
/PIRank-NDCG = NDCG ④)
(10)
which is bounded between and as NDCG, and whose difference with the actual (1 NDCG) gets negligible + 0+. Figure 2 illustrates the model architecture for the above objective. Similarly, we can derive a surrogate loss for the ARP metric in Eq. as:
Σ/= [P sort( (T)
APRRAnt-ARPy,...77
(11)
ΣØ=1 M/
3.2 Example: Differentiability via NeuralSort
Typically, relaxations to permutation matrices consider the Birkhoff polytope of doubly stochastic matrices. doubly-stochastic matrix is a square matrix with entries [o, 1] where every row and column sum to 1. In contrast, NeuralSort (T] is recently proposed relaxation of permutation matrices in the space of unimodal row-stochastic matrices. A unimodal matrix is square matrix with entries in [0, 1] such that the entries in every row sum to (i.e. row-stochastic), but additionally enforce the constraint that the maximizing entry in every row should have unique column index. See Figure for an example of each type. Note that a unimodal matrix is not necessarily vice versa. Permutation matrices are both doubly-stochaste and unimodal.
and
In NeuralSort [1, a unimodal relaxation of the permutation matrix Peort(g) can be defined as follows. Let Ag denote the matrix of absolute pairwise score differences with j-th entry given as [Ayly = 1ū, 0zl. Then, the i-th row of the relaxed permutation matrix is:
P sort(g) (T),. softmax [((L + 21)g Ag1)/r]
(12)
where 1 is the vector with all components equal to 1. Its unimodal property makes it particularly well-suited extracting top-k items because, as seen in Figure 3] taking the maximizing elements of the first & rows yields exactly items but may yield less in the case of doubly-stochastic relaxation. However, the complexity to obtain the top-k rows in this formulation, even for as low as 1, quadratic in I as the full computation of Ag 1 is required for the softmax operation in Eq. T2 This prohibitive when > a common scenario, and motivates the introduction of new relaxation with more favorable complexity for top-k ranking.
5

---

[0.7. = P.0))
[0.5, 0.3
[0.7.0.4] P(
[0.2]
[0.5]
[0.3]
[0.4]
[0.1]
[0.7] 332
Figure 4: Divide-and-conquer strategy for L. = 6= 3 2, k 2 and g" = 0.5, 0.4,0.1,0077 The scores are merged in groups of size 6 = 3 and the respective top k1 2 scores are kept, then the by = 2 outputs are merged to obtain the final top ly = & 2 scores. The effect of relaxation is not shown for readability. At non-zero temperature, the values at non non-terminal nodes would be linear combination of the scores.
3.3 Scaling via Divide-And-Conquee
Our PiRank losses only require the first & rows of the relaxed permutation matrix P Paort(g)- This is specific to the LTR setting in which only the top-ranked items are of interest, in contrast to the full sorting problem that requires the full matrix. In PiRank, we leverage this insight to construct divide-and-conquer variant of differentiable sorting relaxations such as NeuralSort to reduce the complexity the metric computation. Our proposed construction can be viewed as a relaxed and truncated multi-way merge sort algorithm with differentiable sorting relaxations as building blocks. In the following discussion, we use NeuralSort as our running example while noting that the analysis extends more generally to other differentiable relaxations well.
Data Structure Construction. Let = b.bg...bb be a factorization of the list size into d positive integers. Using this factorization, we will construct tree of depth d with branching factor b, at height j. Next, we split the L-dimensional score vector ý into its L constituent scalar values. We set these values as the leaves of the tree. See Figure 4 for example. At every other level of the tree, we will merge values from the level below into equi-sized lists. Let {kz]ğ be sizes for the intermediate results at level j. such that ky = 1 (leaves) and min(k, ky-1 S kj S ky-1b; for j 2 1 (cxplained below). Then, in an iterative manner for levels node at height j are the top-k, scores given by the application of the NeuralSort operator on the concatenation of the values of its children. With ka k. the root value thus obtained is a relaxation of the top-k scores in The top-k rows of the relaxed permutation matrix Psort(g) yielding these scores are constructed by compounding the operations at each iteration.
1, L...., d, the value of
Computational Complexity. The intuition behind the favorable scaling is as follows. At step j. NouralSort is applied on blocks of size kj-1 as it merges b, sub-blocks of size k Obtaining the full sorted list of scores would require to keep all intermediate scores during the process, i.e., list
4 ((max) = bj -..b, b,- -j for > 1. In the last step, the NeuralSort operator is applied of size ka-iba. equal to L in this case, so the overall complexity would be at least quadratic in L as explained previously. However, since only the top-k scores are desired, intermediate outputs can be truncated larger than k. Full truncation corresponds to k/minn = min(k, kyz) Any choice 25min) < kj S k/max) is acceptable recover the top-k scores, with larger values allowing more information to flow at the expense of a higher complexity. Choosing bj Ro L and ky minimal, the list sizes kyk on which NeuralSort is applied at each step can thus be of the order of 2/44,, much smaller than L in the d > 1 and l & L scenario.
Formally, let 71, T2,..... Ta be the relaxation temperatures at each height, with Ta = T and ry S TT+1 for j (1...., d 1). Define the tensor (r()) by reshaping ý to shape (ko, by be,..., ba), yielding components
(0) L. D1 b2
(13)
with in E {l....,b,, b,}} and the first index is always as ko 1. With the tree representation, the first tensor index is the position in the node value vector and the rest of the indices identify the node by the index of each branching starting from the root. For j E 21,2,... d}. recursively define the tensors Q(1) ( and p(i of respective shapes (k2, ky- 1,, bj.... ... ba). (kj, b,+1...... bb)) and

---

Loss Metric
OPA
ARP
MRR
NDCG@1 1
NDOU
NDCO@S
NDCO@T0
NDCU@11
KankNet
0.61
46,740979
0.786148
0.331595
0.336593
0,340928
0.375944
0,398582
LambdaRank
0,618954
46,174503
0.798169
0.392150
0.396045
0,404275
0,426611
0,444942
Softmax
0.612626
46,557617
0.761750
0.331527
0,338999
0,353011
0.381717
0,405312
Approx. NDCG
0.630616
45.461678
0.814873
0,423497
0,409272
0,414501
0,434463
0.453627
NeuralSort
0.635468
44.966999
0.779865
0.373344
0,386647
0,402052
0,450580
0.452863
PiRank-NDCG
0.629763
45,394020
0.813016
0.425006
0.420569
0.426034
0.446428
0.465309
Loss Metric
OPA
ARP
MRR
NDCG@
NDCG@3
NDCG@
NDCG@ 10
NDCG@15
RankNet
0.625170
10,514806
0.599739
0.622155
0.650367
0.704332
0.733015
LanhdaRank
0.636126
10.451870
0.896020
0.633181
0.652220
0.676243
0.723489
0.749001
Soltmax
0.627313
10.472106
0,886976
0.588957
0.618409
0,648358
0.703746
0.732624
Approx. NDOG
0,648793
10,277598
0,903356
0.668700
0.670107
0.690353
0,735641
0,760539
NeuralSort
0.6484416
10,320462
0.898246
0.6400188
0.655990
0.681075
0.729225
0.754867
PiRank NDCG
0.654255
10,250481
0.661661
0.693825
0.763864
Table 1: Benchmark evaluation on (upper) MSLR- MSLR-WEB WEB30K and (lower) Yahoo! C14 test sets. In bold, the best performing method and all other methods not significantly worse.
(ky, bi....,bal with components
kz-1
Pimisg...s softmax (1kj- +1 1-1-20 -21)D(--1
(
v(1-1)
(14)
h by
P00
(1)
Fリ-1)
(15)
I.g.
p= g
kj
p6) Lii....
2
p L.m.iy......
(16)
with (() 1. Intuitively, ÿr6) holds the relaxed top-ky scores at height j and ( is the desired
k score vector. The interpretation of the indices in the tree structure as for y-(0), illustrated in
Figure 4 More importantly, we keep track of the relaxed sorting operation that yielded this output. Q(1) is the relaxed permutation matrix obtained by applying NeuralSort in Eq. 12 to ÿr()), while Pl))
compounds the relaxed permutation matrices obtained so far so it always maps from the initial list size. Finally, define the k x L matrix Í by reshaping the tensor p(d), yielding components
P 14 b = -((d)
(17)
for in E (1....,bj}, The I rows of P are used as the top-k rows of the relaxed sorting operator Psont(g) (T). This approach equivalent to NeuralSort, yielding Eq. 12 for convergence for r + 0+ of this relaxation in the general case 2 is presented in Appendix B In the simple case where L = 3d and we set by = b, k2 = min k,, 8²) for all j E {1....,.)) .d). the complexity to compute P and thus the PiRank losses is then O(T,+11dd + (d - 1)4² L),, which scales favorably in T. if
Proof of
and k = O(1). In the general case, the score list can be padded, e.g. to the power of 2 following L, such that the previous complexity holds for b = 2 and d = [log2 L1, but other factorizations may yield lower complexity depending on L.
4 Experiments
We present two sets of experiments in this section: (a) benchmark evaluation comparing PiRank with other ranking based approaches on publicly available large-scale benchmark L.R datasets, and (b) ablation experiments for the design choices in PiRank.
7

---

0=0.1
0.40
[=1
0.35
T-10
0.30
0.25
0.20
20000
40000
60000
80000
100000
Training
Figure 5: 1 (riankk NDDGGk (k 10, full lines) for different values the temperature parameter r, with the corresponding value of the hard metric NDCG@ 10 (dashed lines), at validation.
4.1 Benchmark Evaluation via TF-Ranking
Datasets. To empirically test PiRank, we consider two of the largest open-source benchmarks for LTR: the MSLR-WEBSHE and the Yahoo! LTR dataset C14 Both datasets have relevance scores on 5-point scale of with 0 denoting complete irrelevance and 4 denoting perfect relevance. We give extensive details on the datasets and experimental protocol in Appendix
Baselines. We focus on neural network-basse approaches and use the open-source TensorFlow Ranking (TFR) framework (2T). TFR consists of high- sugh-qualtty GPU-friendly implementations of several LTR approaches, common evaluation metrics, and standard data loading formats. We compare our proposed loss, PiRank-NCDG. with the following baselines provided by TensorFlow Ranking: Approximate NDCG Loss (25). Pairwise Logistic Loss (RankNet, Eq. P. Pairwise Logistic Loss with lambda-NDCG weights Raak, Eq-Bi 3 and the Softmax Loss. We also include NeuralSort, whose loss is the cross-entrops of the predicted permutation matrix. Of these methods, the Pairwise Logistic Loss (RankNet) is a pairwise approach while the others listwise. While our scope is on differentiable ranking surrogate losses for training neural networks, other methods such as the 31 could potentially yield better results.
tree-based LambdaMART
Setup. All approaches the same 3-layer fully connected network architecture with ReLU activations to compute the scores ÿ for all (query, item) pairs, trained on 100,000 iterations. The maximum list size for each group of items score and rank is fixed 200, for both training and testing. Further experimental details are deferred to Appendix C We evaluate Ordered Pair Accuracy (OPA), Average Relevance Position (ARP), Mean Reciprocal Rank (MRR), and NDCG@K k with E (1,3,5, 10, 15). We determine significance similarly to [32]. For each metric and dataset, the best performing method is determined, then one-sided paired t-test 95% significance level is performed on query-level metrics on the test set to compare the best method with every other method.
Results. Our results are shown in Table I Overall, PiRank shows similar or better performance than the baselines 13 out of 16 metrics. significantly outperform all baselines NDCG@ @ for & 2 5 while Approx. NDCG is competitive on NDCG @ for and MRR. PiRank is also significantly superior on OPA and ARP metries Yahoo! C14 while NeuralSort is superior for MSLR-WEBB3KK.
4.2 Ablation Experiments
Temperature. The temperature hyperparameter 7 used PiRank to control the degree of relaxation. We experiment several values (7 E {0.1, 1, 5,5, 10}) using the HSSL-WEB300 dataset and the experimental settings for ablation provided in Appendix C Figure 5 demonstrates the importance of correctly tuning High values (r > 1) speed up training, especially in the early regime, while low values induce large gradient norms which are unsuitable for training and lead to the
loss stalling or even diverging. Another observation that the relaxed metric & NDCG@
"htrp://wwww.mccrooff.t http://wwww.....ooooo...///////a
httpss//webssooeessadooo....aaa sandbox, www.o........ccommm..moo.mmmmoo.

---

Lraan
Lian
Loan
100
25%
Relative Improvenvett
Lows 40
25%
0%
20
25%
0%
10
0%
10
Figure 6: Relative improvement NDCG@R on different values Lrest, for different Lerain values vs. baseline of Terain = 10.
d'3
100
1000
1500
2000
2500
3000
3500
Luain
Figure 7: Wall-clock time for 100 training steps, each corresponding to 16 queries, for different Leroen and maximal depth d. We & 1 and Ltrain 5 10 13 and 15 such that Lerain 6 for and ky 1. Variation runs too small (~-Is) and omitted for brevity.
closely follows the value of the downstream metric NDCG@ l expected. We further experimented with very high temperature value and an exponentially decreasing annealing schedule in Appendix D
Training List Size. The training list size parameter Ltrain determines the number of items to rank for a query during training. The setting is the same as for the temperature ablation experiment, but with training list sizes Ltrain E {10, 20, 40, 100} which we then evaluate testing list sizes in the same range of values Liest (10, 20, 40, 100). The dataset again MSLR-WEB30K Figure exposes four patterns for NDCG@N k. First, for fixed Liest and k, larger Ltrain is always better. Second, for fixed Lieats we observe diminishing returns along k, as relative improvements decrease for all Ltroin. This observation is confounded by NDCG@ values growing larger with k, but the metric always able to distinguish between ranking functions [33]. Third, for fixed k, our returns along Leest increase with Ltraën (except for Itrain 20 and k == 1). This means that the need for a larger Ltrain more pronounced for larger values of Ltest- Fourth and last, the returns increase most dramatically with Lirain when Ltest > (top left), common industrial setting. Values for NDCG@ k, MRR, OPA, ARP are provided in Appendix D For MRR, using a larger Lirain is always beneficial regardless of Lrest, but always for OPA and ARP.
Depth. A main advantage of the PiRank loss is how can scale very large training list sizes Ltrain- This setting is difficult to come across with traditional LTR datasets, which are manually annotated, but occurs frequently in practice. One example is when the relevance labels are obtained from implicit signals such clicks purchases in recommendation systems. In this case, an LTR model is used to re-rank list of candidates generated by another, simpler, model choosing among all possible items those potentially relevant to query context. An LTR model capable of handling very large lists can reduce the impact of errors made by the simpler candidate generation step, moving to the top item lowly ranked at first that would have been cut off from a smaller list. To test the complexity shown in Section 3.2 in extreme conditions, we create a synthetic dataset as described in Appendix E Figure shows how the training time for depth d = 3 scales much more favorably than for d = 1, following their respective time complexities of (11+1/33 and O(L2).

---

Summary and Limitations
We proposed PiRank, novel class of surrogate loss functions for Learning-Tow -o-nnnkk (LTR) that leverages a continuous, lemperature-controlle relaxation to the sorting operator [T] as a building block. This allows to recover exact expressions of the commonly used non-differentiable ranking metrics in the limit of zero temperature, which we proved in particular for the NDCG metric. Crucially, we proposed a construction inspired by the merge-sort algorithm that permits PiRank scale to very large lists.
In experiments the largest publicly available LTR datasets, observed that PiRank has superior or similar performance with competing methods on the MSLR-WEB30K and Yahoo! C14 benchmarks 13/16 ranking metrics and their variants.
As future work, we would like to explore other recent relaxations of the sorting operator 26 34 35
as building block for the PiRank framework. Further, ranking is core component of modern day technology and influences everyday decision making pipelines involving vulnerable populations, care needs to be taken that proposed systems are extended to account for biases and fairness criteria when deployed in real world settings.
Acknowledgements
Robin Swezey and Bruno Charron supported by Rakuten, Inc. Stefano Ermon is supported in part from NSF (#1 (#1651565, #1665,11122 #1522054, #1733686), ONR (N00014- 19-1-2145), AFOSR 1449550-19-1-002 and Bloomberg.
References
[1] Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In ICLR, 2019.
[2] Tie-Yan Liu et al. Learning to rank for information retrieval. Foundations and Trends Information Retrieval, 3(3):225-333 331,-331,222 2009.
[3] David Cossock and Tong Zhang. Subset ranking using regression. In COLT, 2006.
[4] Ping Li, Qiang Wu, and Christopher Burges. Mcrank: Learning to rank using multiple classification and gradient boosting. In NeurIPS, 2008.
[5] Koby Crammer and Yoram Singer. Pranking with ranking. In NeurlPS, 2002.
[6] Amnon Shashua and Anat Levin. Ranking with large margin principle: Two approaches. NeurIPS, 2003.
[7] Ralf Herbrich. Large margin rank boundaries for ordinal regression. Advances in large margin classifiers. pages 115-132, 2000.
[8] Yoay Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. JMLR, 4(Nov):933-96) 2003.
[9] Chris Burges, Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In /CML, 2005.
[10] Christopher JC Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11(23- 581):81, 2010.
[11] Zhaohui Zheng, Hongyuan Zha, Tong Zhang, Olivier Chapelle, Keke Chen, and Gordon Sun. A general boosting method and its application to learning ranking functions for web search. In NeurIPS, 2008.
[12] Yunho Cao, Jun Xu, Tic- Liu, Hang Yalou Huang, and Hsiao- Hon. Adapting ranking svm document retrieval. SIGIR, 2006.
[13] Christopher J.C. Burges, Robert Ragno, and Quae Viet Le. Learning to rank with nonsmooth cost functions. In NeurIPS, 2007.
[14] Mingrui Wu, Chang, Zhaohui Zheng, and Hongyuan Zha. Smoothing DCG for learning to rank: novel approach using smoothed hinge functions. In C/KM, 2009.
[15] Zhe Cao, Tao Qin, Tin Liu, Ming-Feng Tsai, and Hang Li. Learning rank: from pairwise approach to listwise approach. In JCML, 2007.
[16] Fen Xia, Tie- Yan Liu. Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In ICML, 2008
10

---

[17] Jun Xu and Hang Li. Adarank: boosting algorithm for information retrieval. In SIGIR, 2007.
[18] Yisong Yue, Thomas Finley, Filip Radlinski, and Thorsten Joachims. support vector method for optimizing average precision. In SIGIR, 2007.
[19] Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka. Softrank: optimizing non-smooth rank metrics. WSDM, 2008.
[20] Tao Qin and Tin Liu. Introducing LETOR 4.0 Datasets. 2013.
[21] Rama Kumar Pasumarthi, Scbastian Bruch, Xuanhui Wang, Cheng Li, Michael Bendersky, al. Tf-ranking: Scalable tensorflow library for learning- to rank.. In KDD, 2019.
[22] Tie- Yan Liu. Learning rank for information retrieval. Springer Science & Business Media, 2011.
[23] Mu Zhu. Recall, precision and average precision. Depariment of Statistics and Actuarial Science, University of Waterloo, Waterloo, 2:30, 2004.
[24] Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain-based evaluation of techniques. ACM Transac- tions on Information Systems, 20(4):422 446, 2002.
[25] Tao Qin, Tie-Yan Liu, and Hang L.. A general approximation framework for direct optimization of information retrieval measures. Information retrieval, 13(4)3375-397, 2010.
[26] Mathicu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In /CML, 2020.
[27] Olivier Chapelle and Mingrui Wu. Gradient descent optimization smoothed information retrieval metries. Information retrieval, 13(3))216-235, 2010.
[28] Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhom propagation. arXiv preprint 11X. 1925, 2011.
[29] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning Latent Permutations with Gunbel-Sinkhorn Networks. In ICLR, 2018.
[30] Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable Ranks and Sorting using Optimal Transport. In NeurlPS, 2019.
[3]] Chris Burges, From RankNet LambdaRank to LamblaMART. An Overview. JMLR, 474455774- 2010.
[32] Sashank Reddi, Rama Kumar Pasumarthi. Aditya Krishna Menon, Ankit Singh Rawat, Felix X. Yu, Seungyeon Kim, Andreas Veit, and Sanjiv Kumar. Rankdistil: Knowledge distillation for ranking. In AISTATS, 2021.
[33] Yining Wang, Liwei Wang, Yuanzhi Li, Di He. Wei Chen, and Tie Yan Liu. A theoretical analysis of NDCG ranking measures. JMLR, 30:25-54, 2013.
[34] Sebastian Prillo and Julian Eisenschlos. Softsort: A continuous relaxation for the argsort operator. In ICML, 2020.
[35] Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, et al. Differentiable top-k operator with optimal transport. arXiv preprint 20Xxi:0002.06600 2020.
[36] Lconardo Rigutini, Tiziano Papini, Marco Maggini, and Franco Scarselli. Sortnet: Learning rank by neural preference function. IEEE transactions on neural networks, 22(9):1368-1383 2011.
[37] Ziqiang Cao, Furu Wei, Li Dong, Sujian Li, and Ming Zhou. Ranking with recursive neural networks and its application multi-document summarization. In AAAI, 2015.
[38] Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. End-to-end neural ad-hoc ranking with kernel pooling. In SIGIR, 2017.
[39] Robin Plackett. The analysis of permutations. Applied Statistics, pages 193-202, 1975.
[40] R Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 1959.
[41] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 138.vv1308.3432, 2013.
[42] O. Tange. Gnu parallel the command-line power tool. :login: The USENIX Magazine, 36(1):42-47, Feb
2011.
11


Reviews:
[{"review_id": "ylHPmTvXzst", "reviewer": "Reviewer_scsx", "summary": "The authors provide a new scalable listwise loss for ranking called PiRank. \nThe loss is defined as 1 - a differentiable relaxation of NDCG metric with temperature-controlled inspired by NeuralSort algorithm.\nIn this setting, the difference with the NDCG is negligeable the temperature tends to 0. \nScalability is ensured by a divide-and-conquer strategy where the sorting relaxation is applied to sub-lists of smaller size and then propagate only on the top items from each sub-list to merge the sort.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the paper is relatively clear and easy to follow.\n\nThe authors start by presenting the 3 representative loss function for pointwise, pairwise and listwise surrogate losses alongside the mainly used ranking metrics. The paper is really of interest of the community as it proposes a surrogate loss which approximately optimizes the main used ranking metric: NDCG.\n\nThe authors provide experiments on two large publicly available datasets with 18 different ranking metrics. The code will be made available which is highly appreciated for reproducibility of the results. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n- Can we really say PiRank is a listwise approach? The loss is still based on pairwise comparisons.\n- It would be helpful for the reader to recall the main differences between the baselines and PiRank in the experiment session.\n\nSocietal impact: this is not discussed in the paper because it is not the main object. This is ranking based on relevance only not taking into account diversity, fairness etc.", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "RzdbUKpMTCH", "reviewer": "Reviewer_b1Fc", "summary": "This paper proposes a new class of surrogates called PiRank for ranking metrics optimization. In particular, it uses temperature-controlled relaxation to the permutation matrix to derive a continuous and differentiable sorting operator. Due to the large size of the ranking lists in practical applications, this paper also proposes a divide-and-conquer method to reduce the complexity of metric computation. Experiment results show that the proposed methods can achieve promising results on two popular benchmarks.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "ORIGINALITY: There are existing works that approximate the ranking metrics so that they can be optimized by gradient based methods. Most of them aim to derive a bound of a certain ranking metric. The key is to smooth the rank calculation. In comparison, PiRank utilizes a permutation matrix to represent the rank as in NeuralSort, so that the rank does not need to be directly calculated based on the predicted scores. Then it applies continuous relaxations on the permutation matrix to smooth the ranking metrics, which looks novel. \n\nQUALITY: The paper proposes PiRank for differentiable ranking metric approximations, which can control the level of approximation based on temperature parameters. PiRank relaxes the permutation matrix to achieve differentiability, which is neat and flexible. A divide and conquer method is also proposed, which completes the loop for practical learning to rank tasks. Experiments are performed on two benchmark datasets against several popular baselines. Overall the paper is complete well finished. \n\nThe arguments that other surrogates are loosely related to ranking metrics or simple smoothed versions need to the further investigated. Most surrogates are deriving bounds of the ranking metrics, which are directly related to the metrics, though the bounds may have different levels of looseness. It would be interesting to show that PiRank is a better approximation of the metrics under useful temperatures. \n\nIn lines 79-84, pairwise approaches have been proved to be able to approximate the metrics on the full list when aggregated over all pairs (see Wang et al. 2018, The lambdaloss framework for ranking metric optimization.). \n\n\nCLARITY: The paper is clearly presented and easy to follow. However, the advantage of PiRank over other surrogates could be further elaborated. For example, PiRank also needs to approximate ranking metrics, which is doing the same thing as others. Though PiRank can achieve the exact metric when the temperature is zero, it is useless in this case. \n\nSIGNIFICANCE: Ranking metrics approximation and optimization is an important field in learning to rank. PiRank provides a new perspective in doing this task. The proposed method is neat and easy to apply in practice. \n\nI have read the authors' response and decided to keep my rating of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the experiment results, only PiRank-NDCG is reported, which is also used under metrics other than NDCG. Does this mean PiRank on other metrics does not work as well? \n\nThe divide-and-concur method is proposed to improve the efficiency of PiRank. But will be approximation still correspond to the correct ranking metric? Besides, in experiments, only list size under 100 is studied, which does not show the effectiveness of the divide-and-conqur variant. ", "review_text": "", "extra_scores": {"ethical_concerns": "None as I perceived. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "KsTtXawwlGQ", "reviewer": "Reviewer_BM9C", "summary": "This paper proposes PiRank, a new neural learning-to-rank (LTR) approach based on differentiable sorting operators. The authors present empirical results against two widely used LTR data sets (MSLR-WEB30K and Yahoo! C14).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is generally well-written, flows logically, and is easy to read. I did not notice any major issues with the presentation. The proposed methods and experimental results are also clearly described.\n\nThe proposed algorithm, which is based on NeuralSort is interesting, technically sound, and novel. \n\nThe experimental evaluation has its strengths and weaknesses. The strengths include evaluating on two widely used (and publicly available) LTR data sets, comparing against a number of strong baselines, and implementing the approach within the open source TF-Ranking framework. The two weaknesses include the lack of proper statistical significant testing to determine whether the differences in performance observed are 'meaningful' and the lack of tree-based baselines (such as LambdaMART). The missing LambdaMART baseline is the most serious concern that I have, as it is an exceptionally strong baseline that is worthy of comparison and will help determine the actual significance/impact of the proposed method.\n\nDespite all of the positives of this paper (well written, interesting method), I am unable to recommend it for publication as of this time given the concerns with the experimental evaluation (especially the missing LambdaMART baseline).\n\n===\n\nUpdate based on authors' rebuttal: The rebuttal provided the requested statistical significance tests and the results look favorable for PiRank, thereby providing better support for the authors' claims. I still believe it would be worthwhile to include a comparison against the current state-of-the-art (even if it is not neural-based and even if PiRank does not outperform it -- this is mostly as a point of comparison to provide additional context). I have increased my rating for this paper (from 4 => 6) to reflect this new information.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "IrVRtLBJLA", "reviewer": "Reviewer_WcGQ", "summary": "This paper tackles the problem of Learning To Rank. The idea is to relax ranking metrics (eg DCG), that are non differentiable with respect to the model parameters theta. Originally, these metrics measure how well the predicted ranking (induced by the scores predicted by the model) places high items with high true relevance labels. The relaxed metrics replace the permutation matrix in the original metrics by a relaxed, unimodal matrix, parametrized by a temperature.\n\nThis relaxation was proposed in Neuralsort, but is of quadratic complexity in the total number of items L at each time. In this paper, the authors propose a computationally efficient version of Neuralsort, truncated at the k first items, relying on a divide and conquer strategy. This approach is of much lower complexity, expressed in terms of L,k, and d the depth of the tree.\n\nFinally, the method is evaluated on benchmark learning to rank datasets. It obtains similar or better performance than sota methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The paper is very clearly written, I enjoyed reading it.\n\n2. The proposed method seems very attractive:\n     - it is very interesting computationally when L is large at train time when using trees of depth d>1, and performs similarly or better than widely used competitive methods\n- as the temperature goes to zero, we recover the true, non differentiable loss. This contrasts with previous listwise approaches that consider surrogate losses that may be poorer approximations of the objective.\n\nCons - comments/questions about the hyperparameters - : \n1. I was a bit surprised to read in Appendix C “\t.\tParameters specific to  NeuralSort and PiRank are tau = 5 and d = 1 across all experiments except for ablation “. If d=1, if I understood well, there is no real computational benefit (comparison of the complexity given l214 and L^2)\n2. How is the temperature chosen, e.g. in Table 1? I see in Appendix C that it was fixed to 1. The authors seem to have investigated the effect of different temperatures in sec 4.2; but if I understood well, the temperature is fixed during the training. Did you try an evolving temperature, such as in simulated annealing? e.g. tau goes from 1 to 0 along iterations. If yes, was it the best choice compared to a fixed tau?\n    3.  When tau is large, it is not clear to what extent the surrogate loss you propose is better than the ones considered in the literature.\n\n\nGlobally, I remain positive about the contributions of this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a new method for approximation of sorting and ranking operations in a differentiable manner, with a focus on the scalability of the operations.

The reviewers were unanimous that this paper should be accepted, and I agree with them. Since the problem and methodology cannot be considered very novel (many similar methods exist), and the numerical results are not a major breakthrough, I am not recommending a spotlight.
Decision: Accept (Poster)