Individualized Rank Aggregation using Nuclear Norm Regularization

Introduction

We have seen a number of recent advancements to the theory of rank aggregation. This problem has a number of applications ranging from marketing and advertisements to competitions and election. The main question of rank aggregation is how to consistently combine various individual preferences. This type of data is frequently available to us: what webpage did a user select, who won the chess match, which movie did a user watch, etc…. All of these examples yield comparisons without explicitly revealing an underlying score. That is, only the preference is observed, not necessarily the strength of the preference (in the case of sports one might argue that the score indicates such a magnitude difference). Additionally, numeric scores have been shown to be inconsistent and subject to variations in calibration in various contexts. Given how natural the problem of rank aggregation is, there has been a wide body recent and classical work to understand how to consistently combine preferences. However, all of these methods have a major drawback: they aim to find one ranking. In many settings, various individuals will have separate preferences, and we wish to model those distinctions. For example, we might wish to provide personalized ads, search results, or movie recommendations on a per user basis. In standard contexts we assume that there is one consistent ranking that does well to approximate the behavior of all users, but these aggregation methods cannot model the discrepancies across users. Our goal is to understand how to analyze a method that has the flexibility to account for user differences and can be adaptive; that is, if there are no differences, then the method should have stronger performance guarantees. This task can be seen as rank aggregation analog to the standard collaborative filtering problem.

While there have been significant theoretical advances in the understanding of collaborative filtering, or more generally matrix completion , there has been far less work in understanding how to perform the proposed type of collaborative ranking. Recent work has demonstrated that taking rankings into consideration can significantly improve upon rating prediction accuracy , thus it is a natural question to understand how such collaborative ranking methods might behave. One reason for this discrepancy is this theoretical understanding of single user rank aggregation is already a very challenging problem as discussed above. Whereas, single rating aggregation is trivial: take an average. Another, possibly more interesting distinction is in the amount of apparent information made available. In the standard matrix completion setting we have direct (albeit noisy) access to the true underlying ratings. Therefore, if the noise is sufficiently small, we could order the information into a list. On the other hand, in the collaborative ranking problem we never have direct access to the true signal itself and only observe relative differences. In some sense, this is a harder problem owing to the fact that the comparisons are in themselves functions of the underlying ratings. When we are given, for example, $p$ ratings, then we can convert that to $\binom{p}{2}$ pairwise comparisons. This crude analysis seems to indicate that we would require far greater pairwise comparisons in order to recover the true underlying matrix. We will show that this increase in the number of examples is not required. In the sequel, we will show that under a natural choice model for collaborative ranking, the total number of comparisons needed to estimate the parameters is on the same order as the total number of explicit ratings observations required in the standard matrix completion literature. Thus, we demonstrate that collaborative ranking based pair-wise comparisons from a simple and natural model can yield very similar results as in the standard matrix completion setting.

As alluded to above there has been some work in understanding collaborative rankings and learning user preferences. The nuclear norm approach is fundamentally a regularized $M$-estimator . The application of the nuclear norm approach to collaborative ranking was first proposed by Yi et al. . There work showed very good empirical evidence for using such a nuclear norm regularized based approach. However, that work left open the question of theoretical guarantees. Other results also assume that the underlying ratings are in fact available. However, rather than inferring unknown ratings their goal is to infer unknown ranked preferences from known ratings. That is, they wish to deduce if a user will prefer one item over another rather than guess what their ratings of that item might be . The work by by Weimer et. al. also uses a nuclear norm regularization, but that work assumes access to the true underlying ratings, while we assume access only to pairwise preferences. Other algorithms aggregate users’ ratings by exploiting the similarity of users by nearest neighbor search , low-rank matrix factorization , or probabilistic latent model . However, as noted, numeric ratings can be highly varied even when preferences are shared.

Pairwise preference based ranking methods can effectively address the limitations of rating based methods. Furthermore, numerical ratings can always be transformed into pairwise comparisons. Salimans et al. use a bilinear model and do estimation in the Bayesian framework. Liu et al. use the Bradley-Terry-Luce (BTL) Model. Rather than our low-rank setting, they characterize the similarity between different users by using a mixture model. Both methods are computationally inefficient. More important, all these methods fail to provide theoretical justifications of their algorithms.

There are some theoretical works for learning a single ranking list from pairwise comparisons. Work by Jamieson and Nowak seeks to exploit comparisons to significantly reduce the number of samples required to obtain a good estimate of an individual’s utility function. Their method demonstrates that when the objects exist in a lower-dimensional space, then the number of queries required to learn the user’s utility significantly decreases. One drawback of their approach is that the authors must assume that descriptors or features for the underlying objects are provided; which is not necessarily the case in all contexts. Negahban et al. propose the Rank Centrality algorithm and show rate optimal (up to log factors) error bounds of their algorithm under BTL model. They also provide theoretical analysis of penalized maximum likelihood estimator, which serves as an inspiration of our work.

Our contributions

In this report, we present the first theoretical analysis of a collaborative ranking algorithm under a natural observation model. The algorithm itself is quite simple and falls into the framework of regularized $M$-estimator . We provide finite sample guarantees that hold with high probability on recovering the underlying preference matrix. Furthermore, the techniques outlined in the proof section our general and can be applied to a variety of sampling operators for matrix completion. For example, a simple modification of our proof yields a different class of results for the “one-bit” matrix completion problem .

In the following we present an explicit description of our model in Section 2. In Section 3 we present the proposed estimation procedure that we wish to analyze. Finally, in Section 4 we provide a statement of the main theorem followed by experiments in Section 5. Finally, in Section 6 we present the proof.

Notation:

Problem Statement and Model

In this section we provide a precise description of the underlying statistical model as well as our problem.

and denotes the relative preference that user $k(i)$ has for item $l(i)$ versus $j(i)$. Our observation model takes the form

The above is the standard Bradley-Terry-Luce model for pairwise comparisons. In full generality, one can also consider the Thurstone models for pairwise preferences.

We shall take $\Theta^{*}$ to be low-rank or well approximate by a low-rank matrix. This is analogous to the matrix completion literature and models the fact that the underlying preferences are derived from latent low-dimensional factors. In this way, we can extract features on items and users without explicit domain knowledge.

Estimation Procedure

We consider the following simple estimator for performing collaborating ranking. It is an example of a regularized $M$-estimator .

where $\mathcal{L}_{n}(\Theta)$ is the random loss function and

The method itself has a very simple interpretation. The random loss function encourages the recovered parameters to match the observations. That is, if $y_{i}=1$ then we expect that $\Theta^{*}_{k(i),l(i)}>\Theta^{*}_{k(i),j(i)}$. The second term is the nuclear norm and that encourages the underlying matrix $\Theta^{*}$ to be low-rank .

Main Results

In this section we present the main results of our paper, which demonstrates that we are able to recover the underlying parameters with very few total observations. The result is analogous to similar results presented for matrix completion ,

Under the described sampling model, let $d=(d_{1}+d_{2})/2$, assume $n<d^{2}\log d$, and take $\lambda\geq 32\sqrt{\frac{d\log d}{n}}$. Then, we have that the Frobenius norm of the error $\Delta=\widehat{\Theta}-\Theta^{*}$ satisfies

with probability at least $1-\frac{2}{d^{2}}$ for some universal constant $c_{1}$.

The above result demonstrates that we can obtain consistent estimates of the parameters $\Theta^{*}$ using the convex program outlined in the previous section. Furthermore, the error bound behaves as a parametric error rate, that is the error decays as $\frac{1}{n}$. The result also decomposes into two terms. The first is the penalty for estimating a rank $r$ matrix and the second is the price we pay for estimating an approximately low-rank matrix $\Theta^{*}$ with a rank $r$ matrix. These results exactly match analogous results in the matrix completion literature barring one difference: there is also a dependency on the function $\psi$. However, this necessity is quite natural since if we are interested in parameter recovery, then it would be impossible to distinguish between extremely large parameters. Indeed, this observation is related to the problem of trying to measure the probability of a coin coming up heads when that probability is extremely close to one. Other results in matrix completion also discuss such a requirement as well as the influence of the spikyness parameter . The proof of this result, for which we provide an outline in Section 6, follows similar lines as other results for matrix completion.

Experiments

Here we present simulation results to demonstrate the accuracy of the error rate behavior predicted by Theorem 1. To make the results more clean, we consider the exact low rank case here, which means each individual user’s preference vector is the linear combination of $r$ preference vectors. Then according to our main results, the empirical squared Frobenius norm error $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}$ under our estimation procedure (2) will be scaled as $\frac{rd\log d}{n}$. For all the experiments, we solved the convex program (2) by using proximal gradient descent with step-sizes from for fast convergence via our own implementation in R.

In Figure 1 we report the results of four different problem sizes with equal user size $d_{1}$ and item size $d_{2}$ and the fixed rank $r$, where $d_{1}=d_{2}=d\in\{100,150,200,250\}$, $r=4$. For a given sample size d, we ran $T=10$ trials and computed the squared Frobenius norm error $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}$ averaged over those trials. Panel (a) shows the plots of Frobenius norm error versus raw sample size. It shows the consistency of our estimation procedure because the Frobenius norm error goes to zero as sample size increases. And the curves shift to right as the problem dimension $d$ increases, matching with the intuition that larger matrices require more samples. In panel (b), we plot the simulation results versus the rescaled sample size $N=n/(rd\log d)$. Consistent with the prediction of Theorem 1, the error plots are aligned fairly well and decay at the rate of $1/N$

Proof of Main Result

We now present a proof of the main result. We will use the machinery developed by Negahban and Wainwright and establish a Restricted Strong Convexity (RSC) for our loss. The proof follows standard techniques, with some care when handling the new observation operator.

The key to establishing the RSC condition is to demonstrate that the error in the first order Taylor approximation of the loss is lower-bounded by some quadratic function. To that end we note that for $\Delta=\Theta-\Theta^{*}$ and by the Taylor expansion we have that

Now, we may apply the fact that both $\|\widehat{\Theta}\|_{\infty}$, $\|\Theta^{*}\|_{\infty}\leq\alpha/\sqrt{d_{1}d_{2}}$ and that $\psi(x)$ is symmetric and decreases as $x$ increases to obtain that equation (3) is lower-bounded by:

Therefore, it suffices to prove a lower-bound on $\frac{1}{2n}\left(\langle\!\langle{\Delta},\;{X^{(i)}}\rangle\!\rangle\right)^{2}$ for all possible vectors $\Delta$. For that, we present the following lemma.

For $\|\Theta\|_{\infty}\leq r_{3}:=\frac{2\alpha}{\sqrt{d_{1}d_{2}}}$, $d=(d_{1}+d_{2})/2$, and $n<d^{2}\log d$. When $X^{(i)}$ are i.i.d observations we have with probability greater than $1-2d^{-2^{18}}$

Another key element for establishing the error is the following upper-bound on the operator norm of a random matrix.

We these two ingredients in hand we may now prove the main result. The steps are a slight modification of the ones taken for standard matrix completion . By the optimality of $\widehat{\Theta}$ we have

Let $\Delta=\widehat{\Theta}-\Theta^{*}$, then

By Taylor expansion, the left hand side is lower bounded by

Hölder’s inequality between the nuclear norm and operator norm yields

By the triangle inequality $|\!|\!|\Theta^{*}|\!|\!|_{{\operatorname{\tiny{nuc}}}}-|\!|\!|\widehat{\Theta}|\!|\!|_{{\operatorname{\tiny{nuc}}}}\leq|\!|\!|\Delta|\!|\!|_{{\operatorname{\tiny{nuc}}}}$. If we choose $\lambda>2|\!|\!|\nabla\mathcal{L}_{n}(\Theta^{*})|\!|\!|_{{2}}$, we have

Now, the random matrix $\nabla\mathcal{L}_{n}(\Theta^{*})=\frac{1}{n}\sum_{i=1}^{n}\left(\frac{\exp(\langle\!\langle{X^{(i)}},\;{\Delta}\rangle\!\rangle)}{1+\exp(\langle\!\langle{X^{(i)}},\;{\Delta}\rangle\!\rangle)}-y_{i}\right)X^{(i)}$ and satisfies the conditions of Lemma 2 with $\gamma=2$, so we can take $\lambda=32\sqrt{\frac{d\log d}{n}}$

From Lemma 1 of Negahban and Wainwright , $\Delta$ can be decomposed into $\Delta^{\prime}+\Delta^{\prime\prime}$, where $\Delta^{\prime}$ has rank less than $2r$ and $\Delta^{\prime\prime}$ satisfies

Then by the triangle inequality and $|\!|\!|\Delta^{\prime}|\!|\!|_{{\operatorname{\tiny{nuc}}}}\leq\sqrt{2r}|\!|\!|\Delta^{\prime}|\!|\!|_{{F}}$

Now depending on whether $\Delta$ belongs to set $\mathcal{A}$, we split into two cases. Case 1: When $\Delta\notin\mathcal{A}$, $|\!|\!|\Delta|\!|\!|_{{F}}^{2}\leq 128\alpha|\!|\!|\Delta|\!|\!|_{{\operatorname{\tiny{nuc}}}}\sqrt{\frac{d\log d}{n}}$. From Equation (5), we get

Case 2: Otherwise, from Lemma 1, with probability greater than $1-2d^{-2^{18}}$, $\mathcal{L}_{n}(\widehat{\Theta})-\mathcal{L}_{n}(\Theta^{*})-\langle\!\langle{\nabla\mathcal{L}_{n}(\Theta^{*})},\;{\Delta}\rangle\!\rangle\geq\frac{\psi\left(2\alpha\right)}{3}|\!|\!|\Delta|\!|\!|_{{F}}^{2}$. Therefore, the above equations yield

Now, performing similar calculations as above we have

Combining the two displays above yields the desired result.

2 Proof of Lemma 1

We use a peeling argument as in Lemma 3 of to prove Lemma 1. Before that, we first present the following lemma.

then we have $|\!|\!|\Theta|\!|\!|_{{F}}\geq 128\alpha\sqrt{\frac{d\log d}{n}}:=\mu$. Consider the sets

3 Proof of Lemma 3

Our goal will be to first show that $Z$ concentrates around its mean and then upper bound the expectation. We prove the concentration results via the bounded differences inequality ; since $Z$ is a symmetric function of its arguments, it suffices to establish the bounded differences property with respect to the first coordinate. Suppose we have two samples of $(k(i),l(i),j(i))_{i=1}^{n}$ that only differ at the first coordinate.

Then by the bounded differences inequality, we have

where $\varepsilon_{i}$ are i.i.d. Rademacher random variables. Since $|\Theta_{a(i)l(i)}-\Theta_{a(i)j(i)}|\leq 2r_{3}$, we have by the Ledoux-Talagrand contraction inequality that

By an application of Hölder’s inequality we have that

Let $W_{i}:=\varepsilon_{i}e_{k(i)}(e_{l(i)}-e_{j(i)})^{T}$. $W_{i}$ is a zero-mean random matrix, and since

Notice $|\!|\!|W_{i}|\!|\!|_{{2}}\leq 2$, thus, Lemma 4 yields the tail bound

Set $t=\sqrt{\frac{16\log d_{1}d_{2}}{n\min\{d_{1},d_{2}\}}}$, we obtain with probability greater that $1-\frac{1}{d_{1}d_{2}}$,

By the triangle inequality, $|\!|\!|\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}e_{k(i)}(e_{l(i)}-e_{j(i)})^{T}|\!|\!|_{{2}}\leq|\!|\!|\varepsilon_{i}e_{k(i)}(e_{l(i)}-e_{j(i)})^{T}|\!|\!|_{{2}}\leq 2$ and the fact $n\leq d^{2}\log d$

Plug it into (6) and set $t=\frac{D^{2}}{2d_{1}d_{2}}$, we get the result.

4 Ahlswede-Winter Matrix Bound

As in previous work we also use a version of the Ahlswede-Winter concentration bound. We use a version due to Tropp .

Let $W_{i}$ be independent $d_{1}\times d_{2}$ zero-mean random matrices such that $|\!|\!|W_{i}|\!|\!|_{{2}}\leq M$, and define

as well as $\sigma^{2}:=\sum_{i=1}^{n}\sigma_{i}^{2}$. We have

Discussion

In this paper we presented a theoretical justification for a ranking based collaborative filtering approach based on pairwise comparisons in contrast to other results that rely on knowing the underlying ratings. We provided the first convergence bounds for recovering the underlying user preferences of items and showed that those bounds are analogous to the ones originally developed for rating based matrix completion. The analysis here can also be extended do other observation models, for example to the “one-bit” matrix completion setting as well. However, that extension does not provide any additional insights beyond the analysis presented here. There remain a number of extensions for these methods including adaptive and active recommendations, skewed sampling distributions on the items, as well as different choice models. We leave such extensions for future work.

References