# A Spectral Approach to Item Response Theory

Duc Nguyen
Department of Computer and Information Science
University of Pennsylvania
<EMAIL_ADDRESS>
&Anderson Y. Zhang
Department of Statistics and Data Science
University of Pennsylvania
<EMAIL_ADDRESS>

###### Abstract

The Rasch model is one of the most fundamental models in _item response
theory_ and has wide-ranging applications from education testing to
recommendation systems. In a universe with $n$ users and $m$ items, the Rasch
model assumes that the binary response $X_{li}\in\\{0,1\\}$ of a user $l$ with
parameter $\theta^{*}_{l}$ to an item $i$ with parameter $\beta^{*}_{i}$
(e.g., a user likes a movie, a student correctly solves a problem) is
distributed as
$\mathbb{P}(X_{li}=1)=1/(1+\mathrm{exp}\left(-(\theta^{*}_{l}-\beta^{*}_{i})\right))$.
In this paper, we propose a _new item estimation_ algorithm for this
celebrated model (i.e., to estimate $\beta^{*}$). The core of our algorithm is
the computation of the stationary distribution of a Markov chain defined on an
item-item graph. We complement our algorithmic contributions with finite-
sample error guarantees, the first of their kind in the literature, showing
that our algorithm is consistent and enjoys favorable optimality properties.
We discuss practical modifications to accelerate and robustify the algorithm
that practitioners can adopt. Experiments on synthetic and real-life datasets,
ranging from small education testing datasets to large recommendation systems
datasets show that our algorithm is scalable, accurate, and competitive with
the most commonly used methods in the literature.

##  1 Introduction

Item response theory (IRT) is the study of the relationship between latent
characteristics (a student’s ability versus a test’s difficulty or a user’s
taste versus a movie’s features) and the manifestations of these
characteristics (a student’s performance on a test or a user’s rating of a
movie). Originally developed by the psychometric community [45, 51], item
response theory has been applied to diverse settings such as education testing
[37], crowdsourcing [54], recommendation systems [12], finance [50] and
marketing research [10].

One of the most fundamental models in IRT is the Rasch model [45]. It models
the _binary response $X_{li}\in\\{0,1\\}$_ of user $l$ with latent parameter
$\theta^{*}_{l}\in\mathbb{R}$ to item $i$ with latent parameter
$\beta^{*}_{i}\in\mathbb{R}$ by

$\mathbb{P}(X_{li}=1)=\frac{1}{1+\mathrm{exp}\left(-(\theta^{*}_{l}-\beta^{*}_{i})\right)}\,.$
(1)

For example, in education testing, $\theta^{*}_{l}$ corresponds to the ability
of student $l$, $\beta^{*}_{i}$ the difficulty of problem $i$ and $X_{li}=1$
if the student correctly solves the problem. Binary response data has grown
abundantly in modern domains: Netflix famously switched from a 5-star rating
system to a binary like/dislike feedback system, data on students’ engagement
and performance grows significantly as education moves online during the
pandemic.

Traditionally, the goal of estimation under the Rasch model is to _recover the
item parameters $\beta^{*}$_. In education testing, an estimate of the item
parameters can be used to calibrate scores across different versions of a
test. In recommendation systems, the item parameters can be used to produce a
ranking over the items. In general, estimation is challenging under the Rasch
model because for each user and item pair, we only get a single observation or
none in the case of missing data.

Joint maximum likelihood estimate (JMLE) is one of the earliest methods
developed for the estimation problem [3, 22, 25, 27]. It estimates both the
user and item parameters by maximizing the joint likelihood function using an
alternating maximization algorithm. While efficient, JMLE is known to be
_inconsistent_ (that is, even as $n\rightarrow\infty$, JMLE does not recover
$\beta^{*}$) when the number of items is finite [3, 24] (e.g., Figure 1(a)).
Intuitively, this is because there are many nuisance user parameters to a
finite number of item parameters. As a result, JMLE is mostly used for
prelimary parameter estimation and researchers have developed other solutions
to address the inconsistency problem, broadly consisting of 3 approaches as
follows.

The first approach is marginal maximum likelihood estimate (MMLE) [7]. The
statistician first specifies a prior distribution over the user parameters.
The objective of MMLE is to maximize the marignal likelihood function which
_integrates out_ the user parameters. In pratice, MMLE runs quite fast,
handles missing data well and is reasonably accurate. However, its performance
_depends on the accuracy of the prior distribution_. If misspecified, MMLE may
produce inaccurate estimates (e.g., Figure 1(b)). Model selection is thus a
crucial procedure when applying MMLE to real data.

The second approach is conditional maximum likelihood estimate (CMLE) [3, 22,
27]. CMLE builds on the fact that under the Rasch model the total number of
positive responses $s_{l}$ for each user $l$ is a sufficient statistic for the
user parameter $\theta^{*}_{l}$. Instead of the joint likelihood function,
CMLE maximizes the likelihood conditioned on $\\{s_{l}\\}_{l=1}^{n}$. Unlike
JMLE, CMLE is _statistically consistent without requiring any distribution
assumptions about $\theta^{*}$_. For small datasets with no missing data, CMLE
is quite accurate. However, it may incur _high computational cost and
numerical issues_ on large datasets with many items and missing entries.
Practioners have observed that CMLE often produces inaccurate estimates [35,
36] in this regime (e.g., Figure 1(c)).

The third approach, which our algorithm follows, uses _pairwise information_
that can be extracted from binary responses. Intuitively, if a user responds
to two items, one negatively and one positively, we learn that the later is
‘better’. Following this intuition, previous authors [23, 17, 48] have
designed spectral algorithms that first construct an item-item matrix and then
compute its leading eigenvector. One common limitation of these methods is
that the item-item matrix is _assumed to be dense_. Therefore, these methods
aren’t directly extendable to large scale datasets in applications such as
recommendation systems where the item-item observation is sparse.

Furthermore, most theoretical guarantees for the above methods are asymptotic
$(n\rightarrow\infty)$. However, having finite sample error guarantees is
useful in real-life applications. For example, when we only observe a handful
of responses to a new item, it is important to have an accurate estimate of
the error over the item parameter. Asymptotic guarantees, on the other hand,
are accurate mostly under a large sample size regime, and can be inaccurate in
the data-poor regime.

Our Contributions: Motivated by known limitations of the existing methods, we
propose a new, theoretically grounded algorithm that addresses these
limitations and performs competitively with the most commonly used methods in
the literature. More specifically:

  * •

In Sections 2 and 4, we describe the spectral algorithm and practical
modifications – an accelerated version of the original algorithm and a
regularization strategy – that allow the algorithm to scale to large real-life
datasets with sparse observation patterns and alleviate numerical issues.

  * •

In Section 3, we present _non-asymptotic_ error guarantees for the spectral
method – the first of their kind in the literature – in Theorems 3.1 and 3.3.
Notably, under the regime where $m$ grows, the spectral algorithm has optimal
(up to a constant factor) estimation error achievable by any unbiased
estimator (Theorem 3.4). Under the challenging regime where $m$ is a constant
or grows very slowly we show that the spectral algorithm is, unlike JMLE,
_consistent_ (Corollary 3.2).

  * •

In Section 5, we present experiment results on a wide range of datasets, both
synthetic and real, to show that our spectral algorithm is _competitive_ with
the most commonly used methods in the literature, _works off-the-shelf with
minimal tuning and is scalable_ on large datasets.

###  1.1 Notations and Problem Formulation

As briefly described before, in a universe of $n$ users and $m$ items, each
user $l$ has a latent parameter $\theta^{*}_{l}\in\mathbb{R}$ and each item
$i$ has latent parameter $\beta^{*}_{i}\in\mathbb{R}$. The reader may
recognize that there is a fundamental identifiability issue associated with
the Rasch model pertaining to translation. That is,
$\\{\theta^{*},\beta^{*}\\}$ and
$\\{\theta^{*}+\alpha\mathbf{1}_{n},\beta^{*}+\alpha\mathbf{1}_{m}\\}$
describe the same model for any $\alpha\in\mathbb{R}$. For this reason, we
impose a normalization constraint on the item parameters
${\beta^{*}}^{\top}\mathbf{1}_{m}=0$. We consider the fixed range setting
where $\beta^{*}_{i}\in[\beta^{*}_{\min},\beta^{*}_{\max}]\,\forall i\in[m]$
for some constants $\beta^{*}_{\min}$, $\beta^{*}_{\max}$. Similarly, we
assume that $\theta^{*}_{l}\in[\theta^{*}_{\min},\theta^{*}_{\max}]$ for some
constants $\theta^{*}_{\min},\theta^{*}_{\max}$ 111The bounded range
assumption is a common one in the literature on the Rasch model. Intuitively,
it eliminates the presence of items that are always repsonded positively to
(or negatively to) and users who only responds positively (or negatively) that
leads to parameter unidentifiability [26].. The observed data is
$X\in\\{0,1,*\\}^{n\times m}$ where $*$ denotes missing data and for entries
where $X_{li}\neq*$, $X_{li}$ is independently distributed per Equation (1).
Let $A\in\\{0,1\\}^{n\times m}$ denote the assignment matrix where $A_{li}=1$
if user $l$ responds (either negatively or positively) to item $i$ and $0$ if
user $l$ does not respond to item $i$ (i.e., $X_{li}=*$). Define
$B=A^{\top}A$, i.e., $B_{ij}$ is the number of users who respond to both items
$i,j$. The goal of item estimation is to obtain an estimate $\beta$ from the
observed data $X$ and the metric of interest is the $\ell_{2}$ error,
$\lVert\beta-\beta^{*}\rVert_{2}$.

##  2 The Spectral Estimator

In this section we describe our spectral algorithm which is summarized in
Algorithm 1. At a high level, the algorithm constructs a Markov chain defined
on a graph whose vertices are the items and its transition probabilities are
estimated using the observed user-item response data. The algorithm then
computes the stationary distribution of this Markov chain and the estimate
$\beta$ is obtained following a simple transformation.

We first define, for each item pair $i,j$ and a fixed assignment $A$, a
quantity which we term _pairwise differential measurement_ :

$Y_{ij}=\sum_{l=1}^{n}A_{li}A_{lj}X_{li}(1-X_{lj})\quad\forall i\neq
j\in[m]\,.$ (2)

Intuitively, $Y_{ij}$ is the number of users who respond $1$ to $i$ and $0$ to
$j$. Given the pairwise differential measurements, consider a Markov chain
$P\in[0,1]^{m\times m}$ whose transition probabilities are defined as follows:

$P_{ij}=\begin{cases}\frac{1}{d}Y_{ij}&\text{ if $i\neq j$}\\\ 1-\sum_{k\neq
i}\frac{1}{d}Y_{ik}&\text{ if $i=j$}\end{cases}\quad,$ (3)

where $d$ is a sufficiently large normalization factor chosen such that the
resulting pairwise transition probability matrix does not contain any negative
entries. Typically, $d=O(\max_{i\in[m]}\sum_{k\neq i}B_{ik})$. The algorithm
then computes the stationary distribution $\pi$ of the Markov chain (e.g.,
using power iteration) and recover $\beta$ using a post-processing step. In
real-life datasets, the constructed Markov chain is often sparse (not every
pair of items has non-zero pairwise differential measurements). Practicioners
could take advantage of this sparsity to speed up the computation of the
stationary distribution such as by using sparse matrix-vector multiplication
subroutines.

Algorithm 1 Spectral Estimator

Input:  User-item binary response data $X\in\\{0,1,*\\}^{n\times m}$
Output:  An estimate of the item parameters
$\beta=[\beta_{1},\ldots,\beta_{m}]$

1: Construct a Markov chain $P$ per Equation (3)

2: Compute the stationary distribution of $P$: Initialize
$\pi^{(0)}=[\frac{1}{m},\ldots,\frac{1}{m}]$ For $t=1,2,\ldots$ until
convergence, compute
${\pi^{(t)}}^{\top}=\frac{{\pi^{(t-1)}}^{\top}P}{\lVert{\pi^{(t-1)}}^{\top}P\rVert_{1}}$

3: Compute $z=\pi/d$ and $\bar{\beta}=\log(z)$

4: Return the normalized item parameters, i.e.,
$\beta=\bar{\beta}-\bar{\beta}^{\top}\mathbf{1}/m$

To understand the intuition behind our spectral algorithm, let us consider the
following idealized Markov chain where the state transition probabilities are
exact:

$P^{*}_{ij}=\begin{cases}\frac{1}{d}Y_{ij}^{*}&\text{for }i\neq j\\\
1-\frac{1}{d}\sum_{k\neq i}Y^{*}_{ik}&\text{for }i=j\end{cases}\quad,$ (4)

where $Y_{ij}^{*}=\sum_{l=1}^{n}A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]$. For
every pair $i,j$, given a sufficiently large number of users who respond to
both items, $Y_{ij}$ will concentrate around $Y_{ij}^{*}$. Then, under an
appropriately large scaling factor $d$, $P_{ij}\approx P^{*}_{ij}$ and the two
Markov chains are ‘close’. This means that the stationary distribution of $P$
is also close to that of $P^{*}$. At the same time, the true item parameter
$\beta^{*}$ is directly related to the stationary distribution of $P^{*}$.
This relation is summarized by Proposition 2.1.

######  Proposition 2.1.

Consider the idealized Markov chain described in Equation (4). The stationary
distribution $\pi^{*}$ of $P^{*}$ satisfies
$\pi^{*}_{i}=e^{\beta_{i}^{*}}/(\sum_{k=1}^{m}e^{\beta_{k}^{*}})$ for
$i\in[m]$.

Essentially Proposition 2.1 states that $\pi^{*}$ is proportional to
$e^{\beta^{*}}$. Thus $\beta^{*}$ can be recovered from $\pi^{*}$ up to a
global normalization. Now, given a sufficiently large number of users, the
empirical stationary distribution $\pi$ will be close to $\pi^{*}$ and
naturally the obtained estimate $\beta$ is also close to $\beta^{*}$.

Readers who are familiar with the ranking from pairwise comparison literature
might recognize the similarity between the spectral algorithm and Rank
Centrality [43] for parameter estimation under the Bradley-Terry-Luce model
[38]. Similarly to Rank Centrality, our algorithm constructs a Markov chain on
the item-item graph and recovers parameter estimate from its stationary
distirbution. In both cases, the Markov chain interpretation is motivated by
the unique characteristics of the BTL and Rasch likelihood function. However,
the specific construction differs between our algorithm and Rank Centrality
and so does the resulting analysis.

##  3 Theoretical Analysis

In this section, we present the main theoretical contributions of the paper.
Specifically, we obtain in Section 3.1 two finite sample error bounds for two
different regimes of $m$: where $m$ is a constant or grows very slowly and
where $m$ grows at least logarithmically relative to $n$. In addition to our
upper bounds, we show in Section 3.2 a Cramer-Rao lower bound for the mean
squared error of any unbiased estimator, establishing the optimality of the
spectral algorithm under the the second regime. For the special case $m=2$, we
show that the error rate obtained by the spectral algorithm is optimal up to a
$\log$ factor.

###  3.1 Finite Sample Error Guarantees

Sampling Model: Let us consider a random sampling model where for each user
$l\in[n]$, each item $i\in[m]$ is independently shown to that user with
probability $p$ (i.e., $\mathbb{P}(A_{li}=1)=p$). Once shown an item $l$, the
user $i$ responds with $X_{li}$ distributed according to Equation (1).

Under this sampling model and the regime where _$m$ is a constant or grows
very slowly_, we obtain the following upper bound on the estimation error of
the spectral algorithm which is, to the best of our knowledge, the first
finite sample error guarantee for any consistent estimator under the Rasch
model in the literature.

######  Theorem 3.1.

Consider the sampling model described above. Suppose that $np^{2}\geq
C^{\prime}\log m$ for a sufficiently large constant $C^{\prime}$ then the
output of the spectral algorithm statisfies

$\lVert\beta-\beta^{*}\rVert_{2}\leq\frac{C\sqrt{\max\\{m,\log
np^{2}\\}}}{\sqrt{np^{2}}}$

with probability at least
$1-\min\\{e^{-12m},\frac{1}{(np^{2})^{12}}\\}-\mathrm{exp}\left(-C_{1}np^{2}\right)$,
where $C,C_{1}$ are constants.

As alluded to before in our algorithm description, the proof of Theorem 3.1
uses Markov chain analysis and a central object is the idealized Markov chain
$P^{*}$ with its stationary distribution $\pi^{*}$. The proof is rather long
and involved so we defer the details to the supplementary materials and
describe here the main idea. The starting point is a Markov chain eigen-
perturbation bound (see Lemma A.3):

$\lVert\pi-\pi^{*}\rVert_{2}\leq\frac{\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}}{\mu^{*}(P^{*})-\lVert
P-P^{*}\rVert_{2}}\,,$

where $\mu^{*}(P^{*})$ is the _spectral gap_ of the idealized Markov chain. We
then bound the numerator and the denominator separately. We will show under
the setting of Theorem 3.1 that

$\mu^{*}(P^{*})-\lVert
P-P^{*}\rVert_{2}=\Omega\bigg{(}\frac{1}{d}\bigg{)}\quad\text{and}\quad\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}=O\bigg{(}\frac{\sqrt{\max\\{m,\log
np^{2}\\}}}{dm\sqrt{np^{2}}}\bigg{)}\,.$

Combining these bounds with the following relation gives us the desired error
bound:

$\lVert\beta-\beta^{*}\rVert_{2}=O\bigg{(}m\cdot\lVert\pi-\pi^{*}\rVert_{2}\bigg{)}\,.$

As an immediate consequence of Theorem 3.1, we can also prove the consistency
of the spectral algorithm under the constant $m$ regime. As mentioned
previously, JMLE, one of the most well known methods in the Rasch modeling
literature, is inconsistent in this regime.

######  Corollary 3.2.

Consider the setting of Theorem 3.1. For a fixed $m$ and $p=1$, the spectral
algorithm is a consistent estimator of $\beta^{*}$. That is, its output
$\beta$ satisfies
$\lim_{n\rightarrow\infty}\mathbb{P}(\lVert\beta-\beta^{*}\rVert_{2}<\epsilon)=1\,,\forall\epsilon>0\,.$

_Under the regime where $m$ grows_, we could sharpen the results of Theorem
3.1. Specifically, when the number of items shown to each user is sufficiently
large, we improve by a $\sqrt{p}$ factor which can be significant when $p$ is
small. This is summarized by the following theorem.

######  Theorem 3.3.

Consider the setting of Theorem 3.1. Assume further that $mp\geq
C^{\prime\prime}\log n$ for a sufficiently large constant $C^{\prime\prime}$
then the output of the spectral algorithm statisfies

$\lVert\beta-\beta^{*}\rVert_{2}\leq\frac{C^{*}\sqrt{m}}{\sqrt{np}}$

with probability at least $1-\mathrm{exp}\left(-C_{2}np^{2}\right)-2n^{-9}$,
where $C^{*},C_{2}$ are constants.

The reader may wonder why there would be a difference between the two regimes.
Intuitively, when $m$ is a small constant, the distribution of the number of
items shown to the users are not tightly concentrated. Some users are shown
all of the items while some are shown only one. By design, our spectral
algorithm uses pairwise differential measurements. This means that when a user
responds to only one item, that information is not fully used. On the other
hand, when $mp=O(\log n)$, the number of items shown to the users is
concentrated (all users are shown approximately the same number of items) and
more pairwise differential measurements are available. There is less
information being under-utilized by the algorithm and it enjoys a tighter (in
fact optimal) error rate.

###  3.2 Cramer-Rao Lower Bound

In this section, we present complementary results to our finite error
guarantees obtained in the previous section. Notably, under the regime where
$m$ is allowed to grow with $n$, we show that the minimum mean squared error
achievable by any unbiased estimator is _no more than a constant factor_
smaller than the upper bound for the spectral algorithm established in Theorem
3.3. This optimality result is summarized by the following theorem.

######  Theorem 3.4.

Consider the sampling model described in in Section 3.1. Let $T$ be any
unbiased estimator for the item parameters. Then the mean squared error of
such estimator is lower bounded as

$\mathbb{E}\lVert T(X)-\beta^{*}\lVert^{2}_{2}\,\geq\frac{cm}{np}\,,$

where $T(X)$ is the output of the estimator $T$ when given data $X$ and $c$ is
a constant.

Now note that under the settings of Theorem 3.3, the output of the spectral
algorithm also statisfies
$\lVert\beta-\beta^{*}\rVert_{2}^{2}=O(\frac{m}{np})$. To the best of our
knowledge, this is the first non-asymptotic optimality result for any item
estimation method under the Rasch model.

As noted before, when the number of items is constant, our error bound in
Theorem 3.1 incurs an additional $1/\sqrt{p}$ factor. We now argue that the
upper bound obtained there may already be optimal in this challenging regime.
Consider the special case when $m=2$. Essentially, the goal is to estimate the
_difference of the two item parameters_. For a particular user $l$, suppose
that we have no information about her parameter $\theta_{l}$ other than the
bounded condition. If the user’s responses consist of a single response (the
response to one item is not observed) or that her responses to both items are
identical (either both $0$ or $1$), then we learn little about the difference
between the two items. We refer to these responses as ‘bad’ responses. The
relative difference between the items is only revealed if the user responds
differently to the items. As noted in the description of our spectral
algorithm, we refer to such information as _pairwise differential
measurements_.

For the special case $m=2$, both CMLE and JMLE actually ignore ‘bad’
responses. This is because in both algorithms, it has been shown that
including bad responses in the respective objective likelihood function leads
to parameter unidentifiability [26]. As mentioned earlier, MMLE, requires an
accurate prior distribution in order to obtain good estimate accuracy. This is
not possible when we have no information about the user parameters. With the
exception of MMLE, _all estimation methods_ that we are aware of in the
literature only use pairwise differential measurements.

With these points considered, if we restrict our attention to the class of
algorithms that use pairwise differential measurements, then the spectral
algorithm indeed achieves the best possible (up to a log factor) estimation
error.

######  Theorem 3.5.

Fix $m=2$ and consider the sampling model described in Section 3.1. Let $T$ be
any unbiased estimator for the item parameters that only uses _pairwise
differential measurements_. Then the mean squared error of such estimator is
lower bounded as

$\mathbb{E}\lVert
T(X)-\beta^{*}\lVert^{2}_{2}\,\geq\frac{c^{\prime}}{np^{2}}\,,$

where $T(X)$ is the output of the estimator $T$ when given data $X$ and
$c^{\prime}$ is a constant.

As seen from Theorem 3.1, the estimate produced by the spectral algorithm
satisfies $\lVert\beta-\beta^{*}\rVert^{2}_{2}=\tilde{O}(\frac{1}{np^{2}})$,
establishing its near optimality.

##  4 Practical Implementation Aspects

In this section, we discuss two important practical aspects that practicioners
may consider when applying the spectral algorithm real-life datasets of which
observation pattern may not correspond exactly to the sampling model described
in Section 3.1. Firstly, we identify slow convergence as a problem encountered
by the spectral algorithm when the data is skewed in the sense that some items
are highly responded to by users while some items are rarely responded to. To
address this issue, we propose an accelerated spectral algorithm that enjoys
the same error guarantees as the original spectral algorithm but runs
significantly faster in practice and suffers from fewer numerical issues.
Secondly, we discuss regularization strategy when the spectral algorithm is
applied to datasets with sparse observation patterns.

Accelerating the Spectral Algorithm: Recall that in the original spectral
Algorithm 1, we use a common normalization constant $d$ that generally scales
as $O(\max_{i}\sum_{k\neq i}B_{ik})$. In practice, the distribution of the
user-item assignment could be skewed such that some items are rarely responded
to while some elicit many user responses. In such cases, the items with few
responses will have few pairwise differential measurements $\ll d$. The
induced Markov chain will contain large self-loops for these items. We observe
that these large self-loops lead to a slower convergence when computing the
stationary distribution and more numerical issues. This observation was also
noted in [2] and we propose a similar solution to eliminate large self-loops
that is to use a _different normalizing factor for each vertex_. Consider the
following modified Markov chain:

$\bar{P}_{ij}=\begin{cases}\frac{1}{d_{i}}Y_{ij}&\text{if }i\neq j\\\
1-\frac{1}{d_{i}}\sum_{k\neq i}Y_{ik}&\text{if }i=j\end{cases}\quad,$ (5)

where $Y_{ij}$ is defined in Equation (2) and $\\{d_{i}\\}_{i=1}^{m}$ are
appropriately chosen normalization factors such that the resulting transition
probability matrix does not contain any negative entries. In our experiments,
we choose $d_{i}=O(\sum_{k\neq i}B_{ik})$. The accelerated spectral algorithm
computes the stationary distribution of the above modified Markov chain, and
recovers the item parameters via a post-processing step. The algorithm is
summarized in Algorithm 2.

Input:  User-item binary response data $X\in\\{0,1,*\\}^{n\times m}$
Output:  An estimate of the item parameters
$\beta=[\beta_{1},\ldots,\beta_{m}]$

1: Construct a _modified_ Markov chain $\bar{P}$ per Equation (5)

2: Compute the stationary distribution $\bar{\pi}$ of $\bar{P}$

3: Compute $z=D^{-1}\bar{\pi}$ and $\bar{\beta}=\log(z)$ where
$D=\operatorname*{diag}(d_{1},\ldots,d_{m})$

4: Return the normalized item parameters, i.e.,
$\beta=\bar{\beta}-\bar{\beta}^{\top}\mathbf{1}/m$

Algorithm 2 _Accelerated_ Spectral Estimator

Interestingly, the accelerated algorithm produces essentially the same
estimate as the original algorithm. Under some regularity conditions, there is
a direct one-to-one relation between the stationary distribution $\pi$
obtained using the original Markov chain in Algorithm 1 and the stationary
distribution $\bar{\pi}$ of the Markov chain parametrized by $\bar{P}$. This
result is summarized in Theorem 4.1.

######  Theorem 4.1.

Consider the modified Markov chain $\bar{P}$ constructed per Equation (5) and
the original Markov chain $P$ constructed per Equation (3). Suppose that both
$\bar{P}$ and $P$ admit unique stationary distributions $\bar{\pi}$ and $\pi$,
respectively. Then

$\bar{\pi}_{i}=\frac{\pi_{i}d_{i}}{\sum_{k=1}^{m}\pi_{k}d_{k}}\quad\forall
i\in[m]\,,$

where $d_{i}$ are the normalization factors in the construction of the
modified Markov chain $\bar{P}$.

Assuming _perfect numerical precision_ , the two versions of the spectral
algorithm output the same estimates. Therefore the guarantees in Theorems 3.1
and 3.3 also apply to the accelerated spectral algorithm. However, in our
experiments, we observe that the accelerated spectral algorithm converges much
faster and suffers from fewer numerical issues than the original version on
real-life datasets, leading to better performance overall. We thus use the
accelerated version in our experiments.

Regularization for Sparse Datasets: In some real-life datasets, we observe
that certain pairs of items have few pairwise differential measurements.
Furthermore, the pairwise differential data is one-sided (e.g., users who
respond to the two items always respond positively to one but negatively to
the other). This could happen to pairs that have been shown to only few users.
The existence of many such pairs may also introduce numerical issues and
parameters unidentifiability. For example, when there is an item $i$ such that
$Y_{ji}=0\,\forall j\neq i$, the stationary probability correpsonding to this
item will be 0 and the item parameter estimate will be $-\infty$. As a
solution, we propose adding regularization in the construction of the Markov
chain. Specifically, for every pair of items $i,j$ such that $B_{ij}>0$
redefine

$Y_{ij}=\sum_{l=1}^{n}A_{li}A_{lj}X_{li}(1-X_{lj})+\nu\quad,$

where $\nu$ is a small constant. In all of our experiments on real-life
datasets, we use $\nu=1$ and find that the regularization parameter requires
little tuning. Regularization also ensures the uniqueness of the stationary
distribution. So long as the graph underlying the Markov chain is connected,
adding regularization ensures that no pairwise transition probability is 0.
This makes the constructed Markov chain _ergodic_ and there is a unique
stationary distribution [44].

##  5 Experiments

In this section, we present empirical findings which support the practical
value of our spectral algorithm. Our baselines are the most commonly used
estimation algorithms in the literature: conditional maximum likelihood
estimate (CMLE), marginal maximum likelihood estimate (MMLE) and joint maximum
marginal likelihood (JMLE). Their open source implementation can be found
online [49]. We include the python implementation of our spectral algorithm in
the supplementary materials.

Synthetic Data: We generate the item parameters $\beta^{*}$ from a standard
normal distribution and user parameters $\theta^{*}$ from
$\mathcal{N}(0,\sigma^{2})$ where $\sigma^{2}$ varies for different model
settings. Recall that MMLE requires the statistician to specify the prior
distribution over the user parameters and for synthetic experiments, we
specify this prior distribution to be the standard normal distribution.
Subfigures (a)-(c) of Figure 1 show $\lVert\beta-\beta^{*}\rVert_{2}$ against
$n$ for all 4 algorithms under 3 _different model settings_ while Subfigure
(d) shows inference time. When there is no missing data and MMLE’s prior
distribution is correctly specified ($\sigma=1$), CMLE, MMLE and the spectral
algorithm perform equally well. However, when MMLE’s prior distribution is
misspecified ($\sigma=2$), it produces inconsistent estimates. As mentioned
before, JMLE is known to produce inconsistent estimate when $m$ is small
relative to $n$. On the other hand, CMLE’s performance degrades under
moderately sized dataset with missing data. The spectral algorithm, however,
consistently performs well across all of these settings and is comparatively
scalable.

(a) When the number of items is small, JMLE is known to produce inconsistent
estimate.

(b) When the MMLE prior distribution is misspecified, its performance could
degrade.

(c) In larger datasets with missing data, CMLE’s performance could degrade.

(d) The spectral method is comparatively scalable.

Figure 1: _(Synthetic Data Experiments.)_ The spectral method performs
consistently well (both in terms of $\ell_{2}$ error and time complexity)
across a range of settings while CMLE, MMLE and JMLE could underperform in
unfavorable settings. Presented results have been averaged over 100 trials.

Real Data: We perform experiments on a wide range of real-life datasets from
education testing datasets to book and movie ratings datasets for
recommendation systems. In order to transform ratings data to binary response
data, we follow the procedures in previous works [33, 19]. Specifically, for
each user, we convert all ratings higher than the average to 0 and 1 otherwise
(so that items with a higher parameter value is ‘better’). Since real-life
datasets do not come with true $\beta^{*}$ parameters, we compare the
algorithms on four metrics: area under the ROC curve (denoted AUC) on heldout
test data; log-likelihood on heldout test data; inference time and top-$K$
accuracy where the reference top-$K$ set is determined by average ratings. We
have also followed the standard procedure in the recommendation systems
literature to remove items that have few ($\leq 10$) ratings from the
reference top-$K$ set. In our experiments, we consider $K\in\\{10,25,50\\}$.
We defer extra experiment results where we include additional algorithms such
as Bayesian estimation [42] and pairwise likelihood estimation to the
supplementary materials. We mention here a few notable datasets: RIIID [1]
($m=6k,n=23k$, education testing dataset), ML-20M [28] ($m=27k,n=138k$), Book-
Genome [31] ($m=10k,n=350k$).

Table 3 summarizes the performance of the four methods in our experiments.
Note that the first four datasets are education testing datasets and thus
there are no top-$K$ ranking metrics being measured. For tuning the prior
distribution for MMLE, we select the prior distribution that admits the
highest log-likelihood on a validation set. On the other hand, CMLE, JMLE and
the spectral method requires minimal model tuning. For small scale education
datasets (LSAT, UCI, 3GRADES), there are no missing responses and all methods
perform very similarly to one another. For large scale ratings datasets, the
spectral method remains competitive with the baselines in terms of AUC and
log-likelihood but tends to outperforms in top-$K$ accuracy and is
significantly more efficient.

In large scale ratings datasets, we observe that the competitor methods tend
to assign large parameter value to items that receive only a few but very high
ratings (so after data processing, all of the responses to such items are $0$)
and these items are not included in the reference top-$K$ set. The spectral
method, because it operates on pairwise differentials, is less susceptible to
these noisy responses and thus more accurately recovers the items in the
reference top-$K$ set.

| AUC | Log-likelihood | Top-$[10\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}25\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}50]$ accuracy | Total Inference time (seconds)
---|---|---|---|---
Dataset | Spectral | MMLE | CMLE | JMLE | Spectral | MMLE | CMLE | JMLE | Spectral | MMLE | CMLE | JMLE | Spectral | MMLE | CMLE | JMLE
LSAT | $0.707$ | $0.707$ | $0.707$ | $0.707$ | $-0.487$ | $-0.489$ | $-0.487$ | $-0.485$ | N/A | N/A | N/A | N/A | $0.028$ | $0.159$ | $0.154$ | $0.075$
UCI | $0.565$ | $0.565$ | $0.565$ | $0.565$ | $-0.687$ | $-0.686$ | $-0.692$ | $-0.706$ | N/A | N/A | N/A | N/A | $0.015$ | $0.133$ | $0.136$ | $0.034$
3 GRADES | $0.532$ | $0.532$ | $0.532$ | $0.532$ | $-0.706$ | $-0.692$ | $-0.699$ | $-0.717$ | N/A | N/A | N/A | N/A | $0.021$ | $0.181$ | $0.105$ | $0.009$
RIIID | $0.723$ | $0.724$ | N/A | $0.724$ | $-0.486$ | $-0.49$ | N/A | $-0.486$ | N/A | N/A | N/A | N/A | $13.1$ | $104$ | N/A | $61.2$
HETREC | $0.729$ | $0.729$ | $0.506$ | $0.73$ | $-0.604$ | $-0.603$ | $-1.119$ | $-0.602$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $50.1$ | $140$ | $224\text{k}$ | $144$
ML-100K | $0.662$ | $0.659$ | $0.498$ | $0.665$ | $-0.646$ | $-0.66$ | $-1.159$ | $-0.653$ | $0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.54$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $1.39$ | $16.2$ | $9.56\text{k}$ | $21$
ML-1M | $0.698$ | $0.701$ | $0.468$ | $0.7$ | $-0.626$ | $-0.632$ | $-1.166$ | $-0.63$ | $0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72$ | $0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.62$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.66$ | $19.2$ | $86.9$ | $156\text{k}$ | $194$
EACH MOVIE | $0.716$ | $0.718$ | $0.522$ | $0.716$ | $-0.615$ | $-0.613$ | $-0.946$ | $-0.614$ | $0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.76\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.82$ | $0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.68\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.84$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72$ | $11.3$ | $329$ | $220\text{k}$ | $1.9\text{k}$
ML-10M | $0.714$ | $0.716$ | N/A | $0.716$ | $-0.617$ | $-0.619$ | N/A | $-0.618$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.84\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.7$ | $0.1\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.28\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.32$ | N/A | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.32\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.36$ | $821$ | $3.93\text{k}$ | N/A | $6.55\text{k}$
ML-20M | $0.72$ | $0.71$ | N/A | $0.71$ | $-0.619$ | $-0.619$ | N/A | $-0.619$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.44\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.4$ | N/A | $0.1\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.4$ | $1.58\text{k}$ | $5.36\text{k}$ | N/A | $4.42\text{k}$
BX | $0.546$ | $0.577$ | $0.503$ | $0.57$ | $-0.618$ | $-0.612$ | $-0.8$ | $-0.617$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.16\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.16$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.24\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.2$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.2\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.18$ | $205$ | $2.02\text{k}$ | $156\text{k}$ | $481$
BOOK-GENOME | $0.658$ | $0.665$ | N/A | $0.654$ | $-0.651$ | $-0.645$ | N/A | $-0.651$ | $0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.44\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.42$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.32\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.34$ | N/A | $0.2\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.24\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.38$ | $2.53\text{k}$ | $2.56\text{k}$ | N/A | $4.34\text{k}$

Table 1: _(Real Data Experiments.)_ The spectral method (1st column under each
metric) is competitive with the baselines (best results are shaded) especially
in terms of ranking metrics 333As noted before, CMLE has been observed to
underperform on large datasets with missing data. In some of our experiments,
CMLE fails due to numerical errors or does not converge. The results for CMLE
are marked ‘N/A’ for these experiments.. The spectral method is generally the
fastest method on large datasets. It _works off-the-shelf with minimal tuning_
and is _comparatively accurate_.

##  6 Related Works

The Rasch modeling literature is quite broad and we refer the interested
reader to recent surveys [6, 46]. Since its original formulation to model
psychological tests outcome [45], the model has been extended to account for
more complicated response patterns such as numerical ratings and ordinal
responses [4, 5, 55, 39]. Higher-order models that incorporates bias variables
such as the 2PL and 3PL model [9] and multivariate models [21] remain active
areas of research where machine learning techniques have recently been applied
with substantial success [8]. The Rasch inference problem is also closely
connected to the 1-bit matrix completion problem in machine learning where we
observe a sparse $n\times m$ binary matrix with underlying entrywise
probability $f(M)$ where $f$ is a mapping function (e.g., logistic) and $M$ is
a real-valued matrix. There, the goal is obtain an estimate of $M$. A commonly
proposed approaches for 1-bit matrix completion based on alternating
optimization is exactly joint maximum likelihood estimate [15, 14].

##  7 Ethical Considerations

Our work proposes an algorithm of which real-life applications very often
involve actual human data with sensitive information. For example, the Rasch
model is often studied in the context of education testing and psychological
testing where the subjects of studies are students and patients. Therefore,
deploying our algorithm (or any algorithms in this context) needs to be
accompanied by thoughtful and thorough ethical considerations. In this work,
we provide the algorithmic tool that lays the foundation for our algorithm and
its theoretical guarantee. We believe that a socially constructive application
of our algorithm should always be accompanied by detailed explanation of its
fundamental limitations, assumptions and decision makers need to take into
account these aspects when interpreting the results returned by the algorithm.

##  8 Conclusion

We propose a new spectral algorithm for the item estimation problem under the
celebrated Rasch model. Our algorithm is theoretically well-founded,
practically performant and should be added to the statistician’s quiver of
estimation methods when analyzing binary response data. Extending our
algorithm to more expressive IRT models such as 2PL or 3PL and response types
is an open avenue. In the future, we also hope to generalize the method to
more complicated response data types such as ordinal or rating data, as well
as incorporating ancillary information (user and item features).

##  9 Acknowledgement

The authors would like to thank William Zhang for proofreading and leaving
helpful comments on earlier drafts of this paper. We would also like to thank
the anonymous reviewers for their thoughtful suggestions that have been
incorporated to improve this paper. D.N. and A.Z. are supported by NSF Grant
DMS-2112988. A.Z. acknowledges financial support from the Alfred H. Williams
Faculty Scholar award. Any opinions expressed in this paper are those of the
author and do not necessarily reflect the views of the National Science
Foundation.

## References

  * [1] Riiid answer correctness prediction.  https://www.kaggle.com/c/riiid-test-answer-prediction/.  Accessed: 2022-05-11.
  * [2] Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal.  Accelerated spectral ranking.  In International Conference on Machine Learning, pages 70–79. PMLR, 2018.
  * [3] Erling B Andersen.  Conditional inference for multiple-choice questionnaires.  British Journal of Mathematical and Statistical Psychology, 26(1):31–44, 1973.
  * [4] Erling B Andersen.  Sufficient statistics and latent trait models.  Psychometrika, 42(1):69–81, 1977.
  * [5] David Andrich.  A rating formulation for ordered response categories.  Psychometrika, 43(4):561–573, 1978.
  * [6] Vahid Aryadoust, Li Ying Ng, and Hiroki Sayama.  A comprehensive review of rasch measurement in language assessment: Recommendations and guidelines for research.  Language Testing, 38(1):6–40, 2021.
  * [7] Debabrata Basu.  On the elimination of nuisance parameters.  In Selected Works of Debabrata Basu, pages 279–290. Springer, 2011\.
  * [8] Yoav Bergner, Stefan Droschler, Gerd Kortemeyer, Saif Rayyan, Daniel Seaton, and David E Pritchard.  Model-based collaborative filtering analysis of student response data: Machine-learning item response theory.  International Educational Data Mining Society, 2012.
  * [9] A Lord Birnbaum.  Some latent trait models and their use in inferring an examinee’s ability.  Statistical theories of mental test scores, 1968.
  * [10] Justyna Brzezińska et al.  Latent variable modelling and item response theory analyses in marketing research.  Folia Oeconomica Stetinensia, 16(2):163–174, 2016.
  * [11] Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik.  2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011).  In Proceedings of the 5th ACM conference on Recommender systems, RecSys 2011, New York, NY, USA, 2011. ACM.
  * [12] Chih-Ming Chen, Hahn-Ming Lee, and Ya-Hui Chen.  Personalized e-learning system using item response theory.  Computers & Education, 44(3):237–255, 2005.
  * [13] Pinhan Chen, Chao Gao, and Anderson Y Zhang.  Partial recovery for top-$k$ ranking: Optimality of mle and sub-optimality of spectral method.  arXiv preprint arXiv:2006.16485, 2020.
  * [14] Yunxiao Chen, Chengcheng Li, and Gongjun Xu.  A note on statistical inference for noisy incomplete 1-bit matrix.  arXiv preprint arXiv:2105.01769, 2021.
  * [15] Yunxiao Chen, Xiaoou Li, and Siliang Zhang.  Joint maximum likelihood estimation for high-dimensional exploratory item factor analysis.  Psychometrika, 84(1):124–146, 2019.
  * [16] Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang.  Spectral method and regularized mle are both optimal for top-k ranking.  Annals of statistics, 47(4):2204, 2019.
  * [17] Bruce Choppin.  A fully conditional estimation procedure for rasch model parameters.  1982\.
  * [18] Paulo Cortez and Alice Maria Gonçalves Silva.  Using data mining to predict secondary school student performance.  2008\.
  * [19] Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters.  1-bit matrix completion.  Information and Inference: A Journal of the IMA, 3(3):189–223, 2014\.
  * [20] Persi Diaconis and Laurent Saloff-Coste.  Comparison theorems for reversible markov chains.  The Annals of Applied Probability, 3(3):696–730, 1993.
  * [21] Susan Embretson.  A general latent trait model for response processes.  Psychometrika, 49(2):175–186, 1984.
  * [22] Gerhard H Fischer.  On the existence and uniqueness of maximum-likelihood estimates in the rasch model.  Psychometrika, 46(1):59–77, 1981.
  * [23] Mary Garner Jr.  An eigenvector method for estimating item parameters of the dichotomous and polytomous rasch models.  Journal of Applied Measurement, 3(2):107–128, 2002.
  * [24] Malay Ghosh.  Inconsistent maximum likelihood estimators for the rasch model.  Statistics & Probability Letters, 23(2):165–170, 1995.
  * [25] Shelby J Haberman.  Maximum likelihood estimates in exponential response models.  The annals of statistics, 5(5):815–841, 1977.
  * [26] Shelby J Haberman.  Joint and conditional maximum likelihood estimation for the rasch model for binary responses.  ETS Research Report Series, 2004(1):i–63, 2004.
  * [27] Ronald K Hambleton, Hariharan Swaminathan, and H Jane Rogers.  Fundamentals of item response theory, volume 2.  Sage, 1991.
  * [28] F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  Acm transactions on interactive intelligent systems (tiis), 5(4):1–19, 2015.
  * [29] David R Hunter and Kenneth Lange.  A tutorial on mm algorithms.  The American Statistician, 58(1):30–37, 2004.
  * [30] Sadiq Hussain, Neama Abdulaziz Dahan, Fadl Mutaher Ba-Alwib, and Najoua Ribata.  Educational data mining and analysis of students’ academic performance using weka.  Indonesian Journal of Electrical Engineering and Computer Science, 9(2):447–459, 2018.
  * [31] Denis Kotkov, Alan Medlar, Alexandr Maslov, Umesh Raj Satyal, Mats Neovius, and Dorota Glowacka.  The tag genome dataset for books.  In Proceedings of the 2022 ACM SIGIR Conference on Human Information Interaction and Retrieval (CHIIR’22), volume 5, 2022.
  * [32] John P Lalor, Hao Wu, and Hong Yu.  Learning latent parameters without human response patterns: Item response theory with artificial crowds.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, 2019.
  * [33] Andrew Lan, Mung Chiang, and Christoph Studer.  An estimation and analysis framework for the rasch model.  In International Conference on Machine Learning, pages 2883–2891. PMLR, 2018.
  * [34] Erich L Lehmann and George Casella.  Theory of point estimation.  Springer Science & Business Media, 2006.
  * [35] John Michael Linacre.  Conditional maximum likelihood estimation.
  * [36] John Michael Linacre.  Estimation methods: Jmle, prox, wmle, cmle, pmle, amle.
  * [37] Frederic M Lord.  Applications of item response theory to practical testing problems.  Routledge, 2012.
  * [38] R Duncan Luce.  Individual choice behavior: A theoretical analysis.  Courier Corporation, 2012.
  * [39] Geoff N Masters.  A rasch model for partial credit scoring.  Psychometrika, 47(2):149–174, 1982.
  * [40] Lucas Maystre.  Choix: Inference algorithms for models based on luce’s choice axiom.  https://github.com/lucasmaystre/choix, 2015.
  * [41] Roderick P McDonald.  Test theory: A unified treatment.  psychology press, 2013.
  * [42] Prathiba Natesan, Ratna Nandakumar, Tom Minka, and Jonathan D Rubright.  Bayesian prior choice in irt estimation using mcmc and variational bayes.  Frontiers in psychology, 7:1422, 2016.
  * [43] Sahand Negahban, Sewoong Oh, and Devavrat Shah.  Rank centrality: Ranking from pairwise comparisons.  Operations Research, 65(1):266–287, 2017.
  * [44] James R Norris and James Robert Norris.  Markov chains.  Number 2. Cambridge university press, 1998.
  * [45] Georg Rasch.  Studies in mathematical psychology: I. probabilistic models for some intelligence and attainment tests.  1960\.
  * [46] Alexander Robitzsch.  A comprehensive simulation study of estimation methods for the rasch model.  Stats, 4(4):814–836, 2021.
  * [47] Pedro Rodriguez, Joe Barrow, Alexander Miserlis Hoyle, John P Lalor, Robin Jia, and Jordan Boyd-Graber.  Evaluation examples are not equally informative: How should that change nlp leaderboards?  In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4486–4503, 2021.
  * [48] Roseanna W Saaty.  The analytic hierarchy process—what it is and how it is used.  Mathematical modelling, 9(3-5):161–176, 1987.
  * [49] Ryan Sanchez.  GIRTH: G. Item Response Theory , 11 2021.
  * [50] Carolin Schellhorn and Rajneesh Sharma.  Using the rasch model to rank firms by managerial ability.  Managerial Finance, 2013.
  * [51] Wim J Van der Linden and RK Hambleton.  Handbook of item response theory.  Taylor & Francis Group. Citado na pág, 1(7):8, 1997.
  * [52] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [53] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  Nature Methods, 17:261–272, 2020.
  * [54] Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo.  Whose vote should count more: Optimal integration of labels from labelers of unknown expertise.  Advances in neural information processing systems, 22, 2009.
  * [55] Benjamin D Wright and Geofferey N Masters.  Rating scale analysis.  MESA press, 1982.
  * [56] Cai-Nicolas Ziegler, Sean M McNee, Joseph A Konstan, and Georg Lausen.  Improving recommendation lists through topic diversification.  In Proceedings of the 14th international conference on World Wide Web, pages 22–32, 2005.
  * [57] Aeilko H Zwinderman.  Pairwise parameter estimation in rasch models.  Applied Psychological Measurement, 19(4):369–375, 1995.

##  Appendix A Proofs of Upper Bounds

Proofs overview: The starting point for our proof is a Markov chain eigen-
perturbation bound- Lemma A.3. Without going too deeply into the details and
definitions, we have

$\lVert\pi-\pi^{*}\rVert_{2}\leq\frac{\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}}{\mu^{*}(P^{*})-\lVert
P-P^{*}\rVert_{2}}\,,$

where $\mu^{*}(P^{*})$ is the spectral gap of the idealized Markov chain. We
then bound the numerator and the denominator separately. We will show (see
Corollary A.8):

$\mu^{*}(P^{*})-\lVert P-P^{*}\rVert_{2}\gtrsim\frac{1}{d}\,,$

where $\gtrsim$ denotes $\Omega$-asymptotic relation. For the regime where $m$
is a constant or grows very slowly with respect to $n$, we show (see Lemma
A.9) that

$\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}\lesssim\frac{\sqrt{\max\\{m,\log
np^{2}\\}}}{dm\sqrt{np^{2}}}\,,$

where $\lesssim$ denote $O$-asymptotic relation. For the regime where $m$
grows ($mp\gtrsim\log n$), we show (see Lemma A.11) that

$\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}\lesssim\frac{1}{d\sqrt{mnp}}\,.$

Lastly, we will show that

$\lVert\beta-\beta^{*}\rVert_{2}\lesssim m\cdot\lVert\pi-\pi^{*}\rVert_{2}\,.$

###  A.1 Preliminaries

As a convenient shorthand notation, define $w^{*}_{i}=e^{\beta^{*}_{i}}$ for
$i\in[m]$. Since $\kappa:=\beta_{\max}-\beta_{\min}$,
$w^{*}_{\max}/w^{*}_{\min}=e^{\kappa}$. Let
$\gamma=\min_{l\in[n],i,j\in[m]}\mathbb{E}[X_{li}(1-X_{lj})]$.

Define $B=A^{\top}A$ and the following events:

$\mathcal{A}=\\{\frac{np^{2}}{2}\leq B_{ij}\leq\frac{3np^{2}}{2}\,\forall
i\neq j\in[m]\\}\,,$ $\mathcal{A}^{+}=\mathcal{A}\cap\\{\frac{mp}{2}\leq
A_{l}^{\top}\mathbf{1}\leq\frac{3mp}{2}\,\forall l\in[n]\\}\,.$

Both events happen with high probability under appropriate conditions, as
summarized by two lemmas below.

######  Lemma A.1.

Consider the random sampling scheme described in Section 3.1, we have

$\mathbb{P}(\mathcal{A})\geq 1-\mathrm{exp}\left(-\frac{np^{2}}{20}\right)$

so long as $np^{2}\geq C_{1}\log m$ by a sufficiently large constant $C_{1}$
(e.g., $C_{1}\geq 60$).

###### Proof.

Invoking Chernoff bound, we have:

$\displaystyle\mathbb{P}(\lvert\sum_{l=1}^{n}A_{li}A_{lj}-\mathbb{E}[A_{li}A_{lj}]\rvert>\frac{1}{2}np^{2})\leq
2\mathrm{exp}\left(-\frac{\frac{1}{4}np^{2}}{\frac{1}{2}+2}\right)=\mathrm{exp}\left(-\frac{np^{2}}{10}+\ln
2\right)\,.$

It can be checked that so long as $np^{2}\geq 60\ln m\geq 20\ln 2+40\ln m$ for
$m\geq 2$, then $\mathrm{exp}\left(-\frac{np^{2}}{10}+\ln
2\right)\leq\mathrm{exp}\left(-\frac{np^{2}}{20}-2\ln m\right)$. The rest of
the proof follows by applying union bound over all pairs $i\neq j$.

######  Lemma A.2.

Consider the random sampling scheme described in Section 3.1), we have

$\mathbb{P}(\mathcal{A}^{+})\geq
1-\mathrm{exp}\left(-\frac{np^{2}}{20}\right)-\frac{1}{n^{9}}$

so long as $np^{2}\geq C_{1}\log m$ and $mp\geq C_{1}\log n$ by a sufficiently
large constant $C_{1}$ (e.g., $C_{1}>101$).

###### Proof.

The first term $\mathrm{exp}\left(-\frac{np^{2}}{20}\right)$ is obtained using
the same argument as in the lemma above. For the second term
$\frac{1}{m^{9}}$, we again invoke Chernoff bound:

$\displaystyle\mathbb{P}(\lvert\sum_{l=1}^{n}A_{li}A_{lj}-\mathbb{E}[A_{li}A_{lj}]\rvert>\frac{1}{2}mp)\leq
2\mathrm{exp}\left(-\frac{\frac{1}{4}mp}{\frac{1}{2}+2}\right)=\mathrm{exp}\left(-\frac{mp}{10}+\ln
2\right)\,.$

So long as $mp\geq 100\log n$, one could see that
$\mathrm{exp}\left(-\frac{mp}{10}+\ln 2\right)\leq\frac{1}{n^{10}}$. Applying
union bound over all users $n$ gives us the probability bound.

Under either event $\mathcal{A}$ (or $\mathcal{A}^{+}$) happening, one can
simply set $d=\frac{3mnp^{2}}{2}$. We state without proof the following useful
identities:

$w^{*}_{\min}\geq\frac{\sum_{i=1}^{m}w^{*}_{i}}{me^{\kappa}}\,\quad\text{and}\quad\pi^{*}_{\min}\geq\frac{\sum_{i=1}^{m}\pi^{*}_{i}}{me^{\kappa}}=\frac{1}{me^{\kappa}}\,.$
$w^{*}_{\max}\leq\frac{e^{\kappa}\sum_{i=1}^{m}w^{*}_{i}}{m}\,\quad\text{and}\quad\pi^{*}_{\max}\leq\frac{e^{\kappa}\sum_{i=1}^{m}\pi^{*}_{i}}{m}=\frac{e^{\kappa}}{m}\,.$

Reversibility of the idealized Markov chain: Note that the eigenperturbation
bound in Lemma A.3 requires that the reference Markov chain $P^{*}$ is
reversible. Fortunately for us, this is indeed the case.

######  Proposition 2.1.

For a fixed assignment $A$, consider the following idealized the Markov chain:

$P^{*}_{ij}=\begin{cases}\frac{1}{d}\sum_{l=1}^{n}A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]&\text{for
}i\neq j\\\ 1-\frac{1}{d}\sum_{k\neq i}P^{*}_{ik}&\text{for
}i=j\end{cases}\quad,$

where $d$ is some sufficiently large normalization constant. Then the Markov
chain is reversible and its stationary distribution satisfies
$\pi^{*}_{i}=w_{i}^{*}/(\sum_{k}w_{k}^{*})$ for $i\in[m]$.

###### Proof.

This boils down to verifying the reversility condition, i.e., whether
$\pi_{i}^{*}P_{ij}^{*}=\pi_{j}^{*}P_{ji}^{*}$. One can see that

$\displaystyle\pi_{i}^{*}P^{*}_{ij}$
$\displaystyle=w_{i}^{*}\cdot\frac{1}{\sum_{k\in[m]}w_{k}^{*}}\cdot\sum_{l\in[m]}A_{li}A_{lj}\frac{e^{\theta^{*}_{l}}}{e^{\theta^{*}_{l}}+w^{*}_{i}}\cdot\frac{w_{j}^{*}}{e^{\theta^{*}_{l}}+w_{j}^{*}}$
$\displaystyle=w_{j}^{*}\cdot\frac{1}{\sum_{k\in[m]}w_{k}^{*}}\cdot\sum_{l\in[m]}A_{li}A_{lj}\frac{e^{\theta^{*}_{l}}}{e^{\theta^{*}_{l}}+w^{*}_{j}}\cdot\frac{w_{i}^{*}}{e^{\theta^{*}_{l}}+w_{i}^{*}}$
$\displaystyle=\pi_{j}^{*}P^{*}_{ji}\,.$

This completes the proof.

$\ell_{2}$ eigen-perturbation bound: The reader might recognize the similarity
between the following perturbation bound to Theorem 8 of [16]. Our lemma has
been modified to use the $\ell_{2}$ norm instead of the induced norm in the
original theorem.

######  Lemma A.3.

Consider two discrete time Markov chains $P$ and $P^{*}$ with a finite state
space and stationary distributions $\pi$ and $\pi^{*}$, respectively.
Furthermore, assume that the Markov chain $P^{*}$ is reversible. If $\lVert
P-P^{*}\rVert_{2}\leq\mu^{*}(P^{*})$ where $\mu^{*}(P^{*})$ is the spectral
gap of $P^{*}$, then

$\lVert\pi-\pi^{*}\rVert_{2}\leq\frac{\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}}{\mu^{*}(P^{*})-\lVert
P-P^{*}\rVert_{2}}\,.$

###### Proof.

We have:

$\displaystyle{\pi^{*}}^{\top}-\pi^{\top}$
$\displaystyle={\pi^{*}}^{\top}P^{*}-\pi^{\top}P$
$\displaystyle={\pi^{*}}^{\top}(P^{*}-P+P)-\pi^{\top}P$
$\displaystyle={\pi^{*}}^{\top}(P^{*}-P)+{\pi^{*}}^{\top}P-\pi^{\top}P$
$\displaystyle={\pi^{*}}^{\top}(P^{*}-P)+{(\pi^{*}-\pi)}^{\top}P$
$\displaystyle={\pi^{*}}^{\top}(P^{*}-P)+{(\pi^{*}-\pi)}^{\top}(P-P^{*}+P^{*})$
$\displaystyle={\pi^{*}}^{\top}(P^{*}-P)+{(\pi^{*}-\pi)}^{\top}(P-P^{*})+({\pi^{*}-\pi})^{\top}P^{*}$
$\displaystyle={\pi^{*}}^{\top}(P^{*}-P)+{(\pi^{*}-\pi)}^{\top}(P-P^{*})+({\pi^{*}-\pi})^{\top}(P^{*}-\mathbf{1}{\pi^{*}}^{\top})\,.$

The last equality comes from the simple observation that
$(\pi^{*}-\pi)^{\top}\mathbf{1}=0$. We thus obtain the following normed
inequality:

$\lVert\pi-\pi^{*}\rVert_{2}\leq\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}+\lVert{\pi^{*}-\pi}\lVert_{2}\cdot\rVert
P-P^{*}\rVert_{2}+\lVert{\pi^{*}-\pi}\rVert_{2}\cdot\rVert
P^{*}-\mathbf{1}{\pi^{*}}^{\top}\rVert_{2}\,.$

If we can show $1-\rVert P^{*}-\mathbf{1}{\pi^{*}}^{\top}\rVert_{2}$ is
exactly the spectral gap of the reversible Markov chain $P^{*}$, then the
final inequality is readily obtained after a simple rearrangment. We devote
the rest of the proof towards this.

Because $P^{*}$ is reversible, i.e.,
$\pi^{*}_{i}P^{*}_{ij}=\pi_{j}^{*}P_{ji}^{*}$, it can be checked that the
matrix $\Lambda^{1/2}P^{*}\Lambda^{-1/2}$ is symmetric and so is
$\Lambda^{1/2}\mathbf{1}{\pi^{*}}^{\top}\Lambda^{-1/2}$. Because there is a
similarity transformation between $P^{*}-\mathbf{1}{\pi^{*}}^{\top}$ and
$\Lambda^{1/2}(P^{*}-\mathbf{1}{\pi^{*}}^{\top})\Lambda^{-1/2}$, it suffices
to analyze the spectrum of the later symmetric matrix. Let
$v=[\sqrt{\pi}_{1},\ldots,\sqrt{\pi}_{m}]$ (it has unit length). It can be
checked that

  1. 1.

$v^{\top}\Lambda^{1/2}P^{*}\Lambda^{-1/2}=\pi^{\top}P^{*}\Lambda^{-1/2}=v^{\top}$.
Essentially, $v$ is a eigenvector associated with eigenvalue 1.

  2. 2.

$\Lambda^{1/2}\mathbf{1}{\pi^{*}}^{\top}\Lambda^{-1/2}=1vv^{\top}$.

These two observations and the elementary fact that a Markov chain has leading
eigenvalue 1 readily imply that $1-\lVert
P^{*}-\mathbf{1}{\pi^{*}}^{\top}\rVert_{2}$ is exactly the spectral gap of
$P^{*}$.

###  A.2 Bounding the spectral gap

Towards bounding the denominator of the eigen-perturbation bound, we will
firsrt lower bound the spectral gap of the idealized Markov chain $P^{*}$. We
first state the following useful comparison lemma that has been presented as
Lemma 2 of [43] and is originally due to [20].

######  Lemma A.4.

Consider two reversible Markov chains $P^{*},Q$ with stationary distribution
$\pi^{*},\pi$, respectively that are defined on the same graph $G(V,E)$ of $m$
states. That is, $P^{*}_{ij}=0$ and $Q_{ij}=0$ if $i,j\notin E$. Define
$\alpha=\min_{i,j\in E}\frac{\pi^{*}_{i}P{ij}^{*}}{\pi_{i}Q_{ij}}$ and
$\beta=\max_{i}\frac{\pi_{i}^{*}}{\pi_{i}}$. We have

$\frac{\mu^{*}(P^{*})}{\mu^{*}(Q)}\geq\frac{\alpha}{\beta}\,,$

where $\mu^{*}(.)$ is the spectral gap operator.

Note that the comparison lemma lower bounds the spectral gap of a reversible
Markov chain in terms of another reversible Markov chain. Considera Markov
chain whose pairwise transition probabilties are defined as follows:

$Q_{ij}=\begin{cases}\frac{B_{ij}}{d}&\text{for }i\neq j\\\
1-\frac{1}{d}\sum_{k\neq i}B_{ik}&\text{for }i=j\end{cases}$ (6)

where $d$ is the same normalization constant as in the idealized Markov chain
described in Lemma 2.1. By design, this is a random walk whose stationary
distribution is the uniform distribution, $\pi_{i}=\frac{1}{m}$.

######  Lemma A.5.

Conditioned on event $\mathcal{A}$,

$\mu^{*}(Q)\geq\frac{1}{3}\,.$

###### Proof.

Let $\lambda_{\max,\perp\\!\\!\\!\perp}(Q)$ denote the second largest
eigenvalue of $Q$ and $D=\operatorname*{diag}(\mathbf{1}/d)$. We have:

$\displaystyle Q$
$\displaystyle=I-D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})+D^{-1}B$
$\displaystyle\Rightarrow\lambda_{\max,\perp\\!\\!\\!\perp}(Q)$
$\displaystyle=\lambda_{\max,\perp\\!\\!\\!\perp}(I-D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})+D^{-1}B)$
$\displaystyle=\lambda_{\max,\perp\\!\\!\\!\perp}(I-\underbrace{\big{[}D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})-D^{-1}B\big{]}}_{Laplacian})$
$\displaystyle=1-\lambda_{\min,\perp\\!\\!\\!\perp}(D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})-D^{-1}B)$
$\displaystyle\Rightarrow 1-\lambda_{\max,\perp\\!\\!\\!\perp}(Q)$
$\displaystyle=\lambda_{\min,\perp\\!\\!\\!\perp}(D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})-D^{-1}B)$

In these derivation steps, we have made use of the fundamental property of the
Laplacian of a weighted graph: it has an eigenvalue 0 corresponding to the
eigenvector proportional to $\mathbf{1}_{m}$. We now need to lower bound
$\lambda_{\min,\perp\\!\\!\\!\perp}(D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})-D^{-1}B)$.
Conditioned on event $\mathcal{A}$:

$\displaystyle\lambda_{\min,\perp\\!\\!\\!\perp}(D^{-1}\operatorname*{diag}(B^{\top}\mathbf{1})-D^{-1}B)$
$\displaystyle=\frac{1}{d}\cdot\lambda_{\min,\perp\\!\\!\\!\perp}(B^{\top}\mathbf{1}-B)$
$\displaystyle=\frac{1}{d}\cdot\min_{u\perp\\!\\!\\!\perp\mathbf{1},\lVert
u\rVert_{2}=1}\sum_{ij}(u_{i}-u_{j})^{2}B_{ij}$
$\displaystyle\geq\frac{1}{d}\cdot\frac{1}{2}np^{2}\cdot\min_{u\perp\\!\\!\\!\perp\mathbf{1}_{m},\lVert
u\rVert_{2}=1}\sum_{ij}(u_{i}-u_{j})^{2}$
$\displaystyle\geq\frac{1}{d}\cdot\frac{1}{2}np^{2}\cdot\min_{u\perp\\!\\!\\!\perp\mathbf{1}_{m},\lVert
u\rVert_{2}=1}\,u^{\top}\big{[}m\,I_{m}-\mathbf{1}_{m}\mathbf{1}_{m}^{\top}\big{]}u=\frac{1}{2d}mnp^{2}\,.$

Substituting $d=\frac{3}{2}mnp^{2}$ completes the proof.

######  Lemma A.6.

Conditioned on event $\mathcal{A}$,

$\mu(P^{*})\geq\frac{\gamma}{3e^{2\kappa}}\,,$

where $\gamma=\min_{l\in[n],i,j\in[m]}\mathbb{E}[X_{li}(1-X_{lj})]$.

###### Proof.

To prove the above lower bound, we will combine Lemmas A.4, the definition of
the reference Markov chain $Q$ in Equation (6) with a lower bound on $\alpha$
and an upper bound on $\beta$. We have the following lower bound on $\alpha$:

$\displaystyle\alpha$
$\displaystyle=\min_{i,j}\frac{\pi^{*}_{i}P^{*}_{ij}}{\pi_{i}Q_{ij}}$
$\displaystyle=\min_{i,j}\frac{\pi^{*}_{i}P^{*}_{ij}}{\frac{1}{m}\cdot\frac{1}{d}\sum_{l=1}^{n}A_{li}A_{lj}}=\min_{i,j}\frac{\pi^{*}_{i}\frac{1}{d}\sum_{l=1}^{n}A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]}{\frac{1}{m}\cdot\frac{1}{d}\sum_{l=1}^{n}A_{li}A_{lj}}$
$\displaystyle=\min_{i,j}\frac{\pi^{*}_{i}\sum_{l=1}^{n}A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]}{\frac{1}{m}\cdot\sum_{l=1}^{n}A_{li}A_{lj}}\geq\min_{i,j}\frac{\pi^{*}_{\min}\gamma
B_{ij}}{\frac{1}{m}\cdot B_{ij}}=\frac{\pi^{*}_{\min}\gamma}{\frac{1}{m}}$
$\displaystyle\geq\frac{\gamma}{e^{\kappa}}\,.$

The last inequality follows from $\pi^{*}_{\min}\geq\frac{1}{me^{\kappa}}$
(stated earlier). On the other hand, we have the following upper bound on
$\beta$:

$\displaystyle\beta$
$\displaystyle=\max_{i}\frac{\pi_{i}^{*}}{\pi_{i}}=\max_{i}\frac{w_{i}^{*}d}{\frac{1}{m}\sum_{k=1}^{m}w_{k}^{*}d}$
$\displaystyle\leq\frac{1}{\frac{1}{m}}\cdot\frac{e^{\kappa}}{m}\leq
e^{\kappa}\,.$

Combining the lower bound above with the upper bound on $\alpha$ obtained
earlier, we have

$\mu^{*}(P)\geq\frac{\gamma}{e^{2\kappa}}\cdot\mu^{*}(Q)\,.$

The rest of the proof follows from the conclusion of Lemma A.5.

###  A.3 Bounding the matrix error term $\lVert P-P^{*}\rVert_{2}$

######  Lemma A.7.

Suppose event $\mathcal{A}$ holds. Fix a small constant $\epsilon<1$. Suppose
further that $np^{2}\geq\frac{C_{2}\log m}{\gamma^{2}\epsilon^{2}}$ for a
sufficiently large constant $C_{2}$ (e.g., $C_{2}\geq 30$). Then

$\lVert P-P^{*}\rVert_{2}\leq 2\epsilon\gamma$

with probability at least
$1-\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}np^{2}}{10}\right)$ over the
random responses of the users where $\gamma=\min_{l\in[n],i\neq
j\in[m]}\mathbb{E}[X_{li}(1-X_{lj})]$.

###### Proof.

Fix a pair $i,j$, let
$\mu=\frac{1}{n}\sum_{l=1}^{n}A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]$ (note
that $\mu\leq 1$). Applying Chernoff’s bound gives us

$\displaystyle\mathbb{P}(\lvert\sum_{l=1}^{n}A_{li}A_{lj}X_{li}(1-X_{lj})-A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]\rvert>\epsilon\gamma
B_{ij}\,\lvert\,\mathcal{A})$
$\displaystyle=\mathbb{P}(\lvert\sum_{l=1}^{n}A_{li}A_{lj}X_{li}(1-X_{lj})-A_{li}A_{lj}\mathbb{E}[X_{li}(1-X_{lj})]\rvert>\frac{\epsilon\gamma}{\mu}\cdot\mu
B_{ij}\,\lvert\,\mathcal{A})$ $\displaystyle\leq
2\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}/\mu^{2}\cdot\mu
B_{ij}}{\frac{1}{2}+2}\right)$ $\displaystyle\leq
2\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}\cdot\frac{np^{2}}{2}}{\frac{1}{2}+2}\right)$
$\displaystyle=\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}np^{2}}{5}+\ln
2\right)\,.$

One can see that so long as $np^{2}\geq\frac{30\ln m}{\gamma^{2}\epsilon^{2}}$
(and noting that $30\ln m\geq 20\ln m+20\ln 2\,\forall m\geq 2$) then
$\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}np^{2}}{5}+\ln
2\right)=\mathrm{exp}\left(-2\cdot\frac{\gamma^{2}\epsilon^{2}np^{2}}{10}+\ln
2\right)\leq\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}np^{2}}{10}-2\ln
m\right)$. Applying union bound over all pairs $i\neq j$, we have with
probability at least
$1-\mathrm{exp}\left(-\frac{\gamma^{2}\epsilon^{2}np^{2}}{10}\right)$, $\lvert
P_{ij}-P^{*}_{ij}\rvert\leq\frac{1}{d}\gamma\epsilon
B_{ij}\leq\frac{3\gamma\epsilon np^{2}}{2d}$ for all pairs $i\neq j$. We then
have

$\displaystyle\lVert P-P^{*}\rVert_{2}$
$\displaystyle\leq\lVert\operatorname*{diag}(P)I-\operatorname*{diag}(P^{*})I\rVert_{2}+\lVert[P-P^{*}]_{i\neq
j}\rVert_{2}$ $\displaystyle\leq\max_{i}\lvert
P_{ii}-P_{ii}\rvert+\max_{u,v:\lVert u\rVert=\lVert v\rVert=1}\sum_{i\neq
j}u_{i}(P_{ij}-P_{ij}^{*})v_{j}$ $\displaystyle\leq\max_{i}\lvert\sum_{j\neq
i}P_{ij}-P_{ij}^{*}\rvert+\max_{i\neq j}\lvert
P_{ij}-P^{*}_{ij}\rvert\cdot\sum_{i\neq j}\lvert u_{i}\rvert\lvert
v_{j}\rvert$ $\displaystyle\leq 2m\cdot\max_{i\neq j}\lvert
P_{ij}-P_{ij}^{*}\rvert$ $\displaystyle\leq\frac{3\epsilon\gamma
mnp^{2}}{d}=2\epsilon\gamma\,.$

The conclusion follows from $d=\frac{3mnp^{2}}{2}$.

Before moving on to bounding the projected error term, we first note that the
eigen-perturbation bound in Lemma A.3 holds when $\mu^{*}(P^{*})\geq\lVert
P-P^{*}\rVert_{2}$. We solve for $\epsilon$ such that

$2\epsilon\gamma=\frac{1}{2}\cdot\frac{\gamma}{3e^{2\kappa}}\Rightarrow\epsilon=\frac{1}{12e^{2\kappa}}\,.$

We summarize this condition with the following corollary:

######  Corollary A.8.

Suppose that event $\mathcal{A}$ happense and that

$np^{2}\geq\frac{C_{2}12^{2}e^{4\kappa}}{\gamma^{2}}\log m$

for sufficiently large constant $C_{2}$ (e.g., $C_{2}\geq 30$). Then:

$\mu^{*}(P)-\lVert P-P^{*}\rVert_{2}\geq\frac{\gamma}{6e^{2\kappa}}$

with probability at least
$1-\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot 12^{2}\cdot
e^{4\kappa}}\right)$ over the random responses of the users.

###### Proof.

Substituting $\epsilon=\frac{1}{12e^{2\kappa}}$ into the statement of Lemma
A.7 gives: so long as
$np^{2}\geq\frac{30\gamma^{2}}{\big{(}\frac{1}{12e^{2\kappa}}\big{)}^{2}}\cdot\log
m$ the $\lVert P-P^{*}\rVert_{2}\leq\mu^{*}(P^{*})/2$ with probability at
least
$1-\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10}\cdot\big{(}\frac{1}{12e^{2\kappa}}\big{)}^{2}\right)$.

###  A.4 Bounding the projected error term
$\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}$

######  Lemma A.9.

Conditioned on event $\mathcal{A}$,

$\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}\leq\frac{2e^{\kappa}\sqrt{16\cdot\max\\{m,\log
np^{2}\\}}}{m\sqrt{np^{2}}}\,$

with probability at least
$1-\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(np^{2})^{12}}\\}$ over the
random responses of the users.

###### Proof.

We follow a simlar argument as in the proof of Lemma 8.4 in [13] in turning
the normed term into a linear term. For completeness we reproduce this
argument here. We first have

$\displaystyle\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j=1}^{n}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})\bigg{)}^{2}}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P_{ii}-P_{ii}^{*})\bigg{)}^{2}}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(\sum_{j\neq
i}P^{*}_{ij}-P_{ij})\bigg{)}^{2}}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}^{2}}\,.$

Let $\mathcal{B}$ denote the unit norm ball in $\mathbb{R}^{m}$ and
$\mathcal{V}$ denote a $1/2$-net of $\mathcal{B}$. That is, for every
$u\in\mathcal{B}$, there exists $v\in\mathcal{V}$ such that $\lVert
u-v\rVert_{2}\leq\frac{1}{2}$. For any $u\in\mathcal{B}$ and any corresponding
$v$, we have

$\displaystyle\sum_{i=1}^{n}u_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}$
$\displaystyle=\sum_{i=1}^{n}v_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}+\sum_{i=1}^{n}(u_{i}-v_{i})\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}$
$\displaystyle\leq\sum_{i=1}^{n}v_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}+\frac{1}{2}\cdot\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}^{2}}\,.$

Maximizing both sides of the above inequality with respect to $u$ and
rearranging the terms gives

$\displaystyle\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}^{2}}$
$\displaystyle\leq
2\max_{v\in\mathcal{V}}\sum_{i=1}^{n}v_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P^{*}_{ij}-P_{ij})\bigg{)}\,.$

In summary, we can upper bound the normed term by a more manageable linear
term as follows:

$\displaystyle\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\bigg{(}\sum_{j=1}^{n}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})\bigg{)}^{2}}$
(7) $\displaystyle\leq
2\max_{v\in\mathcal{V}}\sum_{i=1}^{n}v_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P_{ij}^{*}-P_{ij})\bigg{)}\,.$

We now expand on the linear term:

$\displaystyle\sum_{i=1}^{m}v_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}(P_{ji}-P_{ji}^{*})+\pi_{i}^{*}(P_{ij}^{*}-P_{ij})\bigg{)}$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{m}v_{i}\bigg{(}\sum_{j\neq
i}\pi_{j}^{*}\big{[}\sum_{l=1}^{n}A_{li}A_{lj}\big{(}X_{lj}(1-X_{li})-\mathbb{E}[X_{lj}(1-X_{li})]\big{)}\big{]}$
$\displaystyle\quad\quad-\sum_{j\neq
i}\pi_{i}^{*}\big{[}\sum_{l=1}^{n}A_{li}A_{lj}\big{(}X_{li}(1-X_{lj})-\mathbb{E}[X_{li}(1-X_{lj})]\big{)}\big{]}\bigg{)}$
$\displaystyle=\frac{1}{d}\sum_{l=1}^{n}\sum_{i=1}^{m}\bigg{(}\sum_{j\neq
i}v_{i}\pi_{j}^{*}A_{li}A_{lj}\big{[}(X_{lj}(1-X_{li})-\mathbb{E}[X_{lj}(1-X_{li})]\big{]}\big{)}$
$\displaystyle-\frac{1}{d}\sum_{l=1}^{n}\sum_{i=1}^{m}\bigg{(}\sum_{j\neq
i}v_{i}\pi_{i}^{*}A_{li}A_{lj}\big{[}(X_{li}(1-X_{lj})-\mathbb{E}[X_{li}(1-X_{lj})]\big{]}\big{)}$
$\displaystyle=\frac{1}{d}\sum_{l=1}^{n}\sum_{i=1}^{m}\sum_{j\neq
i}\bigg{(}(v_{i}-v_{j})\pi_{j}^{*}A_{li}A_{lj}\big{[}(X_{lj}(1-X_{li})-\mathbb{E}[X_{lj}(1-X_{li})]\big{]}\bigg{)}\,.$

We will use the method of bounded difference to obtain a concentration
inequality on the above sum. Note that this sum is essentially a function $f$
of $n\times m$ independent Bernoulli random variables $\\{X_{li}\\}$. Let $X$
and $X^{\prime}$ be identical copies except for $X_{li}\neq X^{\prime}_{li}$.

$\displaystyle\lvert f(X)-f(X^{\prime})\rvert$
$\displaystyle=\frac{1}{d}\lvert\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})[X_{lj}(\pi^{*}_{i}-\pi_{j}^{*})-\pi_{i}^{*}]\rvert\,.$
(8)

Ignore the normalization factor $d$ for now. Using Cauchy-Schwarz, we can
upper bound the absolute difference term as

$\displaystyle\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})\underbrace{[X_{lj}(\pi^{*}_{i}-\pi_{j}^{*})-\pi_{i}^{*}]}_{\leq\max\\{\pi^{*}_{i},\pi^{*}_{j}\\}\leq\frac{e^{\kappa}}{m}}$
$\displaystyle\leq\frac{e^{\kappa}}{m}\cdot\sqrt{m}\cdot\sqrt{\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})^{2}}=\frac{e^{\kappa}}{\sqrt{m}}\cdot\sqrt{\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})^{2}}\,.$

At this point we can invoke concentration inequality based on bounded
difference (e.g., Hoeffding’s inequality). Fixing a $v\in\mathcal{V}$, we have

$\displaystyle\mathbb{P}\bigg{(}\sum_{l=1}^{n}\sum_{i=1}^{m}\sum_{j\neq
i}(v_{i}-v_{j})\pi_{j}^{*}A_{li}A_{lj}\big{[}(X_{lj}(1-X_{li})-\mathbb{E}[X_{lj}(1-X_{li})]\big{]}>t\,\lvert\,\mathcal{A}\bigg{)}$
$\displaystyle\leq
2\mathrm{exp}\left(-\frac{2t^{2}}{\sum_{l=1}^{n}\sum_{i=1}^{m}\frac{e^{2\kappa}}{m}\cdot\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})^{2}}\right)$
$\displaystyle=2\mathrm{exp}\left(-\frac{2t^{2}}{\frac{e^{2\kappa}}{m}\sum_{i\neq
j}B_{ij}(v_{i}-v_{j})^{2}}\right)$ $\displaystyle[\text{Conditioned on
$\mathcal{A}$, $B_{ij}\leq\frac{3np^{2}}{2}$}]$ $\displaystyle\leq
2\mathrm{exp}\left(-\frac{2t^{2}}{\frac{e^{2\kappa}}{m}\sum_{i\neq
j}\frac{3}{2}np^{2}\cdot(v_{i}-v_{j})^{2}}\right)$ $\displaystyle\leq
2\mathrm{exp}\left(-\frac{2t^{2}}{\frac{e^{2\kappa}}{m}\frac{3}{2}mnp^{2}}\right)$
$\displaystyle=2\mathrm{exp}\left(-\frac{4t^{2}}{3e^{2\kappa}np^{2}}\right)\,.$

Note that our $\frac{1}{2}$-net has cardinality
$(\frac{2}{\frac{1}{2}}+1)^{m}=5^{m}$ (cf. Corollary 4.2.13 [52]) and we are
interested in the probability that large deviation _doesn’t happen for all
$v\in\mathcal{V}$_. Applying union bound over all $v\in\mathcal{V}$, we have

$\displaystyle\mathbb{P}\bigg{(}\sum_{l=1}^{n}\sum_{i=1}^{m}\sum_{j\neq
i}(v_{i}-v_{j})\pi_{j}^{*}A_{li}A_{lj}\big{[}(X_{lj}(1-X_{li})-\mathbb{E}[X_{lj}(1-X_{li})]\big{]}>t\quad\forall
v\in\mathcal{V}\,\lvert\,\mathcal{A}\bigg{)}$ $\displaystyle\leq 2\cdot
5^{m}\cdot\mathrm{exp}\left(-\frac{4t^{2}}{3e^{2\kappa}np^{2}}\right)$
$\displaystyle\leq\mathrm{exp}\left(-\frac{4t^{2}}{3e^{2\kappa}np^{2}}+4m\right)\,.$

Set

$t=e^{\kappa}\sqrt{\frac{3np^{2}}{4}}\cdot\sqrt{4m+12\max\\{m,\log{np^{2}}\\}}.$

Then
$\mathrm{exp}\left(-\frac{4t^{2}}{3e^{2\kappa}np^{2}}+4m\right)\leq\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(np^{2})^{12}}\\}$.
Consequently,

$\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}\leq\frac{2e^{\kappa}\sqrt{\frac{3np^{2}}{4}}\cdot\sqrt{16\cdot\max\\{m,\log
np^{2}\\}}}{d}\leq\frac{2e^{\kappa}\sqrt{np^{2}}\cdot\sqrt{12\cdot\max\\{m,\log
np^{2}\\}}}{d}$

with probability at least
$1-\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(np^{2})^{12}}\\}$. Note that
the factor of $2$ comes from Equation (7). Substituting $d=\frac{3mnp^{2}}{2}$
into the bound above finishes the proof.

###  A.5 Putting it all together

The results of previous sections provide bounds on the numerator and
denominator of the eigenperturbation bound in Lemma A.3. We can now combine
all of them towards obtaining a bound on $\lVert\beta-\beta^{*}\rVert_{2}$. As
an intermediate, we first obtain the following bound on
$\lVert\pi-\pi^{*}\rVert_{2}$:

######  Theorem A.10.

Consider the random sampling scheme described in Section 3.1. Suppose that
$np^{2}\geq\max\\{C_{2}\frac{12^{2}e^{4\kappa}}{\gamma^{2}}\log m,C_{1}\log
m\\}$ for sufficiently large constants (e.g., $C_{2}\geq 30$, $C_{1}\geq
101$). Then

$\lVert\pi-\pi^{*}\rVert_{2}\leq\frac{48/\sqrt{3}e^{3\kappa}}{\gamma}\cdot\frac{\sqrt{\max\\{m,\log
np^{2}\\}}}{m\sqrt{np^{2}}}$

with probability at least
$1-\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(np^{2})^{12}}\\}-\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot
12^{2}\cdot e^{4\kappa}}\right)-\mathrm{exp}\left(-\frac{np^{2}}{20}\right)$.

###### Proof.

We first assume that $\mathcal{A}$ holds. The probability bound in the theorem
statement can be obtained following a simple union bound argument.

From the conclusions of Lemma A.9, we have

$\mathbb{P}\bigg{(}\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}>\frac{2e^{\kappa}\sqrt{16\cdot\max\\{m,\log
np^{2}\\}}}{m\sqrt{np^{2}}}\,\lvert\,\mathcal{A}\bigg{)}\leq\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(np^{2})^{12}}\\}\,.$

From the conclusion of Corollary A.8, we have

$\mathbb{P}\bigg{(}\mu^{*}(P)-\lVert
P-P^{*}\rVert_{2}<\frac{\gamma}{6e^{2\kappa}}\,\lvert\,\mathcal{A}\bigg{)}\leq\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot
12^{2}\cdot e^{4\kappa}}\right)\,.$

Applying Lemma A.3: Conditioned on $\mathcal{A}$ and applying union bound over
the two rare events above, the following holds with probability at least
$1-\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{{(np^{2})}^{12}}\\}-\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot
12^{2}\cdot e^{4\kappa}}\right)$.

$\lVert\pi-\pi^{*}\rVert_{2}\leq\frac{\lVert{\pi^{*}}^{\top}(P^{*}-P)\rVert_{2}}{\mu(P^{*})-\lVert
P-P^{*}\rVert_{2}}\leq\frac{48/\sqrt{3}e^{3\kappa}}{\gamma}\cdot\frac{\sqrt{\max\\{m,\log
np^{2}\\}}}{m\sqrt{np^{2}}}\,.$

Let the above good event be $\mathcal{B}$.

$\displaystyle\mathbb{P}(\mathcal{B}^{c})$
$\displaystyle=\mathbb{P}(\mathcal{B}^{c},\mathcal{A})+\mathbb{P}(\mathcal{B}^{c},\mathcal{A}^{c})$
$\displaystyle\leq\mathbb{P}(\mathcal{B}^{c}\,\lvert\,\mathcal{A})\cdot\mathbb{P}(\mathcal{A})+\mathbb{P}(\mathcal{A}^{c})$
$\displaystyle\leq\mathbb{P}(\mathcal{B}^{c}\,\lvert\,\mathcal{A})+\mathbb{P}(\mathcal{A}^{c})$
$\displaystyle\leq\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{{(np^{2})}^{12}}\\}+\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot
12^{2}\cdot
e^{4\kappa}}\right)+\mathrm{exp}\left(-\frac{np^{2}}{20}\right)\,.$

This completes the proof.

With these results, we are finally ready to prove the main theorem providing
error bounds on the parameters returned by our spectral algorithm.

######  Theorem 3.1.

Consider the random sampling scheme described in Section 3.1. Suppose that
$np^{2}\geq\max\\{C_{2}\frac{12^{2}e^{4\kappa}}{\gamma^{2}}\log m,C_{1}\log
m\\}$ for sufficiently large constants (e.g., $C_{2}\geq 30$, $C_{1}\geq
101$). Then the output of the spectral algorithm (Algorithm 1) satisfies

$\lVert\beta-\beta^{*}\rVert_{2}\leq\frac{96/\sqrt{3}\cdot
e^{4\kappa}}{\gamma}\cdot\frac{\sqrt{\max\\{m,\log np^{2}\\}}}{\sqrt{np^{2}}}$

with probability at least
$1-\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(np^{2})^{12}}\\}-\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot
12^{2}\cdot e^{4\kappa}}\right)-\mathrm{exp}\left(-\frac{np^{2}}{20}\right)$.

###### Proof.

Suppose for now that there is a factor $L$ such that $\lvert\log x-\log
x^{\prime}\rvert\leq L\lvert x-x^{\prime}\rvert$ for all
$x,x^{\prime}\in[\frac{w^{*}_{\min}}{\sum_{j}w^{*}_{j}},\frac{w^{*}_{\max}}{\sum_{j}w^{*}_{j}}]$.
One can see that the output of the spectral algorithm is essentially

$\beta_{i}=\log\pi_{i}-\frac{1}{m}\sum_{k=1}^{m}\log\pi_{k}\,.$

And $\beta^{*}$ is related to $\pi^{*}$ via the same transformation:

$\beta^{*}_{i}=\log\pi^{*}_{i}-\frac{1}{m}\sum_{k=1}^{m}\log\pi^{*}_{k}\,.$

The goal is to relate $\lVert\beta-\beta^{*}\rVert_{2}$ to
$\lVert\pi-\pi^{*}\rVert_{2}$.

$\displaystyle\lVert\beta-\beta^{*}\rVert_{2}^{2}$
$\displaystyle=\sum_{i=1}^{m}(\beta_{i}-\beta^{*}_{i})^{2}=\sum_{i=1}^{m}(\log\pi_{i}-\frac{1}{m}\sum_{k}\log\pi_{k}-\log\pi_{i}^{*}+\frac{1}{m}\sum_{k}\log\pi^{*}_{k})^{2}$
$\displaystyle=\sum_{i=1}^{m}(\log\pi_{i}-\pi^{*}_{i}+\frac{1}{m}\sum_{k}[\log\pi^{*}_{k}-\log\pi_{k}])^{2}$
$\displaystyle\leq
2\sum_{i=1}^{m}\bigg{(}(\log\pi_{i}-\pi^{*}_{i})^{2}+(\frac{1}{m}\sum_{k}[\log\pi^{*}_{k}-\log\pi_{k}])^{2}\bigg{)}$
$\displaystyle=2\sum_{i=1}^{m}(\log\pi_{i}-\pi^{*}_{i})^{2}+2m\cdot\frac{1}{m^{2}}\big{(}\sum_{k}[\log\pi^{*}_{k}-\log\pi_{k}])^{2}\big{)}$
$\displaystyle\leq
2L\sum_{i=1}^{m}\lvert\pi_{i}-\pi^{*}_{i}\rvert^{2}+\frac{2}{m}\cdot
m\cdot\sum_{k=1}^{m}(\log\pi^{*}_{k}-\log\pi_{k})^{2}$ $\displaystyle\leq
2L\lVert\pi-\pi^{*}\rVert_{2}^{2}+2L\sum_{k=1}^{m}\lvert\pi_{k}-\pi^{*}_{k}\rvert^{2}$
$\displaystyle=4L\lVert\pi-\pi^{*}\rVert_{2}^{2}\,.$

Taking the square root of both sides of the inequality gives

$\lVert\beta-\beta^{*}\rVert_{2}\leq 2L\lVert\pi-\pi^{*}\rVert_{2}\,.$

Observe that $w^{*}_{\min}/\sum_{j}w^{*}_{j}\leq\frac{1}{me^{\kappa}}$. One
can thus easily see that the $\log$ function within the dynamic range has
gradient absolutely bounded by $me^{\kappa}$. Therefore $L\leq me^{\kappa}$.
Substituting this upper bound on $L$ into the inequality obtained above and
combining with the conclusion of Theorem A.10 completes the proof.

######  Corollary 3.2.

Consider the setting of Theorem 3.1 and for a fixed $m$ with $p=1$, the
spectral algorithm is a consistent estimator of $\beta^{*}$. That is, its
output $\beta$ satisfies
$\lim_{n\rightarrow\infty}\mathbb{P}(\lVert\beta-\beta^{*}\rVert_{2}<\epsilon)=1\,,\forall\epsilon>0\,.$

###### Proof.

It is easy to see from the conclusion of Theorem 3.1 that as
$n\rightarrow\infty$, for a fixed $m$ and $p=1$ (or any constant $p$ for that
matter), $\lVert\beta-\beta^{*}\rVert_{2}\rightarrow 0$ and

$1-\min\\{\mathrm{exp}\left(-12m\right),\frac{1}{(n)^{12}}\\}-\mathrm{exp}\left(-\frac{\gamma^{2}n}{10\cdot
12^{2}\cdot
e^{4\kappa}}\right)-\mathrm{exp}\left(-\frac{n}{20}\right)\rightarrow 1\,.$

We now prove the error bounds when $m$ is allowed to grow. The proof of
Theorem 3.3 is almost identical to that of Theorem 3.1. The key difference is
that under condition $\mathcal{A}^{+}$ (which happens with probability at
least $1-n^{-9}$ given that $mp\geq C^{\prime\prime}\log n$ for a sufficiently
large constant $C^{\prime\prime}$), one can obtain a stronger bound on the
projected error term $\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}$. The
difference in the projected term is summarized by the lemma below.

######  Lemma A.11.

Conditioned on event $\mathcal{A}^{+}$,

$\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}\leq e^{\kappa}\sqrt{\frac{8}{mnp}}$

with probability at least $1-\mathrm{exp}\left(-12m\right)$ over the random
responses of the users.

###### Proof.

The proof here is almost identical to that of Lemma A.9. The key difference is
that under conditioned $\mathcal{A}^{+}$ we could obtain better bound also
using the bounded difference method. Namely, one can invoke Cauchy-Schwarz on
the absolute difference term in Equation (8) as follows:

$\displaystyle\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})\underbrace{[X_{lj}(\pi^{*}_{i}-\pi_{j}^{*})-\pi_{i}^{*}]}_{\leq\max\\{\pi^{*}_{i},\pi^{*}_{j}\\}\leq\frac{e^{\kappa}}{m}}$
$\displaystyle\leq\frac{e^{\kappa}}{m}\cdot\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})=\frac{e^{\kappa}}{m}\cdot\sum_{j\neq
i}A_{lj}A_{li}A_{lj}(v_{i}-v_{j})$
$\displaystyle\leq\frac{e^{\kappa}}{m}\cdot\sqrt{\underbrace{\sum_{j}A_{lj}}_{\leq\frac{3}{2}mp}}\cdot\sqrt{\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})^{2}}=\sqrt{3/2}\cdot\frac{e^{\kappa}\sqrt{p}}{\sqrt{m}}\cdot\sqrt{\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})^{2}}\,.$

Continuting the same procedures as in the proof of Lemma A.9 gives

$\displaystyle\mathbb{P}\bigg{(}\sum_{l=1}^{n}\sum_{i=1}^{m}\sum_{j\neq
i}(v_{i}-v_{j})\pi_{j}^{*}A_{li}A_{lj}\big{[}(X_{lj}(1-X_{li})-\mathbb{E}[X_{lj}(1-X_{li})]\big{]}>t\quad\forall
v\in\mathcal{V}\,\lvert\,\mathcal{A}\bigg{)}$ $\displaystyle\leq 2\cdot
5^{m}\cdot\mathrm{exp}\left(-\frac{2t^{2}}{\sum_{l=1}^{n}\sum_{i=1}^{m}\frac{e^{2\kappa}}{m}\cdot\sum_{j\neq
i}A_{li}A_{lj}(v_{i}-v_{j})^{2}}\right)$ $\displaystyle=2\cdot
5^{m}\cdot\mathrm{exp}\left(-\frac{2t^{2}}{\frac{3e^{2\kappa}p}{2m}\sum_{i\neq
j}B_{ij}(v_{i}-v_{j})^{2}}\right)$ $\displaystyle\leq 2\cdot
5^{m}\cdot\mathrm{exp}\left(-\frac{8t^{2}}{9e^{2\kappa}p\cdot np^{3}}\right)$
$\displaystyle\leq\mathrm{exp}\left(-\frac{8t^{2}}{9e^{2\kappa}np^{3}}+4m\right)\,.$

Set

$t=e^{\kappa}\sqrt{\frac{9np^{3}}{8}}\cdot\sqrt{16m}.$

Then
$\mathrm{exp}\left(-\frac{8t^{2}}{9e^{2\kappa}np^{3}}+4m\right)\leq\mathrm{exp}\left(-12m\right)$.
Consequently,

$\lVert{\pi^{*}}^{\top}(P-P^{*})\rVert_{2}\leq\frac{e^{\kappa}\sqrt{18mnp^{3}}}{d}$

with probability at least $1-\mathrm{exp}\left(-12m\right)$. Substituting
$d=\frac{3mnp^{2}}{2}$ into the bound above finishes the proof.

With the numerator the eigenperturbation bound in Lemma A.3 updated, we now
have the proof for Theorem 3.3.

######  Theorem 3.3.

Consider the random sampling scheme described in Section 3.1. Suppose that
$np^{2}\geq\max\\{C_{2}\frac{12^{2}e^{4\kappa}}{\gamma^{2}}\log m,C_{1}\log
m\\}$ and $mp\geq C^{\prime\prime}\log m$ for sufficiently large constants
$C_{1},C_{2},C^{\prime\prime}$ (e.g., $C_{2}\geq 30$,
$C_{1},C^{\prime\prime}\geq 101$). Then the output of the spectral algorithm
(Algorithm 1) satisfies

$\lVert\beta-\beta^{*}\rVert_{2}\leq\frac{96/\sqrt{2}e^{4\kappa}}{\gamma}\cdot\frac{\sqrt{m}}{\sqrt{np}}$

with probability at least
$1-\mathrm{exp}\left(-12m\right)-\mathrm{exp}\left(-\frac{\gamma^{2}np^{2}}{10\cdot
12^{2}\cdot e^{4\kappa}}\right)-n^{-9}$.

###### Proof.

Applying Lemma A.3 and Corollary A.8 gives

$\lVert\pi-\pi^{*}\rVert_{2}\leq\frac{48/\sqrt{2}e^{3\kappa}}{\gamma}\cdot\frac{1}{\sqrt{mnp}}\,.$

Following the same proof as that of Theorem 3.1 with minor changes to the
constant factor completes the proof.

##  Appendix B Proofs of Lower Bounds

######  Theorem 3.4.

Consider the sampling model described in in Section 3.1. Let $T$ be any
unbiased estimator for the item parameters. Then the mean squared error of
such estimator is lower bounded as

$\mathbb{E}\lVert\hat{\beta}-\beta^{*}\lVert^{2}_{2}\,\geq\frac{4m}{np}\,.$

###### Proof.

Suppose that we know exactly the user parameter $\theta^{*}$. It is known that
the presence of unknown nuisance parameters does not make the estimation
problem easier (cf. [34, pp. 127-128]). On the other hand, once the user
parameters are exactly known, the $\beta^{*}$ estimation problems reduces to
$m$ estimation problems over each parameter $\beta^{*}_{i}$ for $i\in[m]$. The
Fisher information for a single parameter $I(\beta^{*}_{i})$ is

$\displaystyle I(\beta^{*}_{i})$
$\displaystyle=-\sum_{l=1}^{n}\mathbb{E}_{X_{li}}\bigg{[}\bigg{(}\frac{\partial\ell(X_{li};\beta^{*}_{i})}{\partial\beta^{*}_{i}}\bigg{)}^{2}\bigg{]}$
$\displaystyle=-\sum_{l=1}^{n}\
p\bigg{[}\frac{1}{1+e^{-(\theta^{*}_{l}-\beta^{*}_{i})}}\frac{\partial^{2}}{\partial\beta_{i}^{2}}\log\bigg{(}\frac{1}{1+e^{-(\theta^{*}_{l}-\beta^{*}_{i})}}\bigg{)}+\frac{1}{1+e^{-(\beta^{*}_{i}-\theta^{*}_{l})}}\frac{\partial^{2}}{\partial\beta_{i}^{2}}\log\bigg{(}\frac{1}{1+e^{-(\beta^{*}_{i}-\theta^{*}_{l})}}\bigg{)}\bigg{]}$
$\displaystyle=\sum_{l=1}^{n}p\bigg{[}\frac{e^{-(\theta^{*}_{l}-\beta^{*}_{i})}}{(1+e^{-(\theta^{*}_{l}-\beta^{*}_{i})})^{2}}\bigg{]}$
$\displaystyle\leq\frac{np}{4}\,.$

The last inequality comes from the observation that
$\frac{e^{-(\theta-\beta^{*}_{i})}}{(1+e^{-(\theta-\beta^{*}_{i})})^{2}}\leq\frac{1}{4}\,\forall\theta\in\mathbb{R}$.
Repeating the same argument for every item parameter $i\in[m]$ and applying
the Cramer-Rao lower bound for multivariate parameter finishes the proof.

######  Theorem 3.5.

Fix $m=2$ and consider the sampling model described in in Section 3.1. Let $T$
be any unbiased estimator for the user parameters that only uses _pairwise
differential measurements_. Then the mean squared error of such estimator is
lower bounded as

$\mathbb{E}\lVert T(X)-\beta^{*}\lVert^{2}_{2}\,\geq\frac{1}{np^{2}}\,,$

where $T(X)$ is the output of the estimator $T$ when given data $X$.

###### Proof.

Since there are only two parameters $\beta^{*}_{1}$ and $\beta^{*}_{2}$ and
$\beta_{1}^{*}+\beta_{2}^{*}=0$, the problem reduces to estimating a single
parameter $\delta^{*}$ where $\beta^{*}_{1}=\delta^{*}$,
$\beta^{*}_{2}=-\delta^{*}$. To establish the result in the theorem statement,
we first need to introduce a modified likelihood function that adapts to the
setting where we consider the class of algorithms that uses pairwise
differential measurements.

Note that for $m=2$, an observation
$x\in\\{(1,0),(0,1),(1,*),(0,*),(*,1),(*,0),(*,*)\\}$. To prove the lower
bound, we need to define an alternative observation model (and with it an
alternative likelihood) appopriate to the class of estimators that only use
pairwise differential measurements. Define the pseudo-observation $x^{\prime}$
(in terms of $x$) as

$x^{\prime}=\begin{cases}(1,0)&\text{if }x=(1,0)\\\ (0,1)&\text{if }x=(0,1)\\\
(*,*)&\text{otherwise}\end{cases}\quad,$

We can show the Fisher information under the modified likelihood.

$\displaystyle I(\delta^{*})$
$\displaystyle=-\mathbb{E}\bigg{[}\frac{\partial^{2}}{\partial\delta^{2}}\log\tilde{L}(X^{\prime},\delta^{*})\bigg{]}$
$\displaystyle=-\sum_{l=1}^{n}\bigg{[}\mathbb{P}(x_{l}^{\prime}=(1,0))\cdot\frac{\partial^{2}}{\partial\delta^{2}}\log\mathbb{P}(x_{l}^{\prime}=(1,0))+\mathbb{P}(x_{l}^{\prime}=(0,1))\cdot\frac{\partial^{2}}{\partial\delta^{2}}\log\mathbb{P}(x_{l}^{\prime}=(0,1))\bigg{]}$
$\displaystyle=-p^{2}\sum_{l=1}^{n}\bigg{[}\frac{1}{1+e^{-(\theta^{*}_{l}-\delta^{*})}}\cdot\frac{1}{1+e^{-(-\delta^{*}-\theta^{*}_{l})}}\cdot\frac{\partial^{2}}{\partial\delta^{2}}\log\bigg{(}\frac{1}{1+e^{-(\theta^{*}_{l}-\delta^{*})}}\cdot\frac{1}{1+e^{\delta^{*}+\theta^{*}_{l}}}\bigg{)}$
$\displaystyle+\frac{1}{1+e^{-(\delta^{*}-\theta^{*}_{l})}}\cdot\frac{1}{1+e^{-(\theta^{*}_{l}-(-\delta^{*}))}}\cdot\frac{\partial^{2}}{\partial\delta^{2}}\log\bigg{(}\frac{1}{1+e^{\theta^{*}_{l}-\delta^{*}}}\cdot\frac{1}{1+e^{-\delta^{*}-\theta^{*}_{l}}}\bigg{)}\bigg{]}$
$\displaystyle=-p^{2}\sum_{l=1}^{n}\bigg{[}\frac{1}{1+e^{-(\theta^{*}_{l}-\delta^{*})}}\cdot\frac{1}{1+e^{-(-\delta^{*}-\theta^{*}_{l})}}\cdot(-\frac{e^{\theta^{*}_{l}+\delta^{*}}}{(1+e^{\theta^{*}_{l}+\delta^{*}})^{2}}-\frac{e^{-(\theta^{*}_{l}-\delta^{*})}}{(1+e^{-(\theta^{*}_{l}-\delta^{*})})^{2}})$
$\displaystyle+\frac{1}{1+e^{-(\delta^{*}-\theta^{*}_{l})}}\cdot\frac{1}{1+e^{-(\theta^{*}_{l}+\delta^{*})}}\cdot(-\frac{e^{-(\theta^{*}_{l}+\delta^{*})}}{(1+e^{-(\theta^{*}_{l}+\delta^{*})})^{2}}-\frac{e^{(\theta^{*}_{l}-\delta^{*})}}{(1+e^{(\theta^{*}_{l}-\delta^{*})})^{2}})\bigg{]}$
$\displaystyle=p^{2}\sum_{l=1}^{n}\bigg{[}\frac{1}{1+e^{-(\theta^{*}_{l}-\delta^{*})}}\cdot\frac{1}{1+e^{\delta^{*}+\theta^{*}_{l}}}\cdot(\frac{e^{\theta^{*}_{l}+\delta^{*}}}{(1+e^{\theta^{*}_{l}+\delta^{*}})^{2}}+\frac{e^{-(\theta^{*}_{l}-\delta^{*})}}{(1+e^{-(\theta^{*}_{l}-\delta^{*})})^{2}})$
$\displaystyle+\frac{1}{1+e^{-(\delta^{*}-\theta^{*}_{l})}}\cdot\frac{1}{1+e^{-(\theta^{*}_{l}+\delta^{*})}}\cdot(\frac{e^{-(\theta^{*}_{l}+\delta^{*})}}{(1+e^{-(\theta^{*}_{l}+\delta^{*})})^{2}}+\frac{e^{(\theta^{*}_{l}-\delta^{*})}}{(1+e^{(\theta^{*}_{l}-\delta^{*})})^{2}})\bigg{]}$
$\displaystyle\leq np^{2}\,.$

This finishes the proof.

##  Appendix C Proofs of Results in Section 4

######  Theorem 4.1.

Consider the modified Markov chain $\bar{P}$ constructed per Equation (5) and
the original Markov chain $P$ constructed per Equation (3). Suppose that
$\bar{P}$ and $P$ admit unique stationary distributions $\bar{\pi}$ and $\pi$,
respectively. Then

$\bar{\pi}_{i}=\frac{\pi_{i}d_{i}}{\sum_{k=1}^{m}\pi_{k}d_{k}}\quad\forall
i\,,$

where $d_{i}$ are the normalization factors in the construction of the
modified Markov chain $\bar{P}$.

###### Proof.

As $\bar{\pi}$ is the unique stationary distribution of the modified Markov
chain $\bar{P}$, it must satisfy the fixed point equation:

$\sum_{k\neq i}\bar{\pi}_{k}\bar{P}_{ki}=\sum_{k\neq
i}\bar{\pi}_{i}\bar{P}_{ik}\quad\forall i\in[m]\,.$

Intuitively, this means the total ’inflow’ into a state $i$ is equal to the
total ’outflow’ out of state $i$. By construction, this is equivalent to

$\sum_{k\neq i}\bar{\pi}_{k}\frac{Y_{ik}}{d_{k}}=\sum_{k\neq
i}\bar{\pi}_{i}\frac{Y_{ik}}{d_{i}}\quad\forall i\in[m]\quad(*)\,.$

Similarly, we have for the original Markov chain $P$,

$\sum_{k\neq i}\pi_{k}Y_{ki}=\sum_{k\neq i}\pi_{i}Y_{ik}\quad\forall
i\in[m]\,.$

Note that in the original Markov chain, because we use a global normalization
constant $d$, it does not appear in the fixed point equation. One can easily
see that setting
$\bar{\pi}_{i}=\frac{\pi_{i}d_{i}}{\sum_{k=1}^{m}\pi_{k}d_{k}}$ preserves the
fixed point equation in $(*)$. Assuming that both Markov Chains admit unique
stationary distributions, there is thus a 1-1 relation between $\bar{\pi}$ and
$\pi$ as stated in the theorem. This finishes the proof.

##  Appendix D Additional Experiments

###  D.1 Other Pairwise Methods in the Literature

In this section we describe three methods that are related to our algorithm.
As noted before, previous matrix methods in the literature construct an item-
item matrix and assumes that such matrix is dense. It is unclear how one would
generalize these methods to the case where the item-item matrix is sparse,
which is quite commonly observed in real life datasets. A common quantity that
the previous matrix methods use is

$f_{ij}=\mathbb{P}_{l\in[n]}(X_{li}=1,X_{lj}=0\,\lvert\,X_{li}+X_{lj}=1)\,.$

Intuitively, $f_{ij}$ is the empirical probability at which a user responds
$1$ to item $i$ and $0$ to item $j$, conditioned on the event that the user
responds to exactly only one of the two items. Suppose that we have collected
$f_{ij}$ for all $i\neq j$, consider a matrix $D$ defined entrywise as

$D_{ij}=\frac{f_{ji}}{f_{ij}}\,.$

This is also known as the _positive reciprocal matrix_.

The Row Sum Approach of Choppin [17]: Given the matrix $D$, construct a matrix
$\ln D$ by taking the $\log$ of every entry of $D$. The row sums of this $\ln
D$ matrix is (after appropriate normalization) produce an estimate $\beta$. To
see why, it is helpful to first check that in the limit of infinite data and
suppose that we observe all pairs $i,j$ then $f_{ij}$ is exact and

$f_{ij}=\frac{e^{\beta_{j}^{*}}}{e^{\beta_{i}^{*}}+e^{\beta_{j}^{*}}}\,.$

Then

$D_{ij}=\frac{e^{\beta_{i}^{*}}}{e^{\beta_{j}^{*}}}$

and

$\ln D_{ij}=\beta_{i}^{*}-\beta^{*}_{j}\,.$

It is easy to see that the row sums correspond exactly to $\beta^{*}$.

The Eigenvector Method of Garner [23] and Saaty [48]: Given the matrix $D$,
right the leading eigen-vector. Modulo an appropriate scaling factor, the
leading left eigen-vector is an estimate for $e^{\beta}$. Taking the log of
this eigenvector recovers $\beta$. To see why, verify that

$D\begin{bmatrix}e^{\beta^{*}_{1}}\\\ \vdots\\\
e^{\beta_{m}^{*}}\end{bmatrix}=m\cdot\begin{bmatrix}e^{\beta^{*}_{1}}\\\
\vdots\\\ e^{\beta_{m}^{*}}\end{bmatrix}\,.$

Pairwise Maximum Likelihood Estimate (PMLE): Another pairwise approach used in
the literature is the Pairwise Maximumum Likelihood Estimate (PMLE) [57].
Similar to the intuition behind the pairwise methods mentioned above, PMLE
uses the fact that the conditional probability
$\mathbb{P}_{l\in[n]}(X_{li}=1,X_{lj}=0\,\lvert\,X_{li}+X_{lj}=1)$ does not
involve the user parameter. PMLE maximizes the pairwise conditional
likelihood. We are not able to find any open source python implementation of
PMLE so we use the majorization-minorization (MM) algorithm for estimation
[29] and adapt our implementation from an open source implementation [40]. We
also implement a different version of PMLE using Scipy’s optimization
subroutine [53]. However, the later version has very significant numerical
issues and gives inaccurate results. We therefore use the MM-based version in
our experiments.

For completeness, we conduct extra experiments comparing between our spectral
method and the two previously studied matrix methods on synthetic data with
$m=100$ under full observation data. The result is presented in Figure 2.

Figure 2: Comparison between our spectral method and two matrix methods in the
literature. The performance are quite similar. However, our methods can be
easily generalizable to the setting where the pairwise comparison matrix
contains missing entries whereas the spectral methods in the literature
assumes a full comparison matrix.

Extra Experiment Results with Pairwise MLE: For completeness, we also conduct
extra experiments comparing between the spectral method and PMLE. The result
(together with previous results reported in the main paper) is summarized in
Table 2.

| AUC | Log likelihood | Top-K accuracy | Inference time
---|---|---|---|---
Dataset | Spectral | MMLE | CMLE | PMLE | JMLE | Spectral | MMLE | CMLE | PMLE | JMLE | Spectral | MMLE | CMLE | PMLE | JMLE | Spectral | MMLE | CMLE | PMLE | JMLE
LSAT | $0.707$ | $0.707$ | $0.707$ | $0.707$ | $0.707$ | $-0.487$ | $-0.489$ | $-0.487$ | $-0.487$ | $-0.485$ | N/A | N/A | N/A | N/A | N/A | $0.028$ | $0.159$ | $0.154$ | $0.011$ | $0.075$
UCI | $0.565$ | $0.565$ | $0.565$ | $0.565$ | $0.565$ | $-0.687$ | $-0.686$ | $-0.692$ | $-0.687$ | $-0.706$ | N/A | N/A | N/A | N/A | N/A | $0.015$ | $0.133$ | $0.136$ | $0.015$ | $0.034$
3 GRADES | $0.532$ | $0.532$ | $0.532$ | $0.532$ | $0.532$ | $-0.706$ | $-0.692$ | $-0.699$ | $-0.704$ | $-0.717$ | N/A | N/A | N/A | N/A | N/A | $0.021$ | $0.181$ | $0.105$ | $0.011$ | $0.009$
RIIID | $0.723$ | $0.724$ | N/A | $0.724$ | $0.724$ | $-0.486$ | $-0.49$ | N/A | $-0.486$ | $-0.486$ | N/A | N/A | N/A | N/A | N/A | $13.1$ | $104$ | N/A | $16.3\text{K}$ | $61.2$
HETREC | $0.728$ | $0.729$ | $0.506$ | $0.727$ | $0.73$ | $-0.604$ | $-0.603$ | $-1.119$ | $-0.603$ | $-0.602$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.58$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $50.1$ | $140$ | $224\text{K}$ | $4.25\text{K}$ | $144$
ML-100K | $0.662$ | $0.659$ | $0.498$ | $0.662$ | $0.665$ | $-0.646$ | $-0.66$ | $-1.159$ | $-0.645$ | $-0.653$ | $0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.54$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.5$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $1.39$ | $16.2$ | $9.56\text{K}$ | $368$ | $21$
ML-1M | $0.698$ | $0.701$ | $0.468$ | $0.699$ | $0.7$ | $-0.626$ | $-0.632$ | $-1.166$ | $-0.627$ | $-0.63$ | $0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72$ | $0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.62$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0$ | $0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.66$ | $19.2$ | $86.9$ | $156\text{K}$ | $1.38\text{K}$ | $194$
EACH MOVIE | $0.716$ | $0.718$ | $0.522$ | $0.715$ | $0.716$ | $-0.615$ | $-0.613$ | $-0.946$ | $-0.616$ | $-0.614$ | $0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.76\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.82$ | $0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.68\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.84$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $0.7\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.78$ | $0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72$ | $11.3$ | $329$ | $220\text{K}$ | $446$ | $1.9\text{K}$
ML-10M | $0.714$ | $0.716$ | N/A | $0.714$ | $0.716$ | $-0.617$ | $-0.619$ | N/A | $-0.62$ | $-0.618$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.84\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.7$ | $0.1\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.28\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.32$ | N/A | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.72$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.32\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.36$ | $821$ | $3.93\text{K}$ | N/A | $9.53\text{K}$ | $6.55\text{K}$
ML-20M | $0.709$ | $0.71$ | N/A | $0.709$ | $0.71$ | $-0.619$ | $-0.619$ | N/A | $-0.621$ | $-0.619$ | $0.5\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.8\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.64$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.44\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.4$ | N/A | $0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.5$ | $0.1\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.4\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.4$ | $1.58\text{K}$ | $5.36\text{K}$ | N/A | $12.8\text{K}$ | $4.42\text{K}$
BX | $0.546$ | $0.577$ | $0.503$ | $0.546$ | $0.57$ | $-0.618$ | $-0.612$ | $-0.8$ | $-0.627$ | $-0.617$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.16\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.16$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.24\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.2$ | $0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.0\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.02$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.28\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.3$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.2\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.18$ | $205$ | $2.02\text{K}$ | $156\text{K}$ | $338$ | $481$
BOOK-GENOME | $0.658$ | $0.665$ | N/A | $0.657$ | $0.654$ | $-0.651$ | $-0.645$ | N/A | $-0.649$ | $-0.651$ | $0.6\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.44\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.42$ | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.32\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.34$ | N/A | $0.3\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.44\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.36$ | $0.2\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.24\mathbin{\mathchoice{/\mkern-6.0mu/}{/\mkern-6.0mu/}{/\mkern-5.0mu/}{/\mkern-5.0mu/}}0.38$ | $2.53\text{K}$ | $2.56\text{K}$ | N/A | $7.8\text{K}$ | $4.34\text{K}$

Table 2: Results from Table 3 with PMLE. PMLE is quite competitive when
applied small datasets. However, similarly to CMLE, it tends to converge quite
slowly when applied to large datasets. Overall, both PMLE and the spectral
method are quite competitive but the spectral method is significantly faster.

Extra experiments with a Bayesian method. All of the estimation algorithms
considered so far are point estimation algorithm (i.e., return a single
parameter estimate). In certain applications, one may prefer a Bayesian
estimation algorithm that returns a _distribution_ over the estimate.
Recently, Bayesian algorithms based on variational inference has received
considerable attention in the IRT literature. We conduct extra experiments
using the algorithm proposed in [42] of which implementation can be found in
[32, 47]. Table 3 summarizes the results on a restricted subset of
experiments. One can see that the Bayesian algorithm is somewhat more accurate
than the spectral algorithm. However, it is considerably more complicated and
as a result runs much slower than the spectral algorithm.

Dataset | AUC (Bayesian) | AUC (Spectral)
---|---|---
LSAT | 0.706 | 0.707
3 Grades | 0.5322 | 0.532
UCI | 0.565 | 0.565
ML-100K | 0.695 | 0.662
| LogLik (Bayesian) | Loglik (Spectral)
LSAT | -0.487 | -0.487
3 Grades | -0.681 | -0.687
UCI | -0.693 | -0.706
ML-100K | -0.646 | -0.646
| Top-K (Bayesian) | Top-K (Spectral)
ML-100K | 0; 0; 0.04; | 0.4; 0.6; 0.54
| Time (Bayesian) | Time (Spectral)
LSAT | 63 | 0.028
3 Grades | 27 | 0.015
UCI | 26 | 0.021
ML-100K | 6700 | 2

Table 3: While the Bayesian algorithm is somewhat more accurate than the
spectral algorithm, it is considerably slower. In fact, it is significantly
slower than CMLE, the slowest method considered in our main experiments.

###  D.2 Datasets Metadata and Experiment Setup

Table 4 summarizes the metadata for all the real-life datasets used in our
experiments.

Dataset | $m$ | $m$ | Reference
---|---|---|---
LSAT | 5 | 1000 | [41]
UCI | 4 | 131 | [30]
3 GRADES | 3 | 648 | [18]
RIIID | 6311 | 22906 | [1]
HETREC | 10197 | 2113 | [11]
ML-100K | 1682 | 943 | [28]
ML-1M | 3952 | 6040 | [28]
EACH MOVIE | 1628 | 72916 | [28]
ML-10M | 10681 | 71567 | [28]
ML-20M | 27278 | 138493 | [28]
BX | 6185 | 278858 | [56]
BOOK-GENOME | 9374 | 350332 | [31]
Table 4: Datasets metadata and references.

Experiment Setup: For each experiment on real-life datasets, we first
partition the data randomly dividing the set of users into 80% of users for
training and 20% of users for testing. Within the set of training users, we
further partition into 90% for inference and 10% for validation. For the prior
distribution over the user parameters, we experimented with 10 prior
distributions, all normal distributions but with different means and standard
deviations. For each method, we run inference on the inference set to obtain
an item estimate $\beta$. For ranking metrics evaluation, we compute top-$K$
accuracy with respect to the reference ranking predetermined by average
ratings (after removing items with very high average ratings but receive very
few ratings). For AUC and log-likelihood metrics, we choose the prior
distribution over $\theta$ by evaluating the log-likelihood on the validation
set. The prior distribution corresponding to the high validation log-
likelihood is used to evaluate log-likelihood on the test set.

Python implementation. For readers reading this paper online, we also include
here the python implementation of our spectral algorithm.

⬇

import numpy as np

from scipy.sparse import csc_matrix

INVALID_RESPONSE = -99999

def construct_markov_chain_accelerated(X, lambd=0.1):

m, _ = X.shape

D = np.ma.masked_equal(X, INVALID_RESPONSE, copy=False)

D_compl = 1. - D

M = np.ma.dot(D, D_compl.T) # This computes Mij = sum_l Alj Ali Xli (1-Xlj)

np.fill_diagonal(M, 0)

M = np.round(M)

# Add regularization

M = np.where(np.logical_or((M != 0), (M.T != 0)), M+lambd, M)

d = []

# Construct a row stochastic matrix

for i in range(m):

di = max(np.sum(M[i, :]), 1)

d.append(di)

M[i, :] /= max(d[i], 1)

M[i, i] = 1. - np.sum(M[i, :])

d = np.array(d)

return M, d

def spectral_estimate(X, max_iters=10000, lambd=1, eps=1e-6):

"""Estimate␣the␣hidden␣parameters␣according␣to␣the␣Rasch␣model,␣either␣for␣the␣tests’␣difficulties

␣␣␣␣or␣the␣students’␣abilities.␣We␣follow␣the␣convention␣in␣Girth␣https://eribean.github.io/girth/docs/quickstart/quickstart/

␣␣␣␣the␣response␣matrix␣X␣has␣shape␣(m,␣n)␣where␣m␣is␣the␣number␣of␣items␣and␣n␣is␣the␣number␣of␣users.

␣␣␣␣The␣algorithm␣returns␣the␣item␣estimates.

␣␣␣␣X:␣np.array␣of␣size␣(m,␣n)␣where␣missing␣entries␣have␣value␣INVALID_RESPONSE

␣␣␣␣max_iters:␣int,␣maximum␣number␣of␣iterations␣to␣compute␣the␣stationary␣distribution␣of␣the␣Markov␣chain

␣␣␣␣lambd:␣float,␣regularization␣parameter

␣␣␣␣eps:␣tolerance␣for␣convergence␣checking

␣␣␣␣"""

M, d = construct_markov_chain_accelerated(X, lambd=lambd)

M = csc_matrix(M)

m = len(A)

pi = np.ones((m,)).T

for _ in range(max_iters):

pi_next = (pi @ M)

pi_next /= np.sum(pi_next)

if np.linalg.norm(pi_next - pi) < eps:

pi = pi_next

break

pi = pi_next

pi = pi.T/d

beta = np.log(pi)

beta = beta - np.mean(beta)

return beta