Deep Spectral Ranking

∗ ∗ ∗ †
İlkay Yıldız Jennifer Dy Deniz Erdoğmuş Susan Ostmo

† †† ∗
J. Peter Campbell Michael F. Chiang Stratis Ioannidis
∗
ECE Dept., Northeastern Univ., Boston, MA, USA, {yildizi, jdy, erdogmus, ioannidis}@[Link]
†
Casey Eye Inst., Oregon Health and Science Univ., Portland, OR, USA, {ostmo, campbelp}@[Link]
††
National Eye Inst., National Institutes of Health, Bethesda, MD, USA, {chiangm}@[Link]

Abstract

Learning from ranking observations arises in

many domains, and siamese deep neural net-
works have shown excellent inference perfor-
mance in this setting. However, SGD does not
scale well, as an epoch grows exponentially
with the ranking observation size. We show
that a spectral algorithm can be combined
with deep learning methods to significantly
accelerate training. We combine a spectral
estimate of Plackett-Luce ranking scores with Figure 1: Training time and Top-1 prediction accuracy
a deep model via the Alternating Directions (indicated next to each marker) of DSR-KL, DSR-l2, and
Method of Multipliers with a Kullback-Leibler siamese network vs. query size (K) on the Movehub-Cost
proximal penalty. Compared to a state-of- dataset partitioned w.r.t. rank partitioning. Siamese net-
work training grows exponentially with K; both our algo-
the-art siamese network, our algorithms are rithm, DSR-KL, and the one by Yıldız et al. (2020) scale
up to 175 times faster and attain better pre- more gracefully w.r.t. K. However, DSR-KL has a consid-
dictions by up to 26% Top-1 Accuracy and erably higher accuracy, comparable to (or better than) the
6% Kendall-Tau correlation over five real-life one attained by the less efficient siamese network.
ranking datasets.

parametrized by a score and (b) the probability that

1 Introduction a sample is ranked higher than a set of alternatives is
Learning from ranking observations arises in many do- proportional to this score.
mains, including, e.g., econometrics (McFadden, 1973; Ranking regression assumes that Plackett-Luce scores
Ryzin and Mahajan, 1999), psychometrics (Thurstone, are a parametric function of sample features, regressed
1927; Bradley and Terry, 1952), sports (Elo, 1978), and from ranking observations. Maximum-Likelihood Esti-
medicine (Tian et al., 2019), to name a few. Rank- mation (MLE) in this setting has received significant
ing observations are (potentially noisy and incomplete) attention in the literature, via both shallow (Joachims,
orderings of subsets of samples. Given a dataset of 2002; Pahikkala et al., 2009; Guo et al., 2018; Tian
such ranking observations, probabilistic inference typ- et al., 2019) and deep neural network (DNN) models
ically assumes the existence of an underlying total (Burges et al., 2005; Chang et al., 2016; Dubey et al.,
ordering and aims to recover it. The Plackett Luce 2016; Han, 2018; Yıldız et al., 2019). Siamese neural
model (Plackett, 1975) is a prominent parametric model networks (Bromley et al., 1994) perform extremely well
in this setting; it postulates that (a) each sample is in this setting: for example, Yıldız et al. (2019) train a
5.9M parameter siamese neural network from pairwise
Proceedings of the 24th International Conference on Artifi-
cial Intelligence and Statistics (AISTATS) 2021, San Diego,
comparisons on just 80 images, attaining 0.92 AUC.
California, USA. PMLR: Volume 130. Copyright 2021 by A siamese network assumes that the score of each
the author(s).
sample is determined by a base network: training over
 Deep Spectral Ranking

ranking observations replicates this base network for (Kullback and Leibler, 1951). This leads to training
every sample present in a ranking. However, siamese the DNN regressor with max-entropy loss and an
network training does not scale well with ranking size: additional linear term at each ADMM iteration.
the number of possible ranking observations is O(nK ), • We prove that this new penalty is still amenable to
where n is the number of samples and K is the ranking fast inference via a spectral approach, generalizing
size. Datasets can span this regime, e.g., when multiple Yıldız et al. (2020). Our resulting algorithm, DSR-
labelers generate rankings. For instance, consider a KL, accelerates ranking regression problem for DNN
scenario where the n samples are papers submitted to models by incorporating this spectral solver. To the
a conference, and rankings are generated by a large best of our knowledge, we are the first in bridging
pool of reviewers. In a conference with thousands of the gap between state-of-the-art DNN models and
submissions, each reviewer is assigned K  n papers efficient spectral algorithms for ranking regression.
to rank, and a global ranking is to be inferred by the • We show experimentally that our method signifi-
(potentially Θ(nK )) dataset of partial rankings. cantly outperforms standard siamese networks and
the `2 -penalty ADMM used by Yıldız et al. (2020).
Consequently, stochastic gradient descent (SGD)
epochs can grow exponentially with K. Moreover, These performance benefits are illustrated in Figure 1.
the presence of K samples in each ranking observation Siamese network training grows exponentially with K;
increases the memory footprint of a batch; conversely, both our algorithm, DSR-KL, and the one by Yıldız
large values of K limit the size of batches that can be et al. (2020) scale more gracefully. However, DSR-KL
stored in memory. In particular, when K = Θ(n), SGD has a considerably higher accuracy, comparable to the
requires loading large–and potentially different–subsets one attained by (the less efficient) siamese network.
of the dataset with each ranking; this further deteri-
orates performance. In practice, a single epoch over
K = 7-way rankings takes 4.5 hours on an NVIDIA 2 Related Work
V100 GPU, even when samples have only 5 features.
Ranking regression via the Plackett-Luce (PL) (Plack-
An efficient algorithm for ranking regression over shal- ett, 1975) model has a long history, mostly focusing
low models was recently proposed by Yıldız et al. (2020). on pairwise comparisons, i.e., restricted to K = 2; this
Building on earlier work by Maystre and Grossglauser case is also known as the Bradley-Terry (BT) model
(2015), Yıldız et al. (2020) employ the Alternating Di- (Bradley and Terry, 1952). Among shallow regressors,
rections Method of Multipliers (ADMM) (Boyd et al., RankSVM (Joachims, 2002) learns a target ranking
2011) to separate the learning of regression model pa- from features via a linear Support Vector Machine
rameters from sample scores. On one hand, this sepa- (SVM), with constraints imposed by all possible com-
ration allows them to express the MLE of scores as the parisons. Pahikkala et al. (2009) propose a regularized
stationary distribution of a continuous-time Markov- least-squares based algorithm for learning to rank from
Chain, and learn scores from an O(nK )-sized dataset comparisons. Several works (Joachims, 2002; Pahikkala
using a fast spectral method. On the other hand, the et al., 2009; Guo et al., 2018; Tian et al., 2019) regress
separation allows regressing the linear model parame- comparisons via maximum-likelihood estimation (MLE)
ters from the scores, which are O(n). This separation over BT (Bradley and Terry, 1952) models.
yields significant performance improvements; their al-
gorithm is up to 579 times faster than traditional opti- Deeper models for regressing comparisons have also
mization methods for MLE, including, e.g., Newton’s been extensively explored in the BT setting (Burges
method (Boyd and Vandenberghe, 2004). et al., 2005; Chang et al., 2016; Dubey et al., 2016;
Doughty et al., 2018; Yıldız et al., 2019). Burges et al.
Unfortunately, this approach does not generalize well to (2005) estimate comparisons via a fully connected neu-
deep models. Particularly, Yıldız et al. (2020) regress ral network called RankNet, using the BT model to
scores by minimizing a squared-error proximal penalty, construct a cross-entropy loss. Several works (Chang
resulting in a regression sub-problem. It is well-known et al., 2016; Dubey et al., 2016; Doughty et al., 2018;
that in positive-valued regression, the small bounded Yıldız et al., 2019) learn from comparisons via siamese
range of the squared loss makes DNN training prone to networks (Bromley et al., 1994). Chang et al. (2016)
vanishing gradients and reaching stationary points far and Yıldız et al. (2019) learn from comparisons using
from local minima (Caruana and Niculescu-Mizil, 2004; MLE on the BT model. Dubey et al. (2016) predict
Golik et al., 2013; Bosman et al., 2020). To address image comparisons, via a loss function combining cross-
these issues, we make the following contributions: entropy and hinge loss. Doughty et al. (2018) learn
• We replace the standard `2 -norm proximal penalty similarities and comparisons of videos via hinge loss.
in ADMM with Kullback-Leibler (KL) divergence All of the above methods generalize to rankings under
the PL model, but suffer from the complexity issues
 Yıldız, Dy, Erdoğmuş, Ostmo, Campbell, Chiang, Ioannidis

outlined in the introduction. and Banerjee (2014) show that ADMM with a Breg-
man divergence proximal penalty converges with linear
Cao et al. (2007); Xia et al. (2008) and Ma et al. (2020)
rate for convex objectives. Wang et al. (2018) extend
focus on learning from star/relevance ratings rather
this convergence guarantee to local optima of non-
than rankings; they train a neural network called List-
convex problems. Several works (Shi et al., 2017; Yu
Net that treats ratings as Plackett-Luce scores. Partic-
et al., 2018; Yu and Açıkmeşe, 2019) employ a Breg-
ularly, given a dataset of n ratings, ListNet constructs
n! man ADMM algorithm for distributed optimization of
all (n−K)! possible K-sized rankings; it is then trained
separable problems.
by minimizing the cross entropy between the Plackett-
Luce probabilities that a given K-ranking comprises
the top samples among all n, with scores being (a)
the predicted scores and (b) the ground-truth ratings, 3 Problem Formulation
respectively. Hence, although ListNet solves a very
different problem than ranking regression, it is related Plackett-Luce Model. We introduce here the
to the siamese methods mentioned above through its Plackett-Luce discriminative model that we use in
(exponential in K) objective. our analysis; before describing it for ranking obser-
vations, we first consider the simpler “maximal choice”
Virtually all shallow and deep models for ranking re- setting. Consider a dataset of n samples, indexed by
gression rely on classic optimization methods for direct i ∈ [n] ≡ {1, . . . , n}. Every sample i ∈ [n] has a corre-
parameter inference, resulting in prohibitively slow sponding d-dimensional feature vector xi ∈ Rd . There
training for large rankings. An efficient algorithm for exists an underlying total ordering of these n samples.
ranking regression over shallow models was recently A labeler of this dataset acts as a (possibly noisy) ora-
proposed by Yıldız et al. (2020). Yıldız et al. (2020) cle revealing this total ordering: when presented with
solve the ranking regression problem via Alternating a query A ⊆ [n], i.e., a set of alternatives, the noisy
Directions Method of Multipliers (ADMM) (Boyd et al., labeler chooses the maximal sample in A w.r.t. the un-
2011) with an `2 proximal penalty. This allows them derlying total ordering. Formally, our “labeled” dataset
to express the MLE of scores as the stationary dis- D = {(c` , A` )}m `=1 consists of m observations (c` , A` ),
tribution of a Markov-Chain (MC), extending the ap- ` ∈ [m] ≡ {1, ..., m}, where A` ⊆ [n] is the `-th query
proach developed by Maystre and Grossglauser (2015) submitted to the labeler and c` ∈ A` is her respective
in the feature-less setting. Our approach extends Yıldız `-th maximal choice (i.e., the label). For every sample
et al. (2020) by generalizing (i) the regression model i ∈ [n], we denote by Wi = {` ∈ [m] | i ∈ A` , c` = i}
to DNNs, and (ii) the proximal penalty of ADMM the set of observations where sample i ∈ [n] is chosen,
to Kullback-Leibler (KL) divergence (Kullback and and by Li = {` ∈ [m] | i ∈ A` , c` = 6 i} the set of
Leibler, 1951); this has significant performance impli- observations where sample i ∈ [n] is not chosen.
cations (c.f. Sec. 5). To the best of our knowledge, we
are the first to accelerate ranking regression of deep The Plackett-Luce model asserts that every sample i ∈
models via a spectral method. [n] is associated with a non-negative deterministic score
πi ∈ R+ . Given π = [πi ]i∈[n] ∈ Rn+ : (i) observations
ADMM is typically used when training deep neural (c` , A` ), ` ∈ [m] are independent, and (ii) for a query
networks to enforce sparsity. One application is com- A` , the probability that sample c` ∈ A` is chosen is:
pressed sensing, in which a signal is recovered from
undersampled measurements via a DNN transforma-
tion (Sun et al., 2016; Yang et al., 2020; Li et al., 2018;
P P
P(c` | A` , π) = πc` / j∈A` πj = π` / j∈A` πj , (1)
Ma et al., 2019; Liu et al., 2018). The training objective
combines a standard regression loss with a norm penalty
on measurements, including, e.g., `1 , `2 , Frobenius, or where, in the last equation, we abuse notation to write
nuclear norm. Another application is model pruning the score of the chosen sample as π` ≡ πc` . Note
(Ye et al., 2018, 2019; Zhao and Liao, 2019): ADMM that P(c` | A` , π) = P(c` | A` , sπ), for all s > 0; thus,
is used to enforce weight sparsity by replacing norm w.l.o.g., we assume (or enforce via rescaling) that
penalties with (possibly non-convex) low-cardinality set Plackett-Luce scores satisfy 1> π = 1 , i.e., π is a
constraints. Zhao et al. (2018) train a DNN classifier distribution over [n].
to recover samples distorted by additive adversarial Plackett-Luce readily extends to datasets of (partial)
noise, using an objective that combines a classification ranking observations. In this setting, when presented
loss with an `0 , `1 , `2 , or `∞ norm penalty. with a query A` ⊆ [n] of K = |A` | samples, the labeler
We use ADMM with a Kullback-Leibler (KL) diver- ranks the samples in A` into an ordered sequence α1` 
gence proximal penalty as an alternative to `2 . Wang α2`  · · ·  αK
`
. Under the Plackett-Luce model, this
ranking is expressed as K − 1 maximal choice queries:
 Deep Spectral Ranking

α1` over A` , α2` over A` \ {α1` }, etc., so that: 4 Deep Spectral Ranking Algorithm
K−1
Y XK We wish to devise an efficient algorithm to minimize
P(α1`  α2`  · · ·  αK
`


|A` , π) = πα`t / πα`s . (2) (5). To do so, we extend the Alternating Directions
t=1 s=t Method of Multipliers (ADMM) (Boyd et al., 2011)
used by Yıldız et al. (2020). To this end, we rewrite
The product form of (2) implies that a ranking obser- the minimization of (5) as:
vation in response to a query A` can be converted to
m
K − 1 independent maximal-choice observations (again, X X

α1` over A` , α2` over A` \ {α1` }, and so forth), each Minimize L(D | π) ≡ log πj − log π` (6a)
π,W
`=1 j∈A`
governed by (1), that yield the same joint probabil-
ity. MLE over a dataset of ranking observations thus subject to: π = π̃(X; W ), π ≥ 0, (6b)
reduces to MLE over a dataset of maximal choice ob-
servations. For notational simplicity, we present our where π̃(X; W ) ∈ Rn+ is the vector map whose co-
analysis over maximal-choice datasets in Sec. 4, keeping efficients π̃i ∈ R+ are given by π̃i = π̃(xi ; W ). To
the above reduction in mind. solve (6) via ADMM, consider the following augmented
Lagrangian:
Parameter Inference and Regression. Given ob-
servations D, Maximum Likelihood Estimation (MLE) Lρ (π, W , y) = L(D | π) + y > (π − π̃(X; W ))
of the Plackett-Luce scores π ∈ Rn+ amounts to mini- + ρ · Dp (π||π̃(X; W )), (7)
mizing the negative log-likelihood:
Pm P
where y ∈ Rn is the Lagrangian dual variable corre-
L(D | π) ≡ `=1 log j∈A` πj − log π` . (3) sponding to the equality constraint in (6b), ρ ≥ 0 is a
penalty parameter, and Dp (·||·) is a proximal penalty
To regress scores π from sample features X = term. This term satisfies: (i) Dp (π||π̃) ≥ 0 for all
T
[x1 , .., xn ] ∈ Rn×d , we assume that there exists a func- π, π̃ ∈ Rn+ , and (ii) Dp (π||π̃) = 0 if and only if
0
tion π̃ : R × Rd → [0, 1] (e.g., a DNN), parametrized
d
π̃ = π. Classic ADMM involves using the usual `2
0
by W ∈ Rd , such that: proximal penalty, i.e., Dp (π||π̃) =k π̃ − π k22 . We
depart from this by considering more generic Dp ; as
πi = π̃(xi ; W ), for all i ∈ [n] . (4) we discuss below,
Pn using KL-divergence instead, i.e.,
Dp (π||π̃) = i=1 πi log ππ̃ii has significant advantages
Then, MLE amounts to minimizing the following ob- in our setting.
0
jective w.r.t. W ∈ Rd :
Decoupling Optimization and a Spectral Algo-
m

X X
rithm. In its general form, ADMM alternates between
L D|W ≡ log π̃(xj ; W )−log π̃(x` ; W ) . (5) optimizing π and W until convergence via the following
`=1 j∈A` primal-dual algorithm on the augmented Lagrangian:
In the case of deep models, virtually all state-of-the- π k+1 = arg minLρ (π, W k , y k ) (8a)
art ranking regression methods minimize Eq. (5) via π∈Rn
+

SGD (Chang et al., 2016; Dubey et al., 2016; Doughty W k+1 = arg minLρ (π k+1 , W , y k ) (8b)
et al., 2018; Yıldız et al., 2019). Note that the objec- W ∈Rd0
tive (5) corresponds to a siamese network architecture y k+1 = y + ρ(π k+1 − π̃(X; W k+1 )).
k
(8c)
(Bromley et al., 1994) with base network π̃: for each
observation (c` , A` ) in D, the base network needs to be This has the following immediate computational ad-
evaluated (and back-propagation needs to happen over) vantages. First, step (8b) is equivalent to:
all samples in A` . Hence, if each query A` has size
W k+1 = arg min ρDp π k+1 ||π̃(X; W )


K = |A` |, the siamese network contains K identical
base networks, each receiving the feature vector xi of W ∈Rd0 (9)
a sample i ∈ A` ; this is further exacerbated in rank- k>
− y π̃(X; W ).
ing queries, since each corresponds to K − 1 maximal
choice queries. Overall, the siamese nature of objective Note that this operation does not depend on D: the
(5) implies that K samples need to be loaded in RAM model π̃(X; W ) is regressed directly from the present
to process a single ranking or maximal choice query. score estimates π k+1 via penalty Dp , with the addi-
This, in addition to the fact that the size of
possible tional linear dual term. In particular, as discussed
n
rankings/maximal queries in D grows as K = O(nK ) below, Dp leads to a least squares regression in the
(c.f. Figures 1 and 2c), can make the cost of a single case of the `2 -proximal penalty, and a max-entropy
SGD epoch over Eq. (5) prohibitive. penalty in the case of KL-divergence; both can be
 Yıldız, Dy, Erdoğmuş, Ostmo, Campbell, Chiang, Ioannidis

solved efficiently via SGD. Crucially, an epoch of this by uniformizing M , i.e., increasing self-transition rates
SGD iterates over the O(n) samples, instead of the until all states have the same outgoing rate, and finding
O(nK ) ranking observations, which would be the case the leading left eigenvector via, e.g., the power method
under the siamese approach. (Lei et al., 2016).
Most importantly, step (8a)–which does depend on Yıldız et al. (2020) focus on the case where (i) Plackett-
D–admits a highly efficient spectral implementation; Luce scores are affine functions of sample features, i.e.,
ADMM (8) therefore delegates solving the “expensive” π̃(X; W ) = XW , and (ii) Dp (π||π̃) =k π̃ − π k22 . The
portion of the problem to a highly efficient algorithm. generalization to KL-divergence is naturally suited to
This is a consequence of the following theorem, which Problem (6): this is because the scores computed by
we prove in Appendix A: (13) form, by construction, a distribution over [n].
Theorem 4.1. Given π̃ k ≡ π̃(X; W k ) ∈ Rn+ and Our main technical contribution is to show that this
y k ∈ Rn , a stationary point π ∈ Rn+ of the Aug- generalization to KL penalty is still amenable to a
mented Lagrangian (7) satisfies the balance equations of spectral solution via (13); in practice, this also leads
a continuous-time Markov Chain (MC) with transition to a significantly improved performance over an `2 -
rates: proximal penalty (by up to 56% Top-1 accuracy and
25% Kendall-Tau correlation, as discussed in Sec. 5).
P 2πi σi (π)σP j (π)

λji (π)+
 πt σt (π)− πt σt (π) As shown in Eq. (15) below, the KL-divergence penalty
t∈[n]− t∈[n]+

µji (π) = (10) leads to training π̃(X; W ) with a max-entropy loss
if j ∈ [n]+ and i ∈ [n]−


 and an additional linear term at each ADMM iteration.
λji (π) otherwise, Compared to the `2 -proximal penalty by Yıldız et al.
(2020), max-entropy has been observed to converge
where faster and lead to better fitting (Caruana and Niculescu-
∂Dp (π||π̃ k ) Mizil, 2004; Golik et al., 2013; Bosman et al., 2020).
σi (π) = ρ + yik , for i ∈ [n] (11) Finally, ADMM with Bregman divergence proximal
∂πi
X X
−1 penalties, including KL divergence, has been shown
λji (π) = πt ≥ 0, for i, j ∈ [n] , (12) to offer local convergence guarantees for non-convex
`∈Wi ∩Lj t∈A`
problems (Wang et al., 2018); this further motivates us
to employ KL over other distance measures between
and ([n]+ , [n]− ) is a partition of [n] such that σi (π) ≥ 0
probability distributions.
for all i ∈ [n]+ and σi (π) < 0 for all i ∈ [n]− .
Overall Algorithm. Putting everything together, our
Theorem 4.1 generalizes Theorem 4.2 of Yıldız et al. Deep Spectral Ranking (DSR) algorithm solving Eq. (6)
(2020), which holds only for an `2 penalty for Dp ; is summarized in Algorithm 1. We initialize all samples
Maystre and Grossglauser (2015) had established a with equal scores, i.e., π = π̃ = n1 1. We iteratively
similar result for stationary points of L(D|π). Our update π, W , and y via Eq. (8) until convergence. At
theorem implies that a stationary point can be ob- each ADMM iteration k, we initialize π with π k−1 ,
tained through the following iterative algorithm, called and update π via ILSRX given by Eq. (13). Then, we
ILSRX by Yıldız et al. (2020). Let ssd(M ) be the sta- initialize the DNN parameters W with W k−1 , and fine
tionary distribution of an MC with transition matrix tune the DNN π̃(X; W ) via SGD over Eq. (9). Each
M = [µji (π)]i,j∈[n] , where µji (π) are given by (10). iteration of DSR involves the three steps in Eq. (8).
When matrix M is fixed (i.e., the transition rates are One iteration of ILSRX at step (8a) is O(Km + n2 ) for
known), the vector ssd(M ) is a solution to the linear constructing the transition rates via Eq. (10) and for
system defined by the balance equations π = M π and finding the stationary distribution π via, e.g., a power
1> π = 1, as it is a distribution. However, the tran- method, respectively. The update of y given π̃ and
sition matrix M = M (π) in Theorem 4.1 is itself a π is O(n). Finally, constructing the loss function (9)
function of π, and is therefore a priori unknown. Thus, at each epoch of step (8b) is O(n), while each epoch
following Yıldız et al. (2020); Maystre and Grossglauser goes over O(n) samples of dimension d to train the d0
(2015), we can find π through: weights.
π q+1 = ssd (M (π q )) , for q = 0, 1, 2, . . . . (13) We implement DSR with the two proximal penalty
functions Dp (π||π̃) mentioned above: Kullback-Leibler
We note that the dataset D appears in the computa- (KL) divergence (Kullback and Leibler, 1951) and `2
tion of the rate matrix M , via sets Wi and Lj ; the norm. We describe implementation specifics for each
computation of these weights can be easily parallelized. of these cases below.
The linear system determined by the balance equations Pn
involves n unknowns and can be computed efficiently KL proximal penalty. For Dp (π||π̃) = i=1 πi log ππ̃ii ,
 Deep Spectral Ranking

partition each dataset into training and test sets in two

Algorithm 1 DSR ways. In rank partitioning, we partition the dataset
1: procedure ADMM(X, D, ρ) w.r.t. [m], using 90% of the m observations for training,
2: Initialize π ≡ π̃ ← n1
1; y ← 0
and the remaining 10% for testing. In sample parti-
3: repeat
4: π ← ILSRX(ρ, π, π̃, y) tioning, we partition [n], using 90% of the n samples
5: W ← SGD over Eq. (9) for training, and the remaining 10% for testing. In
6: π̃ ← π̃(X; W )
7: y ← y + ρ(π − π̃) this setting, observations containing samples from both
8: until convergence training and validation/test sets are discarded. We per-
9: return W , π
10: end procedure form 3-fold cross validation on the resulting training
1: procedure ILSRX(ρ, π, π̃, y) sets.
2: repeat
3: Calculate [σi (π)]i∈[n] via Eq. (11) We implement1 five competing algorithms. DSR with
4: Calculate M (π) = [µji (π)]i,j∈[n] via Eq. (10)
5: π ← ssd (M (π)) KL penalty (DSR-KL), DSR with `2 norm penalty
6: until convergence (DSR-l2), and siamese network competitor regress
7: return π
8: end procedure scores via a DNN π̃(X; W ) with parameters W . SR-l2
(Yıldız et al., 2020) and SR-KL use an affine regressor
Spec. Dataset π̃ = Xβ + b1 with parameters β and b, and solve (6)
ROP ICLR-3/4
Movehub- Movehub-
IMDB-4 via ADMM with `2 and KL penalties, respectively.
Cost-4/5 Quality-4/5
K 2 3/4 4/5 4/5 4 We execute all experiments on NVIDIA V100 GPUs
n 100 50 with Intel Gold 6132@2.60Ghz CPUs and 128GB RAM.
d 224 × 224 768 6 5 36 We explain the network architecture and the training
120, 324/ 230, 298/ 230, 298/
m 29, 705
2, 248, 524 2, 118, 756 2, 118, 756
85, 583 procedure of π̃(X; W ) in Section 5.2, and the imple-
X image numerical mentation details of all algorithms, including, e.g. the
convergence criteria in Section 5.3. To evaluate the
Table 1: No. of samples (n), no. of features (d), no. of
observations (m), and query size (K) for datasets with convergence speed of each algorithm, we measure the
image or numerical features (X) elapsed time, including time spent in initialization,
in seconds (Time). Moreover, we measure the pre-
diction performance by Top-1 accuracy (Top-1 Acc.)
we have: and Kendall-Tau correlation (KT) (Kendall, 1938) on
∂Dp (π||π̃ k ) πi validation and test sets (c.f. Section 5.4). We report
σi (π) = ρ +yik = ρ(1+log k )+yik , (14) averages and standard deviations over folds for all al-
∂πi π̃i
gorithms except for the siamese network method: as
for all i ∈ [n] in the transition rates (10). Moreover, training takes several hours, we execute only one fold.
the optimization (9) for training π̃(X; W ) becomes:
n 5.2 Network Architecture and Training
yk
X
arg min (− i π̃i − πik+1 log π̃i ), (15)
W ∈Rd0 i=1 ρ To evaluate each method on ROP, we choose π̃(X; W )
as a state-of-the-art convolutional neural network ar-
which corresponds to max-entropy with an additional chitecture, namely GoogLeNet (Szegedy et al., 2015),
linear term. followed by a fully connected output layer comprising
`2 proximal penalty. For Dp (π||π̃) =k π̃ − π k22 : a single neuron with sigmoid activation. We initialize
the convolutional layers with weights pre-trained on
∂Dp (π||π̃ k ) the ImageNet dataset (Deng et al., 2009). For other
σi (π) = ρ +yik = 2ρ(πi − π̃ik )+yik , (16) datasets, we design π̃(X; W ) as a fully-connected ar-
∂πi
chitecture with relu activation for hidden layers and an
for all i ∈ [n] in the transition rates (10). Moreover, output layer comprising a single neuron with sigmoid
(9) becomes a least squares minimization of the form: activation. We add `2 regularizers to all layers. For
1 each configuration of (i) `2 regularization parameter
arg min k π̃(X; W ) − (π k+1 + y k ) k22 . (17) varying in [2 × 10−5 , 2 × 10−2 ], (ii) learning rate vary-
W ∈Rd 0 ρ
ing in [10−4 , 10−2 ], and (iii) number of layers varying
in [1, 10] for fully connected π̃(X; W ), we run each
5 Experiments method until convergence (c.f. Section 5.3 for criteria).
5.1 Experiment Setup We determine the best set of hyperparameters w.r.t. the
prediction performance via 3-fold cross validation.
We evaluate DSR on real-life datasets summarized in 1
Our code is publicly available at
Table 1; additional details are given in App. B. We [Link]
 Yıldız, Dy, Erdoğmuş, Ostmo, Campbell, Chiang, Ioannidis

5.3 Algorithms We also predict the ranking as α̂` = arg sort[π̃i ]i∈A` ,
i.e. sequence of the samples in A` ordered w.r.t. their
DSR-KL and DSR-l2 are explained in Section 4 estimated scores. We calculate Kendall-tau correla-
and summarized in Algorithm 1. We compute the tion (KT) (Kendall, 1938) as a measure of the corre-
stationary distribution at each iteration of ILSRX lation between each true ranking α` and predicted
(c.f. Eq. (13)) using the power method (Lei et al., 2016). ranking α̂` , ` ∈ {1, ..., mtest }. For observation `,
At each ADMM iteration, we fine tune the DNN re- PK PK ` ` ` `
let T` = t=1 s=1 1(α̂t  α̂s ∧ αt  αs ) be the
gressor π̃(X; W ) via Adam optimization (Kingma and number
Ba, 2015) over Eq. (9). We check the convergence of L PKcorrectly
PK predicted ranking positions, and
F` = t=1 s=1 1(α̂t`  α̂s` ∧ αs`  αt` ) be the number
on the training set and Kendall-Tau correlation (KT) incorrectly predicted ranking positions. Then, KT is
evaluations on the validation set (c.f. Section 5.4) as computed by:
the stopping criterion for: (i) fine-tuning π̃(X; W ) at Pmtest K


each ADMM iteration, and (ii) overall DSR-KL algo- `=1 (T` − F` )/ 2
KT = ∈ [−1, 1], (19)
rithm. We declare convergence when KT on validation mtest
set does not change for 5 iterations, for maximum total
where K


of 50 iterations, with relative tolerance rtol = 10−4 . 2 is the number of sample pairs.
We use the same relative tolerance for the stopping
criterion of the power method. 5.5 Results

To aid convergence in practice (Boyd et al., 2011), we Training Time vs. Prediction Performance. Fig-
update the dual variable at each ADMM iteration with ure 2a and 2b show the training time of DSR-KL and
a multiplicative smoothing parameter γ k = 1/k. We siamese network vs. Top-1 Acc. and KT on test sets
also adapt the penalty parameter as: of Movehub-Cost-4, Movehub-Quality-4, and IMDB-4

k k k 2 k k−1 2
datasets, partitioned with rank partitioning. For all
τ kρ , if k π̃ − π k2 > β k π̃ − π̃
 k2 datasets, DSR-KL results lie on the top left region of
k+1 ρ
ρ = τ , if k π̃ k −π k k22 < β k π̃ k − π̃ k−1 k22 both Top-1 Acc. and KT plots: DSR-KL consistently

 k
ρ , otherwise, leads to much faster training and better predictions
than the siamese counterpart.
where τ = 2 and β = 10.
Table 2 shows the training time and test set prediction
The siamese network competitor minimizes Eq. (5) performance of DSR-KL, DSR-l2, siamese network, SR-
w.r.t. W via SGD. We train a siamese network architec- l2, and SR-KL trained on all datasets (c.f. Table 1),
ture with base network π̃ on observations D via Adam partitioned with rank partitioning. DSR-KL and DSR-
optimization (Kingma and Ba, 2015) over Eq. (5). We l2 are 1.5 − 142 times faster than siamese network over
employ the same convergence criterion and experiment all datasets. Moreover, DSR-KL consistently attains
setup as DSR-KL and DSR-l2 to train and optimize equivalent or better prediction performance than both
the siamese network. siamese network and DSR-l2 w.r.t. both Top-1 Acc. and
Finally, we implement two spectral algorithms that KT. DSR-KL leads to particularly better performance
regress Plackett-scores via an affine model, i.e., π̃ = in ranking predictions, by up to 6% higher KT than
Xβ+b1: SR-l2 proposed by Yıldız et al. (2020), and its siamese and 25% higher KT than DSR-l2 on IMDB-4.
variant SR-KL that uses KL proximal penalty instead of Deeper regression methods consistently outperform the
`2 norm penalty for ADMM. As the stopping criterion predictions of shallow regression methods. Particularly,
for both algorithms, we use kπ k − π k−1k2 < rtol kπ kk2 our deep spectral algorithms DSR-KL and DSR-l2 lead
and k(Xβ k + bk 1) − (Xβ k−1 + bk−1 1k2 < rtol kXβ k + to significantly better predictions than the shallow
bk 1k2 . Following Yıldız et al. (2020), we set the ADMM versions SR-l2 and SR-KL, up to 38% Top-1 Acc. and
penalty parameter as ρ = 1. 41% KT on IMDB-4. The training times of DSR-KL
and DSR-l2 are also not noticeably larger than the
5.4 Evaluation Metrics ones of shallow versions; SR-KL converges even slower
than DSR-KL, by up to 12 times on Movehub-Quality-
Let the test set be Drank = {(α` , A` ) | ` ∈ 5. Unlike SR-l2 that solves a least-squares problem
{1, ..., mtest }}, where α` = α1`  α2`  · · ·  αK `
is with closed form solution, parameter update step of
an ordered sequence of the samples in A` . Given A` , SR-KL (c.f. 15) requires an iterative optimization at
we predict the `-th choice as ĉ` = arg maxi∈A` π̃i . We each ADMM iteration.
calculate the Top-1 accuracy (Top-1 Acc.) as:
Pmtest Table 3 shows the training time and test set predic-
1(ĉ` = α1` ) tion performance of DSR-KL, DSR-l2, siamese network,
Top-1 Acc. = `=1 ∈ [0, 1]. (18)
mtest SR-l2, and SR-KL trained on all datasets, partitioned
 Deep Spectral Ranking

0.90 0.89
0.88
103

Conv. Time (s)

0.88 0.86 0.88
0.82
Test Acc.

Test KT
0.84
0.86 0.58 0.88
0.82 0.89
0.88
0.62
0.84
0.80 102 0.85
0.89 0.85
0.78 0.88
102 103 102 103 2 3 4 5
Time (s) Time (s) K

(a) Training time vs. Top-1 Acc. (b) Training time vs. KT (c) Query size (K) vs. performance
Figure 2: (a)-(b). Training time of DSR-KL and siamese network vs. Top-1 Acc. and KT on test sets of Movehub-Cost-4,
Movehub-Quality-4, and IMDB-4 datasets, partitioned w.r.t. rank partitioning. (c). Training time and prediction
performances of DSR-KL, DSR-l2, and siamese network vs. query size (K) on Movehub-Quality dataset partitioned
w.r.t. rank partitioning. Top-1 accuracy for each K is next to the corresponding marker.

Dataset Method Time (s) ↓ Performance on the Test Set Dataset Method Time (s) ↓ Performance on the Test Set
Top-1 Acc. ↑ KT ↑ Top-1 Acc. ↑ KT ↑

ICLR-3 DSR-KL 152.86 ± 29.98 0.9 ± 0.0 0.86 ± 0.0 ICLR-3 DSR-KL 145.76 ± 9.78 0.48 ± 0.06 0.28 ± 0.09

DSR-l2 165.59 ± 22.63 0.79 ± 0.0 0.5 ± 0.0 DSR-l2 122.92 ± 75.43 0.51 ± 0.02 0.07 ± 0.08
Siamese 1445.77 0.88 0.8 Siamese 827.05 0.48 0.05
SR-KL 529.02 ± 117.26 0.37 ± 0.0 0.02 ± 0.0 SR-KL 96.49 ± 90.02 0.48 ± 0.0 0.0 ± 0.0
SR-l2 20.59 ± 3.02 0.87 ± 0.0 0.82 ± 0.0 SR-l2 4.91 ± 4.6 0.47 ± 0.0 0.06 ± 0.0
Movehub- DSR-KL 49.54 ± 34.2 0.88 ± 0.07 0.85 ± 0.09 Movehub- DSR-KL 17.65 ± 7.68 0.61 ± 0.07 0.45 ± 0.12
Cost-4 Cost-4
DSR-l2 73.38 ± 32.82 0.72 ± 0.02 0.58 ± 0.03 DSR-l2 19.85 ± 3.7 0.05 ± 0.08 -0.3 ± 0.22
Siamese 523.64 0.87 0.82 Siamese 216.22 0.6 0.66
SR-KL 29.64 ± 3.59 0.47 ± 0.0 0.27 ± 0.0 SR-KL 7.45 ± 0.3 0.31 ± 0.0 0.44 ± 0.0
SR-l2 19.7 ± 0.72 0.8 ± 0.0 0.54 ± 0.0 SR-l2 4.13 ± 0.2 0.5 ± 0.0 0.71 ± 0.0
Movehub- Movehub-
DSR-KL 63.05 ± 4.14 0.88 ± 0.0 0.84 ± 0.0 DSR-KL 31.41 ± 5.02 0.88 ± 0.0 0.74 ± 0.05
Quality-4 Quality-4
DSR-l2 531.86 ± 212.91 0.82 ± 0.07 0.75 ± 0.08 DSR-l2 34.72 ± 8.68 0.67 ± 0.11 0.81 ± 0.31
Siamese 710.35 0.88 0.82 Siamese 258.87 0.88 0.88
SR-KL 98.02 ± 3.73 0.17 ± 0.0 -0.1 ± 0.0 SR-KL 7.68 ± 0.2 0.48 ± 0.0 0.05 ± 0.0
SR-l2 18.98 ± 4.11 0.84 ± 0.0 0.62 ± 0.0 SR-l2 4.69 ± 0.1 0.51 ± 0.0 0.55 ± 0.0
IMDB-4 DSR-KL 23.93 ± 16.15 0.9 ± 0.0 0.9 ± 0.05 IMDB-4 DSR-KL 526.01 ± 11.57 0.73 ± 0.29 -0.14 ± 0.25
DSR-l2 54.16 ± 13.22 0.78 ± 0.035 0.38 ± 0.07 DSR-l2 27.73 ± 26.63 0.21 ± 0.21 -0.02 ± 0.08
Siamese 3409.03 0.87 0.78 Siamese 1240.98 0.47 0.02
SR-KL 57.93 ± 0.87 0.16 ± 0.0 -0.04 ± 0.0 SR-KL 31.33 ± 13.26 0.04 ± 0.0 0.05 ± 0.0
SR-l2 9.43 ± 1.02 0.52 ± 0.0 0.08 ± 0.0 SR-l2 6.97 ± 2.71 0.6 ± 0.06 0.04 ± 0.06

ICLR-4 DSR-KL 84.93 ± 1.76 0.88 ± 0.01 0.62 ± 0.06 ICLR-4 DSR-KL 288.45 ± 3.84 0.48 ± 0.13 0.06 ± 0.18

DSR-l2 84.78 ± 1.21 0.63 ± 0.01 0.19 ± 0.01 DSR-l2 280.72 ± 270.75 0.47 ± 0.02 0.032 ± 0.1
Siamese 623.18 0.84 0.76 Siamese 10142.55 0.32 -0.07
SR-KL 347.29 ± 39.6 0.29 ± 0.0 ± 0.0 SR-KL 131.8 ± 120.01 0.45 ± 0.0 -0.07 ± 0.0
SR-l2 503.11 ± 40.35 0.86 ± 0.82 ± 0.0 SR-l2 198.49 ± 6.87 0.37 ± 0.03 -0.01 ± 0.0
ROP DSR-KL 776.71 ± 136.74 0.89 ± 0.0 0.79 ± 0.0 ROP DSR-KL 25.3 ± 15.4 0.8 ± 0.01 0.6 ± 0.02
DSR-l2 694.99 ± 431.12 0.84 ± 0.03 0.68 ± 0.064 DSR-l2 210.45 ± 47.16 0.79 ± 0.01 0.59 ± 0.02
Siamese 1152.06 0.86 0.73 Siamese 4438.61 0.82 0.65
SR-KL 610.91 ± 20.69 0.5 ± 0.0 0.0 ± 0.0 SR-KL 527.76 ± 163.76 0.61 ± 0.0 0.23 ± 0.0
SR-l2 3.08 ± 0.59 0.89 ± 0.0 0.79 ± 0.0 SR-l2 1.96 ± 1.1 0.45 ± 0.0 -0.08 ± 0.0
Movehub- DSR-KL 183.6 ± 48.2 0.85 ± 0.047 0.84 ± 0.08 Movehub- DSR-KL 111.13 ± 31.61 0.76 ± 0.29 0.67 ± 0.15
Cost-5 Cost-5
DSR-l2 216.5 ± 64.34 0.81 ± 0.04 0.69 ± 0.02 DSR-l2 137.14 ± 65.55 0.19 ± 0.05 0.52 ± 0.34
Siamese 7986.22 0.89 0.83 Siamese 2842.12 0.62 0.74
SR-KL 189.85 ± 0.72 0.45 ± 0.0 0.28 ± 0.0 SR-KL 30.51 ± 0.3 0.16 ± 0.0 0.39 ± 0.0
SR-l2 209.5 ± 1.5 0.78 ± 0.0 0.55 ± 0.0 SR-l2 30.14 ± 0.2 0.37 ± 0.0 0.73 ± 0.0
Movehub- Movehub-
DSR-KL 79.35 ± 2.91 0.85 ± 0.05 0.79 ± 0.08 DSR-KL 114.03 ± 30.18 0.92 ± 0.06 0.35 ± 0.25
Quality-5 Quality-5
DSR-l2 91.87 ± 6.31 0.62 ± 0.04 0.5 ± 0.05 DSR-l2 46.99 ± 13.23 0.57 ± 0.34 0.73 ± 0.46
Siamese 2241.49 0.89 0.83 Siamese 752.06 0.76 0.08
SR-KL 924.07 ± 0.2 0.13 ± 0.0 -0.1 ± 0.0 SR-KL 29.68 ± 1.2 0.62 ± 0.0 0.08 ± 0.0
SR-l2 208.1 ± 0.1 0.84 ± 0.0 0.65 ± 0.0 SR-l2 30.03 ± 1.1 0.39 ± 0.0 0.59 ± 0.0

Table 2: Rank Partitioning Table 3: Sample Partitioning

Training time vs. Top-1 Acc. and KT on test sets of all datasets (c.f. Table 1), partitioned w.r.t. rank and sample
partitioning, respectively. We report averages and standard deviations over folds for all algorithms except for siamese. Our
algorithms, as well as the algorithm that attains the best performance for each dataset are indicated in bold.
 Yıldız, Dy, Erdoğmuş, Ostmo, Campbell, Chiang, Ioannidis

Validation Acc.
Log Likelihood
0.8
150000
0.6

200000 0.4

0.2
250000
0 50 100 0 50 100
Time (s) Time (s)

(a) Convergence on Movehub-Cost-4 (b) Convergence on Movehub-Quality-4

Figure 3: Log-likelihood −L on training and Top-1 Acc. on validation sets of Movehub-Cost-4 and Movehub-Quality-4
datasets, partitioned w.r.t. rank partitioning. Each point for DSR-KL and DSR-l2 correspond to an iteration of ADMM,
while each point for siamese corresponds to a training epoch.

Dataset Method Performance on the Test Set

siamese corresponds to a training epoch. DSR-KL
Top-1 Acc. ↑ KT ↑
Movehub- consistently attains higher log-likelihood and better
DSR-KL 0.88 0.85
Cost-4 validation performance than both siamese network and
One-iter.-DSR-KL 0.67 0.53
Movehub- DSR-l2, while converging faster.
DSR-KL 0.88 0.84
Quality-4
One-iter.-DSR-KL 0.75 0.73 Comparison to Naïve Approach. A naïve spectral
algorithm can be constructed by a single iteration of
Figure 4: Test set predictions of DSR-KL vs. One-iter.- the primal steps in (8): (i) solving (8a) to learn π via
DSR-KL on Movehub-Cost-4 and Movehub-Quality-4.
repeated iterations of (13), and (ii) given π, solving
(8b) by training the DNN regressor π̃(X; W ) via SGD
over Eq. (9). Intuitively, this ignores/does not exploit
with sample partitioning. Note that this is the set- the fact that samples with similar features ought to
ting when regressing scores from features is essential, have similar scores. We denote this naive approach as
as training samples cannot participate in any obser- One-iter.-DSR-KL. Unlike One-iter.-DSR-KL, our algo-
vations in validation or test sets. Agreeing with the rithm DSR-KL has the capability of repeatedly adapt-
speed gain in rank partitioning, DSR-KL and DSR-l2 ing both π and W by solving (6) via ADMM. This
are 8 − 175 times faster than the siamese network over advantage is illustrated in Figures 3a and 3b, where not
all datasets. Moreover, DSR-KL leads to particularly only π̃(X; W ), but also π are adjusted until conver-
better performance in maximal-choice predictions, by gence. Moreover, Figure 4 shows the corresponding test
up to 26% higher Top-1 Acc. than siamese on IMDB-4 set predictions of DSR-KL vs. One-iter.-DSR-KL on
and 56% higher Top-1 Acc. than DSR-l2 on Movehub- Movehub-Cost-4 and Movehub-Quality-4; DSR-KL out-
Cost-4. Finally, deeper regression methods DSR-KL, performs One-iter.-DSR-KL by 13-21% Top-1 Acc. and
DSR-l2, and siamese network, outperform the predic- 6-15% KT.
tions of shallow counterparts SR-l2 and SR-KL, by up
to 39% Top-1 Acc. and 11% KT on Movehub-cost-5
and ICLR-3, respectively.
Impact of K. Figures 1 and 2c show training time 6 Conclusion
and prediction performances of DSR-KL, DSR-l2, and
siamese network vs. query size (K) on Movehub-Cost
We model Plackett-Luce scores as deep neural network
and Movehub-Quality datasets partitioned w.r.t. rank
(DNN) functions of sample features. We solve the max-
partitioning. The speed gain of DSR-KL and DSR-
imum likelihood estimation problem for the scores via
l2 over siamese reach up to 43 times as K increases,
ADMM and demonstrate that the scores are equiva-
as each epoch of siamese grows exponentially with K.
lent to the stationary distribution of a Markov Chain.
Moreover, agreeing with Table 2, DSR-KL consistently
Our method significantly outperforms standard siamese
outperforms the predictions of DSR-l2, validating the
networks and state-of-the art spectral algorithms for
extension of ADMM penalty to KL divergence.
ranking regression. Given that the number of rank-
Details on Convergence. Figure 3 shows the log- ings grows exponentially in query size, designing active
likelihood −L on training and Top-1 Acc. on valida- learning algorithms to identify which rankings to solicit
tion sets of Movehub-Cost-4 and Movehub-Quality-4 from labelers is an interesting open problem. Gener-
datasets, partitioned w.r.t. rank partitioning. Each alizing existing active learning algorithms for shallow
point for DSR-KL and DSR-l2 correspond to an over- models, e.g. Guo et al. (2018), to deeper models via
all iteration of ADMM (c.f. (8)), while each point for our efficient algorithms is a promising direction.
 Deep Spectral Ranking

Acknowledgments Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and
Fei-Fei, L. (2009). Imagenet: A large-scale hierar-
Our work is supported by NIH (R01EY019474), NSF chical image database. In Conference on Computer
(SCH-1622542 at MGH, SCH-1622536 at Northeastern, Vision and Pattern Recognition (CVPR), pages 248–
SCH-1622679 at OHSU), Facebook Statistics Research 255.
Award, and by unrestricted departmental funding from
Research to Prevent Blindness (OHSU). Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.
(2019). Bert: Pre-training of deep bidirectional trans-
Bibliography formers for language understanding. In Proceedings
of the 2019 Conference of the North American Chap-
Ataer-Cansızoğlu, E. (2015). Retinal image analytics: A ter of the Association for Computational Linguistics:
complete framework from segmentation to diagnosis. Human Language Technologies, Volume 1 (Long and
Northeastern University. Short Papers), pages 4171–4186.
Blitzer (2017). Movehub city rankings. [Link] Doughty, H., Damen, D., and Mayol-Cuevas, W. (2018).
[Link]/blitzr/movehub-city-rankings? Who’s better? who’s best? pairwise deep ranking for
select=[Link]. skill determination. In Proceedings of the IEEE Con-
Bosman, A. S., Engelbrecht, A., and Helbig, M. (2020). ference on Computer Vision and Pattern Recognition,
Visualising basins of attraction for the cross-entropy pages 6057–6066.
and the squared error neural network loss functions. Dubey, A., Naik, N., Parikh, D., Raskar, R., and Hi-
Neurocomputing. dalgo, C. A. (2016). Deep learning the city: Quanti-
Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, fying urban perception at a global scale. In European
J. (2011). Distributed optimization and statistical Conference on Computer Vision (ECCV), pages 196–
learning via the Alternating Direction Method of 212. Springer.
Multipliers. Foundations and Trends R in Machine Elo, A. E. (1978). The rating of chessplayers, past and
Learning, 3(1):1–122. present. Arco Pub.
Boyd, S. and Vandenberghe, L. (2004). Convex opti- Golik, P., Doetsch, P., and Ney, H. (2013). Cross-
mization. Cambridge University Press. entropy vs. squared error training: a theoretical and
Bradley, R. A. and Terry, M. E. (1952). Rank analysis experimental comparison. In Interspeech, volume 13,
of incomplete block designs: I. the method of paired pages 1756–1760.
comparisons. Biometrika, 39(3/4):324–345.
Guo, Y., Tian, P., Kalpathy-Cramer, J., Ostmo, S.,
Bromley, J., Guyon, I., LeCun, Y., Säckinger, E., Campbell, J. P., Chiang, M. F., Erdoğmuş, D., Dy,
and Shah, R. (1994). Signature verification using a J. G., and Ioannidis, S. (2018). Experimental design
"siamese" time delay neural network. In Advances in under the Bradley-Terry model. In International
Neural Information Processing Systems (NeurIPS), Joint Conference on Artificial Intelligence (IJCAI),
pages 737–744. pages 2198–2204.
Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, Han, B. (2018). DATELINE: Deep Plackett-Luce model
M., Hamilton, N., and Hullender, G. (2005). Learn- with uncertainty measurements. arXiv preprint
ing to rank using gradient descent. In Proceedings of arXiv:1812.05877.
the International Conference on Machine Learning
Joachims, T. (2002). Optimizing search engines using
(ICML), pages 89–96. ACM.
clickthrough data. In Proceedings of the Eighth ACM
Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., and Li, H. SIGKDD International Conference on Knowledge
(2007). Learning to rank: from pairwise approach Discovery and Data Mining, pages 133–142. ACM.
to listwise approach. In Proceedings of the 24th
Kendall, M. G. (1938). A new measure of rank correla-
International Conference on Machine learning, pages
tion. Biometrika, 30(1/2):81–93.
129–136.
Caruana, R. and Niculescu-Mizil, A. (2004). Data min- Kingma, D. P. and Ba, J. (2015). Adam: A method
ing in metric space: an empirical analysis of super- for stochastic optimization. In ICLR (Poster).
vised learning performance criteria. In Proceedings of Kullback, S. and Leibler, R. A. (1951). On informa-
the tenth ACM SIGKDD International Conference tion and sufficiency. The Annals of Mathematical
on Knowledge Discovery and Data Mining, pages Statistics, 22(1):79–86.
69–78. Lei, Q., Zhong, K., and Dhillon, I. S. (2016).
Chang, H., Yu, F., Wang, J., Ashley, D., and Finkel- Coordinate-wise power method. In Advances in Neu-
stein, A. (2016). Automatic triage for a photo series. ral Information Processing Systems (NeurIPS), pages
ACM Transactions on Graphics (TOG), 35(4):148. 2064–2072.
 Yıldız, Dy, Erdoğmuş, Ostmo, Campbell, Chiang, Ioannidis

Leka, O. (2016). IMDB movies dataset. [Link] Thurstone, L. L. (1927). The method of paired com-
[Link]/orgesleka/imdbmovies. parisons for social values. The Journal of Abnormal
Li, Y., Cheng, X., and Gui, G. (2018). Co-robust- and Social Psychology, 21(4):384.
ADMM-net: Joint ADMM framework and DNN for Tian, P., Guo, Y., Kalpathy-Cramer, J., Ostmo, S.,
robust sparse composite regularization. IEEE Access, Campbell, J. P., Chiang, M. F., Dy, J., Erdoğmuş,
6:47943–47952. D., and Ioannidis, S. (2019). A severity score for
Liu, R., Jiang, Z., Fan, X., Li, H., and Luo, Z. (2018). Retinopathy of Prematurity. In Proceedings of the
Single image layer separation via deep ADMM un- 25th ACM SIGKDD International Conference on
rolling. In 2018 IEEE International Conference on Knowledge Discovery & Data Mining, pages 1809–
Multimedia and Expo, pages 1–6. 1819.
Ma, J., Liu, X.-Y., Shou, Z., and Yuan, X. (2019). Deep Wang, F., Cao, W., and Xu, Z. (2018). Convergence of
tensor ADMM-net for snapshot compressive imaging. multi-block Bregman ADMM for nonconvex compos-
In Proceedings of the IEEE International Conference ite problems. Science China Information Sciences,
on Computer Vision (ICCV), pages 10223–10232. 61(12):122101.
Ma, J., Yi, X., Tang, W., Zhao, Z., Hong, L., Chi, E. H., Wang, H. and Banerjee, A. (2014). Bregman Alternat-
and Mei, Q. (2020). Learning-to-rank with parti- ing Direction Method of Multipliers. In Advances in
tioned preference: Fast estimation for the plackett- Neural Information Processing Systems (NeurIPS),
luce model. arXiv preprint arXiv:2006.05067. pages 2816–2824.
Maystre, L. and Grossglauser, M. (2015). Fast and Xia, F., Liu, T.-Y., Wang, J., Zhang, W., and Li,
accurate inference of Plackett-Luce models. In Ad- H. (2008). Listwise approach to learning to rank:
vances in Neural Information Processing Systems theory and algorithm. In Proceedings of the 25th
(NeurIPS), pages 172–180. international conference on Machine learning, pages
McFadden, D. (1973). Conditional logit analysis of 1192–1199.
qualitative choice behavior. Yang, Y., Sun, J., Li, H., and Xu, Z. (2020). ADMM-
Pahikkala, T., Tsivtsivadze, E., Airola, A., Järvinen, CSNet: A deep learning approach for image compres-
J., and Boberg, J. (2009). An efficient algorithm for sive sensing. IEEE Transactions on Pattern Analysis
learning to rank from preference graphs. Machine and Machine Intelligence PAMI, 42(3):521–538.
Learning, 75(1):129–165. Ye, S., Feng, X., Zhang, T., Ma, X., Lin, S., Li, Z.,
Plackett, R. L. (1975). The analysis of permutations. Xu, K., Wen, W., Liu, S., Tang, J., Fardad, M., Lin,
Applied Statistics, pages 193–202. X., Liu, Y., and Wang, Y. (2019). Progressive DNN
compression: A key to achieve ultra-high weight
Ryzin, G. v. and Mahajan, S. (1999). On the rela-
pruning and quantization rates using ADMM.
tionship between inventory costs and variety ben-
efits in retail assortments. Management Science, Ye, S., Zhang, T., Zhang, K., Li, J., Xie, J., Liang,
45(11):1496–1509. Y., Liu, S., Lin, X., and Wang, Y. (2018). A uni-
Shi, Z., Zhang, X., and Yu, Y. (2017). Bregman diver- fied framework of DNN weight pruning and weight
gence for stochastic variance reduction: saddle-point clustering/quantization using ADMM.
and adversarial prediction. In Advances in Neural Yıldız, İ., Dy, J., Erdoğmuş, D., Kalpathy-Cramer, J.,
Information Processing Systems (NeurIPS), pages Ostmo, S., Campbell, J. P., Chiang, M. F., and Ioan-
6031–6041. nidis, S. (2020). Fast and accurate ranking regression.
Sun, J., Li, H., Xu, Z., et al. (2016). Deep ADMM-Net In International Conference on Artificial Intelligence
for compressive sensing MRI. In Advances in Neural and Statistics (AISTATS).
Information Processing Systems (NeurIPS), pages Yıldız, İ., Tian, P., Dy, J., Erdoğmuş, D., Brown, J.,
10–18. Kalpathy-Cramer, J., Ostmo, S., Campbell, J. P.,
Sun, S.-H. (2020). Crawl and visualize ICLR 2020 open- Chiang, M. F., and Ioannidis, S. (2019). Classifica-
review data. [Link] tion and comparison via neural networks. Neural
ICLR2020-OpenReviewData. Networks.
Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, Yu, Y. and Açıkmeşe, B. (2019). Stochastic breg-
S., Anguelov, D., Erhan, D., Vanhoucke, V., and man parallel direction method of multipliers for dis-
Rabinovich, A. (2015). Going deeper with convolu- tributed optimization. In 2019 IEEE 58th Conference
tions. In Computer Vision and Pattern Recognition on Decision and Control (CDC), pages 5550–5555.
(CVPR), 2015. IEEE.
 Deep Spectral Ranking

Yu, Y., Açıkmeşe, B., and Mesbahi, M. (2018). Breg-

man parallel direction method of multipliers for dis-
tributed optimization via mirror averaging. IEEE
Control Systems Letters, 2(2):302–306.
Zhao, H. and Liao, P. (2019). CAE-ADMM: Implicit
bitrate optimization via ADMM-based pruning in
compressive autoencoders.
Zhao, P., Liu, S., Wang, Y., and Lin, X. (2018). An
ADMM-based universal framework for adversarial at-
tacks on deep neural networks. In Proceedings of the
26th ACM International Conference on Multimedia,
page 1065–1073, New York, NY, USA. Association
for Computing Machinery.
Zhu, Y., Kiros, R., Zemel, R., Salakhutdinov, R., Urta-
sun, R., Torralba, A., and Fidler, S. (2015). Aligning
books and movies: Towards story-like visual expla-
nations by watching movies and reading books. In
Proceedings of the IEEE International Conference
on Computer Vision, pages 19–27.