# Towards Reliable Item Sampling for Recommendation Evaluation

Dong Li,1 Ruoming Jin,1 Zhenming Liu,2 Bin Ren,2 Jing Gao,3 Zhi Liu,3

###### Abstract

Since Rendle and Krichene argued that commonly used sampling-based evaluation
metrics are “inconsistent” with respect to the global metrics (even in
expectation), there have been a few studies on the sampling-based recommender
system evaluation. Existing methods try either mapping the sampling-based
metrics to their global counterparts or more generally, learning the empirical
rank distribution to estimate the top-$K$ metrics. However, despite existing
efforts, there is still a lack of rigorous theoretical understanding of the
proposed metric estimators, and the basic item sampling also suffers from the
“blind spot” issue, i.e., estimation accuracy to recover the top-$K$ metrics
when $K$ is small can still be rather substantial. In this paper, we provide
an in-depth investigation into these problems and make two innovative
contributions. First, we propose a new item-sampling estimator that explicitly
optimizes the error with respect to the ground truth, and theoretically
highlight its subtle difference against prior work. Second, we propose a new
adaptive sampling method which aims to deal with the “blind spot” problem and
also demonstrate the expectation-maximization (EM) algorithm can be
generalized for such a setting. Our experimental results confirm our
statistical analysis and the superiority of the proposed works. This study
helps lay the theoretical foundation for adopting item sampling metrics for
recommendation evaluation, and provides strong evidence towards making item
sampling a powerful and reliable tool for recommendation evaluation.

##  1 Introduction

As personalization and recommendation continue to play an integral role in the
emerging AI-driven economy (Fayyaz et al. 2020; Zhao et al. 2021; Peng,
Sugiyama, and Mine 2022; Jin et al. 2021a), proper and rigorous evaluation of
recommendation models becomes increasingly important in recent years for both
academic researchers and industry practitioners (Gruson et al. 2019; Cremonesi
et al. 2011; Dacrema et al. 2019; Rendle 2019). Particularly, ever since
Krichene and Rendle (2020, 2022) pointed out the “inconsistent” issue of item-
sampling based evaluation of commonly used (top-$K$) evaluation metrics, such
as Recall (Hit-Ratio)/Precision, Average Precision (AP) and Normalized
Discounted Cumulative Gain (NDCG), (other than AUC), it has emerged as a major
controversy being hotly debated among recommendation community.

Specifically, the item-sampling strategy calculates the top-$K$ evaluation
metrics using only a small set of item samples (Koren 2008; Cremonesi, Koren,
and Turrin 2010; He et al. 2017; Ebesu, Shen, and Fang 2018; Hu et al. 2018;
Krichene et al. 2019; Wang et al. 2019; Yang et al. 2018a, b). Krichene and
Rendle (2020, 2022) show that the top-$K$ metrics based on the samples differ
from the global metrics using all the items. They suggested a cautionary use
(avoiding if possible) of the sampled metrics for recommendation evaluation.
Due to the ubiquity of sampling methodology, it is not only of theoretical
importance, but also of practical interests to understand item-sampling
evaluation. Indeed, since the number of items in any real world recommendation
systems is typically quite large (easily in the order of tens of millions),
efficient model evaluation based on item sampling can be very useful for
recommendation researchers and practitioners.

To address the discrepancy between item sampling results and the exact top-$K$
recommendation evaluation, Krichene and Rendle (2020) have proposed a few
estimators in recovering global top-$K$ metrics from sampling. Concurrently,
Li et al. (2020) showed that for the top-$K$ Hit-Ratios (Recalls) metric,
there is an (approximately) linear relationship between the item-sampling
top-$k$ and the global top-$K$ metrics ($K=f(k)$, where $f$ is approximately
linear). In another recent study, Jin et al. (2021b) developed solutions based
on MLE (Maximal Likelihood Estimation) and ME (Maximal Entropy) to learn the
empirical rank distribution, which is then used to estimate global top-$K$
metrics.

Despite these latest works on item-sampling estimation (Li et al. 2020;
Krichene and Rendle 2020; Jin et al. 2021b), there remain some major gaps in
making item-sampling reliable and accurate for top-$K$ metrics. Specifically,
the following important problems are remaining open:

_(i)_ What is the optimal estimator given the basic item sampling? All the
earlier estimation methods do not establish any optimality results with
respect to the estimation errors (Krichene and Rendle 2020; Jin et al. 2021b).

_(ii)_ What can we do for the problem of the basic item sampling, which
appears to have a fundamental limitation that prevents us from recovering the
global rank distributions accurately? For the offline recommendation
evaluation, we typically are interested in the top ranked items and top-$K$
metrics, when $K$ is relatively small, say less than $50$. However, the
current item-sampling seems to have a “blind spot” for the top rank
distribution. For example, when there are $n=100$ samples and $N=10k$, the
estimation granularity is only at around 1% ($1/n$) level (Krichene and Rendle
2020; Li et al. 2020). We can only infer that the top items in the samples are
top 1% (top 100) in the global rank, while we can not further tell whether the
top items in sample set are in, for example, top-50, without increasing
sampling size. Given this, even with the best estimator for the item sampling,
we may still not be able to provide accurate results for the top-$K$ metrics.
A remedy is increasing sampling size, but it can significantly increase the
estimation cost too, limiting the benefits of item sampling. Can we sample the
items in a more intelligent manner to circumvent the “blind spot” while
keeping estimation cost low (and the sample size small)?

To address above open questions, we make the following contributions in this
paper:

  * •

We derive an optimal item-sampling estimator and highlight subtle differences
from the BV estimators derived by Krichene and Rendle (2020), and point out
the potential issues of BV estimator because it fails to link the user
population size with the estimation variance. To the best of our knowledge,
this is the first estimator that directly optimizes the estimation errors.

  * •

We address the limitation of the current item sampling approaches by proposing
a new adaptive sampling method. This provides a simple and effective remedy
which helps avoid the sampling “blind spot”, and significantly improves the
accuracy of the estimated metrics with low sample complexity.

  * •

We perform a thorough experimental evaluation on the proposed item-sampling
estimator and the new adaptive sampling method. The experimental results
further confirm the statistical analysis and the superiority of newly proposed
estimators.

Our results help lay the theoretical foundation for adopting item sampling
metrics for recommendation evaluation, and offer a simple yet effective new
adaptive sampling approach to help recommendation practitioners and
researchers to apply item sampling based approaches to speedup offline
evaluation.

The rest of the paper is organized as follows: Section 2 introduces the item
sampling based top-$K$ evaluation framework and review the related work (in
Appendix A); Section 3 introduces the new optimal estimator minimizing its
mean squared error with respect to the ground-truth; Section 4 presents the
new adaptive sampling and estimation method; Section 5 discusses the
experimental results; and finally Section 6 concludes the paper.

##  2 Overview

Table 4 (in Appendix B) highlights the key notations for evaluating
recommendation algorithms used throughout the paper. Given $M$ users and $N$
items. To evaluate the quality of recommender models, each testing user $u$
hides an already clicked (or so called target) item $i_{u}$, and compare it
with the rest of items, derive a rank $R_{u}$. The recommendation model is
considered to be effective if it ranks $i_{u}$ in top (small $R_{u}$).
Formally, given a recommendation model, a metric function (denoted as a metric
$\mathcal{M}$) maps each rank $R_{u}$ to a real-valued score, and then
averages over all the users in the test set:

$T=\frac{1}{M}\sum_{u=1}^{M}{\mathcal{M}}(R_{u})$ (1)

And the corresponding top-K evaluation metric:

$T=\frac{1}{M}\sum_{u=1}^{M}{\bf 1}_{R_{u}\leq K}\cdot{\mathcal{M}}(R_{u})$
(2)

where $\mathbf{1}_{x}=1$ if $x$ is True, 0 otherwise.

The commonly used function ${\mathcal{M}}$ of evaluation metrics (Krichene and
Rendle 2020) are Recall, Precision, AUC, NDCG, and AP. For example:

$\begin{split}&Recall@K=\frac{1}{M}\sum_{u=1}^{M}{\bf 1}_{R_{u}\leq
K}\end{split}$ (3)

###  2.1 Item-Sampling Top-K Evaluation

In the item-sampling based top-K evaluation scenario, for a given user $u$ and
his/her relevant item $i_{u}$, another $n-1$ items from the entire item set
$I$ are sampled. The union of sampled items and $i_{u}$ is $I_{u}$ ($i_{u}\in
I_{u}$, $|I_{u}|=n$). The recommendation model then returns the rank of
$i_{u}$ among $I_{u}$, denoted as $r_{u}$ (again, $R_{u}$ is the rank against
the entire set of items $I$).

Given this, a list of studies (Koren 2008; He et al. 2017) simply replaces
$R_{u}$ with $r_{u}$ for (top-$K$) evaluation. Sampled evaluation metric
denoted as :

$T_{S}\triangleq\frac{1}{M}\sum_{u=1}^{M}{\bf 1}_{r_{u}\leq
K}\cdot{\mathcal{M}}(r_{u})$ (4)

It’s obvious that $r_{u}$ and $R_{u}$ differ substantially, for example,
$r_{u}\in[1,n]$ whereas $R_{u}\in[1,N]$. Therefore, for the same $K$, the
item-sampling top-K metrics and the global top-K metrics correspond to
distinct measures (no direct relationship): $T\neq T_{S}$ ($Recall@K\neq
Recall_{S}@K$). This problem is highlighted in (Krichene and Rendle 2020;
Rendle 2019), referring to these two metrics being inconsistent. From
perspective of statistical inference, the basic sampling-based top-$K$ metric
$T_{S}@K$ is not a reasonable or good estimator (Lehmann and Casella 2006) of
$T@K$.

Li et al. (2020) showed that for some of the most commonly used metrics, the
top-K Recall/HitRatio, there is a mapping function $f$ (approximately linear),
such that $Recall@f(k)\approx{Recall}_{S}@k$. Thus, they give an intuitive
explanation on how to look at a sampling top-$K$ metrics (on Recall) linking
it the same global metric but at a different rank/location.

There are two recent works (see related works in Appendix A) studying the
general metric estimation problem based on the item sampling metrics.
Specifically, given the sampling ranked results in the test set,
$\\{r_{u}\\}^{M}_{u=1}$, how to infer/approximate the $T$ from Eq. 1 or more
commonly Eq. 2, without the knowledge $\\{R_{u}\\}_{u=1}^{M}$?

Two Problems: We consider two fundamental (open) questions for item-sampling
estimation: 1) What is the optimal estimator following for (Krichene and
Rendle 2020)? (Their methods does not directly target to minimizing the
estimation errors). 2) By solving the first problem and the MLE method from
(Jin et al. 2021b), we observe the best effort using the basic item sampling
still fails to recover accurately on the global top-$K$ metrics when $K$ is
small, as well as the rank distribution for the top spots. Those “blind spots”
seem to stemming from the inherent (information) limitation of item sampling
methods, not on the estimators. How can we effectively address such item-
sampling limitations? Next, we will introduce methods to address these two
problems.

##  3 New Estimator for Item-Sampling

In this section, we introduce a new estimator which aims to directly minimize
the expected errors between the item-sampling based top-$K$ metrics and the
global top-$K$ metrics. Here, we consider a similar strategy as (Krichene and
Rendle 2020) though our objective function is different and aims to explicitly
minimize the expected error. We aim to search for a sampled metric
$\widehat{\mathcal{M}}(r)$ to approach $\widehat{T}\approx T$:

$\begin{split}\widehat{T}&=\sum_{r=1}^{n}\tilde{P}(r)\cdot\widehat{\mathcal{M}}(r)=\frac{1}{M}\sum_{u=1}^{M}\widehat{\mathcal{M}}(r_{u})\\\
&\approx\frac{1}{M}\sum_{u=1}^{M}{\mathcal{M}}(R_{u})=\sum_{R=1}^{N}\tilde{P}(R)\cdot{\mathcal{M}}(R)=T\end{split}$

where $\tilde{P}(r)=\frac{1}{M}\sum\limits_{r=1}^{M}\mathbf{1}_{r_{u}=r}$ is
the empirical sampled rank distribution and $\widehat{\mathcal{M}}(r)$ is the
adjusted discrete metric function. An immediately observation is:

$\begin{split}\operatorname*{\mathbb{E}}\widehat{T}&=\sum_{r=1}^{n}\operatorname*{\mathbb{E}}[\tilde{P}(r)]\cdot\widehat{\mathcal{M}}(r)=\sum_{r=1}^{n}{P}(r)\cdot\widehat{\mathcal{M}}(r)\end{split}$
(5)

Following the classical statistical inference (Casella and Berger 2002), the
optimality of an estimator is measured by Mean Squared Error (more derivation
in Appendix C):

$\operatorname*{\mathbb{E}}[T-\sum_{R=1}^{N}P(R)\mathcal{M}(R)]^{2}\\\ $ (6)
$\begin{split}=&\Big{(}\sum_{r=1}^{n}\sum_{R=1}^{N}P(r|R)P(R)\widehat{\mathcal{M}}(r)-\sum_{R=1}^{N}P(R)\mathcal{M}(R)\Big{)}^{2}\\\
+&\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\sum_{R=1}^{N}\tilde{P}(r|R)P(R)\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}\sum_{R=1}^{N}P(r|R)P(R)\widehat{\mathcal{M}}(r)]^{2}\end{split}$

Remark that $\tilde{P}(r|R)$ is the empirical conditional sampling rank
distribution given a global rank $R$. We next use a Jensen’s inequality to
bound the first term in (Eq. 6). Specifically, we may treat
$\sum_{r=1}^{n}P(r|R)\widehat{\mathcal{M}}(r)-\mathcal{M}(R)$ as a random
variable and use
$(\operatorname*{\mathbb{E}}X)^{2}\leq\operatorname*{\mathbb{E}}X^{2}$ to
obtain

$\begin{split}&\Big{(}\sum_{r=1}^{n}\sum_{R=1}^{N}P(r|R)P(R)\widehat{\mathcal{M}}(r)-\sum_{R=1}^{N}P(R)\mathcal{M}(R)\Big{)}^{2}\\\
&\leq\sum_{R=1}^{N}P(R)\Big{(}\sum_{r=1}^{n}P(r|R)\widehat{\mathcal{M}}(r)-\mathcal{M}(R)\Big{)}^{2}\end{split}$

Therefore, we have

$\begin{split}&\operatorname*{\mathbb{E}}[\widehat{T}-\sum_{R=1}^{N}P(R)\mathcal{M}(R)]^{2}\\\
&\leq\underbrace{\sum_{R=1}^{N}P(R)\Big{\\{}\Big{(}\sum_{r=1}^{n}P(r|R)\widehat{\mathcal{M}}(r)-\mathcal{M}(R)\Big{)}^{2}}_{\mathcal{L}_{1}}\\\
&+\underbrace{\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\tilde{P}(r|R)\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}P(r|R)\widehat{\mathcal{M}}(r)]^{2}\Big{\\}}}_{\mathcal{L}_{2}}.\end{split}$

Let $\mathcal{L}=\mathcal{L}_{1}+\mathcal{L}_{2}$, which gives an upper bound
on the expected MSE. Therefore, our goal is to find $\widehat{\mathcal{M}}(r)$
to minimize $\mathcal{L}$. We remark that a seemingly innocent application of
Jensen’s inequality results in an optimization objective that possesses a
range of interesting properties:

1\. Statistical structure. The objective has a variance-bias trade-off
interpretation, i.e.,

$\mathcal{L}_{1}=\sum\limits_{R=1}^{N}{P(R)\Big{(}{\operatorname*{\mathbb{E}}(\widehat{\mathcal{M}}(r)|R)-M(R)}\Big{)}^{2}}$
(7)
$\mathcal{L}_{2}=\sum\limits_{R=1}^{N}{\frac{1}{M}Var(\widehat{\mathcal{M}}(r)|R)}$
(8)

where $\mathcal{L}_{1}$ can be interpreted as a bias term and
$\mathcal{L}_{2}$ can be interpreted as a variance term. Note that while
Krichene and Rendle (2020) also introduce an variance-bias tradeoff objective,
their objective is constructed from heuristics and contains a hyper-parameter
(that determines the relative weight between bias and variance) that needs to
be tuned in an ad-hoc manner. Here, because our objective is constructed from
direct optimization of the MSE, it is more principled and also removes
dependencies on hyper-parameters. See Section 3.1 for proving Eq. 8 ( Eq. 7 is
trivial) and Section 3.2 for more comparison against estimators proposed in
(Krichene and Rendle 2020).

2\. Algorithmic structure. while the objective is not convex, we show that the
objective can be expressed in a compact manner using matrices and we can find
the optimal solution in a fairly straightforward manner. In other words,
Jensen’s inequality substantially simplifies the computation at the cost of
having a looser upper bound. See Section 3.2.

3\. Practical performance. Our experiments also confirm that the new estimator
is effective ( Section 5), which suggests that Jensen’s inequality makes only
inconsequential and moderate performance impact to the estimator’s quality.

###  3.1 Analysis of ${\mathcal{L}}_{2}$

To analyze ${\mathcal{L}}_{2}$, let us take a close look of $\tilde{P}(r|R)$.
Formally, let $X_{r}$ be the random variable representing the number of items
at rank $r$ in the item-sampling data whose original rank in the entire item
set is $R$. Then, we rewrite $\tilde{P}(r|R)=\frac{X_{r}}{M\cdot P(R)}$.
Furthermore, it is easy to observe $(X_{1},\cdots X_{n})$ follows the
multinomial distribution $Multi(P(1|R),\cdots,P(n|R))$ (See $P(r|R)$ defined
in Table 4). We also have:

$\begin{split}&\operatorname*{\mathbb{E}}[X_{r}]=M\cdot P(R)\cdot P(r|R)\\\
&Var[X_{r}]=M\cdot P(R)\cdot P(r|R)(1-P(r|R))\end{split}$ (9)

Next, let us define a new random variable
$\mathcal{B}\triangleq\sum\limits_{r}^{n}{\widehat{\mathcal{M}}(r)X_{r}}$,
which is the weighted sum of random variables under a multinomial
distribution. According to Appendix D, its variance is give by:

$\begin{split}&Var[\mathcal{B}]=\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}{X_{r}}\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}{\operatorname*{\mathbb{E}}[X_{r}]}\widehat{\mathcal{M}}(r)]^{2}\\\
&=M\cdot
P(R)\Big{(}\sum\limits_{r}^{n}{\widehat{\mathcal{M}}^{2}(r)P(r|R)}-\big{(}\sum\limits_{r}^{n}{\widehat{\mathcal{M}}(r)P(r|R)}\big{)}^{2}\Big{)}\end{split}$

${\mathcal{L}}_{2}$ can be re-written (see Appendix E) as:

$\mathcal{L}_{2}=\sum\limits_{R=1}^{N}{\frac{1}{M}Var(\widehat{\mathcal{M}}(r)|R)}$

###  3.2 Closed Form Solution and its Relationship to Bias-Variance Estimator

We can rewrite $\mathcal{L}$ as a matrix format (see Appendix F) and
optimizing it corresponding to a constraint least square optimization and its
solution:

$\begin{split}\mathcal{L}=||\sqrt{D}A\mathbf{x}-\sqrt{D}\mathbf{b}||^{2}_{F}+\frac{1}{M}||\sqrt{\Lambda}_{1}\mathbf{x}||^{2}_{F}-\frac{1}{M}||A\mathbf{x}||^{2}_{F}\end{split}$
(10)
$\begin{split}\mathbf{x}=\Big{(}A^{T}DA-\frac{1}{M}A^{T}A+\frac{1}{M}\Lambda_{1}\Big{)}^{-1}A^{T}D\mathbf{b}\end{split}$
(11)

where $M$ is the number of users and $\mathcal{M}$ is metric function,
$diagM(\cdot)$ is a diagonal matrix:

$\begin{split}\mathbf{x}&=\begin{bmatrix}\widehat{\mathcal{M}}(r=1)\\\
\vdots\\\
\widehat{\mathcal{M}}(r=n)\end{bmatrix}\quad\mathbf{b}=\begin{bmatrix}\mathcal{M}(R=1)\\\
\vdots\\\ \mathcal{M}(R=N)\end{bmatrix}\in\mathbb{R}^{N}\\\
A_{R,r}&=P(r|R)\in\mathbb{R}^{N\times n}\quad
D=diagM\big{(}P(R)\big{)}\in\mathbb{R}^{N\times N}\\\
\Lambda_{1}&=diagM\big{(}\sum\limits_{R=1}^{N}P(r|R)\big{)}\in\mathbb{R}^{n\times
n}\\\ \end{split}$

Relationship to the BV Estimator: The bias-variance trade-off is given by
(Krichene and Rendle 2020):

$\begin{split}\mathcal{L}_{BV}&=\underbrace{\sum\limits_{R=1}^{N}P(R)(\operatorname*{\mathbb{E}}[\widehat{\mathcal{M}}(r)|R]-M(R))^{2}}_{{\mathcal{L}}_{1}}\\\
&+\underbrace{\sum\limits_{R=1}^{N}P(R)\gamma\cdot
Var[\widehat{\mathcal{M}}(r)|R]}_{{\mathcal{L}}_{2}}\end{split}$

We observe the main difference between the BV and our new estimator is on the
${\mathcal{L}}_{2}$ components (variance components): for our estimator, each
$Var[\widehat{\mathcal{M}}(r)|R]$ is regularized by $1/M$ ($M$ is the number
of testing users), where in BV, this term is regularized by $P(R)\gamma$. Our
estimator reveals that as the number of users increase, the variance in the
${\mathcal{L}}_{2}$ components will continue to decrease, where as the BV
estimator does not consider this factor. Thus, as the user size increases, BV
estimator still needs to deal with ${\mathcal{L}}_{2}$ or has to manually
adjust $\gamma$.

Finally, both BV and the new estimator rely on prior distribution $P(R)$,
which is unknown. In (Krichene and Rendle 2020), the uniform distribution is
used for the estimation purpose. In this paper, we propose to leverage the
latest approaches in (Jin et al. 2021b) which provide more accurate estimation
of $P(R)$ for this purpose. The experimental results in Section 5 will confirm
the validity of using such distribution estimations.

##  4 Adaptive Item-Sampling Estimator

Figure 1: Top is distribution of $r_{u}$ with sample set size $n=100$. Rank
$r=1$ is highlighted. Bottom is the relative error of MLE estimator for
different top-$K$. The result is obtained by EASE model (Steck 2019) over
ml-20m dataset.

###  4.1 Blind Spot and Adaptive Sampling

In recommendation, top ranked items are vital, thus it’s more crucial to
obtain an accurate estimation for these top items. However current sampling
approaches treat all items equally and particularly have difficulty in
recovering the the global top-$K$ metrics when K is small. In top of Fig. 1,
we plot the distribution of target items’ rank in the sample set and observe
that most target items rank top 1 (highlighted in red). This could lead to the
”blind spot” problem - when $K$ gets smaller, the estimation of basic
estimators are more inaccurate (see bottom of Fig. 1). Intuitively, when
$r_{u}=1$, it does not mean its global rank $R_{u}$ being $1$, instead, its
expected global rank may be around $100$ (assuming $N=10K$ and sample set size
$n=100$). And the estimation granularity is only at around 1% ($1/n$) level.
This blind spot effect bring a big drawback for current estimators.

Based on above discussion, we propose an adaptive sampling strategy, which
increases acceptable test sample size for users whose target item ranks top
(say $r_{u}=1$) in the sampled data. When $r_{u}=1$, we continue doubling the
sample size until $r_{u}\neq 1$ or until sample size reaches a predetermined
ceiling. See Algorithm 1 (and detailed explanation in Appendix H). The
benefits of this adaptive strategy are two folds: high granularity, with more
items sampled, the counts of $r_{u}=1$ shall reduce, which could further
improve the estimating accuracy; efficiency, we iteratively sample more items
for users whose $r_{u}=1$ and the empirical experiments (Table 2) confirm that
small average adaptive sample size (compared to uniform sample size) is able
to achieve significant better performance.

Algorithm 1 Adaptive Sampling Process

INPUT: Recommender Model $RS$, test user set $\mathcal{U}$, initial size
$n_{0}$, terminal size $n_{max}$

OUTPUT: $\\{(u,r_{u},n_{u})\\}$

1:for all $u\in\mathcal{U}$ do

2: sampling $n_{0}-1$ items, form the sample set $I^{s}_{u}$

3: $n_{u}=n_{0}$, $r_{u}=RS(i_{u},I^{s}_{u})$

4: while $r_{u}=1$ and $n_{u}\neq n_{max}$ do

5: sampling extra $n_{u}$ items, form the new set $I^{s}_{u}$

6: $n_{u}=2n_{u}$, $r_{u}=RS(i_{u},I^{s}_{u})$

7: end while

8: record $n_{u},r_{u}$ for user $u$

9:end for

###  4.2 Maximum Likelihood Estimation by EM

To utilize the adaptive item sampling for estimating the global top-$K$
metrics, we review two routes: 1) approaches from (Krichene and Rendle 2020)
and our aformentioned new estimators in this paper; 2) methods based on MLE
and EM (Jin et al. 2021b). Since every user has different number of item
samples, we found the first route is hard to extend (which requires equal
sample size); but luckily the second route is much more flexible and can be
easily generalized to this situation.

To begin with, we note that for any user $u$ (his/her test item ranks $r_{u}$
in the sample set (with size $n_{u}$) and ranks $R_{u}$ (unknown)), its rank
$r_{u}$ follows a binomial distribution:

$\begin{split}P(r=r_{u}|R=R_{u};n_{u})=Bin(r_{u}-1;n_{u}-1,\theta_{u})\\\
\end{split}$ (12)

Given this, let $\boldsymbol{\Pi}=(\pi_{1},\dots,\pi_{R},\dots,\pi_{N})^{T}$
be the parameters of the mixture of binomial distributions, $\pi_{R}$ is the
probability for user population ranks at position $R$ globally. And then we
have $p(r_{u}|\boldsymbol{\Pi})=\sum_{R=1}^{N}\pi_{R}\cdot
p(r_{u}|\theta_{R};n_{u})$, where
$p(r_{u}|\theta_{R};n_{u})=Bin(r_{u}-1;n_{u}-1,\theta_{R})$. We can apply the
maximal likelihood estimation (MLE) to learn the parameters of the mixture of
binomial distributions ($MB$), which naturally generalizes the EM procedure
(details see Appendix G) used in (Jin et al. 2021b), where each user has the
same $n$ samples:

$\begin{split}\phi(R_{uk})&=P(R_{u}=k|r_{u};\bm{\pi}^{old})\\\
\pi^{new}_{k}&=\frac{1}{M}\sum\limits_{u=1}^{M}\phi(R_{uk})\end{split}$

When the process converges, we obtain $\boldsymbol{\Pi}^{*}$ and use it to
estimate $\boldsymbol{P}$, i.e., $\widehat{P}(R)=\pi^{*}_{R}$. Then, we can
use $\widehat{P}(R)$ in Eq. 17 to estimate the desired metric $metric@K$. The
overall time complexity is linearly with respect to the sample size
$O(t\sum{n_{u}})$ where $t$ is the iteration number.

###  4.3 Sampling Size UpperBound

Figure 2: Sample efficiency w.r.t terminal size. The illustration result is
obtained by EASE model (Steck 2019) over yelp dataset while it consistently be
observed in other datasets.

Now, we consider how to determine the terminal size $n_{max}$. We take the
post-analysis over the different terminal sizes and investigate the average
sampling cost, which introduce the concept sampling efficiency, see Fig. 2.
Formally, we first select a large number $n_{max}\approx N$ and repeat the
aforementioned adaptive sampling process. For each user, his/her sampling set
size could be one of
$\\{n_{0},n_{1}=2n_{0},n_{2}=4n_{0},\dots,n_{t}=n_{max}\\}$. And there are
$m_{j}$ users whose sample set size is $n_{j}$ $(j=0,1,\dots,t)$. The average
sampling cost for each size $n_{j}$ can be defined heuristically:

$\begin{split}C_{j}&=\frac{(M-\sum\limits_{p=0}^{j-1}{m_{p}})\times(n_{j}-n_{j-1})}{m_{j}}\quad
j\neq 0,t\\\ C_{0}&=\frac{M\times n_{0}}{m_{0}}\end{split}$ (13)

The intuition behind Eq. 13 is: at $j$-th iteration, we independently sample
$n_{j}-n_{j-1}$ items for total $M-\sum\limits_{p=0}^{j-1}{m_{p}}$ users, and
there are $m_{j}$ users whose rank $r_{u}>1$. $C_{j}$ is the average items to
be sampled to get a user whose $r_{u}>1$, which reflects sampling efficiency.
In Fig. 2, we can see that when sample reaches $3200$, the sampling efficiency
will reduce quickly (the average cost $C_{j}$ increases fast). Such post
analysis provides insights on how to balance the sample size and sampling
efficiency. In this case, we observe $n_{max}=3200$ can be a reasonable
choice. Even though different dataset can pickup different threshold, we found
in practice $3200$ can serve as a default choice to start, and achieve pretty
good performance for the estimation accuracy.

##  5 Experiments

Table 1: The average relative errors between estimated $Recall@K$ ($K$ from
$1$ to $50$) and the true ones. Unit is $\%$. In each row, the smallest two
results are highlighted in bold, indicating the most accurate results. Sample
set size $n=100$.

dataset | Models | sample set size 100
---|---|---
baseline | this paper
MES | MLE | BV | BV_MES | BV_MLE | MN_MES | MN_MLE
pinterest-20 | EASE | 5.86$\scriptstyle\pm$2.26 | 5.54$\scriptstyle\pm$1.85 | 8.11$\scriptstyle\pm$2.00 | 5.05$\scriptstyle\pm$1.46 | 5.14$\scriptstyle\pm$1.46 | 5.00$\scriptstyle\pm$1.39 | 5.10$\scriptstyle\pm$1.34
MultiVAE | 4.17$\scriptstyle\pm$2.91 | 3.34$\scriptstyle\pm$2.07 | 2.75$\scriptstyle\pm$1.61 | 2.89$\scriptstyle\pm$1.74 | 2.88$\scriptstyle\pm$1.74 | 2.75$\scriptstyle\pm$1.66 | 2.75$\scriptstyle\pm$1.68
NeuMF | 5.17$\scriptstyle\pm$2.74 | 4.28$\scriptstyle\pm$1.95 | 4.23$\scriptstyle\pm$1.79 | 3.83$\scriptstyle\pm$1.59 | 3.84$\scriptstyle\pm$1.72 | 3.60$\scriptstyle\pm$1.50 | 3.76$\scriptstyle\pm$1.44
itemKNN | 5.90$\scriptstyle\pm$2.20 | 5.80$\scriptstyle\pm$1.60 | 8.93$\scriptstyle\pm$1.70 | 5.11$\scriptstyle\pm$1.22 | 5.31$\scriptstyle\pm$1.25 | 5.09$\scriptstyle\pm$1.15 | 5.26$\scriptstyle\pm$1.14
ALS | 4.19$\scriptstyle\pm$2.37 | 3.44$\scriptstyle\pm$1.68 | 3.17$\scriptstyle\pm$1.34 | 3.05$\scriptstyle\pm$1.39 | 3.07$\scriptstyle\pm$1.42 | 2.86$\scriptstyle\pm$1.27 | 2.90$\scriptstyle\pm$1.28
yelp | EASE | 8.08$\scriptstyle\pm$4.94 | 7.89$\scriptstyle\pm$4.70 | 18.60$\scriptstyle\pm$2.78 | 6.10$\scriptstyle\pm$3.74 | 6.56$\scriptstyle\pm$3.90 | 4.84$\scriptstyle\pm$2.17 | 5.61$\scriptstyle\pm$2.30
MultiVAE | 9.33$\scriptstyle\pm$6.61 | 7.67$\scriptstyle\pm$4.94 | 9.70$\scriptstyle\pm$3.22 | 6.84$\scriptstyle\pm$4.10 | 6.80$\scriptstyle\pm$4.04 | 4.30$\scriptstyle\pm$1.27 | 4.35$\scriptstyle\pm$1.31
NeuMF | 15.09$\scriptstyle\pm$6.24 | 15.47$\scriptstyle\pm$5.55 | 22.40$\scriptstyle\pm$3.17 | 13.14$\scriptstyle\pm$4.55 | 13.92$\scriptstyle\pm$4.70 | 13.46$\scriptstyle\pm$2.43 | 14.50$\scriptstyle\pm$2.45
itemKNN | 9.25$\scriptstyle\pm$4.87 | 9.62$\scriptstyle\pm$4.88 | 23.24$\scriptstyle\pm$2.16 | 7.69$\scriptstyle\pm$4.09 | 8.15$\scriptstyle\pm$4.17 | 7.74$\scriptstyle\pm$2.08 | 8.75$\scriptstyle\pm$2.08
ALS | 14.31$\scriptstyle\pm$3.96 | 13.68$\scriptstyle\pm$3.51 | 15.14$\scriptstyle\pm$1.86 | 13.43$\scriptstyle\pm$3.16 | 13.26$\scriptstyle\pm$3.08 | 11.68$\scriptstyle\pm$0.88 | 11.57$\scriptstyle\pm$0.83

In this section, we evaluate the performance of the new proposed estimator in
Eq. 11 compared to the baselines from (Krichene and Rendle 2020; Jin et al.
2021b) and validate the effectiveness and efficiency of adaptive sampling
based MLE (adaptive MLE). Specifically, we aim to answer three questions:

Question 1. How do the new estimators in Section 3 perform compared to
estimators based on learning empirical distributions (i.e., $MLE$, $MES$ in
(Jin et al. 2021b)), and to the $BV$ approach in (Krichene and Rendle 2020)?

Question 2. How effective and efficient the adaptive item-sampling evaluation
method adaptive MLE is, compared with the best estimators for the basic (non-
adaptive) item sampling methods in Section 3?

Question 3. How accurately can these estimators find the best model (in terms
of the global top-K metric) among a list of recommendation models?

#### Experimental Setup

We take three widely-used datasets for recommendation system research,
$pinterest-20$, $yelp$, $ml-20m$. See also Appendix I for dataset statistics.
We follow the work (Jin et al. 2021b) to adopt five popular recommendation
algorithms, including three non-deep-learning methods (itemKNN (Deshpande and
Karypis 2004), ALS (Hu, Koren, and Volinsky 2008), and EASE (Steck 2019)) and
two deep learning ones (NeuMF (He et al. 2017) and MultiVAE (Liang et al.
2018)). Three most popular top-K metrics: $Recall$, $NDCG$ and $AP$ are
utilized for evaluating the recommendation models.

#### Estimating Procedure

There are $M$ users and $N$ items. Each user $u$ is associated with a target
item $i_{u}$. The learned recommendation algorithm/model $A$ would compute the
ranks $\\{R_{u}\\}_{u=1}^{M}$ among all items called global ranks and the
ranks $\\{r_{u}\\}_{u=1}^{M}$ among sampled items called sampled ranks.
Without the knowledge of $\\{R_{u}\\}_{u=1}^{M}$, the estimator tries to
estimate the global metric defined in Eq. 2 based on $\\{r_{u}\\}_{u=1}^{M}$.
We repeat experiments $100$ times, deriving $100$ distinct
$\\{r_{u}\\}_{u=1}^{M}$ set. Below reports experimental results that are
averaged on these $\mathbf{100}$ repeats.

Due to the space limitation, we report representative experimental results in
the following and leave baselines, dataset statistics and more results in the
Appendix I.

### Q1. Accuracy of the Estimators for Basic Item-Sampling

Here, we aim to answer Question 1: comparing the new estimators in Section 3
perform against the state-of-the-art methods from (Krichene and Rendle 2020;
Jin et al. 2021b) under the basic item sampling scheme. Different from (Jin et
al. 2021b), where authors list all the estimating as well as the true results
for $metric@10$ and conclude, here we would quantify the accuracy of each
estimator in terms of relative error, leading to a more rigorous and reliable
comparison. Specifically, we compute the true global $metric@k$ ( $k$ from $1$
to $50$), then we average the absolute relative error between the estimated
$metric@k$ from each estimator and the true one.

The estimators include $BV$ (with the tradeoff parameter $\gamma=0.01$) from
(Krichene and Rendle 2020), $MLE$ (Maximal Likelihood Estimation), $MES$
(Maximal Entropy with Squared distribution distance, where $\eta=0.001$) from
(Jin et al. 2021b) and newly proposed estimators Eq. 11. Table 1 (see Table 6
in Appendix for a complete result version.) presents the average relative
error of the estimators in terms of $Recall@K$ ($k$ from $1$ to $50$). The
results of $NDCG@K$ and $AP@K$ are in Appendix I. We highlight the most and
the second-most accurate estimator. For instance, for model $EASE$ in dataset
$pinterest-20$ (line $1$ of Table 1), the estimator $MN\\_MES$ is the most
accurate one with $5.00\%$ average relative error compared to its global
$Recall@K$ ($K$ from $1$ to $50$).

Overall, we observe from Table 1 that $MN\\_MES$ and $MN\\_MLE$ are among the
most, or the second-most accurate estimators. And in most cases, they
outperform the others significantly. Meantime, they have smaller deviation
compared to their prior estimators $MES$ and $MLE$. In addition, we also
notice that the estimators with the knowledge of some reasonable prior
distribution ($BV\\_MES$, $MN\\_MES$, $BV\\_MLE$, $MN\\_MLE$) could achieve
more accurate results than the others. This indicate that these estimators
could better help the distribution to converge.

### Q2. Performance of Adaptive Sampling

Here, we aim to answer Question 2: comparing the adaptive item sampling method
adaptive MLE, comparing with the best estimators for the basic (non-adaptive)
item sampling methods, such as $BV\\_MES$, $MN\\_MES$, $BV\\_MLE$, $MN\\_MLE$.

Table 2: The average relative errors between estimated $NDCG@K$ ($K$ from $1$
to $50$) and the true ones. Unit is $\%$. In each row, the smallest relative
error is highlighted, indicating the most accurate result.

Dataset | Models | Fix Sample | Adaptive Sample
---|---|---|---
BV_MES | BV_MLE | MN_MES | MN_MLE | average size | adaptive MLE
| sample set size n = 500 |
pinterest-20 | EASE | 3.87$\scriptstyle\pm$2.13 | 4.33$\scriptstyle\pm$2.23 | 4.17$\scriptstyle\pm$2.45 | 4.33$\scriptstyle\pm$2.50 | 307.74$\scriptstyle\pm$1.41 | 1.46$\scriptstyle\pm$0.63
MultiVAE | 2.66$\scriptstyle\pm$1.75 | 2.58$\scriptstyle\pm$1.75 | 3.26$\scriptstyle\pm$2.14 | 3.07$\scriptstyle\pm$2.09 | 286.46$\scriptstyle\pm$1.48 | 1.67$\scriptstyle\pm$0.70
NeuMF | 2.82$\scriptstyle\pm$1.98 | 2.79$\scriptstyle\pm$1.96 | 3.24$\scriptstyle\pm$2.30 | 3.22$\scriptstyle\pm$2.27 | 259.77$\scriptstyle\pm$1.28 | 1.73$\scriptstyle\pm$0.83
itemKNN | 3.99$\scriptstyle\pm$2.22 | 4.18$\scriptstyle\pm$2.24 | 4.23$\scriptstyle\pm$2.47 | 4.06$\scriptstyle\pm$2.44 | 309.56$\scriptstyle\pm$1.31 | 1.42$\scriptstyle\pm$0.67
ALS | 3.35$\scriptstyle\pm$1.89 | 3.24$\scriptstyle\pm$1.87 | 3.90$\scriptstyle\pm$2.24 | 3.80$\scriptstyle\pm$2.23 | 270.75$\scriptstyle\pm$1.22 | 1.84$\scriptstyle\pm$1.07
| sample set size n = 500 |
yelp | EASE | 5.63$\scriptstyle\pm$3.73 | 5.48$\scriptstyle\pm$3.66 | 4.03$\scriptstyle\pm$2.53 | 4.04$\scriptstyle\pm$2.53 | 340.79$\scriptstyle\pm$2.03 | 3.55$\scriptstyle\pm$2.00
MultiVAE | 7.68$\scriptstyle\pm$5.86 | 7.48$\scriptstyle\pm$5.74 | 5.77$\scriptstyle\pm$3.87 | 5.64$\scriptstyle\pm$3.82 | 288.70$\scriptstyle\pm$2.24 | 5.09$\scriptstyle\pm$2.60
NeuMF | 9.34$\scriptstyle\pm$5.50 | 9.55$\scriptstyle\pm$5.50 | 8.43$\scriptstyle\pm$4.07 | 8.91$\scriptstyle\pm$4.13 | 290.62$\scriptstyle\pm$2.11 | 4.43$\scriptstyle\pm$2.55
itemKNN | 5.01$\scriptstyle\pm$2.99 | 4.99$\scriptstyle\pm$2.96 | 3.65$\scriptstyle\pm$2.28 | 3.71$\scriptstyle\pm$2.29 | 369.16$\scriptstyle\pm$2.51 | 3.67$\scriptstyle\pm$2.73
ALS | 13.39$\scriptstyle\pm$7.34 | 13.94$\scriptstyle\pm$7.61 | 12.57$\scriptstyle\pm$5.46 | 13.67$\scriptstyle\pm$5.80 | 297.07$\scriptstyle\pm$2.29 | 5.48$\scriptstyle\pm$3.34

Table 3: Accuracy of predicting of the winner models for different datasets.
Values in table is the number of correct predictions over 100 repeats. The
larger number, the better estimator

Dataset | Top-K | Metrics | Fix Sample | AdaptiveSample
---|---|---|---|---
BV_MES | BV_MLE | MN_MES | MN_MLE | adaptive MLE
sample set size n = 500 | sample set size $260\sim 310$
pinterest-20 | 10 | RECALL | 69 | 73 | 67 | 69 | 78
NDCG | 58 | 59 | 58 | 60 | 84
AP | 54 | 57 | 52 | 52 | 68
20 | RECALL | 69 | 73 | 70 | 74 | 81
NDCG | 69 | 73 | 68 | 73 | 79
AP | 57 | 60 | 54 | 56 | 69

Table 2 (complete version in appendix Table 7) presents the average relative
error of the estimators in terms of $NDCG@K$ ($k$ from $1$ to $50$). We
highlight the most accurate estimator. For the basic item sampling, we choose
$500$ sample size for datasets $pinterest-20$ and $yelp$, and $1000$ sample
size for dataset $ml-20m$. The upperbound threshold $n_{max}$ is set to
$3200$.

We observe the adaptive sampling uses much less sample size (typically
$200-300$ vs $500$ on $pinterest-20$, $yelp$ datasets and $700-800$ vs $1000$
on $ml-20m$ dataset). Particularly, the relative error of the adaptive
sampling is significantly smaller than that of the basic sampling methods. On
the first ($pinterest-20$) and third ($ml-20m$) datasets, the relative errors
have reduced to less than $2\%$. In other words, the adaptive method has been
much more effective (in terms of accuracy) and efficient (in terms of sample
size). This also confirms the benefits in addressing the “blind spot” issue,
which provides higher resolution to recover global $K$ metrics for small $K$
($K\leq 50$ here).

### Q3. Estimating the Winner

Table 3 (complete version in appendix Table 8) indicates the results of among
the $100$ repeats, how many times that a estimator could match the best
recommendation algorithms for a given $metric@K$. More concretely, for a
global $metric@K$ (compute from Eq. 2), there exist a recommendation
algorithm/model which performs best called the winner. The estimator could
also estimate $metric@K$ for each algorithm based on its
$\\{r_{u}\\}_{u=1}^{M}$. Among these estimated $metric@K$, one can also find a
best recommendation model. Intuitively, if the estimator is accurate enough,
it could find the same winner as the truth. Thus, we counting the success time
that a estimator can find it as another measure of estimating accuracy. From
the Table 3, We observe that new proposed adaptive estimators could achieve
competitive or even better results to the baselines with much less average
sample cost.

##  6 Conclusion

In this paper, we propose first item-sampling estimators which explicitly
optimizes its mean square error with respect to the ground truth assuming the
prior of the rank distribution is given. Then we highlight the subtle
difference between the estimators from (Krichene and Rendle 2020) and ours,
and point out the potential issue of the former - failing to link the user
size with the variance. Furthermore, we address the limitation of the current
item sampling approach, whose typically do not have sufficient granularity to
recover the top $K$ global metrics when $K$ is small. We then propose an
effective adaptive item-sampling method. The experimental evaluation
demonstrate the new adaptive item sampling significantly improve both the
sampling efficiency and estimation accuracy. Our results provide a solid step
towards making item sampling available for the recommendation research and
practice. In the future, we would like to further investigate how to combine
item-sampling working with user-sampling to speedup the offline evaluation,
and investigate other aspects of the evaluation criteria such as fairness and
robustness.

## References

  * Casella and Berger (2002) Casella, G.; and Berger, R. 2002.  _Statistical Inference_.  Thomson Learning.
  * Cover and Thomas (2006) Cover, T. M.; and Thomas, J. A. 2006.  _Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)_.  USA: Wiley-Interscience.  ISBN 0471241954.
  * Cremonesi et al. (2011) Cremonesi, P.; Garzotto, F.; Negro, S.; Papadopoulos, A.; and Turrin, R. 2011.  Comparative evaluation of recommender system quality.  In _CHI’11 Extended Abstracts on Human Factors in Computing Systems_ , 1927–1932.
  * Cremonesi, Koren, and Turrin (2010) Cremonesi, P.; Koren, Y.; and Turrin, R. 2010.  Performance of Recommender Algorithms on Top-n Recommendation Tasks.  In _RecSys’10_.
  * Dacrema et al. (2019) Dacrema, M. F.; Boglio, S.; Cremonesi, P.; and Jannach, D. 2019.  A Troubling Analysis of Reproducibility and Progress in Recommender Systems Research.  arXiv:1911.07698.
  * Deshpande and Karypis (2004) Deshpande, M.; and Karypis, G. 2004.  Item-Based Top-N Recommendation Algorithms.  _ACM Trans. Inf. Syst._
  * Ebesu, Shen, and Fang (2018) Ebesu, T.; Shen, B.; and Fang, Y. 2018.  Collaborative Memory Network for Recommendation Systems.  In _SIGIR’18_.
  * Fayyaz et al. (2020) Fayyaz, Z.; Ebrahimian, M.; Nawara, D.; Ibrahim, A.; and Kashef, R. 2020.  Recommendation Systems: Algorithms, Challenges, Metrics, and Business Opportunities.  _applied sciences_ , 10(21): 7748.
  * Gruson et al. (2019) Gruson, A.; Chandar, P.; Charbuillet, C.; McInerney, J.; Hansen, S.; Tardieu, D.; and Carterette, B. 2019.  Offline Evaluation to Make Decisions About PlaylistRecommendation Algorithms.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , WSDM ’19, 420–428. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450359405.
  * He et al. (2017) He, X.; Liao, L.; Zhang, H.; Nie, L.; Hu, X.; and Chua, T.-S. 2017.  Neural Collaborative Filtering.  WWW ’17.
  * Hu et al. (2018) Hu, B.; Shi, C.; Zhao, W. X.; and Yu, P. S. 2018.  Leveraging Meta-Path Based Context for Top- N Recommendation with A Neural Co-Attention Model.  In _KDD’18_.
  * Hu, Koren, and Volinsky (2008) Hu, Y.; Koren, Y.; and Volinsky, C. 2008.  Collaborative filtering for implicit feedback datasets.  In _ICDM’08_.
  * Jin et al. (2021a) Jin, R.; Li, D.; Gao, J.; Liu, Z.; Chen, L.; and Zhou, Y. 2021a.  Towards a better understanding of linear models for recommendation.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, 776–785.
  * Jin et al. (2021b) Jin, R.; Li, D.; Mudrak, B.; Gao, J.; and Liu, Z. 2021b.  On Estimating Recommendation Evaluation Metrics under Sampling.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 4147–4154.
  * Koren (2008) Koren, Y. 2008.  Factorization Meets the Neighborhood: A Multifaceted Collaborative Filtering Model.  In _KDD’08_.
  * Krichene et al. (2019) Krichene, W.; Mayoraz, N.; Rendle, S.; Zhang, L.; Yi, X.; Hong, L.; Chi, E. H.; and Anderson, J. R. 2019.  Efficient Training on Very Large Corpora via Gramian Estimation.  In _ICLR’2019_.
  * Krichene and Rendle (2020) Krichene, W.; and Rendle, S. 2020.  On Sampled Metrics for Item Recommendation.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’20.
  * Krichene and Rendle (2022) Krichene, W.; and Rendle, S. 2022.  On sampled metrics for item recommendation.  _Commun. ACM_ , 65(7): 75–83.
  * Lehmann and Casella (2006) Lehmann, E. L.; and Casella, G. 2006.  _Theory of point estimation_.  Springer Science & Business Media.
  * Li et al. (2020) Li, D.; Jin, R.; Gao, J.; and Liu, Z. 2020.  On Sampling Top-K Recommendation Evaluation.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’20.
  * Liang et al. (2018) Liang, D.; Krishnan, R. G.; Hoffman, M. D.; and Jebara, T. 2018.  Variational Autoencoders for Collaborative Filtering.  In _WWW’18_.
  * Peng, Sugiyama, and Mine (2022) Peng, S.; Sugiyama, K.; and Mine, T. 2022.  Less is More: Reweighting Important Spectral Graph Features for Recommendation.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’22, 1273–1282. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450387323.
  * Rendle (2019) Rendle, S. 2019.  Evaluation metrics for item recommendation under sampling.  _arXiv preprint arXiv:1912.02263_.
  * Steck (2019) Steck, H. 2019.  Embarrassingly Shallow Autoencoders for Sparse Data.  _WWW’19_.
  * Wang et al. (2019) Wang, X.; Wang, D.; Xu, C.; He, X.; Cao, Y.; and Chua, T. 2019.  Explainable Reasoning over Knowledge Graphs for Recommendation.  In _The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI2019_.
  * Yang et al. (2018a) Yang, L.; Bagdasaryan, E.; Gruenstein, J.; Hsieh, C.-K.; and Estrin, D. 2018a.  OpenRec: A Modular Framework for Extensible and Adaptable Recommendation Algorithms.  In _WSDM’18_.
  * Yang et al. (2018b) Yang, L.; Cui, Y.; Xuan, Y.; Wang, C.; Belongie, S. J.; and Estrin, D. 2018b.  Unbiased Offline Recommender Evaluation for Missing-Not-at-Random Implicit Feedback.  In _RecSys’18_.
  * Zhao et al. (2021) Zhao, W. X.; Mu, S.; Hou, Y.; Lin, Z.; Chen, Y.; Pan, X.; Li, K.; Lu, Y.; Wang, H.; Tian, C.; Min, Y.; Feng, Z.; Fan, X.; Chen, X.; Wang, P.; Ji, W.; Li, Y.; Wang, X.; and Wen, J.-R. 2021.  RecBole: Towards a Unified, Comprehensive and Efficient Framework for Recommendation Algorithms.  In _In Proceedings of Conference on Information and Knowledge Management (CIKM ’21)_.

##  Appendix A Related Work: Efforts in Metric Estimation

There are two recent works studying the general metric estimation problem
based on the item sampling metrics. Specifically, given the sampling ranked
results in the test set, $\\{r_{u}\\}^{M}_{u=1}$, how to infer/approximate the
$T$ from Eq. 1 or more commonly Eq. 2, without the knowledge
$\\{R_{u}\\}_{u=1}^{M}$?

Krichene and Rendle’s approaches: (Krichene and Rendle 2020) develop a
discrete function $\widehat{\mathcal{M}}(r)$ so that:

$\begin{split}T&=\frac{1}{M}\sum_{u=1}^{M}\mathbf{1}_{R_{u}\leq
K}\cdot{\mathcal{M}}(R_{u})\\\
&\approx\frac{1}{M}\sum_{u=1}^{M}\widehat{\mathcal{M}}(r_{u})=\sum_{r=1}^{n}\tilde{P}(r)\widehat{\mathcal{M}}(r)=\widehat{T}\end{split}$
(14)

where $\tilde{P}(r)$ is the empirical rank distribution on the sampling data (
Table 4). They have proposed a few estimators based on this idea, including
estimators that use the unbiased rank estimators, minimize bias with
monotonicity constraint ($CLS$), and utilize Bias-Variance ($BV$) tradeoff.
Their study shows that only the last one ($BV$) is competitive. They further
derive a solution based on the Bias-Variance ($BV$) tradeoff:

$\begin{split}&\widehat{\mathcal{M}}=\Big{(}(1.0-\gamma)A^{T}A+\gamma\text{diag}(\boldsymbol{c})\Big{)}^{-1}A^{T}\boldsymbol{b}\\\
&A\in\mathbb{R}^{N\times n},\quad A_{R,r}=\sqrt{P(R)}P(r|R)\\\
&\boldsymbol{b}\in\mathbb{R}^{N},\quad b_{R}=\sqrt{P(R)}\mathcal{M}(R)\\\
&\boldsymbol{c}\in\mathbb{R}^{n},\quad
c_{r}=\sum\limits_{R}^{N}{P(R)P(r|R)}\end{split}$ (15)

Jin et al.’s Method: (Jin et al. 2021b) proposed different types of estimators
based on learning the empirical rank distribution $(P(R))_{R=1}^{N}$:

$T=\frac{1}{M}\sum_{u=1}^{M}\mathbf{1}_{R_{u}\leq
K}\cdot{\mathcal{M}}(R_{u})=\sum_{R=1}^{K}P(R)\cdot{\mathcal{M}}(R)$ (16)

Thus, if $P(R)$ can be estimated (by $\widehat{P}(R)$), then the metric Eq. 16
can be estimated by:

$\widehat{T}=\sum_{R=1}^{K}\widehat{P}(R)\cdot{\mathcal{M}}(R)$ (17)

They further proposed two approaches to learn the empirical rank distribution
$(P(R))_{R=1}^{N}$. The first approach is to learn the parameters of the
mixture of binomial distributions ($MB$) given $\\{r_{u}\\}_{u=1}^{M}$ based
on maximal likelihood estimation (MLE). The other approach for estimating a
(discrete) probability distribution is based on the principal of maximal
entropy (Cover and Thomas 2006).

##  Appendix B Notation

$M$ | # of users in test set
---|---
$N$ | # of total items
$I$ | the set of all items, and $|I|=N$
$i_{u}$ | target item for user $u$ in test set
$R_{u}$ | rank of item $i_{u}$ among $I$ for user $u$
$n$ | sample set size (1 target item, $n-1$ sampled items)
$I_{u}$ |  $I_{u}\backslash i_{u}$ consists of $n-1$ sampled items for $u$
$r_{u}$ | rank of item $i_{u}$ among $I_{u}$
$T$ | evaluation metric, e.g. $Recall$
$T_{S}$ | sampled evaluation metric, e.g. $Recall_{S}$
$\widehat{T}$ | estimated evaluation metric
Table 4: Definition of notations

##  Appendix C Rewriting of Eq. 6

$\begin{split}&\operatorname*{\mathbb{E}}[T-\sum_{R=1}^{N}P(R)\mathcal{M}(R)]^{2}\\\
=&\operatorname*{\mathbb{E}}[\operatorname*{\mathbb{E}}T-\sum_{R=1}^{N}P(R)\mathcal{M}(R)+T-\operatorname*{\mathbb{E}}T]^{2}\\\
=&\Big{(}\operatorname*{\mathbb{E}}T-\sum_{R=1}^{N}P(R)\mathcal{M}(R)\Big{)}^{2}+\operatorname*{\mathbb{E}}[T-\operatorname*{\mathbb{E}}T]^{2}\\\
=&\Big{(}\sum_{r=1}^{n}P(r)\widehat{\mathcal{M}}(r)-\sum_{R=1}^{N}P(R)\mathcal{M}(R)\Big{)}^{2}\\\
+&\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\tilde{P}(r)\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}P(r)\widehat{\mathcal{M}}(r)]^{2}\\\
=&\Big{(}\sum_{r=1}^{n}\sum_{R=1}^{N}P(r|R)P(R)\widehat{\mathcal{M}}(r)-\sum_{R=1}^{N}P(R)\mathcal{M}(R)\Big{)}^{2}\\\
+&\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\sum_{R=1}^{N}\tilde{P}(r|R)P(R)\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}\sum_{R=1}^{N}P(r|R)P(R)\widehat{\mathcal{M}}(r)]^{2}\end{split}$

##  Appendix D Linear Combination of Coefficients

Considering $X=(X_{1},\dots,X_{n})$ is the random variables of a sample $M$
times multinomial distribution with $n$ cells probabilities
$(\theta_{1},\dots,\theta_{n})$. We
have:$\frac{X_{i}}{M}\rightarrow\theta_{i},\text{ when }M\rightarrow\infty$

$\begin{split}&\operatorname*{\mathbb{E}}[{X_{i}}]=M\theta_{i}\quad
Var[X_{i}]=M\theta_{i}(1-\theta_{i})\\\
&Cov(X_{i},X_{j})=-M\theta_{i}\theta_{j}\end{split}$ (18)

Considering the a new random variable deriving from the linear combination:
$\mathcal{A}=\sum\limits_{i=1}^{n}{w_{i}X_{i}}$, where the ${w_{i}}$ are the
constant coefficients.

$\begin{split}\operatorname*{\mathbb{E}}[\mathcal{A}]&=M\cdot\sum\limits_{i=1}^{n}{w_{i}\theta_{i}}\\\
Var[\mathcal{A}]&=\operatorname*{\mathbb{E}}[\mathcal{A}^{2}]-(\operatorname*{\mathbb{E}}[\mathcal{A}])^{2}=\sum\limits_{i}^{n}{w^{2}_{i}[M\theta_{i}-M\theta_{i}^{2}]}-2\sum\limits_{i\neq
j}{w_{i}w_{j}[M\theta_{i}\theta_{j}]}\\\
&=M\sum\limits_{i}^{n}{w^{2}_{i}\theta_{i}}-M\cdot\Big{(}\sum\limits_{i}^{n}{w^{2}_{i}\theta^{2}_{i}}+2\sum\limits_{i\neq
j}w_{i}w_{j}\theta_{i}\theta_{j}\Big{)}\\\
&=M\cdot\Big{(}\sum\limits_{i}^{n}{w^{2}_{i}\theta_{i}}-\big{(}\sum\limits_{i}^{n}{w_{i}\theta_{i}}\big{)}^{2}\Big{)}\end{split}$

##  Appendix E Rewriting of $L_{2}$

$\begin{split}\mathcal{L}_{2}&=\sum\limits_{R=1}^{N}{P(R)\cdot\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\tilde{P}(r|R)\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}P(r|R)\widehat{\mathcal{M}}(r)]^{2}}\\\
&=\sum\limits_{R=1}^{N}{P(R)\cdot\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\frac{X_{r}}{M\cdot
P(R)}\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}\frac{\operatorname*{\mathbb{E}}[X_{r}]}{M\cdot
P(R)}\widehat{\mathcal{M}}(r)]^{2}}\\\
&=\sum\limits_{R=1}^{N}{\frac{1}{M^{2}\cdot
P(R)}\cdot\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}{X_{r}}\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}{\operatorname*{\mathbb{E}}[X_{r}]}\widehat{\mathcal{M}}(r)]^{2}}\\\
&=\sum\limits_{R=1}^{N}{\frac{1}{M}\cdot\Big{(}\sum\limits_{r}^{n}{\widehat{\mathcal{M}}^{2}(r)P(r|R)}-\big{(}\sum\limits_{r}^{n}{\widehat{\mathcal{M}}(r)P(r|R)}\big{)}^{2}\Big{)}}\\\
&=\sum\limits_{R=1}^{N}{\frac{1}{M}Var(\widehat{\mathcal{M}}(r)|R)}\end{split}$

##  Appendix F Least Square Formulation

This section would take the conclusion from Appendix D to derive the quadratic
form for Equation 10:

$\begin{split}\mathcal{L}_{1}&=\sum\limits_{R=1}^{N}{P(R)\Big{(}\sum\limits_{r=1}^{n}{P(r|R)\widehat{\mathcal{M}}(r)-\mathcal{M}(R)}\Big{)}^{2}}\\\
&=||\sqrt{D}A\mathbf{x}-\sqrt{D}\mathbf{b}||^{2}_{F}\\\
\mathcal{L}_{2}&=\sum\limits_{R=1}^{N}{P(R)\cdot\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\tilde{P}(r|R)\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}P(r|R)\widehat{\mathcal{M}}(r)]^{2}}\\\
&=\sum\limits_{R=1}^{N}{P(R)\cdot\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}\frac{X_{r}}{M\cdot
P(R)}\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}\frac{\operatorname*{\mathbb{E}}[X_{r}]}{M\cdot
P(R)}\widehat{\mathcal{M}}(r)]^{2}}\\\
&=\sum\limits_{R=1}^{N}{\frac{1}{m^{2}\cdot
P(R)}\cdot\operatorname*{\mathbb{E}}[\sum_{r=1}^{n}{X_{r}}\widehat{\mathcal{M}}(r)-\sum_{r=1}^{n}{\operatorname*{\mathbb{E}}[X_{r}]}\widehat{\mathcal{M}}(r)]^{2}}\\\
&=\sum\limits_{R=1}^{N}{\frac{1}{M}\cdot\Big{(}\sum\limits_{r}^{n}{\widehat{\mathcal{M}}^{2}(r)P(r|R)}-\big{(}\sum\limits_{r}^{n}{\widehat{\mathcal{M}}(r)P(r|R)}\big{)}^{2}\Big{)}}\\\
&=\frac{1}{M}\mathbf{x}^{T}\Lambda_{1}\mathbf{x}-\frac{1}{M}||A\mathbf{x}||^{2}_{F}=\frac{1}{M}||\sqrt{\Lambda_{1}}\mathbf{x}||^{2}_{F}-\frac{1}{M}||Ax||^{2}_{F}\end{split}$
(19)

##  Appendix G EM steps

E-step

$\begin{split}\log\mathcal{L}&=\sum\limits_{u=1}^{M}\log\sum\limits_{k=1}^{N}{P(r_{u},R_{uk};\bm{\pi})}\\\
&=\sum\limits_{u=1}^{M}\log\sum\limits_{k=1}^{N}{\phi(R_{uk})\cdot\frac{P(r_{u},R_{uk};\bm{\pi})}{\phi(R_{uk})}}\\\
&\geq\sum\limits_{u=1}^{M}\sum\limits_{k=1}^{N}{\phi(R_{uk})\cdot\log
P(r_{u},R_{uk};\bm{\pi})}+constant\\\
&\triangleq\sum\limits_{u=1}^{M}Q_{u}(\bm{\pi},\bm{\pi}^{old})=Q(\bm{\pi},\bm{\pi}^{old})\end{split}$
(20)

where

$\begin{split}\phi(R_{uk})&=P(R_{u}=k|r_{u};\bm{\pi}^{old})\\\
&=\frac{\pi^{old}_{k}\cdot
P(r_{u}|R_{u}=k;n_{u})}{\sum\limits_{j=1}^{N}\pi^{old}_{j}\cdot
P(r_{u}|R_{u}=j;n_{u})}\end{split}$ (21)

where $\phi$ is the posterior, $\bm{\pi}^{old}$ is the known probability
distribution and $\bm{\pi}$ is parameter.

M-step: Derived from the Lagrange maximization procedure:

$\begin{split}\pi^{new}_{k}=\frac{1}{M}\sum\limits_{u=1}^{M}\phi(R_{uk})\end{split}$
(22)

##  Appendix H Adaptive Sampling Explanation

A detailed explanation for Algorithm 1. Specifically, we start from an initial
sample set size parameter $n_{0}$. We sample $n_{0}-1$ items and compute the
rank $r_{u}$ for all users. For those users with $r_{u}>1$, we take down the
sample set size $n_{u}=n_{0}$. For those with $r_{u}=1$, we double the sample
set size $n_{1}=2n_{0}$, in other words, we sample another set of $n_{0}$
items (since we already sample $n_{0}-1$). Consequently, we check the rank
$r_{u}$ and repeat the process until $r_{u}\neq 1$ or sample set size is
$n_{max}$. We will discuss how to determine $n_{max}$ later in Section 4.3.

##  Appendix I More Experimental Results

###  I.1 Item-sampling based estimators

The estimators evaluated in this section are: $\mathbf{BV}$ (Bias-Variance
Estimator)(Krichene and Rendle 2020); $\mathbf{MLE}$ (Maximal Likelihood
Estimation)(Jin et al. 2021b); $\mathbf{MES}$ (Maximal Entropy with Squared
distribution distance)(Jin et al. 2021b); BV_MLE, BV_MES (Eq. 15 with $P(R)$
obtained from $MLE$ and $MES$; basically, we consider combining the two
approaches from BV (Krichene and Rendle 2020) and $\mathbf{MLE}$ (MES) (Jin et
al. 2021b)); the new multinomial distribution based estimator with different
prior, short as MN_MLE, MN_MES, Eq. 11 with prior $P(R)$ obtained from $MLE$
and $MES$ estimators.

###  I.2 Reproducibility

We release code at https://github.com/dli12/AAAI23-Towards-Reliable-Item-
Sampling-for-Recommendation-Evaluation.

###  I.3 Dataset Statistics

Table 5 shows the information of the three datasets used in this paper.

Table 5: Dataset Statistics Dataset | Interactions | Users | Items | Sparsity
---|---|---|---|---
pinterest-20 | 1,463,581 | 55,187 | 9,916 | 99.73$\%$
yelp | 696,865 | 25,677 | 25,815 | 99.89$\%$
ml-20m | 9,990,682 | 136,677 | 20,720 | 99.65$\%$

###  I.4 Complete Table

Due to space limitation, we put the complete version of Table 1, Table 2 and
Table 3 in below, see Table 6, Table 7 and Table 8 respectively.

Table 6: The average relative errors between estimated $Recall@K$ ($K$ from
$1$ to $50$) and the true ones. Unit is $\%$. In each row, the smallest two
results are highlighted in bold, indicating the most accurate results. Sample
set size $n=100$.

dataset | Models | sample set size 100
---|---|---
baseline | this paper
MES | MLE | BV | BV_MES | BV_MLE | MN_MES | MN_MLE
pinterest-20 | EASE | 5.86$\scriptstyle\pm$2.26 | 5.54$\scriptstyle\pm$1.85 | 8.11$\scriptstyle\pm$2.00 | 5.05$\scriptstyle\pm$1.46 | 5.14$\scriptstyle\pm$1.46 | 5.00$\scriptstyle\pm$1.39 | 5.10$\scriptstyle\pm$1.34
MultiVAE | 4.17$\scriptstyle\pm$2.91 | 3.34$\scriptstyle\pm$2.07 | 2.75$\scriptstyle\pm$1.61 | 2.89$\scriptstyle\pm$1.74 | 2.88$\scriptstyle\pm$1.74 | 2.75$\scriptstyle\pm$1.66 | 2.75$\scriptstyle\pm$1.68
NeuMF | 5.17$\scriptstyle\pm$2.74 | 4.28$\scriptstyle\pm$1.95 | 4.23$\scriptstyle\pm$1.79 | 3.83$\scriptstyle\pm$1.59 | 3.84$\scriptstyle\pm$1.72 | 3.60$\scriptstyle\pm$1.50 | 3.76$\scriptstyle\pm$1.44
itemKNN | 5.90$\scriptstyle\pm$2.20 | 5.80$\scriptstyle\pm$1.60 | 8.93$\scriptstyle\pm$1.70 | 5.11$\scriptstyle\pm$1.22 | 5.31$\scriptstyle\pm$1.25 | 5.09$\scriptstyle\pm$1.15 | 5.26$\scriptstyle\pm$1.14
ALS | 4.19$\scriptstyle\pm$2.37 | 3.44$\scriptstyle\pm$1.68 | 3.17$\scriptstyle\pm$1.34 | 3.05$\scriptstyle\pm$1.39 | 3.07$\scriptstyle\pm$1.42 | 2.86$\scriptstyle\pm$1.27 | 2.90$\scriptstyle\pm$1.28
yelp | EASE | 8.08$\scriptstyle\pm$4.94 | 7.89$\scriptstyle\pm$4.70 | 18.60$\scriptstyle\pm$2.78 | 6.10$\scriptstyle\pm$3.74 | 6.56$\scriptstyle\pm$3.90 | 4.84$\scriptstyle\pm$2.17 | 5.61$\scriptstyle\pm$2.30
MultiVAE | 9.33$\scriptstyle\pm$6.61 | 7.67$\scriptstyle\pm$4.94 | 9.70$\scriptstyle\pm$3.22 | 6.84$\scriptstyle\pm$4.10 | 6.80$\scriptstyle\pm$4.04 | 4.30$\scriptstyle\pm$1.27 | 4.35$\scriptstyle\pm$1.31
NeuMF | 15.09$\scriptstyle\pm$6.24 | 15.47$\scriptstyle\pm$5.55 | 22.40$\scriptstyle\pm$3.17 | 13.14$\scriptstyle\pm$4.55 | 13.92$\scriptstyle\pm$4.70 | 13.46$\scriptstyle\pm$2.43 | 14.50$\scriptstyle\pm$2.45
itemKNN | 9.25$\scriptstyle\pm$4.87 | 9.62$\scriptstyle\pm$4.88 | 23.24$\scriptstyle\pm$2.16 | 7.69$\scriptstyle\pm$4.09 | 8.15$\scriptstyle\pm$4.17 | 7.74$\scriptstyle\pm$2.08 | 8.75$\scriptstyle\pm$2.08
ALS | 14.31$\scriptstyle\pm$3.96 | 13.68$\scriptstyle\pm$3.51 | 15.14$\scriptstyle\pm$1.86 | 13.43$\scriptstyle\pm$3.16 | 13.26$\scriptstyle\pm$3.08 | 11.68$\scriptstyle\pm$0.88 | 11.57$\scriptstyle\pm$0.83
ml-20m | EASE | 10.45$\scriptstyle\pm$1.03 | 11.52$\scriptstyle\pm$1.03 | 36.59$\scriptstyle\pm$0.31 | 8.99$\scriptstyle\pm$0.74 | 9.86$\scriptstyle\pm$0.77 | 9.07$\scriptstyle\pm$0.61 | 10.09$\scriptstyle\pm$0.69
MultiVAE | 9.93$\scriptstyle\pm$0.38 | 9.48$\scriptstyle\pm$0.22 | 22.24$\scriptstyle\pm$0.37 | 9.85$\scriptstyle\pm$0.36 | 9.50$\scriptstyle\pm$0.22 | 9.82$\scriptstyle\pm$0.28 | 9.53$\scriptstyle\pm$0.14
NeuMF | 4.35$\scriptstyle\pm$1.50 | 6.05$\scriptstyle\pm$1.35 | 28.27$\scriptstyle\pm$0.42 | 3.67$\scriptstyle\pm$1.14 | 4.81$\scriptstyle\pm$1.14 | 3.64$\scriptstyle\pm$1.05 | 4.79$\scriptstyle\pm$1.08
itemKNN | 15.31$\scriptstyle\pm$1.18 | 17.19$\scriptstyle\pm$1.15 | 36.63$\scriptstyle\pm$0.42 | 14.02$\scriptstyle\pm$0.75 | 15.24$\scriptstyle\pm$0.83 | 14.16$\scriptstyle\pm$0.68 | 15.41$\scriptstyle\pm$0.77
ALS | 36.17$\scriptstyle\pm$0.83 | 35.21$\scriptstyle\pm$0.64 | 36.39$\scriptstyle\pm$0.21 | 36.50$\scriptstyle\pm$0.74 | 35.75$\scriptstyle\pm$0.62 | 36.32$\scriptstyle\pm$0.56 | 35.60$\scriptstyle\pm$0.48

Table 7: The average relative errors between estimated $NDCG@K$ ($K$ from $1$
to $50$) and the true ones. Unit is $\%$. In each row, the smallest relative
error is highlighted, indicating the most accurate result.

Dataset | Models | Fix Sample | Adaptive Sample
---|---|---|---
BV_MES | BV_MLE | MN_MES | MN_MLE | average size | adaptive MLE
| sample set size n = 500 |
pinterest-20 | EASE | 3.87$\scriptstyle\pm$2.13 | 4.33$\scriptstyle\pm$2.23 | 4.17$\scriptstyle\pm$2.45 | 4.33$\scriptstyle\pm$2.50 | 307.74$\scriptstyle\pm$1.41 | 1.46$\scriptstyle\pm$0.63
MultiVAE | 2.66$\scriptstyle\pm$1.75 | 2.58$\scriptstyle\pm$1.75 | 3.26$\scriptstyle\pm$2.14 | 3.07$\scriptstyle\pm$2.09 | 286.46$\scriptstyle\pm$1.48 | 1.67$\scriptstyle\pm$0.70
NeuMF | 2.82$\scriptstyle\pm$1.98 | 2.79$\scriptstyle\pm$1.96 | 3.24$\scriptstyle\pm$2.30 | 3.22$\scriptstyle\pm$2.27 | 259.77$\scriptstyle\pm$1.28 | 1.73$\scriptstyle\pm$0.83
itemKNN | 3.99$\scriptstyle\pm$2.22 | 4.18$\scriptstyle\pm$2.24 | 4.23$\scriptstyle\pm$2.47 | 4.06$\scriptstyle\pm$2.44 | 309.56$\scriptstyle\pm$1.31 | 1.42$\scriptstyle\pm$0.67
ALS | 3.35$\scriptstyle\pm$1.89 | 3.24$\scriptstyle\pm$1.87 | 3.90$\scriptstyle\pm$2.24 | 3.80$\scriptstyle\pm$2.23 | 270.75$\scriptstyle\pm$1.22 | 1.84$\scriptstyle\pm$1.07
| sample set size n = 500 |
yelp | EASE | 5.63$\scriptstyle\pm$3.73 | 5.48$\scriptstyle\pm$3.66 | 4.03$\scriptstyle\pm$2.53 | 4.04$\scriptstyle\pm$2.53 | 340.79$\scriptstyle\pm$2.03 | 3.55$\scriptstyle\pm$2.00
MultiVAE | 7.68$\scriptstyle\pm$5.86 | 7.48$\scriptstyle\pm$5.74 | 5.77$\scriptstyle\pm$3.87 | 5.64$\scriptstyle\pm$3.82 | 288.70$\scriptstyle\pm$2.24 | 5.09$\scriptstyle\pm$2.60
NeuMF | 9.34$\scriptstyle\pm$5.50 | 9.55$\scriptstyle\pm$5.50 | 8.43$\scriptstyle\pm$4.07 | 8.91$\scriptstyle\pm$4.13 | 290.62$\scriptstyle\pm$2.11 | 4.43$\scriptstyle\pm$2.55
itemKNN | 5.01$\scriptstyle\pm$2.99 | 4.99$\scriptstyle\pm$2.96 | 3.65$\scriptstyle\pm$2.28 | 3.71$\scriptstyle\pm$2.29 | 369.16$\scriptstyle\pm$2.51 | 3.67$\scriptstyle\pm$2.73
ALS | 13.39$\scriptstyle\pm$7.34 | 13.94$\scriptstyle\pm$7.61 | 12.57$\scriptstyle\pm$5.46 | 13.67$\scriptstyle\pm$5.80 | 297.07$\scriptstyle\pm$2.29 | 5.48$\scriptstyle\pm$3.34
| sample set size n = 1000 |
ml-20m | EASE | 3.45$\scriptstyle\pm$0.83 | 4.16$\scriptstyle\pm$0.81 | 3.74$\scriptstyle\pm$1.51 | 3.85$\scriptstyle\pm$1.53 | 899.89$\scriptstyle\pm$1.90 | 2.01$\scriptstyle\pm$0.56
MultiVAE | 3.20$\scriptstyle\pm$1.44 | 4.37$\scriptstyle\pm$1.58 | 4.76$\scriptstyle\pm$2.68 | 3.87$\scriptstyle\pm$2.58 | 771.26$\scriptstyle\pm$1.84 | 1.21$\scriptstyle\pm$0.60
NeuMF | 1.02$\scriptstyle\pm$0.65 | 1.14$\scriptstyle\pm$0.74 | 1.94$\scriptstyle\pm$1.35 | 1.90$\scriptstyle\pm$1.23 | 758.45$\scriptstyle\pm$1.61 | 0.92$\scriptstyle\pm$0.51
itemKNN | 4.44$\scriptstyle\pm$1.07 | 5.36$\scriptstyle\pm$1.05 | 3.52$\scriptstyle\pm$1.67 | 4.13$\scriptstyle\pm$1.68 | 725.72$\scriptstyle\pm$1.49 | 2.02$\scriptstyle\pm$0.63
ALS | 12.28$\scriptstyle\pm$2.07 | 17.12$\scriptstyle\pm$2.38 | 13.42$\scriptstyle\pm$4.44 | 13.48$\scriptstyle\pm$4.90 | 705.76$\scriptstyle\pm$1.56 | 5.27$\scriptstyle\pm$1.39

Table 8: Accuracy of predicting of the winner models for different datasets.
Values in table is the number of correct predictions over 100 repeats. The
larger number, the better estimator.

Dataset | Top-K | Metrics | Fix Sample | AdaptiveSample
---|---|---|---|---
BV_MES | BV_MLE | MN_MES | MN_MLE | adaptive MLE
sample set size n = 500 | sample set size $260\sim 310$
pinterest-20 | 10 | RECALL | 69 | 73 | 67 | 69 | 78
NDCG | 58 | 59 | 58 | 60 | 84
AP | 54 | 57 | 52 | 52 | 68
20 | RECALL | 69 | 73 | 70 | 74 | 81
NDCG | 69 | 73 | 68 | 73 | 79
AP | 57 | 60 | 54 | 56 | 69
| sample set size n = 500 | sample set size $280\sim 370$
yelp | 10 | RECALL | 98 | 97 | 100 | 100 | 100
NDCG | 96 | 96 | 100 | 100 | 100
AP | 95 | 95 | 100 | 100 | 94
20 | RECALL | 100 | 100 | 100 | 100 | 100
NDCG | 100 | 100 | 100 | 100 | 100
AP | 97 | 96 | 100 | 100 | 98
| sample set size n = 1000 | sample set size $700\sim 900$
ml-20m | 10 | RECALL | 100 | 100 | 100 | 100 | 100
NDCG | 100 | 100 | 100 | 100 | 100
AP | 100 | 100 | 100 | 100 | 100
20 | RECALL | 100 | 100 | 100 | 100 | 100
NDCG | 100 | 100 | 100 | 100 | 100
AP | 100 | 100 | 100 | 100 | 100

###  I.5 More Results

Due to the space limitation, we present two complementary experimental results
for Table 1 as well as Table 2.

Table 9 show the result of average relative errors between estimated $AP@K$
($K$ from $1$ to $50$) and the true ones. The proposed estimator especially
$MN\\_MES$ performs best in general, which is consistent with the observation
in Section 5.

Table 10 show the result of average relative errors between estimated $NDCG@K$
($K$ from $1$ to $50$) and the true ones. In Table 1, the sample set size
$n=100$ while here is $500$. The result consistently confirm the superiority
of models proposed in this paper. Specifically, from the Table 10, we can find
that $MN\\_MES$ estimator performs best or second best (highlighted) in most
of the cases.

Table 11 presents the average relative errors in terms of $Recall$ metric.
There are four advanced estimators with fixed sampling set size ($n=500$ or
$1000$) and a proposed adaptive based estimator. We follow the adaptive
sampling strategy in Section 4 and obtain the average sampling set size for
each dataset and model. For example, the average sampling set size is $307$
for EASE model in pinterest-20 dataset, compared to the estimators with
$n=500$ sample set size. Nevertheless, the adaptive based estimator can even
achive much better performance, say $1.69\%$ relative error compared to the
$2.78\%$ from MN_MES estimator. All these results consistently support the
superiority of the adaptive sampling strategy and the adaptive estimator.

Table 9: The average relative errors between estimated $AP@K$ ($K$ from $1$ to
$50$) and the true ones. Unit is $\%$. In each row, the smallest two results
are highlighted in bold, indicating the most accurate results. Sample set size
$n=100$.

dataset | Models | sample set size 100
---|---|---
baseline | this paper
MES | MLE | BV | BV_MES | BV_MLE | MN_MES | MN_MLE
pinterest-20 | EASE | 17.45$\scriptstyle\pm$6.14 | 17.85$\scriptstyle\pm$4.50 | 23.50$\scriptstyle\pm$2.25 | 16.88$\scriptstyle\pm$3.91 | 17.19$\scriptstyle\pm$3.87 | 17.06$\scriptstyle\pm$3.54 | 17.30$\scriptstyle\pm$3.52
MultiVAE | 6.45$\scriptstyle\pm$5.05 | 4.68$\scriptstyle\pm$3.40 | 3.58$\scriptstyle\pm$2.29 | 4.04$\scriptstyle\pm$2.94 | 4.03$\scriptstyle\pm$2.93 | 3.78$\scriptstyle\pm$2.66 | 3.76$\scriptstyle\pm$2.66
NeuMF | 8.62$\scriptstyle\pm$6.12 | 7.28$\scriptstyle\pm$4.77 | 9.43$\scriptstyle\pm$3.33 | 6.39$\scriptstyle\pm$4.19 | 7.04$\scriptstyle\pm$4.39 | 6.19$\scriptstyle\pm$3.89 | 6.58$\scriptstyle\pm$3.99
itemKNN | 17.46$\scriptstyle\pm$6.07 | 18.17$\scriptstyle\pm$4.12 | 23.90$\scriptstyle\pm$1.97 | 16.81$\scriptstyle\pm$3.53 | 17.41$\scriptstyle\pm$3.49 | 17.02$\scriptstyle\pm$3.17 | 17.46$\scriptstyle\pm$3.15
ALS | 7.78$\scriptstyle\pm$5.56 | 7.03$\scriptstyle\pm$4.30 | 3.39$\scriptstyle\pm$1.79 | 6.31$\scriptstyle\pm$3.70 | 6.48$\scriptstyle\pm$3.76 | 5.80$\scriptstyle\pm$3.30 | 6.07$\scriptstyle\pm$3.39
yelp | EASE | 9.87$\scriptstyle\pm$6.09 | 9.72$\scriptstyle\pm$5.78 | 22.16$\scriptstyle\pm$2.90 | 7.44$\scriptstyle\pm$4.68 | 8.04$\scriptstyle\pm$4.87 | 6.14$\scriptstyle\pm$2.64 | 7.22$\scriptstyle\pm$2.72
MultiVAE | 12.07$\scriptstyle\pm$10.12 | 9.66$\scriptstyle\pm$7.90 | 6.00$\scriptstyle\pm$3.04 | 9.53$\scriptstyle\pm$7.03 | 9.11$\scriptstyle\pm$6.82 | 6.85$\scriptstyle\pm$3.24 | 6.20$\scriptstyle\pm$3.08
NeuMF | 33.32$\scriptstyle\pm$7.85 | 34.41$\scriptstyle\pm$6.23 | 41.36$\scriptstyle\pm$2.64 | 32.00$\scriptstyle\pm$5.34 | 33.04$\scriptstyle\pm$5.23 | 33.05$\scriptstyle\pm$2.14 | 34.15$\scriptstyle\pm$2.12
itemKNN | 14.97$\scriptstyle\pm$6.82 | 15.94$\scriptstyle\pm$6.24 | 31.18$\scriptstyle\pm$2.11 | 13.43$\scriptstyle\pm$5.48 | 14.17$\scriptstyle\pm$5.43 | 14.21$\scriptstyle\pm$2.20 | 15.45$\scriptstyle\pm$2.17
ALS | 31.31$\scriptstyle\pm$13.11 | 31.06$\scriptstyle\pm$11.63 | 13.59$\scriptstyle\pm$4.14 | 32.91$\scriptstyle\pm$10.21 | 32.38$\scriptstyle\pm$10.10 | 32.00$\scriptstyle\pm$4.18 | 31.29$\scriptstyle\pm$4.17
ml-20m | EASE | 31.30$\scriptstyle\pm$1.29 | 32.83$\scriptstyle\pm$1.23 | 57.14$\scriptstyle\pm$0.23 | 29.29$\scriptstyle\pm$1.10 | 30.66$\scriptstyle\pm$1.05 | 29.48$\scriptstyle\pm$0.91 | 31.04$\scriptstyle\pm$0.90
MultiVAE | 29.01$\scriptstyle\pm$2.90 | 25.61$\scriptstyle\pm$2.54 | 12.75$\scriptstyle\pm$0.42 | 30.07$\scriptstyle\pm$2.25 | 27.17$\scriptstyle\pm$2.18 | 30.33$\scriptstyle\pm$2.00 | 26.74$\scriptstyle\pm$1.97
NeuMF | 9.10$\scriptstyle\pm$2.05 | 11.64$\scriptstyle\pm$1.74 | 37.40$\scriptstyle\pm$0.40 | 8.12$\scriptstyle\pm$1.55 | 9.86$\scriptstyle\pm$1.50 | 8.29$\scriptstyle\pm$1.40 | 9.99$\scriptstyle\pm$1.37
itemKNN | 43.81$\scriptstyle\pm$1.44 | 46.09$\scriptstyle\pm$1.17 | 62.55$\scriptstyle\pm$0.28 | 42.14$\scriptstyle\pm$1.04 | 43.82$\scriptstyle\pm$1.00 | 42.36$\scriptstyle\pm$0.94 | 44.12$\scriptstyle\pm$0.92
ALS | 88.83$\scriptstyle\pm$4.86 | 84.37$\scriptstyle\pm$4.40 | 28.12$\scriptstyle\pm$0.97 | 91.43$\scriptstyle\pm$3.89 | 87.73$\scriptstyle\pm$3.77 | 90.49$\scriptstyle\pm$3.43 | 87.04$\scriptstyle\pm$3.38

Table 10: The average relative errors between estimated $NDCG@K$ ($K$ from $1$
to $50$) and the true ones. Unit is $\%$. In each row, the smallest two
results are highlighted in bold, indicating the most accurate results. Sample
set size $n=500$.

dataset | Models | sample set size 500
---|---|---
baseline | this paper
MES | MLE | BV | BV_MES | BV_MLE | MN_MES | MN_MLE
pinterest-20 | EASE | 5.11$\scriptstyle\pm$3.09 | 4.52$\scriptstyle\pm$2.42 | 5.53$\scriptstyle\pm$2.12 | 3.87$\scriptstyle\pm$2.13 | 4.33$\scriptstyle\pm$2.23 | 4.17$\scriptstyle\pm$2.45 | 4.33$\scriptstyle\pm$2.50
MultiVAE | 4.01$\scriptstyle\pm$2.60 | 2.89$\scriptstyle\pm$2.05 | 2.29$\scriptstyle\pm$1.58 | 2.66$\scriptstyle\pm$1.75 | 2.58$\scriptstyle\pm$1.75 | 3.26$\scriptstyle\pm$2.14 | 3.07$\scriptstyle\pm$2.09
NeuMF | 4.27$\scriptstyle\pm$2.85 | 3.20$\scriptstyle\pm$2.22 | 2.75$\scriptstyle\pm$1.83 | 2.82$\scriptstyle\pm$1.98 | 2.79$\scriptstyle\pm$1.96 | 3.24$\scriptstyle\pm$2.30 | 3.22$\scriptstyle\pm$2.27
itemKNN | 5.13$\scriptstyle\pm$2.99 | 4.36$\scriptstyle\pm$2.46 | 5.23$\scriptstyle\pm$2.15 | 3.99$\scriptstyle\pm$2.22 | 4.18$\scriptstyle\pm$2.24 | 4.23$\scriptstyle\pm$2.47 | 4.06$\scriptstyle\pm$2.44
ALS | 4.53$\scriptstyle\pm$2.86 | 3.65$\scriptstyle\pm$2.13 | 3.16$\scriptstyle\pm$1.77 | 3.35$\scriptstyle\pm$1.89 | 3.24$\scriptstyle\pm$1.87 | 3.90$\scriptstyle\pm$2.24 | 3.80$\scriptstyle\pm$2.23
yelp | EASE | 8.59$\scriptstyle\pm$5.62 | 6.32$\scriptstyle\pm$4.28 | 4.85$\scriptstyle\pm$3.16 | 5.63$\scriptstyle\pm$3.73 | 5.48$\scriptstyle\pm$3.66 | 4.03$\scriptstyle\pm$2.53 | 4.04$\scriptstyle\pm$2.53
MultiVAE | 10.83$\scriptstyle\pm$8.83 | 8.57$\scriptstyle\pm$6.91 | 6.48$\scriptstyle\pm$4.79 | 7.68$\scriptstyle\pm$5.86 | 7.48$\scriptstyle\pm$5.74 | 5.77$\scriptstyle\pm$3.87 | 5.64$\scriptstyle\pm$3.82
NeuMF | 11.52$\scriptstyle\pm$7.27 | 10.82$\scriptstyle\pm$6.16 | 12.82$\scriptstyle\pm$5.17 | 9.34$\scriptstyle\pm$5.50 | 9.55$\scriptstyle\pm$5.50 | 8.43$\scriptstyle\pm$4.07 | 8.91$\scriptstyle\pm$4.13
itemKNN | 7.72$\scriptstyle\pm$5.18 | 5.87$\scriptstyle\pm$3.38 | 5.31$\scriptstyle\pm$3.26 | 5.01$\scriptstyle\pm$2.99 | 4.99$\scriptstyle\pm$2.96 | 3.65$\scriptstyle\pm$2.28 | 3.71$\scriptstyle\pm$2.29
ALS | 16.30$\scriptstyle\pm$10.72 | 15.65$\scriptstyle\pm$9.30 | 15.26$\scriptstyle\pm$7.00 | 13.39$\scriptstyle\pm$7.34 | 13.94$\scriptstyle\pm$7.61 | 12.57$\scriptstyle\pm$5.46 | 13.67$\scriptstyle\pm$5.80
ml-20m | EASE | 5.93$\scriptstyle\pm$2.02 | 7.44$\scriptstyle\pm$1.08 | 14.35$\scriptstyle\pm$0.56 | 5.78$\scriptstyle\pm$0.95 | 6.78$\scriptstyle\pm$0.93 | 5.59$\scriptstyle\pm$1.49 | 6.14$\scriptstyle\pm$1.47
MultiVAE | 7.53$\scriptstyle\pm$2.95 | 10.27$\scriptstyle\pm$1.68 | 10.41$\scriptstyle\pm$1.08 | 7.22$\scriptstyle\pm$1.42 | 9.35$\scriptstyle\pm$1.46 | 7.01$\scriptstyle\pm$2.18 | 8.08$\scriptstyle\pm$2.26
NeuMF | 2.82$\scriptstyle\pm$1.92 | 1.71$\scriptstyle\pm$1.00 | 4.41$\scriptstyle\pm$0.91 | 1.29$\scriptstyle\pm$0.71 | 1.46$\scriptstyle\pm$0.83 | 2.10$\scriptstyle\pm$1.31 | 2.11$\scriptstyle\pm$1.32
itemKNN | 8.45$\scriptstyle\pm$2.12 | 10.50$\scriptstyle\pm$1.27 | 18.98$\scriptstyle\pm$0.66 | 8.24$\scriptstyle\pm$1.12 | 9.46$\scriptstyle\pm$1.10 | 7.40$\scriptstyle\pm$1.60 | 8.96$\scriptstyle\pm$1.56
ALS | 28.45$\scriptstyle\pm$5.33 | 37.22$\scriptstyle\pm$2.88 | 40.95$\scriptstyle\pm$1.72 | 27.89$\scriptstyle\pm$2.30 | 33.53$\scriptstyle\pm$2.47 | 26.31$\scriptstyle\pm$3.81 | 30.61$\scriptstyle\pm$4.08

Table 11: The average relative errors between estimated $Recall@K$ ($K$ from
$1$ to $50$) and the true ones. Unit is $\%$. In each row, the smallest
relative error is highlighted, indicating the most accurate result.

Dataset | Models | Fix Sample | Adaptive Sample
---|---|---|---
BV_MES | BV_MLE | MN_MES | MN_MLE | average size | adaptive MLE
| sample set size n = 500 |
pinterest-20 | EASE | 2.54$\scriptstyle\pm$0.85 | 2.68$\scriptstyle\pm$0.87 | 2.78$\scriptstyle\pm$1.05 | 2.83$\scriptstyle\pm$1.06 | 307.74$\scriptstyle\pm$1.41 | 1.69$\scriptstyle\pm$0.60
MultiVAE | 2.17$\scriptstyle\pm$1.08 | 2.13$\scriptstyle\pm$1.09 | 2.60$\scriptstyle\pm$1.30 | 2.55$\scriptstyle\pm$1.35 | 286.46$\scriptstyle\pm$1.48 | 1.95$\scriptstyle\pm$0.65
NeuMF | 2.45$\scriptstyle\pm$1.15 | 2.44$\scriptstyle\pm$1.15 | 2.76$\scriptstyle\pm$1.37 | 2.80$\scriptstyle\pm$1.38 | 259.77$\scriptstyle\pm$1.28 | 2.00$\scriptstyle\pm$0.81
itemKNN | 2.49$\scriptstyle\pm$0.97 | 2.59$\scriptstyle\pm$0.94 | 2.79$\scriptstyle\pm$1.12 | 2.79$\scriptstyle\pm$1.20 | 309.56$\scriptstyle\pm$1.31 | 1.63$\scriptstyle\pm$0.51
ALS | 2.65$\scriptstyle\pm$1.04 | 2.63$\scriptstyle\pm$1.06 | 3.02$\scriptstyle\pm$1.32 | 2.98$\scriptstyle\pm$1.33 | 270.75$\scriptstyle\pm$1.22 | 2.00$\scriptstyle\pm$0.73
| sample set size n = 500 |
yelp | EASE | 4.68$\scriptstyle\pm$2.43 | 4.56$\scriptstyle\pm$2.35 | 3.47$\scriptstyle\pm$1.79 | 3.49$\scriptstyle\pm$1.78 | 340.79$\scriptstyle\pm$2.03 | 3.48$\scriptstyle\pm$1.40
MultiVAE | 6.14$\scriptstyle\pm$3.48 | 6.07$\scriptstyle\pm$3.46 | 4.68$\scriptstyle\pm$2.27 | 4.67$\scriptstyle\pm$2.28 | 288.70$\scriptstyle\pm$2.24 | 5.08$\scriptstyle\pm$2.14
NeuMF | 6.59$\scriptstyle\pm$2.38 | 6.73$\scriptstyle\pm$2.35 | 5.48$\scriptstyle\pm$1.43 | 5.68$\scriptstyle\pm$1.42 | 290.62$\scriptstyle\pm$2.11 | 4.01$\scriptstyle\pm$1.51
itemKNN | 3.94$\scriptstyle\pm$1.94 | 3.95$\scriptstyle\pm$1.92 | 2.92$\scriptstyle\pm$1.60 | 2.96$\scriptstyle\pm$1.57 | 369.16$\scriptstyle\pm$2.51 | 3.25$\scriptstyle\pm$1.59
ALS | 10.00$\scriptstyle\pm$3.47 | 10.31$\scriptstyle\pm$3.65 | 9.29$\scriptstyle\pm$2.03 | 9.80$\scriptstyle\pm$2.23 | 297.07$\scriptstyle\pm$2.29 | 5.25$\scriptstyle\pm$2.38
| sample set size n = 1000 |
ml-20m | EASE | 1.39$\scriptstyle\pm$0.21 | 1.69$\scriptstyle\pm$0.28 | 1.81$\scriptstyle\pm$0.46 | 1.73$\scriptstyle\pm$0.46 | 899.89$\scriptstyle\pm$1.90 | 1.07$\scriptstyle\pm$0.24
MultiVAE | 2.23$\scriptstyle\pm$0.58 | 2.91$\scriptstyle\pm$0.72 | 3.55$\scriptstyle\pm$1.23 | 2.98$\scriptstyle\pm$1.50 | 771.26$\scriptstyle\pm$1.84 | 1.10$\scriptstyle\pm$0.39
NeuMF | 0.82$\scriptstyle\pm$0.30 | 0.85$\scriptstyle\pm$0.28 | 1.51$\scriptstyle\pm$0.66 | 1.69$\scriptstyle\pm$0.70 | 758.45$\scriptstyle\pm$1.61 | 0.78$\scriptstyle\pm$0.27
itemKNN | 1.84$\scriptstyle\pm$0.24 | 2.13$\scriptstyle\pm$0.27 | 1.97$\scriptstyle\pm$0.42 | 2.17$\scriptstyle\pm$0.49 | 725.72$\scriptstyle\pm$1.49 | 1.17$\scriptstyle\pm$0.28
ALS | 9.41$\scriptstyle\pm$0.97 | 12.83$\scriptstyle\pm$1.27 | 10.63$\scriptstyle\pm$2.53 | 10.57$\scriptstyle\pm$3.18 | 705.76$\scriptstyle\pm$1.56 | 4.29$\scriptstyle\pm$1.05