# Debiased Recommendation with Noisy Feedback

Haoxuan Li  Peking UniversityBeijing, China<EMAIL_ADDRESS>,  Chunyuan
Zheng  Peking UniversityBeijing, China<EMAIL_ADDRESS>,  Wenjie
Wang  National University of SingaporeSingapore, Singapore
<EMAIL_ADDRESS>,  Hao Wang  Zhejiang UniversityHangzhou, China
<EMAIL_ADDRESS>,  Fuli Feng  University of Science and
Technology of China<EMAIL_ADDRESS>and  Xiao-Hua Zhou  Peking
UniversityBeijing, China<EMAIL_ADDRESS>
(2024)

###### Abstract.

Ratings of a user to most items in recommender systems are usually missing not
at random (MNAR), largely because users are free to choose which items to
rate. To achieve unbiased learning of the prediction model under MNAR data,
three typical solutions have been proposed, including error-imputation-based
(EIB), inverse-propensity-scoring (IPS), and doubly robust (DR) methods.
However, these methods ignore an alternative form of bias caused by the
inconsistency between the observed ratings and the users’ true preferences,
also known as noisy feedback or outcome measurement errors (OME), _e.g._ , due
to public opinion or low-quality data collection process. In this work, we
study intersectional threats to the unbiased learning of the prediction model
from data MNAR and OME in the collected data. First, we design OME-EIB, OME-
IPS, and OME-DR estimators, which largely extend the existing estimators to
combat OME in real-world recommendation scenarios. Next, we theoretically
prove the unbiasedness and generalization bound of the proposed estimators. We
further propose an alternate denoising training approach to achieve unbiased
learning of the prediction model under MNAR data with OME. Extensive
experiments are conducted on three real-world datasets and one semi-synthetic
dataset to show the effectiveness of our proposed approaches. The code is
available at https://github.com/haoxuanli-pku/KDD24-OME-DR.

Bias, Debias, Noisy Feedback, Recommender Systems

††journalyear: 2024††copyright: acmlicensed††conference: Proceedings of the
30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining ; August
25–29, 2024; Barcelona, Spain.††booktitle: Proceedings of the 30th ACM SIGKDD
Conference on Knowledge Discovery and Data Mining (KDD ’24), August 25–29,
2024, Barcelona, Spain††doi: 10.1145/3637528.3671915††isbn:
979-8-4007-0490-1/24/08††ccs: Information systems Recommender systems

##  1\. Introduction

Recommender systems (RS) are designed to generate meaningful recommendations
to a collection of users for items or products that might interest them, which
have made a number of significant advancements in recent years (Zhao et al.,
2019; Zhang et al., 2020b; Rui et al., 2022; Wang et al., 2023b).
Nevertheless, direct use of these advanced models in real-world scenarios
while ignoring the presence of numerous biases in the collected data can lead
to sub-optimal performance of the rating prediction model (Chen et al., 2023;
Yang et al., 2021, 2023). Among these, the problem of missing data is
particularly prevalent, as users are free to choose items to rate and the
ratings with a lower value are more likely to be missing (De Myttenaere et
al., 2014), leading to the collected data in RS is always missing not at
random (MNAR) (Marlin and Zemel, 2009). MNAR ratings pose a serious challenge
to the unbiased evaluation and learning of the prediction model because the
observed data might not faithfully represent the entirety of user-item pairs
(Schnabel et al., 2016; Wang et al., 2019).

To tackle this problem, previous studies evaluate the performance of a
prediction model by computing the _prediction inaccuracy_ : the average of the
prediction errors (_e.g._ , the squared difference between a predicted rating
and the _potentially observed_ rating) for all ratings (Saito, 2019, 2020). To
unbiasedly estimate the prediction inaccuracy when the ratings are partially
observable, three typical approaches have been proposed, including: (1) The
error-imputation-based (EIB) approaches (Steck, 2010; Hernández-Lobato et al.,
2014), which compute an imputed error for each missing rating. (2) The
inverse-propensity-scoring (IPS) approaches (Schnabel et al., 2016; Saito et
al., 2020), which inversely weight the prediction error for each observed
rating with the probability of observing that rating. (3) The doubly robust
(DR) approaches (Li et al., 2023f; Song et al., 2023; Li et al., 2024c, b),
which use both the error imputation model and the propensity model to estimate
the prediction inaccuracy, and the estimation is unbiased when either the
imputed errors or the learned propensities are accurate.

Despite the widespread use of these methods, they ignore an alternative form
of bias caused by the inconsistency between the observed ratings and the
users’ true preferences, also known as noisy feedback or outcome measurement
errors (OME). Similar to selection bias, OME also arises from systematic bias
during the data collection. For example, the collected user feedback may
differ from the true user preferences due to the influence of public opinions
(Zheng et al., 2021). Meanwhile, low-quality data collection such as
recommender attacks (Gunes et al., 2014) or carelessly filling out the after-
sales assessment can also result in noisy user feedback (Wang et al., 2021a).
Therefore, to make current debiased recommendation techniques more applicable
to real-world scenarios that may contain OME, it is worthwhile to develop new
model evaluation criteria and corresponding estimators to achieve unbiased
learning under OME.

In this work, we study intersectional threats to the unbiased learning of the
prediction model introduced by data MNAR and OME from historical interactions,
where the observed ratings are not only MNAR but may differ from the true
ratings due to the presence of OME. In such a context, a natural evaluation
criterion for the prediction models is proposed, called _true prediction
inaccuracy_ : the average of the _true_ prediction errors (_e.g._ , the
squared difference between a predicted rating and the _true_ rating) for all
ratings. Given the collected data with OME, the true prediction errors are
difficult to obtain even for the observed ratings, making the previous
debiasing estimators severely biased in estimating the true prediction
inaccuracy and training the rating prediction model.

To combat the influence of OME on the performance of the prediction model,
many data-driven error parameter estimation methods are developed in recent
machine learning literature (Northcutt et al., 2021; Scott et al., 2013;
Scott, 2015; Xia et al., 2019). Meanwhile, given knowledge of measurement
error parameters, recent studies propose unbiased risk minimization approaches
for learning under noisy labels (Natarajan et al., 2013; Chou et al., 2020;
Patrini et al., 2017; Van Rooyen et al., 2015a). Despite the prevalence of OME
in real-world recommendation scenarios, there is still only limited work
focusing on denoising in RS (Qin et al., 2021; Chen et al., 2022; Liu et al.,
2021; Zhang et al., 2023a). For example, (Zhang et al., 2023b) proposes to
overcome noisy confounders by leveraging the sensitivity analysis in the
statistics literature. By noticing that noisy feedback typically has large
loss values in the early stages, (Wang et al., 2021a) proposes adaptive
denoising training and (Gao et al., 2022a) proposes self-guided denoising
learning for implicit feedback. However, most of these methods are heuristic
and lack theoretical guarantees of statistical unbiasedness for estimating the
true prediction inaccuracy.

To address the above problem, we extend the widely adopted EIB, IPS, and DR
estimators to achieve unbiased estimations with the true prediction inaccuracy
under OME, named OME-EIB, OME-IPS, and OME-DR estimators, respectively. Our
methods are built upon the existing weak separability assumption (Menon et
al., 2015), which states that there exist ”perfectly positive” and ”perfectly
negative” samples among the entire user-item pairs. Specifically, we discuss
the rationality of the weak separability assumption in real-world
recommendation scenarios and build up the linkage between the observed and
true outcome probabilities at specific instances, from which we are able to
obtain unbiased estimations of the measurement error parameters. We also
derive explicit forms of the biases and the generalization bounds of the
proposed OME-EIB, OME-IPS, and OME-DR estimators under inaccurately estimated
measurement error parameters, from which we prove the double robustness of the
OME-DR estimator. We further propose an alternating denoise training approach
to achieve unbiased learning of the prediction model, which corrects for data
MNAR and OME in parallel. In particular, the imputation model learns to
accurately estimate the prediction errors made by the prediction model, while
the prediction model learns from the imputation model to reduce the prediction
errors in itself. In this way, the prediction and imputation models mutually
regularize each other to reduce both prediction and imputation inaccuracies.
The effectiveness of our proposed approaches is validated on three real-world
datasets and one semi-synthetic dataset with varying MNAR levels and OME
rates. To the best of our knowledge, our holistic evaluation is the first to
examine how OME with its measurement error parameters’ estimation in the
context of selection bias interact to affect the debiased recommendations.

The contributions of this paper are summarized as follows.

  * •

We formulate OME caused by the inconsistency between the observed ratings and
the users’ true preferences, and establish an evaluation criterion for the
unbiased learning of the prediction model under OME, named true prediction
inaccuracy.

  * •

We develop OME-EIB, OME-IPS, and OME-DR estimators for unbiasedly estimating
the true prediction inaccuracy of the prediction model under MNAR data with
OME, and theoretically analyze the biases and generalization bounds of the
estimators.

  * •

We further propose an alternating denoise training approach to estimate the
measurement error parameters and achieve unbiased learning of the prediction
model under MNAR data with OME, which corrects for data MNAR and OME in
parallel.

  * •

We conduct extensive experiments on three real-world datasets and one semi-
synthetic dataset, and the results demonstrate the superiority of our methods
with varying MNAR and OME rates.

##  2\. Preliminaries

###  2.1. Task Formulation without OME

Let $\mathcal{U}=\\{u_{1},\ldots,u_{N}\\}$ be a set of users,
$\mathcal{I}=\\{i_{1},\ldots,i_{M}\\}$ a set of items, and
$\mathcal{D}=\mathcal{U}\times\mathcal{I}$ the collection of all user-item
pairs. The potentially observed rating matrix
$\mathbf{R}\in\mathbb{R}^{N\times M}$ comprises potentially observed ratings
$r_{u,i}$, which represents the observed rating if user $u$ had rated the item
$i$. In RS, given the user-item features $x_{u,i}$, the prediction model
$f_{\theta}(x_{u,i})$ parameterized by $\theta$ aims to accurately predict the
ratings of all users for all items, and then recommend to the user the items
with the highest predicted ratings, as described in (Ricci et al., 2010). The
prediction matrix $\hat{\mathbf{R}}\in\mathbb{R}^{N\times M}$ comprises the
predicted ratings $f_{\theta}(x_{u,i})$ obtained from this prediction model.
If the rating matrix $\mathbf{R}$ had been fully observed, then the
_prediction inaccuracy_ $\mathcal{P}$ of the prediction model can be measured
using

$\mathcal{P}=\mathcal{P}(\hat{\mathbf{R}},\mathbf{R})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}e_{u,i},$

where $e_{u,i}=\ell(f_{\theta}(x_{u,i}),r_{u,i})$ is the prediction error, and
$\ell(\cdot,\cdot)$ is a pre-defined loss, such as the mean square error
(MSE), _i.e._ , $e_{u,i}=(f_{\theta}(x_{u,i})-r_{u,i})^{2}$. Let
$\mathbf{O}\in$ $\\{0,1\\}^{N\times M}$ be an indicator matrix, where each
entry $o_{u,i}$ is an observation indicator: $o_{u,i}=1$ if the rating
$r_{u,i}$ is observed, and $o_{u,i}=0$ if the rating $r_{u,i}$ is missing.
Given $\mathbf{R}^{o}$ as the set of the observed entries in the rating matrix
$\mathbf{R}$, the rating prediction model aims to train the prediction model
that minimizes the prediction inaccuracy $\mathcal{P}$. Nonetheless, as users
are free to choose items to rate, leading to the collection of observational
data that is always missing not at random (MNAR) (Marlin and Zemel, 2009; De
Myttenaere et al., 2014; Zhang et al., 2024), _e.g._ , the ratings with a
lower value are more likely to be missing. Let
$\mathcal{O}=\left\\{(u,i)\mid(u,i)\in\mathcal{D},o_{u,i}=1\right\\}$ be the
set of user-item pairs for the observed ratings, the direct use of the naive
estimator
$\mathcal{E}_{\mathrm{N}}=\mathcal{E}_{\mathrm{N}}(\hat{\mathbf{R}},\mathbf{R}^{o})=\frac{1}{|\mathcal{O}|}\sum_{(u,i)\in\mathcal{O}}e_{u,i}$
that computes on the observed data would yield severely biased estimation
(Schnabel et al., 2016; Wang et al., 2019).

###  2.2. Existing Estimators

To unbiasedly estimate the prediction inaccuracy $\mathcal{P}$ given the
partially observed ratings $\mathbf{R}^{o}$, the error-imputation-based (EIB)
approaches (Steck, 2010; Hernández-Lobato et al., 2014) compute an imputed
error $\hat{e}_{u,i}$ for each missing rating, and estimate the prediction
inaccuracy with

$\displaystyle\mathcal{E}_{\mathrm{EIB}}(\hat{\mathbf{R}},\mathbf{R}^{o})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}(o_{u,i}e_{u,i}+(1-o_{u,i})\hat{e}_{u,i}),$

which is an unbiased estimator of the prediction inaccuracy when the imputed
errors are accurate, _i.e._ , $\hat{e}_{u,i}=e_{u,i}$.

The inverse-propensity-scoring (IPS) approaches (Schnabel et al., 2016; Saito
et al., 2020) first learn $\hat{p}_{u,i}$ as the estimate of the propensity
$p_{u,i}=\mathbb{P}(o_{u,i}=1\mid x_{u,i})$, _i.e._ , the probability of
observing the rating, then inversely weight the prediction error for each
observed rating with the learned propensity, and estimate the prediction
inaccuracy with

$\displaystyle\mathcal{E}_{\mathrm{IPS}}(\hat{\mathbf{R}},\mathbf{R}^{o})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}e_{u,i}}{\hat{p}_{u,i}},$

which is an unbiased estimator of the prediction inaccuracy when the learned
propensities are accurate, _i.e._ , $\hat{p}_{u,i}=p_{u,i}$.

The doubly robust (DR) approaches (Wang et al., 2019; Li et al., 2023d, e, c)
use both the error imputation model and the propensity model to estimate the
prediction inaccuracy with

$\displaystyle\mathcal{E}_{\mathrm{DR}}(\hat{\mathbf{R}},\mathbf{R}^{o})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\left(\hat{e}_{u,i}+\frac{o_{u,i}(e_{u,i}-\hat{e}_{u,i})}{\hat{p}_{u,i}}\right),$

which is an unbiased estimator of the prediction inaccuracy when either the
imputed errors or the learned propensities are accurate, _i.e._ ,
$\hat{e}_{u,i}=e_{u,i}$ or $\hat{p}_{u,i}=p_{u,i}$, this is also known as
double robustness.

##  3\. Methodology

###  3.1. Task Formulation under OME

Despite many methods have been proposed for achieving unbiased learning to
tackle the data MNAR problem (Schnabel et al., 2016; Wang et al., 2019; Saito,
2020; Wang et al., 2023a; Li et al., 2024a), they ignore an alternative form
of bias caused by the inconsistency between the observed ratings and the
users’ true preferences, also known as noisy feedback or outcome measurement
errors (OME). Both data MNAR and OME arise from systematic bias during the
data collection. In RS, two common scenarios that cause incorrect user
feedback signals include the influence of public opinions (Zheng et al.,
2021), and the low-quality data collection such as recommender attacks (Gunes
et al., 2014) or carelessly filling out the after-sales assessments (Wang et
al., 2021a). Formally, we denote $\mathbf{R}^{*}$ as the user’s true
preference matrix, with $r^{*}_{u,i}$ as its entries, which may deviate from
the potentially observed ratings $r_{u,i}$. Let $\mathbb{P}({r}_{u,i}=0\mid
r^{*}_{u,i}=1)=\rho_{01}$ and $\mathbb{P}({r}_{u,i}=1\mid
r^{*}_{u,i}=0)=\rho_{10}$ be the false negative rate and false positive rate,
respectively, where $\rho_{01}+\rho_{10}<1$, then we have

$\mathbb{P}(r_{u,i}=1\mid
x_{u,i})=(1-\rho_{01})\cdot\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})+\rho_{10}\cdot\mathbb{P}(r^{*}_{u,i}=0\mid x_{u,i}).$

To make current debiased recommendation techniques more applicable to real-
world scenarios that may contain OME, we then establish a new model evaluation
criterion for the unbiased learning under OME, named _true prediction
inaccuracy_ , formally defined as

$\mathcal{P}^{*}=\mathcal{P}(\hat{\mathbf{R}},\mathbf{R}^{*})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}e_{u,i}^{*},$

where $e_{u,i}^{*}=\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i})$ is called the _true
prediction error._

###  3.2. Proposed OME-EIB, OME-IPS, and OME-DR Estimators

To achieve unbiased learning of $r^{*}_{u,i}$ using MNAR data with OME, a
typical class of methods (Natarajan et al., 2013; Liu and Tao, 2015) propose
the use of a surrogate loss $\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})$ based
on the observed labels $r_{u,i}$, which satisfies

$\mathbb{E}_{r\mid
r^{*}}[\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})]=\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i}).$

Considering the cases $r^{*}_{u,i}=1$ and $r^{*}_{u,i}=0$ separately, we have

$\displaystyle\left(1-\rho_{01}\right)\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),1)+\rho_{01}\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),0)=\ell(f_{\theta}(x_{u,i}),1),$
$\displaystyle\left(1-\rho_{10}\right)\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),0)+\rho_{10}\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),1)=\ell(f_{\theta}(x_{u,i}),0).$

Solving these equations for $\tilde{\ell}(f_{\theta}(x_{u,i}),1)$ and
$\tilde{\ell}(f_{\theta}(x_{u,i}),0)$ gives

$\displaystyle\tilde{\ell}(f_{\theta}(x_{u,i}),1)$
$\displaystyle=\frac{\left(1-\rho_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\rho_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\rho_{01}-\rho_{10}},$
$\displaystyle\tilde{\ell}(f_{\theta}(x_{u,i}),0)$
$\displaystyle=\frac{\left(1-\rho_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\rho_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\rho_{01}-\rho_{10}}.$

However, the existing surrogate loss-based methods require fully observed
noisy labels $r_{u,i}$, which prevents the direct use of such methods for RS
in the presence of missing data. To fill this gap, motivated by the broad
usage of EIB, IPS, and DR estimators in the missing data literature (Bang and
Robins, 2005; Little and Rubin, 2019), we extend the above surrogate loss-
based methods to address the data MNAR and OME in parallel.

Specifically, given knowledge of error parameters $\rho_{01}$ and $\rho_{10}$,
let
$\tilde{e}_{u,i}=r_{u,i}\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),1)+(1-r_{u,i})\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),0)$
be the surrogate loss with the rating $r_{u,i}$, the OME-EIB estimator
estimates the true prediction inaccuracy
$\mathcal{P}^{*}=\mathcal{P}(\hat{\mathbf{R}},\mathbf{R}^{*})$ with

$\displaystyle\mathcal{E}_{\mathrm{OME-
EIB}}(\hat{\mathbf{R}},\mathbf{R}^{o};\rho_{01},\rho_{10})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}(1-o_{u,i})\bar{e}_{u,i}{}+{}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}r_{u,i}\\{\left(1-\rho_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\rho_{01}\ell(f_{\theta}(x_{u,i}),0)\\}}{1-\rho_{01}-\rho_{10}}{}+{}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}(1-r_{u,i})\\{\left(1-\rho_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\rho_{10}\ell(f_{\theta}(x_{u,i}),1)\\}}{1-\rho_{01}-\rho_{10}},$

where $\bar{e}_{u,i}$ is the imputed error for estimating $\tilde{e}_{u,i}$,
and OME-EIB is an unbiased estimator of the true prediction inaccuracy when
the imputed errors are accurate, _i.e._ , $\bar{e}_{u,i}=\tilde{e}_{u,i}$.
Since the proof is not trivial, we postpone to show unbiasedness of OME-EIB
estimator and the following OME-IPS and OME-DR estimators in Sec. 3.4.

Similarly, the OME-IPS estimator estimates
$\mathcal{P}^{*}=\mathcal{P}(\hat{\mathbf{R}},\mathbf{R}^{*})$ with

$\displaystyle\mathcal{E}_{\mathrm{OME-
IPS}}(\hat{\mathbf{R}},\mathbf{R}^{o};\rho_{01},\rho_{10}){}={}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}r_{u,i}}{\hat{p}_{u,i}}\cdot\frac{\left(1-\rho_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\rho_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\rho_{01}-\rho_{10}}{}+{}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}(1-r_{u,i})}{\hat{p}_{u,i}}\cdot\frac{\left(1-\rho_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\rho_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\rho_{01}-\rho_{10}},$

where $\hat{p}_{u,i}$ is the learned propensity for estimating $p_{u,i}$, and
OME-IPS is an unbiased estimator of the true prediction inaccuracy when the
learned propensities are accurate, _i.e._ , $\hat{p}_{u,i}=p_{u,i}$.

The OME-DR estimator estimates
$\mathcal{P}^{*}=\mathcal{P}(\hat{\mathbf{R}},\mathbf{R}^{*})$ with

$\displaystyle\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\rho_{01},\rho_{10})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\left(1-\frac{o_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}{}+{}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}r_{u,i}}{\hat{p}_{u,i}}\cdot\frac{\left(1-\rho_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\rho_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\rho_{01}-\rho_{10}}{}+{}$
$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}(1-r_{u,i})}{\hat{p}_{u,i}}\cdot\frac{\left(1-\rho_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\rho_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\rho_{01}-\rho_{10}},$

which is an unbiased estimate of the true prediction inaccuracy when either
the imputed errors or the learned propensities are accurate, _i.e._ ,
$\bar{e}_{u,i}=\tilde{e}_{u,i}$ or $\hat{p}_{u,i}=p_{u,i}$.

###  3.3. Identification and Estimation of $\rho_{01}$ and $\rho_{10}$

The proposed OME-EIB, OME-IPS, and OME-DR estimators require knowledge of the
known error parameters $\rho_{01}$ and $\rho_{10}$, which are usually not
directly available from the collected data. By building upon the existing weak
separability assumption (Menon et al., 2015), we present a data-driven
identification and estimation method of $\rho_{01}$ and $\rho_{10}$.

We impose the following weak separability assumption that

$\inf_{(u,i)\in\mathcal{D}}\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})=0\quad\text{and}\quad\sup_{(u,i)\in\mathcal{D}}\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})=1,$

which also known as mutual irreducibility (Scott et al., 2013; Scott, 2015) in
the observational label noise literature. This does not require the true
ratings to be separable, _i.e._ , $\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})\in\\{0,1\\}$ for all user-item pairs, but instead stipulates that
there exist ”perfectly positive” and ”perfectly negative” samples among the
entire user-item pairs. In real-world recommendation scenarios, the weak
separability assumption is easily satisfied, providing there exists at least
one ”perfectly positive” feedback and one ”perfectly negative” feedback among
the thousands of collected ratings. For example, in the movie rating scenario,
”perfectly positive” feedback refers to at least one of the users who made a
positive review of the movie is fully reliable, and we do not need to know who
that user exactly is.

By noting the linkage between the observed and the true ratings

$\displaystyle\mathbb{P}(r_{u,i}=1\mid x_{u,i})={}$
$\displaystyle{}(1-\rho_{01})\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})+\rho_{10}\mathbb{P}(r^{*}_{u,i}=0\mid x_{u,i})$ $\displaystyle={}$
$\displaystyle{}(1-\rho_{01}-\rho_{10})\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})+\rho_{10},$

which demonstrates the monotonicity between $\mathbb{P}(r_{u,i}=1\mid
x_{u,i})$ and $\mathbb{P}(r^{*}_{u,i}=1\mid x_{u,i})$ under
$\rho_{01}+\rho_{10}<1$, we have

$\displaystyle(u^{<},i^{<})$
$\displaystyle=\arg\min_{(u,i)\in\mathcal{D}}\mathbb{P}(r_{u,i}=1\mid
x_{u,i})=\arg\min_{(u,i)\in\mathcal{D}}\mathbb{P}(r^{*}_{u,i}=1\mid x_{u,i}),$
$\displaystyle(u^{>},i^{>})$
$\displaystyle=\arg\max_{(u,i)\in\mathcal{D}}\mathbb{P}(r_{u,i}=1\mid
x_{u,i})=\arg\max_{(u,i)\in\mathcal{D}}\mathbb{P}(r^{*}_{u,i}=1\mid x_{u,i}).$

Then, we can identify the error parameters $\rho_{01}$ and $\rho_{10}$ via

$\rho_{01}=1-{}\mathbb{P}(r_{u^{>},i^{>}}=1\mid
x_{u^{>},i^{>}})\quad\text{and}\quad\rho_{10}=\mathbb{P}(r_{u^{<},i^{<}}=1\mid
x_{u^{<},i^{<}}),$

where $\mathbb{P}(r_{u^{>},i^{>}}=1\mid x_{u^{>},i^{>}})$ and
$\mathbb{P}(r_{u^{<},i^{<}}=1\mid x_{u^{<},i^{<}})$ can be unbiasedly
estimated from the existing EIB, IPS, or DR estimators for estimating
$\mathbb{P}(r_{u,i}=1\mid x_{u,i})$ without considering the OME.

###  3.4. Theoretical Analyses

Since the OME-DR estimator degenerates to the OME-IPS estimator when
$\bar{e}_{u,i}=0$, and degenerates to the OME-EIB estimator when
$\hat{p}_{u,i}=1$, without loss of generality, we only analyze the explicit
bias form of the OME-DR estimator. Following existing literature (Schnabel et
al., 2016; Wang et al., 2019), we assume that the indicator matrix
$\mathbf{O}$ contains independent random variables and each $o_{u,i}$ follows
a Bernoulli distribution with probability $p_{u,i}$. In addition, due to the
presence of OME, we also consider the randomness of the potentially observed
ratings $r_{u,i}$ given the true ratings $r^{*}_{u,i}$, _e.g._ , $r_{u,i}=1$
with probability $1-\rho_{01}$ given $r^{*}_{u,i}=1$, and $r_{u,i}=0$ with
probability $\rho_{01}$ given $r^{*}_{u,i}=1$.

###### Theorem 3.1 (Bias of OME-DR Estimator).

Given $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ with
$\hat{\rho}_{01}+\hat{\rho}_{10}<1$, imputed errors $\bar{\mathbf{E}}$ and
learned propensities $\hat{\mathbf{P}}$ with $\hat{p}_{u,i}>0$ for all user-
item pairs, the bias of the OME-DR estimator is

$\displaystyle\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]=\frac{1}{|\mathcal{D}|}\left|\sum_{(u,i)\in\mathcal{D}}\left(1-\frac{o_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}\right.+$
$\displaystyle\sum_{(u,i):r^{*}_{u,i}=1}\left(\frac{p_{u,i}\omega_{11}-\hat{p}_{u,i}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),1)+\frac{p_{u,i}\omega_{01}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),0)\right)+$
$\displaystyle\left.\sum_{(u,i):r^{*}_{u,i}=0}\left(\frac{p_{u,i}\omega_{10}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),1)+\frac{p_{u,i}\omega_{00}-\hat{p}_{u,i}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),0)\right)\right|,$

where $\omega_{11}$, $\omega_{01}$, $\omega_{10}$, and $\omega_{00}$ are given
by

$\displaystyle\omega_{11}$
$\displaystyle=\frac{1-\rho_{01}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{01}=\frac{\rho_{01}-\hat{\rho}_{01}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},$
$\displaystyle\omega_{10}$
$\displaystyle=\frac{\rho_{10}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{00}=\frac{1-\hat{\rho}_{01}-\rho_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

The bias of the OME-DR estimator includes the three terms: (1) The first term
shares a similar form to the bias of the previous IPS estimator and leads to
smaller bias when $\hat{p}_{u,i}\approx p_{u,i}$. (2) The second term is novel
for OME, specifically focusing on the estimated false negative rate
$\hat{\rho}_{01}$ that corresponds to the positive samples $r^{*}_{u,i}=1$.
Moreover, we find that $\omega_{11}=1$ and $\omega_{01}=0$ when the the
estimated false negative rate $\hat{\rho}_{01}$ is accurate, _i.e._ ,
$\hat{\rho}_{01}=\rho_{01}$, which results in smaller bias when
$\bar{e}_{u,i}\approx\tilde{e}_{u,i}$. (3) The third term is similar to the
second term, but instead focuses on the estimated false positive rate
$\hat{\rho}_{10}$ that corresponds to the negative samples $r^{*}_{u,i}=0$,
and also results in smaller bias when $\bar{e}_{u,i}\approx\tilde{e}_{u,i}$.
Given the importance of bias derivation for constructing estimators under OME,
we provide a proof sketch as below (see Appendix A for more details).

###### Proof Sketch.

By definition, bias of the OME-DR estimator is

$\displaystyle\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]=\left|\mathbb{E}_{\mathbf{R},\mathbf{O}}\left[\mathcal{E}_{\mathrm{OME-
DR}}\right]-\mathcal{P}^{*}\right|.$

Then, we can derive the bias of the OME-DR estimator as follows

$\displaystyle\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]=\left|\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\mathbb{E}_{\mathbf{O}}\left[\mathcal{E}_{\mathrm{OME-
DR}}\right]\right]-\mathcal{P}^{*}\right|$ $\displaystyle={}$
$\displaystyle{}\left|\frac{1}{|\mathcal{D}|}\sum_{(u,i):r^{*}_{u,i}=1}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right]-\ell(f_{\theta}(x_{u,i}),1)\right.$
$\displaystyle+{}$
$\displaystyle{}\left.\frac{1}{|\mathcal{D}|}\sum_{(u,i):r^{*}_{u,i}=0}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right]-\ell(f_{\theta}(x_{u,i}),0)\right|.$

For the user-item pairs with $r^{*}_{u,i}=1$, we have

$\displaystyle\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\tilde{e}_{u,i}\right]$
$\displaystyle={}$
$\displaystyle{}\left(1-\rho_{01}\right)\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),1;\hat{\rho}_{01},\hat{\rho}_{10})+\rho_{01}\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),0;\hat{\rho}_{01},\hat{\rho}_{10})$
$\displaystyle={}$
$\displaystyle{}\left(1-\rho_{01}\right)\cdot\frac{\left(1-\hat{\rho}_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\hat{\rho}_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$
$\displaystyle{}+\rho_{01}\cdot\frac{\left(1-\hat{\rho}_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\hat{\rho}_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$
$\displaystyle={}$
$\displaystyle{}\frac{1-\rho_{01}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),1)+\frac{\rho_{01}-\hat{\rho}_{01}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),0)$
$\displaystyle:={}$
$\displaystyle{}\omega_{11}\ell(f_{\theta}(x_{u,i}),1)+\omega_{01}\ell(f_{\theta}(x_{u,i}),0),$

where $\omega_{11}$ and $\omega_{01}$ are given by

$\displaystyle\omega_{11}=\frac{1-\rho_{01}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{01}=\frac{\rho_{01}-\hat{\rho}_{01}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

Similar results hold for the user-item pairs with $r^{*}_{u,i}=0$ that

$\displaystyle\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\tilde{e}_{u,i}\right]$
$\displaystyle={}$
$\displaystyle{}\frac{\rho_{10}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),1)+\frac{1-\hat{\rho}_{01}-\rho_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),0)$
$\displaystyle:={}$
$\displaystyle{}\omega_{10}\ell(f_{\theta}(x_{u,i}),1)+\omega_{00}\ell(f_{\theta}(x_{u,i}),0),$

where $\omega_{10}$ and $\omega_{00}$ are given by

$\displaystyle\omega_{10}=\frac{\rho_{10}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{00}=\frac{1-\hat{\rho}_{01}-\rho_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

This completes the proof. ∎

We formally describe double robustness under OME as follows.

###### Corollary 3.2 (Double Robustness).

Given $\hat{\rho}_{01}=\rho_{01}$ and $\hat{\rho}_{10}=\rho_{10}$, the OME-DR
estimator is unbiased when either imputed errors $\bar{\mathbf{E}}$ or learned
propensities $\hat{\mathbf{P}}$ are accurate for all user-item pairs.

The above result is obtained via substituting either
$\bar{e}_{u,i}=\tilde{e}_{u,i}$ or $\hat{p}_{u,i}=p_{u,i}$ into the bias of
the OME-DR estimator in Theorem 3.1. Given the estimated error parameters
$\hat{\rho}_{01}$ and $\hat{\rho}_{01}$, we obtain the optimal prediction
model under OME by minimizing the OME-DR estimator over a hypothesis space
$\mathcal{F}$ of the prediction models $f_{\theta}$

$\displaystyle\hat{\mathbf{R}}^{\ddagger}=\arg\min_{f_{\theta}\in\mathcal{F}}\\{\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})\\}.$

We next derive the generalization bound of the optimal prediction model in
terms of the empirical Rademacher complexity (Shalev-Shwartz and Ben-David,
2014). The basic idea of proving the performance guarantee under OME is to
exploit the inheritance of the Lipschitz continuity from the ture prediction
loss $\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i})$ to the surrogate loss
$\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})$.

###### Lemma 3.3 (Lipschitz Continuity).

Given $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ with
$\hat{\rho}_{01}+\hat{\rho}_{10}<1$, if
$\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i})$ is $L$-Lipschitz in
$f_{\theta}(x_{u,i})$ for all $r^{*}_{u,i}$, then
$\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})$ is
$\frac{2L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$-Lipschitz in
$f_{\theta}(x_{u,i})$ for all $r_{u,i}$.

The above lemma immediately leads to a generalization bound with respect to
the true ratings by using the contraction principle for Rademacher complexity
(see Appendix A for proofs).

###### Theorem 3.4 (Generalization Bound).

Given $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ with
$\hat{\rho}_{01}+\hat{\rho}_{10}<1$, suppose
$\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i})$ is $L$-Lipschitz in
$f_{\theta}(x_{u,i})$ for all $r^{*}_{u,i}$, and $\hat{p}_{u,i}\geq C_{p}$,
$|\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})|\leq C_{l}$ for all $r_{u,i}$,
then with probability $1-\eta$, the true prediction inaccuracy
$\mathcal{P}(\hat{\mathbf{R}}^{\ddagger},\mathbf{R}^{*})$ of the optimal
prediction matrix using the OME-DR estimator with imputed errors
$\bar{\mathbf{E}}$ and learned propensities $\hat{\mathbf{P}}$ has the upper
bound

$\displaystyle\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}}^{\ddagger},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})+\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}}^{\ddagger},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]+$
$\displaystyle\left(1+\frac{2}{C_{p}}\right)\left[\frac{4L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\mathcal{R}(\mathcal{F})+\left(C_{l}+\frac{4L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\right)\sqrt{\frac{2\log(4/\eta)}{|\mathcal{D}|}}\right],$

where $\mathcal{R}(\mathcal{F})$ is the empirical Rademacher complexity
defined as

$\mathcal{R}(\mathcal{F})=\mathbb{E}_{\mathbf{\sigma}\sim\\{-1,+1\\}^{|\mathcal{D}|}}\sup_{f_{\theta}\in\mathcal{F}}\left[\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\sigma_{u,i}f_{\theta}(x_{u,i})\right],$

in which $\mathbf{\sigma}=\\{\sigma_{u,i}:(u,i)\in\mathcal{D}\\}$, and
$\sigma_{u,i}$ are independent uniform random variables taking values in
$\\{-1,+1\\}$. The random variables $\sigma_{u,i}$ are called Rademacher
variables.

Table 1. RE on ML-100K dataset with $\rho_{01}$ = 0.2 and $\rho_{10}$ = 0.1.
The best two results are bolded and the best baseline is underlined.

| ROTATE | SKEW | CRS | ONE | THREE | FIVE
---|---|---|---|---|---|---
Naive (Koren et al., 2009) | 0.125 $\pm$ 0.002 | 0.179 $\pm$ 0.001 | 0.175 $\pm$ 0.002 | 0.241 $\pm$ 0.002 | 0.264 $\pm$ 0.003 | 0.299 $\pm$ 0.003
OME ($\hat{\rho}_{01},\hat{\rho}_{10}$) | 0.087 $\pm$ 0.006 | 0.163 $\pm$ 0.002 | 0.104 $\pm$ 0.014 | 0.161 $\pm$ 0.013 | 0.179 $\pm$ 0.014 | 0.213 $\pm$ 0.014
OME ($\rho_{01},{\rho}_{10}$) | 0.024 $\pm$ 0.003 | 0.136 $\pm$ 0.002 | 0.105 $\pm$ 0.004 | 0.067 $\pm$ 0.004 | 0.076 $\pm$ 0.004 | 0.100 $\pm$ 0.004
MRDR (Guo et al., 2021) | 0.098 $\pm$ 0.003 | 0.089 $\pm$ 0.001 | 0.099 $\pm$ 0.002 | 0.172 $\pm$ 0.004 | 0.190 $\pm$ 0.004 | 0.194 $\pm$ 0.004
SDR (Li et al., 2023f) | 0.097 $\pm$ 0.002 | 0.089 $\pm$ 0.001 | 0.102 $\pm$ 0.002 | 0.172 $\pm$ 0.003 | 0.191 $\pm$ 0.003 | 0.194 $\pm$ 0.003
TDR (Li et al., 2023b) | 0.092 $\pm$ 0.002 | 0.080 $\pm$ 0.001 | 0.103 $\pm$ 0.002 | 0.171 $\pm$ 0.003 | 0.189 $\pm$ 0.003 | 0.195 $\pm$ 0.003
EIB (Steck, 2010) | 0.366 $\pm$ 0.001 | 0.256 $\pm$ 0.001 | 0.150 $\pm$ 0.001 | 0.562 $\pm$ 0.001 | 0.605 $\pm$ 0.001 | 0.635 $\pm$ 0.001
OME-EIB ($\hat{\rho}_{01},\hat{\rho}_{10}$) | 0.362 $\pm$ 0.001 | 0.255 $\pm$ 0.001 | 0.144 $\pm$ 0.001 | 0.554 $\pm$ 0.001 | 0.598 $\pm$ 0.001 | 0.627 $\pm$ 0.001
OME-EIB (${\rho}_{01},{\rho}_{10}$) | 0.357 $\pm$ 0.001 | 0.253 $\pm$ 0.001 | 0.144 $\pm$ 0.001 | 0.546 $\pm$ 0.001 | 0.589 $\pm$ 0.001 | 0.618 $\pm$ 0.001
IPS (Schnabel et al., 2016) | 0.110 $\pm$ 0.002 | 0.116 $\pm$ 0.002 | 0.134 $\pm$ 0.003 | 0.212 $\pm$ 0.004 | 0.231 $\pm$ 0.004 | 0.254 $\pm$ 0.004
OME-IPS ($\hat{\rho}_{01},\hat{\rho}_{10}$) | 0.060 $\pm$ 0.003 | 0.096 $\pm$ 0.002 | 0.075 $\pm$ 0.017 | 0.111 $\pm$ 0.006 | 0.125 $\pm$ 0.007 | 0.144 $\pm$ 0.007
OME-IPS (${\rho}_{01},{\rho}_{10}$) | 0.013 $\pm$ 0.003∗ | 0.068 $\pm$ 0.003∗ | 0.052 $\pm$ 0.004∗ | 0.034 $\pm$ 0.005∗ | 0.038 $\pm$ 0.006∗ | 0.050 $\pm$ 0.005∗
DR (Saito, 2020) | 0.106 $\pm$ 0.002 | 0.087 $\pm$ 0.001 | 0.104 $\pm$ 0.002 | 0.190 $\pm$ 0.003 | 0.209 $\pm$ 0.003 | 0.216 $\pm$ 0.003
OME-DR ($\hat{\rho}_{01},\hat{\rho}_{10}$) | 0.056 $\pm$ 0.004 | 0.067 $\pm$ 0.001 | 0.045 $\pm$ 0.018 | 0.090 $\pm$ 0.006 | 0.102 $\pm$ 0.006 | 0.106 $\pm$ 0.007
OME-DR (${\rho}_{01},{\rho}_{10}$) | 0.009 $\pm$ 0.003∗ | 0.039 $\pm$ 0.002∗ | 0.022 $\pm$ 0.003∗ | 0.013 $\pm$ 0.004∗ | 0.016 $\pm$ 0.005∗ | 0.012 $\pm$ 0.004∗

  * •

Note: * means statistically significant results ($\text{p-value}\leq 0.05$)
using the paired-t-test compared with the best baseline.

###  3.5. Alternating Denoise Training Approach

Input: observed ratings $\mathbf{R}^{o}$, learned propensities
$\hat{p}_{u,i}$, initial estimates $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$, a
pre-trained model $h_{\theta^{\prime}}(x_{u,i})$ for estimating
$\mathbb{P}(r_{u,i}=1\mid x_{u,i})$ via existing method.

1 while  _stopping criteria is not satisfied_ do

2 for  _number of steps for training the denoising prediction model_ do

3 Sample a batch $\\{(u_{j},i_{j})\\}_{j=1}^{J}$ from $\mathcal{D}$;

4 Update $\theta$ by descending along the gradient
$\nabla_{\theta}\mathcal{E}_{\mathrm{OME-
DR}}(\theta,\phi;\hat{\rho}_{01},\hat{\rho}_{10})$;

5 $(u^{<},i^{<})\leftarrow\arg\min_{(u,i)\in\mathcal{D}}f_{\theta}(x_{u,i})$;

6 $(u^{>},i^{>})\leftarrow\arg\max_{(u,i)\in\mathcal{D}}f_{\theta}(x_{u,i})$;

7 end for

8

9 for  _number of steps for training the denoising imputation model_ do

10 $\hat{\rho}_{01}\leftarrow 1-h_{\theta^{\prime}}(x_{u^{>},i^{>}})$ and
$\hat{\rho}_{10}\leftarrow h_{\theta^{\prime}}(x_{u^{<},i^{<}})$;

11 Sample a batch $\\{(u_{k},i_{k})\\}_{k=1}^{K}$ from $\mathcal{O}$;

12 Update $\phi$ by descending along the gradient
$\nabla_{\phi}\mathcal{L}_{\bar{e}}(\theta,\phi;\hat{\rho}_{01},\hat{\rho}_{10})$;

13

14 end for

15

16 end while

Algorithm 1 Alternating Denoise Training with OME-DR.

We further propose an alternating denoise training approach to achieve
unbiased learning of the prediction model, which corrects for data MNAR and
OME in parallel. Specifically, we first train a propensity model using the
observed MNAR data. Based on the estimated propensities, the denoising
prediction and imputation models are alternately updated, which also
facilitates the accurate estimations $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$
of the error parameters $\rho_{01}$ and $\rho_{10}$.

Propensity Estimation via Logistic Regression. Since unbiased ratings are
difficult to be collected in the real-world scenarios (Saito and Nomura,
2022), following previous studies (Schnabel et al., 2016; Li et al., 2023b),
we adopt logistic regression to train a propensity model
$\hat{p}_{u,i}=\sigma(w^{\top}x_{u,i}+\beta_{u}+\gamma_{i})$ parameterized by
$\psi=(w,\beta_{1},\dots,\beta_{N},\gamma_{1},\dots,\gamma_{M})$ using the
observed MNAR data, where $\sigma(\cdot)$ is the sigmoid function,
$w\in\mathbb{R}^{N+M}$ is the weight vector, $\beta_{u}$ and $\gamma_{i}$ are
the user-specific and item-specific constants, respectively. We train the
propensity model by minimizing the loss

$\displaystyle\mathcal{L}_{p}(\psi)=-\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}o_{u,i}\log(\hat{p}_{u,i})+(1-o_{u,i})\log(1-\hat{p}_{u,i}).$

Denoising Prediction Model Training. Based on the learned propensities
$\hat{p}_{u,i}$, imputed errors $\bar{e}_{u,i}(\phi)$, and initial estimates
$\hat{\rho}_{01}$ and $\hat{\rho}_{10}$, we train the denoising prediction
model by minimizing the estimated true prediction inaccuracy from the proposed
OME-DR estimator $\mathcal{E}_{\mathrm{OME-
DR}}(\theta,\phi;\hat{\rho}_{01},\hat{\rho}_{10})$. To obtain more accurate
estimates $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ from the training loop, we
then compute the minimum and maximum predicted ratings in the training batch
to update $(u^{<},i^{<})$ and $(u^{>},i^{>})$, respectively. The choice not to
employ a separate noisy rating prediction model for computing $(u^{<},i^{<})$
and $(u^{>},i^{>})$ is guaranteed by the monotonicity between
$\mathbb{P}(r_{u,i}=1\mid x_{u,i})$ and $\mathbb{P}(r^{*}_{u,i}=1\mid
x_{u,i})$ (see Sec. 3.3 for proofs), where the latter has a larger gap between
the minimum and the maximum, making it easier to distinguish $(u^{<},i^{<})$
and $(u^{>},i^{>})$.

Denoising Imputation Model Training. Given a pre-trained model
$h_{\theta^{\prime}}(x_{u,i})$ for estimating $\mathbb{P}(r_{u,i}=1\mid
x_{u,i})$ via existing methods (Schnabel et al., 2016; Wang et al., 2019), we
update the estimates $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ by computing
$1-h_{\theta^{\prime}}(x_{u^{>},i^{>}})$ and
$h_{\theta^{\prime}}(x_{u^{<},i^{<}})$, respectively. We finally train the
denoising imputation model $\bar{e}_{u,i}(\phi)$ by minimizing the loss

$\mathcal{L}_{\bar{e}}(\theta,\phi;\hat{\rho}_{01},\hat{\rho}_{10})=\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\frac{o_{u,i}(\tilde{e}_{u,i}-{\bar{e}}_{u,i})^{2}}{\hat{p}_{u,i}}.$

The overall training process with OME-DR is summarized in Alg. 1.

(a) Estimation error of $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$

(b) RE on EIB-based methods

(c) RE on IPS-based methods

(d) RE on DR-based methods

Figure 1. Estimation errors of $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ and RE
with varying observed data ratios. Table 2. Performance on AUC, NDCG@K, and
Recall@K on the MAR test set of Coat, Music and KuaiRec with $\rho_{01}$ = 0.2
and $\rho_{10}$ = 0.1. The best three results are bolded, and the best
baseline is underlined.

| Coat | Music | KuaiRec
---|---|---|---
Method | AUC | NDCG@5 | Recall@5 | AUC | NDCG@5 | Recall@5 | AUC | NDCG@50 | Recall@50
MF (Koren et al., 2009) | 0.619±0.002 | 0.531±0.005 | 0.364±0.005 | 0.632±0.005 | 0.616±0.003 | 0.361±0.001 | 0.621±0.002 | 0.652±0.003 | 0.702±0.002
OME (Liu and Tao, 2015) | 0.621±0.003 | 0.543±0.006 | 0.371±0.007 | 0.650±0.005 | 0.615±0.004 | 0.373±0.004 | 0.645±0.002 | 0.660±0.002 | 0.722±0.002
T-MF (Wang et al., 2021a) | 0.633±0.004 | 0.540±0.005 | 0.372±0.006 | 0.650±0.005 | 0.614±0.003 | 0.376±0.004 | 0.657±0.002 | 0.665±0.002 | 0.739±0.003
R-MF (Wang et al., 2021a) | 0.641±0.004 | 0.544±0.005 | 0.376±0.009 | 0.657±0.005 | 0.614±0.006 | 0.371±0.004 | 0.645±0.002 | 0.661±0.001 | 0.720±0.003
LCD-MF (Dai et al., 2022b) | 0.631±0.003 | 0.552±0.007 |  0.381±0.006 | 0.659±0.005 | 0.617±0.005 | 0.374±0.004 | 0.664±0.003 | 0.677±0.003 | 0.738±0.003
EIB (Steck, 2010) | 0.621±0.003 | 0.547±0.006 | 0.368±0.008 | 0.648±0.003 | 0.620±0.002 | 0.371±0.002 | 0.641±0.001 | 0.653±0.001 | 0.713±0.002
IPS (Schnabel et al., 2016) | 0.625±0.002 | 0.534±0.009 | 0.360±0.008 | 0.648±0.001 | 0.615±0.001 | 0.369±0.001 | 0.636±0.001 | 0.642±0.002 | 0.714±0.001
SNIPS (Schnabel et al., 2016) | 0.631±0.004 | 0.544±0.008 | 0.369±0.007 | 0.659±0.005 | 0.617±0.005 | 0.375±0.004 | 0.657±0.002 | 0.670±0.001 | 0.735±0.001
CVIB (Wang et al., 2020) | 0.626±0.001 | 0.552±0.009 | 0.379±0.004 | 0.661±0.001 | 0.612±0.002 | 0.381±0.001 | 0.653±0.001 | 0.644±0.001 | 0.736±0.001
DAMF (Saito and Nomura, 2022) | 0.631±0.004 | 0.548±0.006 | 0.367±0.006 | 0.640±0.003 | 0.627±0.002 | 0.377±0.004 | 0.657±0.003 | 0.669±0.003 | 0.735±0.004
DR (Saito, 2020) | 0.633±0.009 | 0.548±0.015 | 0.360±0.011 | 0.654±0.009 | 0.613±0.007 | 0.372±0.005 | 0.643±0.002 | 0.650±0.001 | 0.721±0.001
DR-JL (Wang et al., 2019) | 0.633±0.005 | 0.546±0.006 | 0.366±0.007 | 0.650±0.002 | 0.617±0.001 | 0.382±0.001 | 0.644±0.001 | 0.669±0.002 | 0.725±0.002
MRDR-JL (Guo et al., 2021) | 0.634±0.005 | 0.538±0.010 | 0.373±0.008 | 0.659±0.002 | 0.624±0.007 | 0.376±0.006 | 0.658±0.003 | 0.670±0.002 | 0.741±0.003
DR-BIAS (Dai et al., 2022a) | 0.632±0.004 | 0.549±0.009 | 0.369±0.008 | 0.660±0.001 | 0.619±0.003 | 0.378±0.002 | 0.665±0.004 | 0.679±0.004 | 0.737±0.002
DR-MSE (Dai et al., 2022a) | 0.631±0.003 | 0.557±0.008 | 0.374±0.008 | 0.662±0.002 | 0.623±0.004 | 0.374±0.002 | 0.653±0.002 | 0.660±0.002 | 0.732±0.002
DIB (Liu et al., 2021) | 0.626±0.003 | 0.550±0.009 | 0.376±0.006 | 0.647±0.005 | 0.626±0.005 | 0.382±0.006 | 0.641±0.002 | 0.642±0.003 | 0.738±0.003
MR (Li et al., 2023a) | 0.630±0.005 | 0.546±0.009 | 0.376±0.007 | 0.656±0.005 | 0.623±0.004 | 0.380±0.004 | 0.637±0.002 | 0.644±0.004 | 0.723±0.002
SDR (Li et al., 2023f) | 0.635±0.005 | 0.543±0.005 | 0.368±0.006 | 0.660±0.006 | 0.618±0.006 | 0.376±0.005 | 0.661±0.003 | 0.675±0.001 | 0.739±0.002
TDR (Li et al., 2023b) | 0.638±0.007 | 0.556±0.014 | 0.370±0.013 | 0.657±0.004 | 0.616±0.002 | 0.371±0.003 | 0.650±0.002 | 0.670±0.001 | 0.723±0.003
IPS-V2 (Li et al., 2023e) | 0.631±0.005 | 0.549±0.008 | 0.373±0.008 | 0.648±0.005 | 0.615±0.005 | 0.373±0.004 | 0.658±0.002 | 0.675±0.003 | 0.734±0.002
DR-V2 (Li et al., 2023e) | 0.631±0.005 | 0.553±0.009 | 0.378±0.006 | 0.636±0.003 | 0.620±0.002 | 0.392±0.004 | 0.658±0.001 | 0.671±0.001 | 0.734±0.002
OME-EIB (ours) | 0.627±0.002 | 0.563${}^{*}_{\pm 0.002}$ | 0.387${}^{*}_{\pm 0.002}$ | 0.664±0.003 | 0.622±0.004 | 0.384±0.005 | 0.667±0.003 | 0.682${}^{*}_{\pm 0.002}$ | 0.742±0.002
OME-IPS (ours) | 0.636±0.002 | 0.548±0.003 | 0.373±0.004 | 0.664±0.003 | 0.625±0.002 | 0.385±0.002 | 0.671${}^{*}_{\pm 0.002}$ | 0.693${}^{*}_{\pm 0.004}$ | 0.763${}^{*}_{\pm 0.002}$
OME-DR (ours) | 0.651${}^{*}_{\pm 0.006}$ | 0.561±0.006 | 0.385${}^{*}_{\pm 0.005}$ | 0.671${}^{*}_{\pm 0.003}$ | 0.632${}^{*}_{\pm 0.003}$ | 0.389±0.002 | 0.662±0.002 | 0.677±0.004 | 0.743±0.002

  * •

Note: * means statistically significant results ($\text{p-value}\leq 0.05$)
using the paired-t-test compared with the best baseline.

##  4\. Semi-Synthetic Experiments

To investigate if the proposed estimators are able to estimate the true
prediction inaccuracy accurately in the presence of OME and MNAR effect,
several semi-synthetic experiments are conducted on a widely-used dataset
MovieLens-100K (ML-100K). We first adopt MF to complete the five-scaled rating
matrix $\mathbf{R}$. However, the completed matrix will have an unrealistic
rating distribution, thus we sort the matrix entries in ascending order and
assign a positive feedback probability of 0.1 for the lowest $p_{1}$
proportion, a positive feedback probability of 0.3 for the next $p_{2}$
proportion, and so on to obtain a true positive feedback probability
$\gamma_{u,i}$ for each user-item pair. The adjusted probability matrix
contains $\gamma_{u,i}\in\\{0.1,0.3,0.5,0.7,0.9\\}$ with proportion
$\left[p_{1},p_{2},p_{3},p_{4},p_{5}\right]$, respectively.

Second, following the previous studies (Wang et al., 2019; Schnabel et al.,
2016; Guo et al., 2021), we use six matrices below as the prediction matrix
$\hat{\mathbf{R}}$:
$\bullet$ ROTATE: Set predicted $\hat{r}_{u,i}=\gamma_{u,i}-0.2$ when
$\gamma_{u,i}\geq 0.3$, and $\hat{r}_{u,i}=0.9$ when $\gamma_{u,i}=0.1$.
$\bullet$ SKEW: Predicted $\hat{r}_{u,i}$ are sampled from the Gaussian
distribution $\mathcal{N}(\mu=\gamma_{u,i},\sigma=(1-\gamma_{u,i})/{2})$, and
clipped to the interval $[0.1,0.9]$.
$\bullet$ CRS: If the true $\gamma_{u,i}\leq 0.6$, then $\hat{r}_{u,i}=0.2$.
Otherwise, $\hat{r}_{u,i}=0.6$.
$\bullet$ ONE: The predicted matrix $\mathbf{\hat{R}}$ is identical to the
true positive feedback probability matrix, except that randomly select
$\gamma_{u,i}=0.1$ with total amount $|\\{(u,i)\mid\gamma_{u,i}=0.9\\}|$ are
flipped to 0.9.
$\bullet$ THREE: Same as ONE, but flipping $\gamma_{u,i}=0.3$ instead.
$\bullet$ FIVE: Same as ONE, but flipping $\gamma_{u,i}=0.5$ instead.

Next, we assign the propensity $p_{u,i}=p\alpha^{\min(4,6-r_{u,i})}$ for each
user-item pair and obtain the estimate propensities

$\frac{1}{\hat{p}_{u,i}}=\frac{1-{\beta}}{p_{u,i}}+\frac{\beta}{p_{e}},$

where $p_{e}=|\mathcal{D}|^{-1}\sum_{(u,i)\in\mathcal{D}}o_{u,i}$, $p$ is set
to 1 in our experiment and $\beta$ is randomly sampled from a uniform
distribution ${U}(0,\,1)$ to introduce noises. Then, we sample the binary true
feedback matrix $\mathbf{R}^{*}$ and binary observation matrix $\mathbf{O}$ as
follows:

$o_{u,i}\sim\operatorname{Bern}(p_{u,i}),\forall(u,i)\in\mathcal{D},\quad
r^{*}_{u,i}\sim\operatorname{Bern}(\gamma_{u,i}),\forall(u,i)\in\mathcal{D},$

where $\operatorname{Bern}(\cdot)$ denotes the Bernoulli distribution. Then we
flip the feedback matrix according to the $\rho_{01}$ and $\rho_{10}$ to
generate a binary noise feedback matrix $\mathbf{R}$. The absolute relative
error (RE) is used for evaluation, which is defined as
$\operatorname{RE}(\mathcal{E}_{est})=|\mathcal{P}^{*}-\mathcal{E}_{est}(\hat{\mathbf{R}},\mathbf{R})|/\mathcal{P}^{*}$,
where $\mathcal{E}_{est}$ denotes the estimate prediction inaccuracy. The
smaller the RE, the more accurate the estimation. In addition, we provide both
results for using estimated $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$ to
estimate $\mathcal{P}^{*}$ and directly using true $\rho_{01}$ and $\rho_{10}$
to estimate $\mathcal{P}^{*}$.

Performance Comparison. We compare the proposed methods with the Naive method
(Koren et al., 2009), the EIB method (Steck, 2010), the IPS method (Schnabel
et al., 2016), and the DR-based methods (Wang et al., 2019; Guo et al., 2021;
Li et al., 2023b, f). The RE results are shown in Table 1 with $\rho_{01}=0.2$
and $\rho_{10}=0.1$. First, most debiasing and denoising methods have lower RE
than the Naive method. In addition, our proposed methods stably and
significantly outperform the corresponding debiasing baseline methods.
Meanwhile, the OME methods are only able to denoising, thus they still have a
large RE, even the true $\rho$ is used for estimation. This shows the
effectiveness of our method in the presence of both the OME and MNAR effects.

In Depth Analysis. We explore the effect of the proportion of observed data on
the estimation accuracy of $\hat{\rho}_{01}$ and $\hat{\rho}_{10}$, and the
results when $\rho_{01}=0.2$ and $\rho_{10}=0.1$ are shown in Figure 1. We
take ROTATE as an example, and the same phenomenon is observed for the other
five prediction matrices. First, our methods stably outperform the baseline
methods in all scenarios. Second, the estimation error decreases significantly
as the proportion of observed data increases. Moreover, even with the
estimation error, our estimation results are only slightly worse than using
the real $\rho$. This further validates the stability and practicality of our
methods.

##  5\. Real-World Experiments

Datasets and Experiment Details. We verify the effectiveness of our methods on
three real-world datasets: Coat (Schnabel et al., 2016), Music (Schnabel et
al., 2016) and KuaiRec (Gao et al., 2022b). Coat includes 6,960 MNAR ratings
and 4,640 missing-at-random (MAR) ratings from 290 users to 300 items. Music
has 311,704 MNAR ratings and 54,000 MAR ratings of 15,400 users to 1,000
items. For Coat and Music, we binarize the ratings less than three to 0 and
otherwise to 1. KuaiRec is a fully exposed large-scale industrial dataset,
which has 4,676,570 video watching ratio records from 1,411 users to 3,327
items. We binarize the records less than one to 0 and otherwise to 1. We adopt
three common metrics, _i.e._ , AUC, NDCG@K, and Recall@K for performance
evaluation. For Coat and Music, K is set to 5. For KuaiRec, K is set to 50.
All the experiments are implemented on PyTorch with Adam as the optimizer. For
all experiments, we use GeForce RTX 3090 as the computing resource. Logistic
regression is used as the propensity model for all the methods requiring
propensity. The learning rate is tuned in $\\{0.001,0.005,0.01,0.05\\}$ and
the batch size is tuned in $\\{64,128,256\\}$ for Coat and
$\\{2048,4096,8192\\}$ for Music and KuaiRec. We tune the embedding dimension
in $\\{4,8,16,32\\}$ for Coat and $\\{8,16,32,64\\}$ for Music and KuaiRec.
Moreover, we tune the weight decay rate in $[1e-6,5e-3]$.

Baselines. We use matrix factorization (MF) (Koren et al., 2009) as the base
model and compare our methods to the following debiasing methods: EIB (Steck,
2010), IPS (Schnabel et al., 2016), SNIPS (Schnabel et al., 2016), CVIB (Wang
et al., 2020), DAMF (Saito and Nomura, 2022), DR (Saito, 2020), DR-JL (Wang et
al., 2019), MRDR-JL (Guo et al., 2021), DR-BIAS (Dai et al., 2022a), DR-MSE
(Dai et al., 2022a), DIB (Liu et al., 2021), MR (Li et al., 2023a), SDR (Li et
al., 2023f), TDR (Li et al., 2023b), IPS-V2 (Li et al., 2023e) and DR-V2 (Li
et al., 2023e). We also compare denoising methods including surrogate loss
minimization (OME) (Liu and Tao, 2015), T-MF (Wang et al., 2021a), R-MF (Wang
et al., 2021a), and LCD-MF (Dai et al., 2022b).

Performance Comparision. Table 2 shows the prediction performance with varying
baselines and our methods. First, most of the debiasing and denoising methods
have better performance compared to the Naive method, which shows the
necessity of debiasing and denoising. Meanwhile, our methods exhibit the most
competitive performance in all three datasets, significantly outperforming the
baselines including debiasing methods and denoising methods.

##  6\. Related Work

###  6.1. Debiased Recommendation

The data collected in recommender systems are often systematically subject to
varying types of bias, such as conformity bias (Liu et al., 2016), item
popularity bias (Wei et al., 2021; Zhang et al., 2021), latent confounders
(Ding et al., 2022; Li et al., 2023d), and position bias (Oosterhuis, 2022,
2023). In order to achieve unbiased learning of the prediction model, three
typical approaches have been proposed, including: (1) The error-imputation-
based (EIB) approaches (Steck, 2010; Hernández-Lobato et al., 2014; Saito,
2020), which compute an imputed error for each missing rating. (2) The
inverse-propensity-scoring (IPS) approaches (Schnabel et al., 2016; Saito et
al., 2020; Swaminathan and Joachims, 2015; Saito, 2019), which inversely
weight the prediction error for each observed rating with the probability of
observing that rating. (3) The doubly robust (DR) approaches (Wang et al.,
2019; Saito, 2020; Kweon and Yu, 2024), which use both the error imputation
model and the propensity model, and the unbiased learning of the prediction
model can be achieved when either the error imputation model or the propensity
model is accurate. Based on the above EIB, IPS, and DR estimators, in terms of
learning paradigms, recent studies have investigated flexible trade-offs
between bias and variance (Guo et al., 2021; Dai et al., 2022a), parameter
sharing in multi-task learning (Ma et al., 2018; Zhang et al., 2020a; Wang et
al., 2022a), and the use of a few unbiased ratings to improve the estimation
of the prediction inaccuracy (Bonner and Vasile, 2018; Chen et al., 2021a; Liu
et al., 2020; Wang et al., 2021b; Liu et al., 2022; Lin et al., 2023). In
terms of statistical theory, recent studies have developed targeted DR (TDR)
(Li et al., 2023b) and conservative DR (CDR) (Song et al., 2023) to combat the
inaccurate imputed errors, StableDR (Li et al., 2023f) to combat sparse data,
and new propensity estimation methods based on balancing metrics (Luo et al.,
2021; Li et al., 2023e; Yang et al., 2023). In addition, (Saito and Nomura,
2022) proposes to minimize the propensity-independent generalization error
bound via adversarial learning. (Li et al., 2023a) extends DR to multiple
robust learning. These methods have also been applied to sequential
recommendation (Wang et al., 2022b) and social recommendation (Chen et al.,
2018). Furthermore, methods based on information bottlenecks (Liu et al.,
2021; Wang et al., 2020) and representation learning (Yang et al., 2023; Pan
et al., 2023) have also been proposed for debiased recommendation. In this
work, we extend the previous debiasing methods to a more realistic RS
scenario, in which the observed ratings and the users’ true preferences may be
different.

###  6.2. Outcome Measurement Error

Outcome measurement error (OME) refers to the inconsistency between the
observed outcomes and the true outcomes, also known as noisy outcomes in
social science (Roberts, 1985), biostatistics (Hui and Walter, 1980), and
psychometrics (Shrout and Lane, 2012). The error models or transition matrices
in OME establish the relation between the true outcomes and the observed
outcomes, including uniform (Angluin and Laird, 1988; Van Rooyen et al.,
2015b), class-conditional (Menon et al., 2015; Scott et al., 2013; Liu and
Tao, 2015), and instance-dependent (Chen et al., 2021b; Xia et al., 2020)
structures of outcome misclassification. Many data-driven error parameter
estimation methods are developed in recent machine learning literature
(Northcutt et al., 2021; Scott et al., 2013; Scott, 2015; Xia et al., 2019).
Meanwhile, given knowledge of measurement error parameters, recent studies
propose unbiased risk minimization approaches for learning under noisy labels
(Natarajan et al., 2013; Chou et al., 2020; Patrini et al., 2017; Van Rooyen
et al., 2015a).

Despite the prevalence of OME in real-world recommendation scenarios, there is
still only limited work focusing on denoising in RS (Zhang et al., 2023b; Chen
et al., 2022; Zhang et al., 2023a). Recently, by noticing that noisy feedback
typically has large loss values in the early stages, (Wang et al., 2021a)
proposes adaptive denoising training and (Gao et al., 2022a) proposes self-
guided denoising learning in implicit feedback. However, the existing methods
are mostly heuristic and require the fully observed noisy labels, which
prevents the direct use of such methods for RS in the presence of missing
data. To fill this gap, we extend the surrogate loss-based methods to address
the data MNAR and OME in parallel.

##  7\. Conclusion

In this study, we explored the challenges characterized MNAR data with noisy
feedback encountered in real-world recommendation scenarios. First, we
introduced the concept of true prediction inaccuracy as a more comprehensive
evaluation criterion that accounts for OME, and proposed OME-EIB, OME-IPS, and
OME-DR estimators to provide unbiased estimations of the true prediction
inaccuracy. Next, we derived the explicit forms of the biases and the
generalization bounds of the proposed estimators, and proved the double
robustness of our OME-DR estimator. We further proposed an alternating denoise
training approach that corrects for MNAR data with OME. The effectiveness of
our methods was validated on both semi-synthetic and real-world datasets with
varying MNAR and OME rates. The potential limitations includes the usage of
weak separability assumption, and accurate measurement error parameters’
estimation for ensuring unbiasedness. In future research, we aim to develop
unbiased learning methods applicable to more complex OME forms, study
alternative practical assumptions for identifying and estimating the error
parameters, and extend the applicability of the proposed methods to a wider
range of RS settings.

## Acknowledgements

This work was supported in part by National Natural Science Foundation of
China (623B2002, 62272437).

## References

  * (1)
  * Angluin and Laird (1988) Dana Angluin and Philip Laird. 1988.  Learning from noisy examples.  _Machine learning_ (1988), 343–370.
  * Bang and Robins (2005) Heejung Bang and James M Robins. 2005.  Doubly robust estimation in missing data and causal inference models.  _Biometrics_ (2005), 962–973.
  * Bonner and Vasile (2018) Stephen Bonner and Flavian Vasile. 2018.  Causal embeddings for recommendation. In _RecSys_.
  * Chen et al. (2022) Huiyuan Chen, Yusan Lin, Menghai Pan, Lan Wang, Chin-Chia Michael Yeh, Xiaoting Li, Yan Zheng, Fei Wang, and Hao Yang. 2022.  Denoising self-attentive sequential recommendation. In _RecSys_.
  * Chen et al. (2021a) Jiawei Chen, Hande Dong, Yang Qiu, Xiangnan He, Xin Xin, Liang Chen, Guli Lin, and Keping Yang. 2021a.  AutoDebias: Learning to Debias for Recommendation. In _SIGIR_.
  * Chen et al. (2023) Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He. 2023.  Bias and debias in recommender system: A survey and future directions.  _ACM Transactions on Information Systems_ (2023), 1–39.
  * Chen et al. (2018) Jiawei Chen, Can Wang, Martin Ester, Qihao Shi, Yan Feng, and Chun Chen. 2018.  Social recommendation with missing not at random data. In _ICDM_.
  * Chen et al. (2021b) Pengfei Chen, Junjie Ye, Guangyong Chen, Jingwei Zhao, and Pheng-Ann Heng. 2021b.  Beyond class-conditional assumption: A primary attempt to combat instance-dependent label noise. In _AAAI_.
  * Chou et al. (2020) Yu-Ting Chou, Gang Niu, Hsuan-Tien Lin, and Masashi Sugiyama. 2020.  Unbiased risk estimators can mislead: A case study of learning with complementary labels. In _ICML_.
  * Dai et al. (2022a) Quanyu Dai, Haoxuan Li, Peng Wu, Zhenhua Dong, Xiao-Hua Zhou, Rui Zhang, Xiuqiang He, Rui Zhang, and Jie Sun. 2022a.  A Generalized Doubly Robust Learning Framework for Debiasing Post-Click Conversion Rate Prediction. In _KDD_.
  * Dai et al. (2022b) Quanyu Dai, Yalei Lv, Jieming Zhu, Junjie Ye, Zhenhua Dong, Rui Zhang, Shu-Tao Xia, and Ruiming Tang. 2022b.  LCD: Adaptive label correction for denoising music recommendation. In _CIKM_.
  * De Myttenaere et al. (2014) Arnaud De Myttenaere, Bénédicte Le Grand, Boris Golden, and Fabrice Rossi. 2014.  Reducing offline evaluation bias in recommendation systems.  _arXiv preprint arXiv:1407.0822_ (2014).
  * Ding et al. (2022) Sihao Ding, Peng Wu, Fuli Feng, Xiangnan He, Yitong Wang, Yong Liao, and Yongdong Zhang. 2022.  Addressing Unmeasured Confounder for Recommendation with Sensitivity Analysis. In _KDD_.
  * Gao et al. (2022b) Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. 2022b.  KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems. In _CIKM_.
  * Gao et al. (2022a) Yunjun Gao, Yuntao Du, Yujia Hu, Lu Chen, Xinjun Zhu, Ziquan Fang, and Baihua Zheng. 2022a.  Self-guided learning to denoise for robust recommendation. In _SIGIR_.
  * Gunes et al. (2014) Ihsan Gunes, Cihan Kaleli, Alper Bilge, and Huseyin Polat. 2014.  Shilling attacks against recommender systems: a comprehensive survey.  _Artificial Intelligence Review_ (2014), 767–799.
  * Guo et al. (2021) Siyuan Guo, Lixin Zou, Yiding Liu, Wenwen Ye, Suqi Cheng, Shuaiqiang Wang, Hechang Chen, Dawei Yin, and Yi Chang. 2021.  Enhanced Doubly Robust Learning for Debiasing Post-Click Conversion Rate Estimation. In _SIGIR_.
  * Hernández-Lobato et al. (2014) José Miguel Hernández-Lobato, Neil Houlsby, and Zoubin Ghahramani. 2014.  Probabilistic matrix factorization with non-random missing data. In _ICML_.
  * Hui and Walter (1980) Sui L Hui and Steven D Walter. 1980.  Estimating the error rates of diagnostic tests.  _Biometrics_ (1980), 167–171.
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009.  Matrix factorization techniques for recommender systems.  _Computer_ (2009), 30–37.
  * Kweon and Yu (2024) Wonbin Kweon and Hwanjo Yu. 2024.  Doubly Calibrated Estimator for Recommendation on Data Missing Not At Random. In _WWW_.
  * Li et al. (2023a) Haoxuan Li, Quanyu Dai, Yuru Li, Yan Lyu, Zhenhua Dong, Xiao-Hua Zhou, and Peng Wu. 2023a.  Multiple Robust Learning for Recommendation. In _AAAI_.
  * Li et al. (2023b) Haoxuan Li, Yan Lyu, Chunyuan Zheng, and Peng Wu. 2023b.  TDR-CL: Targeted Doubly Robust Collaborative Learning for Debiased Recommendations. In _ICLR_.
  * Li et al. (2023c) Haoxuan Li, Kunhan Wu, Chunyuan Zheng, Yanghao Xiao, Hao Wang, Zhi Geng, Fuli Feng, Xiangnan He, and Peng Wu. 2023c.  Removing Hidden Confounding in Recommendation: A Unified Multi-Task Learning Approach. In _NeurIPS_.
  * Li et al. (2023d) Haoxuan Li, Yanghao Xiao, Chunyuan Zheng, and Peng Wu. 2023d.  Balancing unobserved confounding with a few unbiased ratings in debiased recommendations. In _WWW_.
  * Li et al. (2023e) Haoxuan Li, Yanghao Xiao, Chunyuan Zheng, Peng Wu, and Peng Cui. 2023e.  Propensity Matters: Measuring and Enhancing Balancing for Recommendation. In _ICML_.
  * Li et al. (2024a) Haoxuan Li, Chunyuan Zheng, Sihao Ding, Peng Wu, Zhi Geng, Fuli Feng, and Xiangnan He. 2024a.  Be Aware of the Neighborhood Effect: Modeling Selection Bias under Interference for Recommendation. In _ICLR_.
  * Li et al. (2024b) Haoxuan Li, Chunyuan Zheng, Shuyi Wang, Kunhan Wu, Hao Wang, peng Wu, Zhi Geng, Xu Chen, and Xiao-Hua Zhou. 2024b.  Relaxing the Accurate Imputation Assumption in Doubly Robust Learning for Debiased Collaborative Filtering. In _ICML_.
  * Li et al. (2023f) Haoxuan Li, Chunyuan Zheng, and Peng Wu. 2023f.  StableDR: Stabilized Doubly Robust Learning for Recommendation on Data Missing Not at Random. In _ICLR_.
  * Li et al. (2024c) Haoxuan Li, Chunyuan Zheng, Yanghao Xiao, Peng Wu, Zhi Geng, Xu Chen, and Peng Cui. 2024c.  Debiased Collaborative Filtering with Kernel-Based Causal Balancing. In _ICLR_.
  * Lin et al. (2023) Zinan Lin, Dugang Liu, Weike Pan, Qiang Yang, and Zhong Ming. 2023.  Transfer learning for collaborative recommendation with biased and unbiased data.  _Artificial Intelligence_ (2023), 103992.
  * Little and Rubin (2019) Roderick JA Little and Donald B Rubin. 2019.  _Statistical analysis with missing data_. Vol. 793.  John Wiley & Sons.
  * Liu et al. (2020) Dugang Liu, Pengxiang Cheng, Zhenhua Dong, Xiuqiang He, Weike Pan, and Zhong Ming. 2020.  A general knowledge distillation framework for counterfactual recommendation via uniform data. In _SIGIR_.
  * Liu et al. (2022) Dugang Liu, Pengxiang Cheng, Zinan Lin, Jinwei Luo, Zhenhua Dong, Xiuqiang He, Weike Pan, and Zhong Ming. 2022.  KDCRec: Knowledge distillation for counterfactual recommendation via uniform data.  _IEEE Transactions on Knowledge and Data Engineering_ (2022).
  * Liu et al. (2021) Dugang Liu, Pengxiang Cheng, Hong Zhu, Zhenhua Dong, Xiuqiang He, Weike Pan, and Zhong Ming. 2021.  Mitigating Confounding Bias in Recommendation via Information Bottleneck. In _RecSys_.
  * Liu and Tao (2015) Tongliang Liu and Dacheng Tao. 2015.  Classification with noisy labels by importance reweighting.  _IEEE Transactions on pattern analysis and machine intelligence_ (2015), 447–461.
  * Liu et al. (2016) Yiming Liu, Xuezhi Cao, and Yong Yu. 2016.  Are You Influenced by Others When Rating? Improve Rating Prediction by Conformity Modeling. In _RecSys_.
  * Liu et al. (2021) Yiyu Liu, Qian Liu, Yu Tian, Changping Wang, Yanan Niu, Yang Song, and Chenliang Li. 2021.  Concept-aware denoising graph neural network for micro-video recommendation. In _CIKM_.
  * Luo et al. (2021) Jinwei Luo, Dugang Liu, Weike Pan, and Zhong Ming. 2021.  Unbiased recommendation model based on improved propensity score estimation.  _Journal of Computer Applications_ (2021), 3508.
  * Ma et al. (2018) Xiao Ma, Liqin Zhao, Guan Huang, Zhi Wang, Zelin Hu, Xiaoqiang Zhu, and Kun Gai. 2018.  Entire Space Multi-Task Model: An Effective Approach for Estimating Post-Click Conversion Rate. In _SIGIR_.
  * Marlin and Zemel (2009) Benjamin M Marlin and Richard S Zemel. 2009.  Collaborative prediction and ranking with non-random missing data. In _RecSys_.
  * Menon et al. (2015) Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. 2015.  Learning from corrupted binary labels via class-probability estimation. In _ICML_.
  * Mohri et al. (2018) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2018.  _Foundations of machine learning_.  MIT press.
  * Natarajan et al. (2013) Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. 2013.  Learning with noisy labels. In _NeurIPS_.
  * Northcutt et al. (2021) Curtis Northcutt, Lu Jiang, and Isaac Chuang. 2021.  Confident learning: Estimating uncertainty in dataset labels.  _Journal of Artificial Intelligence Research_ (2021), 1373–1411.
  * Oosterhuis (2022) Harrie Oosterhuis. 2022.  Reaching the end of unbiasedness: Uncovering implicit limitations of click-based learning to rank. In _SIGIR_.
  * Oosterhuis (2023) Harrie Oosterhuis. 2023.  Doubly robust estimation for correcting position bias in click feedback for unbiased learning to rank.  _ACM Transactions on Information Systems_ (2023), 1–33.
  * Pan et al. (2023) Hang Pan, Jiawei Chen, Fuli Feng, Wentao Shi, Junkang Wu, and Xiangnan He. 2023.  Discriminative-Invariant Representation Learning for Unbiased Recommendation. In _IJCAI_.
  * Patrini et al. (2017) Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. 2017.  Making deep neural networks robust to label noise: A loss correction approach. In _CVPR_.
  * Qin et al. (2021) Yuqi Qin, Pengfei Wang, and Chenliang Li. 2021.  The world is binary: Contrastive learning for denoising next basket recommendation. In _SIGIR_.
  * Ricci et al. (2010) Francesco Ricci, Lior Rokach, and Bracha Shapira. 2010.  Introduction to recommender systems handbook.  In _Recommender systems handbook_. Springer, 1–35.
  * Roberts (1985) Fred S Roberts. 1985.  Measurement theory.  (1985).
  * Rui et al. (2022) Yong Rui, Vicente Ivan Sanchez Carmona, Mohsen Pourvali, Yun Xing, Wei-Wen Yi, Hui-Bin Ruan, and Yu Zhang. 2022.  Knowledge mining: A cross-disciplinary survey.  _Machine Intelligence Research_ (2022), 89–114.
  * Saito (2019) Yuta Saito. 2019.  Unbiased Pairwise Learning from Implicit Feedback. In _NeurIPS Workshop_.
  * Saito (2020) Yuta Saito. 2020.  Asymmetric Tri-training for Debiasing Missing-Not-At-Random Explicit Feedback. In _SIGIR_.
  * Saito (2020) Yuta Saito. 2020.  Doubly robust estimator for ranking metrics with post-click conversions. In _RecSys_.
  * Saito and Nomura (2022) Yuta Saito and Masahiro Nomura. 2022.  Towards Resolving Propensity Contradiction in Offline Recommender Learning. In _IJCAI_.
  * Saito et al. (2020) Yuta Saito, Suguru Yaginuma, Yuta Nishino, Hayato Sakata, and Kazuhide Nakata. 2020.  Unbiased recommender learning from missing-not-at-random implicit feedback. In _WSDM_.
  * Schnabel et al. (2016) Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. 2016.  Recommendations as Treatments: Debiasing Learning and Evaluation. In _ICML_.
  * Scott (2015) Clayton Scott. 2015.  A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In _AISTATS_.
  * Scott et al. (2013) Clayton Scott, Gilles Blanchard, and Gregory Handy. 2013.  Classification with asymmetric label noise: Consistency and maximal denoising. In _COLT_.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David. 2014.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press.
  * Shrout and Lane (2012) Patrick E Shrout and Sean P Lane. 2012.  Psychometrics.  (2012).
  * Song et al. (2023) Zijie Song, Jiawei Chen, Sheng Zhou, Qihao Shi, Yan Feng, Chun Chen, and Can Wang. 2023.  CDR: Conservative doubly robust learning for debiased recommendation. In _CIKM_.
  * Steck (2010) Harald Steck. 2010.  Training and testing of recommender systems on data missing not at random. In _KDD_.
  * Swaminathan and Joachims (2015) Adith Swaminathan and Thorsten Joachims. 2015.  The self-normalized estimator for counterfactual learning. In _NeurIPS_.
  * Van Rooyen et al. (2015a) Brendan Van Rooyen et al. 2015a.  Machine learning via transitions.  (2015).
  * Van Rooyen et al. (2015b) Brendan Van Rooyen, Aditya Menon, and Robert C Williamson. 2015b.  Learning with symmetric label noise: The importance of being unhinged. In _NeurIPS_.
  * Wang et al. (2022a) Hao Wang, Tai-Wei Chang, Tianqiao Liu, Jianmin Huang, Zhichao Chen, Chao Yu, Ruopeng Li, and Wei Chu. 2022a.  ESCM2: Entire space counterfactual multi-task model for post-click conversion rate estimation. In _SIGIR_.
  * Wang et al. (2023a) Jun Wang, Haoxuan Li, Chi Zhang, Dongxu Liang, Enyun Yu, Wenwu Ou, and Wenjia Wang. 2023a.  CounterCLR: Counterfactual contrastive learning with non-random missing data in recommendation. In _ICDM_.
  * Wang et al. (2021a) Wenjie Wang, Fuli Feng, Xiangnan He, Liqiang Nie, and Tat-Seng Chua. 2021a.  Denoising implicit feedback for recommendation. In _WSDM_.
  * Wang et al. (2023b) Wenjie Wang, Yang Zhang, Haoxuan Li, Peng Wu, Fuli Feng, and Xiangnan He. 2023b.  Causal Recommendation: Progresses and Future Directions. In _SIGIR_.
  * Wang et al. (2019) Xiaojie Wang, Rui Zhang, Yu Sun, and Jianzhong Qi. 2019.  Doubly Robust Joint Learning for Recommendation on Data Missing Not at Random. In _ICML_.
  * Wang et al. (2021b) Xiaojie Wang, Rui Zhang, Yu Sun, and Jianzhong Qi. 2021b.  Combating Selection Biases in Recommender Systems with A Few Unbiased Ratings. In _WSDM_.
  * Wang et al. (2020) Zifeng Wang, Xi Chen, Shao-Lun Wen, Rui anFd Huang, Ercan E Kuruoglu, and Yefeng Zheng. 2020.  Information Theoretic Counterfactual Learning from Missing-Not-At-Random Feedback. In _NeurIPS_.
  * Wang et al. (2022b) Zhenlei Wang, Shiqi Shen, Zhipeng Wang, Bo Chen, Xu Chen, and Ji-Rong Wen. 2022b.  Unbiased sequential recommendation with latent confounders. In _WWW_.
  * Wei et al. (2021) Tianxin Wei, Fuli Feng, Jiawei Chen, Ziwei Wu, Jinfeng Yi, and Xiangnan He. 2021.  Model-agnostic counterfactual reasoning for eliminating popularity bias in recommender system. In _KDD_.
  * Xia et al. (2020) Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. 2020.  Part-dependent label noise: Towards instance-dependent label noise. In _NeurIPS_.
  * Xia et al. (2019) Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. 2019.  Are anchor points really indispensable in label-noise learning?. In _NeurIPS_.
  * Yang et al. (2023) Mengyue Yang, Guohao Cai, Furui Liu, Jiarui Jin, Zhenhua Dong, Xiuqiang He, Jianye Hao, Weiqi Shao, Jun Wang, and Xu Chen. 2023.  Debiased recommendation with user feature balancing.  _ACM Transactions on Information Systems_ (2023).
  * Yang et al. (2021) Mengyue Yang, Quanyu Dai, Zhenhua Dong, Xu Chen, Xiuqiang He, and Jun Wang. 2021.  Top-N recommendation with counterfactual user preference simulation. In _CIKM_.
  * Zhang et al. (2023a) Chi Zhang, Rui Chen, Xiangyu Zhao, Qilong Han, and Li Li. 2023a.  Denoising and Prompt-Tuning for Multi-Behavior Recommendation. In _WWW_.
  * Zhang et al. (2024) Honglei Zhang, Shuyi Wang, Haoxuan Li, Chunyuan Zheng, Xu Chen, Li Liu, Shanshan Luo, and Peng Wu. 2024.  Uncovering the Propensity Identification Problem in Debiased Recommendations. In _ICDE_.
  * Zhang et al. (2020a) Wenhao Zhang, Wentian Bao, Xiao-Yang Liu, Keping Yang, Quan Lin, Hong Wen, and Ramin Ramezani. 2020a.  Large-scale Causal Approaches to Debiasing Post-click Conversion Rate Estimation with Multi-task Learning. In _WWW_.
  * Zhang et al. (2020b) Yongfeng Zhang, Xu Chen, et al. 2020b.  Explainable recommendation: A survey and new perspectives.  _Foundations and Trends® in Information Retrieval_ (2020), 1–101.
  * Zhang et al. (2021) Yang Zhang, Fuli Feng, Xiangnan He, Tianxin Wei, Chonggang Song, Guohui Ling, and Yongdong Zhang. 2021.  Causal intervention for leveraging popularity bias in recommendation. In _SIGIR_.
  * Zhang et al. (2023b) Zhiheng Zhang, Quanyu Dai, Xu Chen, Zhenhua Dong, and Ruiming Tang. 2023b.  Robust causal inference for recommender system to overcome noisy confounders. In _SIGIR_.
  * Zhao et al. (2019) Xiangyu Zhao, Long Xia, Jiliang Tang, and Dawei Yin. 2019.  Deep reinforcement learning for search, recommendation, and online advertising: a survey.  _ACM Sigweb Newsletter_ , 1–15.
  * Zheng et al. (2021) Yu Zheng, Chen Gao, Xiang Li, Xiangnan He, Depeng Jin, and Yong Li. 2021.  Disentangling User Interest and Conformity for Recommendation with Causal Embedding. In _WWW_.

##  Appendix A Proofs

Theorem 3.1 (Bias of OME-DR Estimator). _Given $\hat{\rho}_{01}$ and
$\hat{\rho}_{10}$ with $\hat{\rho}_{01}+\hat{\rho}_{10}<1$, imputed errors
$\bar{\mathbf{E}}$ and learned propensities $\hat{\mathbf{P}}$ with
$\hat{p}_{u,i}>0$ for all user-item pairs, the bias of the OME-DR estimator is
_

$\displaystyle\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]=\frac{1}{|\mathcal{D}|}\left|\sum_{(u,i)\in\mathcal{D}}\left(1-\frac{o_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}\right.+$
$\displaystyle\sum_{(u,i):r^{*}_{u,i}=1}\left(\frac{p_{u,i}\omega_{11}-\hat{p}_{u,i}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),1)+\frac{p_{u,i}\omega_{01}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),0)\right)+$
$\displaystyle\left.\sum_{(u,i):r^{*}_{u,i}=0}\left(\frac{p_{u,i}\omega_{10}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),1)+\frac{p_{u,i}\omega_{00}-\hat{p}_{u,i}}{\hat{p}_{u,i}}\ell(f_{\theta}(x_{u,i}),0)\right)\right|,$

_where $\omega_{11}$, $\omega_{01}$, $\omega_{10}$, and $\omega_{00}$ are
given by_

$\displaystyle\omega_{11}$
$\displaystyle=\frac{1-\rho_{01}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{01}=\frac{\rho_{01}-\hat{\rho}_{01}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},$
$\displaystyle\omega_{10}$
$\displaystyle=\frac{\rho_{10}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{00}=\frac{1-\hat{\rho}_{01}-\rho_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

###### Proof.

By definition, the bias of the OME-DR estimator is

$\displaystyle\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]=\left|\mathbb{E}_{\mathbf{R},\mathbf{O}}\left[\mathcal{E}_{\mathrm{OME-
DR}}\right]-\mathcal{P}^{*}\right|.$

By double expectation formula, the first term is

$\displaystyle\mathbb{E}_{\mathbf{R},\mathbf{O}}\left[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})\right]$
$\displaystyle={}$
$\displaystyle{}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\mathbb{E}_{\mathbf{O}}\left[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})\right]\right]$
$\displaystyle={}$
$\displaystyle{}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\left(\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right)\right]$
$\displaystyle={}$
$\displaystyle{}\frac{1}{|\mathcal{D}|}\sum_{(u,i):r^{*}_{u,i}=1}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right]$
$\displaystyle+{}$
$\displaystyle{}\frac{1}{|\mathcal{D}|}\sum_{(u,i):r^{*}_{u,i}=0}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right].$

Then, we can derive the bias of the OME-DR estimator as follows

$\displaystyle\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]=\left|\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\mathbb{E}_{\mathbf{O}}\left[\mathcal{E}_{\mathrm{OME-
DR}}\right]\right]-\mathcal{P}^{*}\right|$ $\displaystyle={}$
$\displaystyle{}\left|\frac{1}{|\mathcal{D}|}\sum_{(u,i):r^{*}_{u,i}=1}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right]-\ell(f_{\theta}(x_{u,i}),1)\right.$
$\displaystyle+{}$
$\displaystyle{}\left.\frac{1}{|\mathcal{D}|}\sum_{(u,i):r^{*}_{u,i}=0}\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{p_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right]-\ell(f_{\theta}(x_{u,i}),0)\right|$
$\displaystyle={}$
$\displaystyle{}\frac{1}{|\mathcal{D}|}\left|\sum_{(u,i):r^{*}_{u,i}=1}\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\sum_{(u,i):r^{*}_{u,i}=0}\left(1-\frac{p_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}\right.$
$\displaystyle+{}$
$\displaystyle{}\sum_{(u,i):r^{*}_{u,i}=1}\left(\frac{p_{u,i}}{\hat{p}_{u,i}}\cdot\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\tilde{e}_{u,i}\right]-\ell(f_{\theta}(x_{u,i}),1)\right)$
$\displaystyle+{}$
$\displaystyle{}\left.\sum_{(u,i):r^{*}_{u,i}=0}\left(\frac{p_{u,i}}{\hat{p}_{u,i}}\cdot\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\tilde{e}_{u,i}\right]-\ell(f_{\theta}(x_{u,i}),0)\right)\right|.$

On one hand, for the user-item pairs with $r^{*}_{u,i}=1$, we have

$\displaystyle\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\tilde{e}_{u,i}\right]$
$\displaystyle={}$
$\displaystyle{}\left(1-\rho_{01}\right)\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),1;\hat{\rho}_{01},\hat{\rho}_{10})+\rho_{01}\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),0;\hat{\rho}_{01},\hat{\rho}_{10})$
$\displaystyle={}$
$\displaystyle{}\left(1-\rho_{01}\right)\cdot\frac{\left(1-\hat{\rho}_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\hat{\rho}_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$
$\displaystyle{}+\rho_{01}\cdot\frac{\left(1-\hat{\rho}_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\hat{\rho}_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$
$\displaystyle={}$
$\displaystyle{}\frac{1-\rho_{01}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),1)+\frac{\rho_{01}-\hat{\rho}_{01}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),0)$
$\displaystyle:={}$
$\displaystyle{}\omega_{11}\ell(f_{\theta}(x_{u,i}),1)+\omega_{01}\ell(f_{\theta}(x_{u,i}),0),$

where $\omega_{11}$ and $\omega_{01}$ are given by

$\displaystyle\omega_{11}=\frac{1-\rho_{01}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{01}=\frac{\rho_{01}-\hat{\rho}_{01}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

On the other hand, for the user-item pairs with $r^{*}_{u,i}=0$, we have

$\displaystyle\mathbb{E}_{\mathbf{R}\mid\mathbf{O}}\left[\tilde{e}_{u,i}\right]$
$\displaystyle={}$
$\displaystyle{}\rho_{10}\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),1;\hat{\rho}_{01},\hat{\rho}_{10})+(1-\rho_{10})\cdot\tilde{\ell}(f_{\theta}(x_{u,i}),0;\hat{\rho}_{01},\hat{\rho}_{10})$
$\displaystyle={}$
$\displaystyle{}\rho_{10}\cdot\frac{\left(1-\hat{\rho}_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\hat{\rho}_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$
$\displaystyle{}+(1-\rho_{10})\cdot\frac{\left(1-\hat{\rho}_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\hat{\rho}_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$
$\displaystyle={}$
$\displaystyle{}\frac{\rho_{10}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),1)+\frac{1-\hat{\rho}_{01}-\rho_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\ell(f_{\theta}(x_{u,i}),0)$
$\displaystyle:={}$
$\displaystyle{}\omega_{10}\ell(f_{\theta}(x_{u,i}),1)+\omega_{00}\ell(f_{\theta}(x_{u,i}),0),$

where $\omega_{10}$ and $\omega_{00}$ are given by

$\displaystyle\omega_{10}=\frac{\rho_{10}-\hat{\rho}_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},\quad\omega_{00}=\frac{1-\hat{\rho}_{01}-\rho_{10}}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

This completes the proof. ∎

Lemma 3.3 (Lipschitz Continuity). _Given $\hat{\rho}_{01}$ and
$\hat{\rho}_{10}$ with $\hat{\rho}_{01}+\hat{\rho}_{10}<1$, if
$\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i})$ is $L$-Lipschitz in
$f_{\theta}(x_{u,i})$ for all $r^{*}_{u,i}$, then
$\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})$ is
$\frac{2L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}$-Lipschitz in
$f_{\theta}(x_{u,i})$ for all $r_{u,i}$._

###### Proof.

The explicit form of $\tilde{\ell}(f_{\theta}(x_{u,i}),1)$ and
$\tilde{\ell}(f_{\theta}(x_{u,i}),0)$ are

$\displaystyle\tilde{\ell}(f_{\theta}(x_{u,i}),1)$
$\displaystyle=\frac{\left(1-\hat{\rho}_{10}\right)\ell(f_{\theta}(x_{u,i}),1)-\hat{\rho}_{01}\ell(f_{\theta}(x_{u,i}),0)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}},$
$\displaystyle\tilde{\ell}(f_{\theta}(x_{u,i}),0)$
$\displaystyle=\frac{\left(1-\hat{\rho}_{01}\right)\ell(f_{\theta}(x_{u,i}),0)-\hat{\rho}_{10}\ell(f_{\theta}(x_{u,i}),1)}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}.$

Then the conclusion can be dirived directly from
$\hat{\rho}_{01}+\hat{\rho}_{10}<1$. ∎

###### Lemma A.1 (McDiarmid’s Inequality).

Let $V$ be some set and let $f:V^{m}\rightarrow\mathbb{R}$ be a function of
$m$ variables such that for some $c>0$, for all $i\in[m]$ and for all
$x_{1},\ldots,x_{m},x_{i}^{\prime}\in V$ we have

$\left|f\left(x_{1},\ldots,x_{m}\right)-f\left(x_{1},\ldots,x_{i-1},x_{i}^{\prime},x_{i+1},\ldots,x_{m}\right)\right|\leq
c$

Let $X_{1},\ldots,X_{m}$ be $m$ independent random variables taking values in
$V$. Then, with probability of at least $1-\eta$ we have

$\left|f\left(X_{1},\ldots,X_{m}\right)-\mathbb{E}\left[f\left(X_{1},\ldots,X_{m}\right)\right]\right|\leq
c\sqrt{\log\left(\frac{2}{\eta}\right)m/2}.$

###### Proof.

The proof can be found in Lemma 26.4 of (Shalev-Shwartz and Ben-David, 2014).
∎

Theorem 3.4 (Generalization Bound). _Given $\hat{\rho}_{01}$ and
$\hat{\rho}_{10}$ with $\hat{\rho}_{01}+\hat{\rho}_{10}<1$, suppose
$\ell(f_{\theta}(x_{u,i}),r^{*}_{u,i})$ is $L$-Lipschitz in
$f_{\theta}(x_{u,i})$ for all $r^{*}_{u,i}$, and $\hat{p}_{u,i}\geq C_{p}$,
$|\tilde{\ell}(f_{\theta}(x_{u,i}),r_{u,i})|\leq C_{l}$ for all $r_{u,i}$,
then with probability $1-\eta$, the true prediction inaccuracy
$\mathcal{P}(\hat{\mathbf{R}}^{\ddagger},\mathbf{R}^{*})$ of the optimal
prediction matrix using the OME-DR estimator with imputed errors
$\bar{\mathbf{E}}$ and learned propensities $\hat{\mathbf{P}}$ has the upper
bound _

$\displaystyle\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}}^{\ddagger},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})+\operatorname{Bias}[\mathcal{E}_{\mathrm{OME-
DR}}(\hat{\mathbf{R}}^{\ddagger},\mathbf{R}^{o};\hat{\rho}_{01},\hat{\rho}_{10})]+$
$\displaystyle\left(1+\frac{2}{C_{p}}\right)\left[\frac{4L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\mathcal{R}(\mathcal{F})+\left(C_{l}+\frac{4L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\right)\sqrt{\frac{2\log(4/\eta)}{|\mathcal{D}|}}\right].$

###### Proof.

The true prediction inaccuracy can be decomposed as

$\displaystyle\mathcal{P}^{*}=\mathcal{E}_{\mathrm{OME-
DR}}+\left(\mathcal{P}^{*}-\mathbb{E}[\mathcal{E}_{\mathrm{OME-
DR}}]\right)+\left(\mathbb{E}[\mathcal{E}_{\mathrm{OME-
DR}}]-\mathcal{E}_{\mathrm{OME-DR}}\right)$
$\displaystyle\leq{}\mathcal{E}_{\mathrm{OME-
DR}}+\operatorname{Bias}(\mathcal{E}_{\mathrm{OME-
DR}})+\left(\mathbb{E}[\mathcal{E}_{\mathrm{OME-
DR}}]-\mathcal{E}_{\mathrm{OME-DR}}\right)$
$\displaystyle\leq{}\mathcal{E}_{\mathrm{OME-
DR}}+\operatorname{Bias}(\mathcal{E}_{\mathrm{OME-
DR}})+\sup_{f_{\theta}\in\mathcal{F}}\left(\mathbb{E}[\mathcal{E}_{\mathrm{OME-
DR}}]-\mathcal{E}_{\mathrm{OME-DR}}\right).$

To simplify notation, let
$\mathcal{B(\mathcal{F})}=\sup_{f_{\theta}\in\mathcal{F}}\left(\mathbb{E}[\mathcal{E}_{\mathrm{OME-
DR}}]-\mathcal{E}_{\mathrm{OME-DR}}\right)$, which can be decomposed as

$\displaystyle\mathcal{B(\mathcal{F})}=\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}[\mathcal{B(\mathcal{F})}]+\left\\{\mathcal{B(\mathcal{F})}-\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}[\mathcal{B(\mathcal{F})}]\right\\}.$

For the first term
$\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}[\mathcal{B(\mathcal{F})}]$,
according to the Rademacher Comparison Lemma (Shalev-Shwartz and Ben-David,
2014) and Talagrand’s Lemma (Mohri et al., 2018), we have

$\displaystyle\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}[\mathcal{B(\mathcal{F})}]$
$\displaystyle\leq
2\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}\mathbb{E}_{\mathbf{\sigma}}\sup_{f_{\theta}\in\mathcal{F}}\left[\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\sigma_{u,i}\left(\left(1-\frac{o_{u,i}}{\hat{p}_{u,i}}\right)\bar{e}_{u,i}+\frac{o_{u,i}\tilde{e}_{u,i}}{\hat{p}_{u,i}}\right)\right]$
$\displaystyle\leq
2\left(1+\frac{2}{C_{p}}\right)\frac{2L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\cdot\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}\mathbb{E}_{\mathbf{\sigma}}\sup_{f_{\theta}\in\mathcal{F}}\left[\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\sigma_{u,i}f_{\theta}(x_{u,i})\right]$
$\displaystyle=2\left(1+\frac{2}{C_{p}}\right)\frac{2L}{1-\hat{\rho}_{01}-\hat{\rho}_{10}}\cdot\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}\\{\mathcal{R}(\mathcal{F})\\},$

where $\mathcal{R}(\mathcal{F})$ is the empirical Rademacher complexity of
$\mathcal{F}$

$\mathcal{R}(\mathcal{F})=\mathbb{E}_{\mathbf{\sigma}\sim\\{-1,+1\\}^{|\mathcal{D}|}}\sup_{f_{\theta}\in\mathcal{F}}\left[\frac{1}{|\mathcal{D}|}\sum_{(u,i)\in\mathcal{D}}\sigma_{u,i}f_{\theta}(x_{u,i})\right].$

By applying McDiarmid’s inequality, and let $c=\frac{2}{|\mathcal{D}|}$, with
probability at least $1-\frac{\eta}{2}$,

$\left|\mathcal{R}(\mathcal{F})-\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}\\{\mathcal{R}(\mathcal{F})\\}\right|\leq
2\sqrt{\frac{\log(4/\eta)}{2|\mathcal{D}|}}=\sqrt{\frac{2\log(4/\eta)}{|\mathcal{D}|}}.$

For the rest term
$\mathcal{B(\mathcal{F})}-\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}[\mathcal{B(\mathcal{F})}]$,
by applying McDiarmid’s inequality, and let
$c=\frac{2}{|\mathcal{D}|}C_{l}\left(1+\frac{2}{C_{p}}\right)$, with
probability at least $1-\frac{\eta}{2}$,

$\left|\mathcal{B(\mathcal{F})}-\underset{S\sim\mathcal{\mathbb{P}}^{|\mathcal{D}|}}{\mathbb{E}}[\mathcal{B(\mathcal{F})}]\right|\leq
C_{l}\left(1+\frac{2}{C_{p}}\right)\sqrt{\frac{2\log(4/\eta)}{|\mathcal{D}|}}.$

After adding the inequalities above, we can rearrange the terms to obtain the
stated results. ∎