Minimax-optimal Inference from Partial Rankings

Introduction

Given a set of individual preferences from multiple decision makers or judges, we address the problem of computing a consensus ranking that best represents the preference of the population collectively. This problem, known as rank aggregation, has received much attention across various disciplines including statistics, psychology, sociology, and computer science, and has found numerous applications including elections, sports, information retrieval, transportation, and marketing . While consistency of various rank aggregation algorithms has been studied when a growing number of sampled partial preferences is observed over a fixed number of items , little is known in the high-dimensional setting where the number of items and number of observed partial rankings scale simultaneously, which arises in many modern datasets. Inference becomes even more challenging when each individual provides limited information. For example, in the well known Netflix challenge dataset, 480,189 users submitted ratings on 17,770 movies, but on average a user rated only $209$ movies. To pursue a rigorous study in the high-dimensional setting, we assume that users provide partial rankings over subsets of items generated according to the popular Plackett-Luce (PL) model from some hidden preference vector over all the items and are interested in estimating the preference vector (see Definition 1).

Intuitively, inference becomes harder when few users are available, or each user is assigned few items to rank, meaning fewer observations. The first goal of this paper is to quantify the number of item assignments needed to achieve a target estimation error. Secondly, in many practical scenarios such as crowdsourcing, the systems have the control over the item assignment. For such systems, a natural question of interest is how to optimally assign the items for a given budget on the total number of item assignments. Thirdly, a common approach in practice to deal with partial rankings is to break them into pairwise comparisons and apply the state-of-the-art rank aggregation methods specialized for pairwise comparisons . It is of both theoretical and practical interest to understand how much the performance degrades when rank breaking schemes are used.

1 Problem setup

We describe our model in the context of recommender systems, but it is applicable to other systems with partial rankings. Consider a recommender system with $m$ users indexed by $[m]$ and $n$ items indexed by $[n]$. For each item $i\in[n]$, there is a hidden parameter $\theta^{\ast}_{i}$ measuring the underlying preference. Each user $j$, independent of everyone else, randomly generates a partial ranking $\sigma_{j}$ over a subset of items $S_{j}\subseteq[n]$ according to the PL model with the underlying preference vector $\theta^{\ast}=(\theta^{\ast}_{1},\ldots,\theta^{\ast}_{n})$.

A partial ranking $\sigma:[|S|]\to S$ is generated from $\{\theta^{\ast}_{i},i\in S\}$ under the PL model in two steps: (1) independently assign each item $i\in S$ an unobserved value $X_{i},$ exponentially distributed with mean $e^{-\theta^{\ast}_{i}};$ (2) select $\sigma$ so that $X_{\sigma(1)}\leq X_{\sigma(2)}\leq\cdots\leq X_{\sigma(|S|)}$.

The PL model can be equivalently described in the following sequential manner. To generate a partial ranking $\sigma$, first select $\sigma(1)$ in $S$ randomly from the distribution {e^{\theta^{\ast}_{i}}}/\big{(}\sum_{i^{\prime}\in S}e^{\theta^{\ast}_{i^{\prime}}}\big{)}; secondly, select $\sigma(2)$ in $S\setminus\{\sigma(1)\}$ with the probability distribution {e^{\theta^{\ast}_{i}}}/\big{(}{\sum_{{i^{\prime}}\in S\setminus\{\sigma(1)\}}e^{\theta^{\ast}_{i^{\prime}}}}\big{)}; continue the process in the same fashion until all the items in $S$ are assigned. The PL model is a special case of the following class of models.

A partial ranking $\sigma:[|S|]\to S$ is generated from $\{\theta^{\ast}_{i},i\in S\}$ under the Thurstone model for a given CDF $F$ in two steps: (1) independently assign each item $i\in S$ an unobserved utility $U_{i},$ with CDF $F(c-\theta^{*}_{i});$ (2) select $\sigma$ so that $U_{\sigma(1)}\geq U_{\sigma(2)}\geq\cdots\geq U_{\sigma(|S|)}$.

To recover the PL model from the Thurstone model, take $F$ to be the CDF for the standard Gumbel distribution: $F(c)=e^{-(e^{-c})}$. Equivalently, take $F$ to be the CDF of $-\log(X)$ such that $X$ has the exponential distribution with mean one. For this choice of $F,$ the utility $U_{i}$ having CDF $F(c-\theta^{*}_{i}),$ is equivalent to $U_{i}=-\log(X_{i})$ such that $X_{i}$ is exponentially distributed with mean $e^{-\theta^{*}_{i}}.$ The corresponding partial permutation $\sigma$ is such that $X_{\sigma(1)}\leq X_{\sigma(2)}\leq\cdots\leq X_{\sigma(|S|)},$ or equivalently, $U_{\sigma(1)}\geq U_{\sigma(2)}\geq\cdots\geq U_{\sigma(|S|)}.$ (Note the opposite ordering of $X$’s and $U$’s.)

We denote the number of items assigned to user $j$ by $k_{j}:=|S_{j}|$ and the average number of assigned items per use by $k=\frac{1}{m}\sum_{j=1}^{m}k_{j};$ parameter $k$ may scale with $n$ in this paper. We consider two scenarios for generating the subsets $\{S_{j}\}_{j=1}^{m}$: the random item assignment case where the $S_{j}$’s are chosen independently and uniformly at random from all possible subsets of $[n]$ with sizes given by the $k_{j}$’s, and the deterministic item assignment case where the $S_{j}$’s are chosen deterministically.

Our main results depend on the structure of a weighted undirected graph $G$ defined as follows.

Each item $i\in[n]$ corresponds to a vertex $i\in[n]$. For any pair of vertices $i,i^{\prime}$, there is a weighted edge between them if there exists a user who ranks both items $i$ and $i^{\prime}$; the weight equals $\sum_{j:i,i^{\prime}\in S_{j}}\frac{1}{k_{j}-1}$.

Let $A$ denote the weighted adjacency matrix of $G$. Let $d_{i}=\sum_{j}A_{ij},$ so $d_{i}$ is the number of users who rank item $i,$ and without loss of generality assume $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$. Let $D$ denote the $n\times n$ diagonal matrix formed by $\{d_{i},i\in[n]\}$ and define the graph Laplacian $L$ as $L=D-A$. Observe that $L$ is positive semi-definite and the smallest eigenvalue of $L$ is zero with the corresponding eigenvector given by the normalized all-one vector. Let $0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ denote the eigenvalues of $L$ in ascending order.

Theorem 1 gives a lower bound for the estimation error that scales as $\sum_{i=2}^{n}\frac{1}{d_{i}}$. The lower bound is derived based on a genie-argument and holds for both the PL model and the more general Thurstone model. Theorem 2 shows that the Cramér-Rao lower bound scales as $\sum_{i=2}^{n}\frac{1}{\lambda_{i}}$. Theorem 3 gives an upper bound for the squared error of the maximum likelihood (ML) estimator that scales as $\frac{mk\log n}{(\lambda_{2}-\sqrt{\lambda_{n}})^{2}}$. Under the full rank breaking scheme that decomposes a $k$-way comparison into $\binom{k}{2}$ pairwise comparisons, Theorem 4 gives an upper bound that scales as $\frac{mk\log n}{\lambda_{2}^{2}}.$ If the comparison graph is an expander graph, i.e., $\lambda_{2}\sim\lambda_{n}$ and $mk=\Omega(n\log n),$ our lower and upper bounds match up to a $\log n$ factor. This follows from the fact that $\sum_{i}\lambda_{i}=\sum_{i}d_{i}=mk$, and for expanders $mk=\Theta(n\lambda_{2}).$ Since the Erdős-Rényi random graph is an expander graph with high probability for average degree larger than $\log n,$ when the system is allowed to choose the item assignment, we propose a random assignment scheme under which the items for each user are chosen independently and uniformly at random. It follows from Theorem 1 that $mk=\Omega(n)$ is necessary for any item assignment scheme to reliably infer the underlying preference vector, while our upper bounds imply that $mk=\Omega(n\log n)$ is sufficient with the random assignment scheme and can be achieved by either the ML estimator or the full rank breaking or the independence-preserving breaking that decompose a $k$-way comparison into $\lfloor k/2\rfloor$ non-intersecting pairwise comparisons, proving that rank breaking schemes are also nearly optimal.

2 Related Work

There is a vast literature on rank aggregation, and here we can only hope to cover a fraction of them we see most relevant. In this paper, we study a statistical learning approach, assuming the observed ranking data is generated from a probabilistic model. Various probabilistic models on permutations have been studied in the ranking literature (see, e.g., ). A nonparametric approach to modeling distributions over rankings using sparse representations has been studied in . Most of the parametric models fall into one of the following three categories: noisy comparison model, distance based model, and random utility model. The noisy comparison model assumes that there is an underlying true ranking over $n$ items, and each user independently gives a pairwise comparison which agrees with the true ranking with probability $p>1/2$. It is shown in that $O(n\log n)$ pairwise comparisons, when chosen adaptively, are sufficient for accurately estimating the true ranking.

The Mallows model is a distance-based model, which randomly generates a full ranking $\sigma$ over $n$ items from some underlying true ranking $\sigma^{\ast}$ with probability proportional to $e^{-\beta d(\sigma,\sigma^{\ast})}$, where $\beta$ is a fixed spread parameter and $d(\cdot,\cdot)$ can be any permutation distance such as the Kemeny distance. It is shown in that the true ranking $\sigma^{\ast}$ can be estimated accurately given $O(\log n)$ independent full rankings generated under the Mallows model with the Kemeny distance.

In this paper, we study a special case of random utility models (RUMs) known as the Plackett-Luce (PL) model. It is shown in that the likelihood function under the PL model is concave and the ML estimator can be efficiently found using a minorization-maximization (MM) algorithm which is a variation of the general EM algorithm. We give an upper bound on the error achieved by such an ML estimator, and prove that this is matched by a lower bound. The lower bound is derived by comparing to an oracle estimator which observes the random utilities of RUM directly. The Bradley-Terry (BT) model is the special case of the PL model where we only observe pairwise comparisons. For the BT model, proposes RankCentrality algorithm based on the stationary distribution of a random walk over a suitably defined comparison graph and shows $\Omega(n{\sf poly}(\log n))$ randomly chosen pairwise comparisons are sufficient to accurately estimate the underlying parameters; one corollary of our result is a matching performance guarantee for the ML estimator under the BT model. More recently, analyzed various algorithms including RankCentrality and the ML estimator under a general, not necessarily uniform, sampling scheme.

In a PL model with priors, MAP inference becomes computationally challenging. Instead, an efficient message-passing algorithm is proposed in to approximate the MAP estimate. For a more general family of random utility models, Soufiani et al. in give a sufficient condition under which the likelihood function is concave, and propose a Monte-Carlo EM algorithm to compute the ML estimator for general RUMs. More recently in , the generalized method of moments together with the rank-breaking is applied to estimate the parameters of the PL model and the random utility model when the data consists of full rankings.

Main results

In this section, we present our theoretical findings and numerical experiments.

In this section, we derive an oracle lower bound for any estimator of $\theta^{\ast}$. The lower bound is constructed by considering an oracle who reveals all the hidden scores in the PL model as side information and holds for the general Thurstone models.

Suppose $\sigma_{1}^{m}$ are generated from the Thurstone model for some CDF $F.$ For any estimator $\widehat{\theta},$

where $\mu$ is the probability density function of $F$, i.e., $\mu=F^{\prime}$ and $I(\mu)=\int\frac{\left(\mu^{\prime}(x)\right)^{2}}{\mu(x)}dx$; the second inequality follows from the Jensen’s inequality. For the PL model, which is a special case of the Thurstone models with $F$ being the standard Gumbel distribution, $I(\mu)=1$.

Theorem 1 shows that the oracle lower bound scales as $\sum_{i=2}^{n}\frac{1}{d_{i}}$. We remark that the summation begins with $1/d_{2}.$ This makes some sense, in view of the fact that the parameters $\theta^{\ast}_{i}$ need to sum to zero. For example, if $d_{1}$ is a moderate value and all the other $d_{i}$’s are very large, then we may be able to accurately estimate $\theta_{i}^{*}$ for $i\neq 1$ and therefore accurately estimate $\theta_{1}^{*}.$ The oracle lower bound also depends on the dynamic range $b$ and is tight for $b=0$, because a trivial estimator that always outputs the all-zero vector achieves the lower bound.

Theorem 1 implies that $mk=\Omega(n)$ is necessary for any item assignment scheme to reliably infer $\theta^{\ast}$, i.e., ensuring $E[||\widehat{\theta}-\theta^{*}||^{2}]=o(n)$. It provides the first converse result on inferring the parameter vector under the general Thurstone models to our knowledge. For the Bradley-Terry model, which is a special case of the PL model where all the partial rankings reduce to the pairwise comparisons, i.e., $k=2$, it is shown in that $m=\Omega(n)$ is necessary for the random item assignment scheme to achieve the reliable inference based on the information-theoretic argument. In contrast, our converse result is derived based on the Bayesian Cramé-Rao lower bound , applies to the general models with any item assignment, and is considerably tighter if $d_{i}$’s are of different orders.

2 Cramér-Rao lower bound

In this section, we derive the Cramér-Rao lower bound for any unbiased estimator of $\theta^{\ast}$.

where the second inequality follows from the Jensen’s inequality.

The Cramér-Rao lower bound scales as $\sum_{i=2}^{n}\frac{1}{\lambda_{i}}$. When $G$ is disconnected, i.e., all the items can be partitioned into two groups such that no user ever compares an item in one group with an item in the other group, $\lambda_{2}=0$ and the Cramér-Rao lower bound is infinity, which is valid (and of course tight) because there is no basis for gauging any item in one connected component with respect to any item in the other connected component and the accurate inference is impossible for any estimator. Although the Cramér-Rao lower bound only holds for any unbiased estimator, we suspect that a lower bound with the same scaling holds for any estimator, but we do not have a proof.

3 ML upper bound

In this section, we study the ML estimator based on the partial rankings. The ML estimator of $\theta^{\ast}$ is defined as $\widehat{\theta}_{{\sf ML}}\in\arg\max_{\theta\in\Theta_{b}}{\mathcal{L}}(\theta)$, where ${\mathcal{L}}(\theta)$ is the log likelihood function given by

As observed in , ${\mathcal{L}}(\theta)$ is concave in $\theta$ and thus the ML estimator can be efficiently computed either via the gradient descent method or the EM type algorithms.

The following theorem gives an upper bound on the error rates inversely dependent on $\lambda_{2}$. Intuitively, by the well-known Cheeger’s inequality, if the spectral gap $\lambda_{2}$ becomes larger, then there are more edges across any bi-partition of $G$, meaning more pairwise comparisons are available between any bi-partition of movies, and therefore $\theta^{\ast}$ can be estimated more accurately.

Assume $\lambda_{n}\geq C\log n$ for a sufficiently large constant $C$ in the case with $k>2$. Then with high probability,

We compare the above upper bound with the Cramér-Rao lower bound given by Theorem 2. Notice that $\sum_{i=1}^{n}\lambda_{i}=mk$ and $\lambda_{1}=0$. Therefore, $\frac{mk}{\lambda_{2}^{2}}\geq\sum_{i=2}^{n}\frac{1}{\lambda_{i}}$ and the upper bound is always larger than the Cramér-Rao lower bound. When the comparison graph $G$ is an expander and $mk=\Omega(n\log n)$, by the well-known Cheeger’s inequality, $\lambda_{2}\sim\lambda_{n}=\Omega(\log n)$ , the upper bound is only larger than the Cramér-Rao lower bound by a logarithmic factor. In particular, with the random item assignment scheme, we show that $\lambda_{2},\lambda_{n}\sim\frac{mk}{n}$ if $mk\geq C\log n$ and as a corollary of Theorem 3, $mk=\Omega(n\log n)$ is sufficient to ensure $\|\widehat{\theta}_{{\sf ML}}-\theta^{\ast}\|_{2}=o(\sqrt{n})$, proving the random item assignment scheme with the ML estimation is minimax-optimal up to a $\log n$ factor.

Suppose $S_{1}^{m}$ are chosen independently and uniformly at random among all possible subsets of $[n]$. Then there exists a positive constant $C>0$ such that if $m\geq Cn\log n$ when $k=2$ and $mk\geq Ce^{2b}\log n$ when $k>2$, then with high probability

Theorem 3 provides the first finite-sample error rates for inferring the parameter vector under the PL model to our knowledge. For the Bradley-Terry model, which is a special case of the PL model with $k=2$, derived the similar performance guarantee by analyzing the rank centrality algorithm and the ML estimator. More recently, extended the results to the non-uniform sampling scheme of item pairs, but the performance guarantees obtained when specialized to the uniform sampling scheme require at least $m=\Omega(n^{4}\log n)$ to ensure $\|\widehat{\theta}-\theta^{\ast}\|_{2}=o(\sqrt{n})$, while our results only require $m=\Omega(n\log n)$.

4 Rank breaking upper bound

In this section, we study two rank-breaking schemes which decompose partial rankings into pairwise comparisons.

Given a partial ranking $\sigma$ over the subset $S\subset[n]$ of size $k$, the independence-preserving breaking scheme (IB) breaks $\sigma$ into $\lfloor k/2\rfloor$ non-intersecting pairwise comparisons of form $\{i_{t},i^{\prime}_{t},y_{t}\}_{t=1}^{\lfloor k/2\rfloor}$ such that $\{i_{s},i^{\prime}_{s}\}\cap\{i_{t},i^{\prime}_{t}\}=\emptyset$ for any $s\neq t$ and $y_{t}=1$ if $\sigma^{-1}(i_{t})<\sigma^{-1}(i^{\prime}_{t})$ and otherwise. The random IB chooses $\{i_{t},i^{\prime}_{t}\}_{t=1}^{\lfloor k/2\rfloor}$ uniformly at random among all possibilities.

If $\sigma$ is generated under the ${\sf PL}$ model, then the IB breaks $\sigma$ into independent pairwise comparisons generated under the ${\sf PL}$ model. Hence, we can first break partial rankings $\sigma_{1}^{m}$ into independent pairwise comparisons using the random IB and then apply the ML estimator on the generated pairwise comparisons with the constraint that $\theta\in\Theta_{b}$, denoted by $\widehat{\theta}_{{\sf IB}}$. Under the random assignment scheme, as a corollary of Theorem 3, $mk=\Omega(n\log n)$ is sufficient to ensure $\|\widehat{\theta}_{{\sf IB}}-\theta^{\ast}\|_{2}=o(\sqrt{n})$, proving the random item assignment scheme with the random IB is minimax-optimal up to a $\log n$ factor in view of the oracle lower bound in Theorem 1.

Suppose $S_{1}^{m}$ are chosen independently and uniformly at random among all possible subsets of $[n]$ with size $k.$ There exists a positive constant $C>0$ such that if $mk\geq Cn\log n$, then with high probability,

Given a partial ranking $\sigma$ over the subset $S\subset[n]$ of size $k$, the full breaking scheme (FB) breaks $\sigma$ into all $\binom{k}{2}$ possible pairwise comparisons of form $\{i_{t},i^{\prime}_{t},y_{t}\}_{t=1}^{\binom{k}{2}}$ such that $y_{t}=1$ if $\sigma^{-1}(i_{t})<\sigma^{-1}(i^{\prime}_{t})$ and otherwise.

If $\sigma$ is generated under the ${\sf PL}$ model, then the FB breaks $\sigma$ into pairwise comparisons which are not independently generated under the ${\sf PL}$ model. We pretend the pairwise comparisons induced from the full breaking are all independent and maximize the weighted log likelihood function given by

with the constraint that $\theta\in\Theta_{b}$. Let $\widehat{\theta}_{{\sf FB}}$ denote the maximizer. Notice that we put the weight $\frac{1}{k_{j}-1}$ to adjust the contributions of the pairwise comparisons generated from the partial rankings over subsets with different sizes.

Furthermore, suppose $S_{1}^{m}$ are chosen independently and uniformly at random among all possible subsets of $[n]$. There exists a positive constant $C>0$ such that if $mk\geq Cn\log n$, then with high probability,

Theorem 4 shows that the error rates of $\widehat{\theta}_{{\sf FB}}$ inversely depend on $\lambda_{2}$. When the comparison graph $G$ is an expander, i.e., $\lambda_{2}\sim\lambda_{n}$, the upper bound is only larger than the Cramér-Rao lower bound by a logarithmic factor. The similar observation holds for the ML estimator as shown in Theorem 3. With the random item assignment scheme, Theorem 4 imply that the FB only need $mk=\Omega(n\log n)$ to achieve the reliable inference, which is optimal up to a $\log n$ factor in view of the oracle lower bound in Theorem 1.

The rank breaking schemes considered in breaks the full rankings according to rank positions while our schemes break the partial rankings according to the item indices. The results in establish the consistency of the generalized method of moments under the rank breaking schemes when the data consists of full rankings. In contrast, Corollary 2 and Theorem 4 apply to the more general setting with partial rankings and provide the finite-sample error rates, proving the optimality of the random IB and FB with the random item assignment scheme.

5 Numerical experiments

Suppose there are $n=1024$ items and the underlying preference vector $\theta^{\ast}$ is uniformly distributed over $[-b,b]$. We generate $d$ full rankings over $1024$ items according to the ${\sf PL}$ model with parameter $\theta^{\ast}.$ Fix a $k\in\{512,256,\ldots,2\}$. We break each full ranking $\sigma$ into $n/k$ partial rankings over subsets of size $k$ as follows: Let $\{S_{j}\}_{j=1}^{n/k}$ denote a partition of $[n]$ generated uniformly at random such that $S_{j}\cap S_{j^{\prime}}=\emptyset$ for $j\neq j^{\prime}$ and $|S_{j}|=k$ for all $j$; generate $\{\sigma_{j}\}_{j=1}^{n/k}$ such that $\sigma_{j}$ is the partial ranking over set $S_{j}$ consistent with $\sigma$. In this way, in total we generate $m=dn/k$ $k$-way comparisons which are all independently generated from the PL model. To compute the ML estimator of $\theta^{\ast}$ based on the generated partial rankings, we apply the minorization-maximation (MM) algorithm proposed in . We measure the estimation error by the normalized mean square error (MSE) defined as $\frac{mk}{n^{2}}\|\widehat{\theta}_{{\sf ML}}-\theta^{\ast}\|^{2}$.

We run the simulation with $b=0,2$ and $d=16,32,64,128$. The results are depicted in Fig. 1. We also plot the Cramér-Rao limit given by $\left(1-\frac{1}{k}\sum_{l=1}^{k}\frac{1}{l}\right)^{-1}$ as per Theorem 2. The oracle lower bound in Theorem 1 implies that the normalized MSE is at least $1$. We can see that the normalized MSE approaches the Cramér-Rao limit as $d$ increases and achieves the oracle lower bound if further $k$ becomes large, suggesting the ML estimator is minimax-optimal. Moreover, with a large number of partial rankings available, i.e., $d$ is large enough, when $k$ is decreased from $n$ to $2$, the normalized MSE increases roughly by a factor of $4$ if $b=0$ and $6$ if $b=2$, suggesting that the random IB is minimax-optimal up to a $\log n$ factor. Also, we observe that the normalized MSE is not as sensitive to the value of $b$ as claimed by our upper bounds given by Corollary 1. Notice that in the case with $b=2$, according to the PL model, the item with the highest preference is ranked higher than the item with lowest preference with probability $\frac{e^{4}}{1+e^{4}}\approx 0.98$.

Proofs

We introduce some additional notations used in the proof. For a vector $x$, let $\|x\|_{2}$ denote the usual $l_{2}$ norm. Let $\mathbf{1}$ denote the all-one vector and $\mathbf{0}$ denote the all-zero vector with the appropriate dimension. Let ${\mathcal{S}}^{n}$ denote the set of $n\times n$ symmetric matrices with real-valued entries. For $X\in{\mathcal{S}}^{n}$, let $\lambda_{1}(X)\leq\lambda_{2}(X)\leq\cdots\leq\lambda_{n}(X)$ denote its eigenvalues sorted in increasing order. Let ${\rm Tr}(X)=\sum_{i=1}^{n}\lambda_{i}(X)$ denote its trace and $\|X\|=\max\{-\lambda_{1}(X),\lambda_{n}(X)\}$ denote its spectral norm. For two matrices $X,Y\in{\mathcal{S}}^{n}$, we write $X\leq Y$ if $Y-X$ is positive semi-definite, i.e., $\lambda_{1}(Y-X)\geq 0$. Recall that ${\mathcal{L}}(\theta)$ is the log likelihood function. The first-order partial derivative of ${\mathcal{L}}(\theta)$ is given by

and the Hessian matrix $H(\theta)\in{\mathcal{S}}^{n}$ with $H_{ii^{\prime}}(\theta)=\frac{\partial^{2}{\mathcal{L}}(\theta)}{\partial\theta_{i}\partial\theta_{i^{\prime}}}$ is given by

and then the Laplacian of the pairwise comparison graph $G$ satisfies $L=\sum_{j=1}^{m}L_{j}$.

We first introduce a key auxiliary result used in the proof. Let $F$ be a fixed CDF (to be used in the Thurstone model), let $b>0$ and suppose $\theta$ is a parameter to be estimated with $\theta\in[-b,b]$ from observation $U=(U_{1},\ldots,U_{d}),$ where the $U_{i}$’s are independent with the common CDF given by $F(c-\theta)$. The following proposition gives a lower bound on the average MSE for a fixed prior distribution based on Van Trees inequality .

Let $p_{0}$ be a probability density on $$such that$p_{0}(1)=p_{0}(-1)=0$and define the prior density of$\Theta$as$p(\theta)=\frac{1}{b}p_{0}(\frac{\theta}{b})$. Then for any estimator$T(U)$of$\Theta$,

where $\mu$ is the probability density function of $F$ with $I(\mu)=\int\frac{\left(\mu^{\prime}(x)\right)^{2}}{\mu(x)}dx$ and $I(p_{0})=\int_{-1}^{1}\frac{\left(p_{0}^{\prime}(\theta)\right)^{2}}{p_{0}(\theta)}d\theta$.

It follows from the Van Trees inequality that

where the Fisher information $I(\theta)=dI(\mu)$ and

Let $\widehat{\theta}$ be a given estimator. The minimax MSE for $\widehat{\theta}$ is greater than or equal to the average MSE for a given prior distribution on $\theta^{*}.$ Let $p_{0}(\theta)=\cos^{2}(\pi\theta/2)$, then $I(p_{0})=\pi^{2}$. Define $p(\theta)=\frac{1}{b}p_{0}(\frac{\theta}{b})$. If $n$ is even we use the following prior distribution. The prior distribution of $\theta^{*}_{i}$ for $i$ odd is $p(\theta)$ and for $i$ even, $\theta^{*}_{i}\equiv-\theta^{*}_{i-1}.$ If $n$ is odd use the same distribution for $\theta^{*}_{1}$ through $\theta^{*}_{n-1}$ and set $\theta^{*}_{n}\equiv 0.$ Note that $\theta^{*}\in\Theta_{b}$ with probability one. For simplicity, we assume $n$ is odd in the rest of this proof; the modification for $n$ even is trivial. We use the genie argument, so that the observer can see the hidden utilities in the Thurstone model. The estimation of $\theta^{*}$ decouples into $\lfloor\frac{n}{2}\rfloor$ disjoint problems, so we can focus on the estimation of $\theta_{1}$ from the vector of random variables $U=(U_{1},\ldots,U_{d_{1}})$ associated with item 1 and the vector of random variables $V=(V_{1},\ldots,V_{d_{2}})$ associated with item 2. The distribution functions of the $U_{i}$’s are all $F(c-\theta_{1}^{\ast})$ and the distribution functions of the $V_{i}$’s are all $F(c+\theta_{1}^{\ast})$, and the $U$’s and $V$’s are all mutually independent given $\theta^{*}.$ Recall that $\mu$ is the probability density function of $F$, i.e., $\mu=F^{\prime}$. The Fisher information for each of the $d_{1}+d_{2}$ observations is $I(\mu)$, so that Proposition 1 carries over to this situation with $d=d_{1}+d_{2}.$ Therefore, for any estimator $T(U,V)$ of $\Theta^{*}_{1}$ (the random version of $\theta_{1}^{*}$),

By this reasoning, for any odd value of $i$ with $1\leq i<n$ we have

Summing over all odd values of $i$ in the range $1\leq i<n$ yields the theorem. Furthermore, since $\sum_{i=1}^{n}d_{i}=mk$, by Jensen’s inequality, $\sum_{i=2}^{n}\frac{1}{d_{i}}\geq\frac{(n-1)^{2}}{\sum_{i=2}^{n}d_{i}}\geq\frac{(n-1)^{2}}{mk}.$ ∎

2 Proof of Theorem 2

If $\theta$ equals the all-zero vector, then

3 Proof of Theorem 3

With probability at least $1-\frac{2e^{2}}{n}$,

Observed that $-H(\theta)$ is positive semi-definite with the smallest eigenvalue equal to zero. The following lemma lower bounds its second smallest eigenvalue.

where the inequality holds with probability at least $1-n^{-1}$ in the case with $k>2$.

Case $k_{j}=2,\forall j\in[m]$: The Hessian matrix simplifies as

Observe that $H(\theta)$ is deterministic given $S_{1}^{m}$. Since $|\theta_{i}|\leq b,\forall i\in[n]$,

It follows that $-H(\theta)\geq\frac{e^{2b}}{(1+e^{2b})^{2}}L$ and the theorem follows.

Case $k_{j}>2$ for some $j\in[m]$: We first introduce a key auxiliary result used in the proof.

Fix $\theta$ satisfying the conditions of the lemma. It is easy to see that for each $i,$ $p_{i}\geq\frac{1}{re^{2b}}.$ The matrix $A$ is positive semidefinite, and its smallest eigenvalue is zero, with the corresponding eigenvector $\mathbf{1}.$ So $\lambda_{2}(A)=\min_{\alpha}\alpha^{T}A\alpha$ subject to the constraints $\alpha^{T}\mathbf{1}=0$ and $\|\alpha\|^{2}=1.$ For $\alpha$ satisfying the constraints,

The proof of the first part of the lemma is complete. We remark that the bound of the lemma is nearly tight for the case $\theta_{1}=\ldots=\theta_{r-1}=b$ and $\theta_{r}=-b,$ for which $\lambda_{2}(A)=\frac{e^{2b}r}{((r-1)e^{2b}+1)^{2}}.$ The final equivalence mentioned in the lemma follows from the facts $\lambda_{1}(e^{2b}A)=\lambda_{1}(B)=0$ with common corresponding eigenvector $\mathbf{1},$ and $\lambda_{i}(e^{2b}A)\geq\frac{1}{r}=\lambda_{i}(B)$ for $2\leq i\leq r.$ ∎

Recall that $L$ is the Laplacian of $G$ and $L=\sum_{j=1}^{m}L_{j}$. It follows that

Define $\Delta=\widehat{\theta}_{{\sf ML}}-\theta^{\ast}$. It follows from the definition that $\Delta$ is orthogonal to the all-one vector. By the definition of the ML estimator, ${\mathcal{L}}(\widehat{\theta}_{{\sf ML}})\geq{\mathcal{L}}(\theta^{\ast})$ and thus

where the last inequality holds due to the Cauchy-Schwartz inequality. By the Taylor expansion, there exists a $\theta=a\widehat{\theta}_{{\sf ML}}+(1-a)\theta^{\ast}$ for some $a\in$ such that

where the last inequality holds because the Hessian matrix $-H(\theta)$ is positive semi-definite with $H(\theta)\mathbf{1}=\mathbf{0}$ and $\Delta^{\top}\mathbf{1}=0$. Combining (12) and (13),

Note that $\theta\in\Theta_{b}$ by definition. The theorem follows by Lemma 1 and Lemma 2.

4 Proof of Corollary 1

and thus $\lambda_{2}\geq\frac{mk}{2(n-1)}$ and $\lambda_{n}\leq\frac{3mk}{2(n-1)}$. By the assumption that $mk\geq Ce^{2b}\log n$ for some sufficiently large constant $C$, $\lambda_{2}-16e^{2b}\sqrt{\lambda_{n}\log n}\geq\frac{mk}{4n}.$ Then the corollary follow from Theorem 3. ∎

5 Proof of Corollary 2

6 Proof of Theorem 4

It follows from the definition of ${\mathcal{L}}(\theta)$ given by (2) that

which is a sum of $d_{i}$ independent random variables with mean zero and bounded by $1$. By Hoeffding’s inequality, $|\nabla_{i}L(\theta^{*})|\leq\sqrt{d_{i}\log n}$ with probability at least $1-2n^{-2}$. By union bound, $\|\nabla L(\theta^{\ast})\|_{2}\leq\sqrt{mk\log n}$ with probability at least $1-2n^{-1}$. The Hessian matrix is given by

If $|\theta_{i}|\leq b,\forall i\in[n]$, $\frac{\exp(\theta_{i}+\theta_{i^{\prime}})}{\left[\exp(\theta_{i})+\exp(\theta_{i^{\prime}})\right]^{2}}\geq\frac{e^{2b}}{(1+e^{2b})^{2}}.$ It follows that $-H(\theta)\geq\frac{e^{2b}}{(1+e^{2b})^{2}}L$ for $\theta\in\Theta_{b}$ and the theorem follows from (14).

References