Debiased Collaborative Filtering with Kernel-Based Causal Balancing
Authors: Haoxuan Li
Chunyuan Zheng
Yanghao Xiao
Peng Wu
Zhi Geng
Xu Chen
Peng Cui
Venue: ICLR 2024 spotlight (2024)
Keywords: Recommender System
Causal Inference
Bias
Debias
Balancing
Primary area: general machine learning (i.e., none of the above)

Abstract: Collaborative filtering builds personalized models from the collected user feedback. However, the collected data is observational rather than experimental, leading to various biases in the data, which can significantly affect the learned model. To address this issue, many studies have focused on propensity-based methods to combat the selection bias by reweighting the sample loss, and demonstrate that
balancing is important for debiasing both theoretically and empirically. However, there are two questions that still need to be addressed: which function class should be balanced and how to effectively balance that function class? In this paper, we first perform theoretical analysis to show the effect of balancing finite-dimensional function classes on the bias of IPS and DR methods, and based on this, we propose a universal kernel-based balancing method to balance functions on the reproducing kernel Hilbert space. In addition, we propose a novel adaptive causal balancing method during the alternating update between unbiased evaluation and training of the prediction model. Specifically, the prediction loss of the model is projected in the kernel-based covariate function space, and the projection coefficients are used to determine which functions should be prioritized for balancing to reduce the estimation bias. We conduct extensive experiments on three real-world datasets to demonstrate the effectiveness of the proposed approach.

Published as a conference paper at ICLR 2024
DEBIASED COLLABORATIVE FILTERING WITH KERNEL- BASED CAUSAL BALANCING
Haoxuan Li
Chunyuan Zheng'
Yanghao Xiao²
Peng Wu?
Zhi Geng?
Xu Chen 1M
Peng Cui
Peking University University of Chinese Academy of Sciences
Beijjig Technology and Business University
*Renmin University of China
Tsinghua University
hxlisstu. pku. edu.cn en
xu. ca.n@rur edu en
cuipetsinghua edu, en
ABSTRACT
Debiased collaborative filtering aims learn an unbiased prediction model by removing different biases in observational datasets. To solve this problem, one of the simple and effective methods is based on the propensity score, which adjusts the observational sample distribution to the target one by reweighting observed instances. Ideally, propensity scores should be learned with causal balancing con- straints. However, existing methods usually ignore such constraints implement them with unreasonable approximations, which may affect the accuracy of the learned propensity scores. To bridge this gap, in this paper, first analyze the gaps between the causal balancing requirements and existing methods such as learning the propensity with cross-entropy loss or manually selecting functions balance. Inspired by these gaps, we propose to approximate the balancing functions in repro- ducing kernel Hilbert space and demonstrate that, based on the universal property and representer theorem of kernel functions, the causal balancing constraints can better satisfied. Meanwhile, we propose an algorithm that adaptively balances the kernel function and theoretically analyze the generalization error bound of our methods. We conduct extensive experiments to demonstrate the effectiveness our methods, and to promote this rescarch direction, we have released our project at
INTRODUCTION
Collaborative filtering (CF) is the basis for large number of real-world applications, such as recommender system, social network, and drug repositioning. However, the collected data may contain different types of biases, which poses challenges effectively learning CF models that can well represent the target sample populations (Marlin and Zemel [2009). To solve this problem, people have proposed many debiased CF methods, among which propensity-basee and effective, which adjust the observational sample distribution to the target one by reweighting observed instances. For example, (Schabel al. (2016) proposes to use the inverse propensity score (IPS) to reweight the observed user-item interactions. The doubly robust (DR) method is another powerful and widely-used propensity- based method for debiasing, which combines an imputation model to reduce the variance and achieve double robustness property, i.e., unbiased either the learned propensity scores or the imputed errors are accurate (Wang et al. 2019).
methods simple
Despite previous propensity- based methods have achieved many promising results, most of them ignore the causal balancing constraints (Imai and Ratkovic 2014 [i et al., 2018 2023d). which has been demonstrated be important and necessary for learning accurate propensities. Specifically, causal balancing requires that the propensity score can effectively pull in the distance between the observed and unobserved sample for any given function Φ(-) (Imai and Ratkovic, 2014), that is
(l
(1
0u.i) (g.))((Zu.))
F
E
E(o(zux)),
Pu.i
Pu,i
"Corresponding author.

---

Published as a conference paper at ICLR 2024
where Zu,i is the covariate of user and item i, ou,i indicates whether the outcome of user to item i is observed, and Pu,; == P(ou,, = 1/zu,s) is the propensity score.
Existing debiased CF methods usually learn the propensity score based on two strategies: (I) adopting cross-entropy to train Pu,i that predicts ou,; using all user-item pairs (Wang et al. 2019), which does not consider the balancing property; (2) using the above causal balancing constraint to learn Pu,i with finite manually selected balancing functions ((-) (Li et al. 2023e). However, the selected balancing functions may not be a good proxy of all functions, leading to insufficient balancing.
To bridge the above gaps, we propose a debiased CF method that can adaptively capture functions that are more in need of being balanced. Specifically, we first analyze the relations between the causal balancing constraints and previous propensity score learning methods, motivating our research from novel perspective. Then, achieve the balancing property for any Φ(-), we propose to conduct causal balancing in the reproducing kernel Hilbert space (RKHS), where any continuous function can be approximated based on Gaussian or exponential kernels. Moreover, we design a kernel balancing algorithm to adaptively balance the selected functions and theoretically analyze the generalization error bounds. Note that the proposed kernel balancing method applies to both pure propensity- and ba-ed methods. The main contributions of this paper can be concluded as follows
We theoretically prove the unbiasedness condition of the propensity-ban function balancing perspective, revealing the shortcomings of previous propensity learning methods using cross-entropy and manually specified balancing functions.
methods from the
We design novel kernel balancing method that adaptively find the balancing functions that contribute the most to reducing the estimation bias via convex optimization, named adaptive kernel balancing, and derive the corresponding generalization error bounds.
We conduct extensive experiments on three publicly available datasets to demonstrate the effective- ness of the proposed adaptive kernel balancing approach for IPS and DR estimators.
2
PRELIMINARIES
2.1 DEBIASED COLLABORATIVE FILTERING
Let 1/ and I be the whole user and item sets, respectively. Denote U. = {ui,..., um C li and I, ..,,..., in C I be the observed user and item sets randomly sampled from the super- population, and D = Uo x Io {(u, u E Uo E Io} be the corresponding user-item set. For each user-item pair (u, i) D, we denote Zu.i E R Tu, E E and o..: E {0, as the user-item features, the rating of user to item and whether Tu, is observed in the dataset, respectively. For brevity, denote O = {(u. i) (u, i) E D,o,, = 1} as the set user-item pairs with obseverd Tu,i-
Let Pu,i ( 0,) be the prediction model parameterized by 0r, which predicts Tu,i according to the features Fu,i. To achieve the unbiased learning, should be trained by minimizing the ideal loss:
Lideal (0p)
1
Σ (u.))ED
Cu,b
D
where eu,i L(fan Tu.i) is the prediction error with C(:-) be an arbitrary loss function, e.g., mean square loss or cross-entropy loss. However, observing all ra,s is impractical so that cu,s is not computable for ou, = 0. A naive method for solving this problem is approximating Lideat(f)) directly based on the observed samples, that is to minimize the naive loss
LNavve (0.)
Cu,i-
(M
However, due to the existence of selection bias, NNaive is not unbiased in terms of estimating (O,) (Wang et al. 2019). To further build unbiased estimators, previous studies propose to use propensity score to adjust observed sample weights, and design the IPS loss
1
Lirs (0.) =
Pu,i
(L,))D
2

---

Published as a conference paper at ICLR 2024
where Pu.s <( 1: 8y) is the estimation of propensity score Pu.i- It can be demonstrated that (0,) is unbiased when Pu.i = Pu,i (Schnabel et al. 2016 Wang et al. 2019). To further improve the robustness and reduce the vanance, researchers extend the IPS method to many DR
methods (Wang et al. 2019 2021
Li et al. 2023b f with the DR loss
(0, =
1
Σ
Ca, + Ou, (eu,i En,i)
D
Pu,s
(u.i)ED
where :., ( ; 0e) is the imputed error. The DR estimator unbiased when all the estimated propensity scores or the imputed errors are accurate. In both the IPS and DR methods, computing the propensity score of great importance, which directly determines the final debiasing performance.
2.2 CAUSAL BALANCING
In many causal inference studies (Imai and Ratkovic 2014] Imbens and Rubin 2013 Rosenbaum 2020; Sant' Anna et al., 2022), accurately computing the propensity score is quite challenging, since it is hard to specify the propensity model structure and estimate the model parameters. To solve this problem, researchers propose general strategy learn the propensity scores without specifying model structure based on the following causal balancing constraints (Imbens and Rubin (0155)
Ou Du
Ou.i (x))))))
E
E
Elo(xu,;))l
(1)
Pu.i
Pu,i
where Φ X'' X for any balancing function. Inspired by such property, recent work (Li al. (023c) proposes to learn the propensity by minimizing the distance between the first and second terms in Equation (I)
a balancing function applied to the covariant. Ideally, this equation should hold
However, in this method, the finite balancing functions 6(-) )) are manually selected (e.g., the first and
second moments), which may not be a good proxy of all functions, leading to insufficient balancing.
CONNECTING CAUSAL BALANCING AND EXISTING PROPENSITY LEARNING
In the field of debiased collaborative filtering, there are usually two types propensity score learning methods: (I) using cross-entropy to train Pa,; that predicts ou,i using all user-item pairs; (2) adopting the causal balancing method with a finite number of manually selected balancing functions ((-).
3.1 CROSS-ENTROPT BASED STRATEGY
Recall that the propensity model ( 0p) aims to predict the probability of observing ru. in the dataset (i.e., Ou,i 1). The cross-entropy based strategy learns O, based the following loss
(p(0p)= = Σ
-o,, log (I 0p)] - -(1 - ou., [1 =(I,,,i0))}
(u.))D
By taking the first derivative of this loss function w.r. 0p. the optimal ( si 0,) should satisfy @Cp(0p)
(.x (1 o,, ou, (u.))OT((uu.. 0p) 0. ग (Z 0p)
Σ (u.))D
(2)
d0,
x [IIn,si0p 0p)
By comparing this requirement with the causal balancing constraint in Equation [T) we can see that we let @(F,,;) ) ( p00p then Equation (2) is special case of Equation (T). which means that the cross-entropy based strategy is not sufficient to achieve causal balancing.
3.2 CAUSAL BALANCING WITH MANUALLY SPECIFIED BALANCING FUNCTIONS
Li et al. (203e)) a recent work on using causal balancing for debiased collaborative filtering, In this work, the authors first manually select and fix balancing functions (+() (.))...)).)).................... h)))
Denote vi., ( Ow) be the balancing weight assigned sample (u, i), then the objective
3

---

Published as a conference paper at ICLR 2024
function and constrains of the optimization problem for learning fw is shown below
max
Σ
Vugs log Wn,i
(u,1)0
s.t.
1
Σ
Ou 1 un (Tu,) = Σ
1
(Zw.)) (u,))ED
j (L
D
D
(u
Ou, u, 1,
Wn, 0
v(u,i)
D
(M,))D
where the objective aims to effectively avoid extremely small balancing weight via maximizing the entropy (Guiasu and Shenitzer, 1985). The first constraint is the empirical implementation of Equation based on balancing functions (-), ()..)))..... (.))())) and the second constraint imposes normalization regularization wu,s.. Remarkably, this objective is convex w.zf. Wa,b which can be solved by the Lagrange multiplier method. The following Theorem shows the estimation bias depends on the distance between Cu,i and Hi = span (h()) (suu)..... (xm.)))
Theorem 1. Ifcu. E H. an unbiased ideal loss estimation in term of the IPS method.
(.), then the above learned propensities lead to
The balancing functions ()...) (()) (-) are manually selected in Li et al. 2023e). which is equivalent to letting ((xu,) ) = (Zu,)) j e [I.....J} in Equation This method improves the cross-entropy based strategy by using more balancing functions. However, the selected balancing functions may not well represent eu,i that is, Cu,i & H. span(h (.)....) (.)) which may lead to inaccurate balancing weights estimation and biased prediction model learning.
4
KERNEL-BASED CAUSAL BALANCING
4.1 KERNEL FUNCTION, UNIVERSAL PROPERTY, AND REPRESENTER THEOREM
To satisfy the causal balancing constraint in Equation with Gaussian and exponential kernels in the reproducing kernel Hilbert space (RKHS). To begin with, first introduce several basic definitions and properties of the kernel function.
approximate the balancing function
Definition 1 (Kernel function). Let X be non-empty set. A function K X x X is kernel function if there exists a Hilbert space H and a feature map vp X - H. such that Va, x' E X, K (xx,²)) (v()), (xx²)
Gaussian and exponential kernels are two typical kernel functions, which are formulated follows
K Gaau (x.x') = exp (-1le-
|| [|1===a'11 x'113
|1 (-lix
x'
and K ExEp(ax, exp
20
20
Definition 2 (Univeesal kernel). For X compact Hausdorff. a kernel is universal for any continuous E the corresponding RKHS such that
function
X + R and > 0, there exists
supzex [f(x:) e(x)) <
Lemma Sriperumbudur et al. (201T)). Both the Gaussian and exponential kernels are universal.
This lemma shows that there is function in RKHS H = spaan (..,)) | E X} that can approach any continuous function when the kernel function <<(:z) is chosen as the Gaussian or exponential kernel. However, H. might be infinity dimension space with | co, which leads to infinity constraints for the optimization problem. The following representer theorem guarantees the optimality of kernel methods under penalized empirical risk minimization and provides form of the best possible choice of kernel balancing under finite samples.
Lemma 2 (Representer theorem). If Ω h(llfl) for some increasing function h R, R. then some empirical risk minimizer must admit the form f()) = >i= (;,,), for some a (on, (0n,...,0a) On) E RRn. h is strictly increasing, all minimizers admit this form.
4

---

Published as a conference paper at ICLR 2024
4.2 WORST-CASS KERNEL BALANCING
Next, we propose kernel balancing IPS (KBIPS) and kernel balancing DR (KBDR) for debiased CF
LKBIPS(0,
Ou,
D
(a.i)ED
(K.D
Σ (u,jEE
(éut iu, Cus)]:
(3)
where the balancing weights i..i are learned via either the proposed worst-case kernel balancing in the of this section or the proposed adaptive kernel balancing method in Section 4.3
For illustration purposes, we use KBIPS as an example, and KBDR can be derived in similar way Theorem shows that when the prediction error function Ga,i E H. s (.), "ali)....,.e.e h ()) and the learned balancing weights can balance those functions KBIPS estimator leads the unbiased ideal loss estimation. However, in practice, the prediction error function C could be any continuous function, lying in much larger hypothesis space than ((,z)) x)) is chosen as the Gaussian or exponential kernel, we can assume én,i E H span ("; x (u,, i) E 2 x I} holds with any approximation error c.
(.)3. then the above
Hl By Lemma ! when the kernel function ((,
Note that the empirical bias of the KBIPS estimator for estimating the ideal loss
Bias(LKBIPs = [LKBIPS Lideal (0,)}²
Σ
(ou, 1)eu,i
D
(u.i)E
then the worst-case kernel balancing (WKB) method focuses on controlling the worst-case bias of KBIPS by playing the following minimax game
2 L( 1)eu,
min O.
sup eEA
D
(ou,
1)eu,
min
sup cEH
Elu.)ED 2
(MLi)ED
where H fe(-) E H [le()) IDI E(u,)ED ei.
1} is the normalized RKHS. By the representer theorem in Lemma 2 the right-hand side is the same the following
1) (GA)D as.K K(r,,
D
min 8w
sup 0.,1
D EluieD 2
4.3 ADAPTIVE KERNEL BALANCING
There are [D] kernel functions in the above objective. Since there are usually large number of users and items in the recommender systems, [D] is quite large, which makes infeasible to balance all kernel functions. To solve this problem, straightforward method is to randomly select / functions from span ((,, Fu.s) (u, i) E D) to balance, named random kernel balancing (RKB). However, this method regards all kernel functions equally important, which harms the debiasing performance.
To overcome the shortcomings of the WKB and RKB methods, we propose a novel adaptive kernel balancing (AKB) method that adaptively select which kernel functions balance. Given current prediction model ( 0,), we first fit Cu,i using the kernel functions RKHS
2
(aI, am,)) arg min a
Cu.
a KI (a.))D
Σ
(u.i)ED
For KBDR, it requires that c,.i Ê.,i H, span (.)) Same as the follows, egg. K(Fu.i,
(01 nm) should minimize the mean squared error between Gy,1 é.,s and
E(WNeD Os,t I
5

---

Published as a conference paper at ICLR 2024
then balance the J functions with maximal |a,,t] where J is Alyper-paaameter This method aims to balance the kernel functions that contribute most to eu,ú, which leads to the following optimization
min
Σ
Wu,s s log Wa,t 2 +
E
Ow
(u,i)EO
s.t.
E 2 0
jE [l,.....
and iu,i 20 0
v(u,i)
Σ
Ou Wu,i = 1
(u,))D
Σ
On, (5) (Irux)
Σ
1
(T (
j jE(l....,
D
(u,))ED
(uNEED
1
Σ (u,))ED
ou Wa (1
(Iu,k)
H6 (Z.,))
je
D
(u,jED
The above optimization problem is equivalent the following
min Lw (fxr Px
Σ
Wns log Wa.s +
?
(I-C
+ -(+)) -c7
(5)
(a.i)EO
1=1
where
Σ (uD))D
th
(xxx))) (a.)EDD
Σ
jE (I......).
[D]
Since achieving strict balancing constraints on all balancing functions is usually infeasible as J increases, we introduce a slack variable E, and pre-specified threshold C, which penalizes the loss when the deviation AL C.
4.4 LEARNING ALGORITHM AND GENERALIZATION ERROR BOUNDS
Taking the AKBDR method as example, because the balancing weights u... and prediction errors eu,i are relying on each other, thus we adopt a widely used joint learning framework to train the prediction model Pu,s f 0,), balancing weight model tū.; = g(Fu.s: ow), and imputation model ê = ( 0.) alternatively. Specifically, we train the prediction model by minimizing the LKBDR (0,) loss shown in Equation 3 train the balancing weight model by minimizing the L.w (fw. in Equation 5 and train the imputation model by minimizing the loss function Le(O.) below
(O.
= D
Σ
ou Wn - ew,,)²
(6)
(u.j)ED
and the whole procedure of the proposed joint learning process is summarized in Alg.
Next, we analyze the generalization bound of the KBIPS and KBDR methods.
Theorem 2 (Generalization Bounds in RKHS). Let K be bounded kernel, sup, K(x, x) B < oc, and Bx (M) {S F |I S M) is the corresponding kernel-based hypotheses space. Suppose Wa.s < C, 5(r, -) is L-Lipschitz continuous for all r, and that Eg := sup, 5(r, 0) co. Then with probability at least 1 17, we have
2CLMB VIDI
log(4/n)
Lideal (0,) S (KB)PS(0,) + [Bias(CKBIPs(O.))
+ 5C + LMB)
2/DI
2LMB
log (4/ (4/1))
(0)) < LKADR(O,) + (0-])
+ +5EE + LMB)
VD
2
Remarkably, the above generalization bounds in RKHS can be greatly reduced by adopting the proposed KBIPS and KBDR learning methods, because the prediction model minimizes the debiased losses LKBIPS(O,) (0,) and CKBDR(0,) during the model training phase, and Bias (aaRISs and Bias (LKBDR (f,)) also be controlled via WKB AKB methods.

---

Published as a conference paper at ICLR 2024
Algorithm 1: The Proposed Adaptive KBDR (AKBDR) Learning Algorithm
Input: observed ratings Y and number of balancing functions J.
while stopping criteria is not satisfied do for number of steps for training the imputation model do
Sample batch of user-item pairs {(u, it) from O; Update 0g by descending along the gradient Vo, Le (O.); end
for number of steps for training the balancing weight model do
Sample batch of user-item pairs {uum km)) m=1 from D:
Solve the Equation 4 and select J functions h( km with maximum am
Update Ow by descending along the gradient Vo., Lw (0w);
10
end
11
for number of steps for training the prediction model do n=1 from D; Update 0, by descending along the gradient V CKBRR (0.);
Sample a batch of user-item pairs {[un )n))
12
14
end
15 end
RELATED WORK
Debiased Collaborative Filtering. Collaborative filtering (CF) plays an important role in today's digital and informative world (Chen et al. 2018 Huang et al. 2023 Lv et al. 2023 2024). However, the collected data is observational rather than experimental, leading to various biases in the data, which seriously affects the quality of the learned model. One of the most important biases is the selection bias, which causes the distribution of the training data to be different from the distribution of the test data, thus making challenging to achieve unbiased estimation and learning (Wang et al. 20226
2023b Zou et al. 2023 Wang et al. 2023a| 2024). If we learn the model directly the training data without debiasing, it will harm the prediction performance on the test data (Wang et al. 2023c Zhang
al. 2023 Bai al. 2024; Zhang al., 2024). Many previous methods are proposed mitigate the selection bias problem (Schnabel et al.; 2016)] Wang et al. 2019 Chen et al. 2021 Li et al.) 2023c)
The prror-imputation-baee based (EIB) methods attempt to impute the missing events, and then train CF model on both observed and imputed data (Chang et al. 2010 Steck 2010 Hernández-Lobato
et al. 2014). Another common type of debiasing method is propensity based, including inverse propensity scoring (IPS) methods (Imbens and Rubin 2015) Schnabel et al., [0166] Saito et al. 2020
Luo et al., 202T Oosterhuis 2022). and doubly robust (DR) methods (Morgan and Winship 2015
Wang al.) 22099] (aito 2020). Specifically, IPS adjusts the distribution by reweighting the observed events, while DR combines the EIB and IPS methods, which takes advantage of both, i.e., has lower variance and bias. Based on the above advantages, many competing DR-based methods are proposed, such as MRDR (Guo et al. 2021), DR-BIAS (Dai et al. 2022), ESCM²-DR (Wang et al. 2022a). TDR (Li et al. 2023b), SDR (Li et al. 2023f.. and N-DR (Li et al.. 2024). Given the widespread of the propensity model, ei al. (2023d) proposed a method to train balancing weights with a few unbiased ratings for debiasing. More recently, Li et al. (2023e) proposed a propensity balaneing measurement to regularize the IPS and DR estimators. In this paper, we extend the above idea by proposing novel kernel-based balancing IPS and DR estimators that adaptively find the balancing functions that contribute the most to reducing the estimation bias.
Covariate Balancing in Causal Inference. Balaneing refers to aligning the distribution of covariates in the treatment and control groups, which is crucial to the estimation of causal effects based on observational datasets (Stuart 2010, [mbens and Rubin 2015). This is because balaneing ensures that units receiving different treatments are comparable directly, and the association becomes causation under the unconfoundedness assumption (Imai and Ratkovic 2014 Hernán and Robins 2020). In randomized controlled experiments, balancing is naturally maintained due to the complete random assignment of treatments. However, in observational studies, treatment groups typically exhibit systematic differences in covariates, which can result in a lack of balance. To obtain accurate estimates of causal effects in observational studies, a wide variety of methods have emerged for balancing the finite order moments of covariates, including matching (Rosenbaum and Rubin 1983 Stuart 2010
7

---

Published as a conference paper at ICLR 2024
Table I: Performance AUC, NDCG@ K, and Fl @ K on COAT, MUSIC and PRODUCT. The best
two results are bolded and the best bascline result is underlined for IPS-based and DR-based methods.
COAT
MUSIC
PRODUCT
Method
AUC
NDCG@5
FIØS
AUC
NDCG@5
FLG5
AUC
NDCG@20
F1
MF
0. 42.00s
2000
a..67
0.635
0.75340.500
2.449
0.124
IPS
0.71729.00
0.6172000
0.477
0.678_0.01
0.638420.02
0.318g0002
0.755
0.452gams
0.131 20004
SNIPS
0,714
0.61420022
0.474
0.683_00c22
0.639
0.316
0.754
0.455
0.126
ASIPS
0.719
0.618200:2
0.476ea.0m
0.679-0ocs
0.64020.cos
0.319
0.757+0.000
0.474
0.130
+ IPS-V2
0.7 a.726
0.027.0.000
0.479
0.685
0.02
0.320 0.022
0.
0.264.0.cm
0.476
0.135
10.00
RKBIPS-ENN Exp
0.714
0.61820010
0.676_
0.642.0.cm cea
0.318
0.763
0.463g00007
0.134
RKRIPS-Gia
1.715
0.19_0000
0.475 10.000
0.678 0..c
po.cos
0.315
1.760
0.470
0.133
10.00
WKBIPS.
g..23
0:62440000
0.687_0033
3.654
0.322:0002
2.765
g.475
0.138
W WKIPPS-Gai
0.
0.722 20.004
2.025
0.479
0.65020.002
0:321
0.76820.000
0.137 0.476
AKBIPS- Exp
0.7322-0.044
2.00
0.483
0.689
2000
0.65820.02
0.324
0.766
0.138 0.478
AKBIPS-Cau
23.10
2.,84
0.688
-oocs
p0.c0
0.334 20.022
30.000
0.13% 0.480
20.00s
+ DR
0.718 oos
0.623
0.474ga.00 o0
0.684_000
0.658 coa
0.326
0.755 a0
0.462gam00
0.138
DR-JI.
0.725
0.629.0007
0.47%
0.685_002
1..53
0.324_om0
0.324
0. 0.76660..00
g.467
0.1 0.156
MRDR-II
0.727
0.627
2..80
0,84-00022
0.65220.00
0.325
20.022
0.76840.006
0.475g0.00
0.139220004
DR-BLL BIRBBIAS
2,726
0.62920000
8,0827
0.685
0.68-00022
2.653
0.768
8.477
0.137 20.004
+ DR-MSE
0.727=0.007
0.631
2.484
0.687
0.657=0.00
0.327
0.770
0.1 0.1:0=20008 0.450
MR
g.724
0.636.0.006
0.481 20.000
0.691
2..47
0.316
0.776 10.500
0.483
0,142 10.008
TDR
0.714
go
c0.c0m
00002
10.000
0.486
+ TDR-IL
0.731 1.0.0:
0.539 10.007
0.4841..00
0.689
0o0c
j..50
0.327
0,003
0.772 10.0t0
0.772
0.489
10.00t
0.142 100000
SDR
0.735
0.64
0.484_3.com
0.688_0003
2.66
0.329
0.77330.001
0.491
0.143
DR-V2
0.734.9.00 007
0639_0000
0.487
0.600__ooc
1.660
0.77310.o0
0.488g5.00
0.488
RKBDR- Exp
0.730
0,482
0.68220022
0.64842..om
0.323g0002
0.765
2.4002
0.138
RKBOR- Gau
0,726=0.003
0.630ana08
0.480
0.683
0.652xo.om
0.325=0.02
0.766.0.000
0. 0.134.2..0 0.469
WKBDR-BB Exp
0.735
0.637
0.083
0.685
0.654saocus
0.325=00002
0.773
0.489=3005
0.142+0.008
WKBDR-Gaa
0.732
0.63810000
10.00
0.687
0.655
0.327
20.022
0.773
10.000
0.490.a.::
10.004
+ AKBDR-ENs Exp
0.745
20.04
0.645 goors
0.692 n.09
0.66L
0.328
20000
0.782
0.498g2.00
0.147 0.147
AKBDR-CGa
0.746
0.646
0.492
0.694 0,0ce
0.664 incm
0.332 0.003
0.782 10.000
0,5033 5.00
0.148 10,004
Note: means statistically sigmificant results (p go-value S 0.05) using the paired test compared with the best buseline method.
Wu et al., 2020), stratification (Hernán and Robins 2020), entropy balancing (Hainmueller) 2012 2
Zhao and Percival 2017), covariate balancing (Imai and Ratkovic 2014), and weighted eucl lidein balancing (Chen and Zhou| 2023). In recent years, several approaches are developed balancing infinite order moments of covariates (Sant' Anna et al. 2022) or the covariates distributions (Wong) and Chan 2018). However, it is unrealistic to balance infinite order moments with only finite samples, therefore in this paper we propose a novel balancing method that adaptively finds the balancing functions in RKHS that are most important for achieving unbiased learning.
6 EXPERIMENTS
Datasets and Experimental Details. Following the previous studies (Wang et al. 2019: Chen et al. 2021| Wang et al. 202T Li et al. 2023b), we conduct real-world experiments on three widely used benchmark datasets: COAT, MUSIC, and a large-scale industrial dataset PRODUCT. The COAT dataset consists of 6,960 biased ratings and 4,640 unbiased ratings evaluated by 290 users to 300 items. The MUSIC dataset consists of 311,704 biased ratings and 54.000 unbiased ratings evaluated by 15,400 users to 1,000 items. The PRODUCT dataset consists of 4,676,570 records of video watching ratios from 1,411 users 3,327 items and is almost fully exposed. Both COAT and MUSIC are five-scale datasets, and we binarize the ratings less than three as 0, otherwise as 1. For the PRODUCT dataset, we binarize the video watching ratios less than two as O, otherwise as 1. We adopt three widely used evaluation metrics: AUC, NDCG@ @ K, and Fl @ K to measure the debiasing performance. We set K 5 5 for COAT and MUSIC and K 20 for PRODUCT. We use Adam as the optimizer and tune the learning rate in (0.01, 0.03, 0.05, 0.13. weight decay in [le 6, 5e - 3], margin threshold C in {1e 6, 5e 5, le 5,... .., 1). kernel hyper- prrperparammter ²² in (0.5, 1, 5) for both Gaussian and exponential kernels, and regularization hyper-paramett y in {1, 5, 10, 20, 50). We set the batch size to 128 on COAT and 2,048 on MUSIC and PRODUCT.
Baselines. We implement our proposed RKB, WKB, and AKB methods with both Gaussian and exponential kernels by taking MF (Koren et al. 2009) as the base model. We compare our methods with the following IPS-based baselines: IPS (Schnabel et al. 2016). SNIPS (Schnabel et al. 2016), ASIPS (Saito, 2020), and V2 (Li et al. 2023e). Meanwhile, we also compare our methods with the following BR-based baselines: DR (Saioo 2020). DR-JL (Wang al. 2019). MRDR (Guo et al.
202T), DR-BIAS (Dai et al.) 2022). DR-MSE (Dai et al., 2022). MR (Li et al. 2023a). TDR (Li
al. 2023b), TDR-JI. (Li et al. 2023b). StableDR (Li et al. 2023f). and DR- V (Li et al. 2023e).
8

---

Published as a conference paper at ICLR 2024
MBIPS RK00PS
WKSEES AKCHPP
XBL2S 0XDIPS
WXBIPS AKBLPSS
MIDRR
MIDR
WXDDR
0.40
0.79
0.52
NDCORD
0.70
5.50
1076
2.40
0.40
2.46-
0.75
0.75
of bbblsncinn fuactions
N.mumbor of balancing functions
N.ummbr balancing fonctions
Jo J.Number balancii functions
(a) AUC with IPS
(b) NDCG@ 20 with IPS
(c) AUC with DR
(d) NDCG@ with DR
Figure 1: Effects of the value of J on AUC and NDCG@ 20 on the PRODUCT dataset.
125
AKBIPS
125
AKSIPS
IPS
AXBIPS AXBOD
IPS DRJL
AKBIPS
DRgl
AKRDR
AKTOR
BR.
AKBDD
0.70
NDCC820
0.50
0.69
0.77
0.48
0.78
0.46
0.60
0.75
0.44
Regularization strength
Regulatization strongth
Regulatizatin strengia
Regulaaizatinn strength
(a) AUC on Music
(b) NDCG@5 on Music
(c) AUC on Product
(d) NDCG@ on Product
Figure 2: Effects of parper-rr on AUC and NDCG@ K on MUSIC and PRODUCT datasets.
Performance Comparison. We compare the proposed methods with previous methods, as shown in Table I First, all the debiasing methods outperform MF, and AKBDR achieves the optimal performance on all three datasets with either Gaussian or exponential kernels. Second, methods with balancing properties such as IPS-V2 and DR-V2 achieve competitive performance, which demonstrates the importance of propensity balancing. Third, for our methods, RKB methods perform the worst due to the insufficient balancing caused by random selected functions, while AKB methods perform the best due to the most important kernel functions are adaptively found and balanced.
In-Depth Analysis. We further explore the impact of the value on the debiasing performance of kemel balancing methods the PRODUCT dataset. We also implement the moment balancing (MB) methods which balance the first J-th order moments for comparison and the results are shown in We find the performance for all methods except WKB increases monotonically as the value of J increases because more functions or moments being balanced leads to less bias. Since the WKB methods focus on controlling the worst-case, the performance does not change for different J and shows competitive performance with AKB methods when J is small (e.g., / 1). In addition, kernel balancing methods stably outperform moment balancing methods with varying values of J even the balancing functions are selected randomly, validating the effectiveness of kernel balancing.
Figure I
Sensitivity Analysis. To explore the effect of balancing regularization hyper-parameter y on debiasing performance, we conduct sensitivity analysis on AKB methods with varying y in {1, 2, 10, 20) on the MUSIC and PRODUCT datasets, as shown in Figure 2 The AKB methods consistently outperform the baseline methods under different regularization strengths. Specifically, even when the balancing constraint strength is small, the AKB method can still get significant performance gains, and the optimal performance is achieved around the moderate (e.g., 5 or 10).
7 CONCLUSION
In the informatioon-rriver landscape, collaborative filtering is pivotal for various e-commerce plat- forms. However, selection bias in the collected data poses a great challenge for collaborative filtering model training. To mitigate this issue, this paper theoretically reveal that previous debiased collabo- rative filtering approaches are restricted to balancing nitee-dimensionll pre-specified functions of features. To fill the gap, we first develop two new estimators, KBIPS and KBDR, which extend the widely-used IPS and DR estimators in debiased collaborative filtering. Then we propose universal kernel-based balancing method that adaptively achieves balance for the selected functions in an RKHS. Based on it. we further propose an adaptive kernel balancing method. Theoretical analysis demonstrates that the proposed balancing method reduces both estimation bias and the generalization bound, Extensive experiments real- wollw datasets validate the effectiveness of our methods.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work was supported in part by National Natural Science Foundation of China (No. 623B2002. 62102420, 12301370)
REFERENCES
Shuanghao Bai, Min Zhang, Wanqi Zhou, Siteng Huang, Zhirong Luan, Donglin Wang, and Badong Chen. pompt-basee distribution alignment for unsupervised domain adaptation. In AAAI, 2024.
Yin-Wen Chang, Cho-Jui Hsieh, Kai-Wei Rei Chang, Michael Ringgaard, and Chih-Jen Lin. Training and testing low-degree polynomial data mappings via linear svm. Journal of Machine Learning Research, 1 (14), 2010.
Jiawei Chen, Can Wang, Martin Ester, Qihao Shi, Yan Feng, and Chun Chen, Social recommendation with missing not at random data. In ICDM, 2018.
Jiawei Chen, Hande Dong, Yang Qiu, Xiangnan He, Xin Xin, Liang Chen, Guli Lin, and Keping Yang. Autodebias: Learning to debias for recommendation. In SIGIR, 2021.
Juan Chen and Yingchun Zhou. Weighted euclidean balancing for a matrix exposure in estimating causal effect. wxxiv.org/abs/2:33300666// 2023.
Quanyu Dai, Haoxuan Li, Peng Wu, Zhenhua Dong, Xiao-Hua Zhou, Rui Zhang, Xiuqiang He, Rui Zhang, and Jie Sun. A generalized doubly robust learning framework for debiasing post-click conversion rate prediction. In KDD, 2022.
Silviu Guiasu and Abe Shenitzer. The principle of maximum entropy. The Mathematical Intelligencer, 7:42-48, 1985.
Siyuan Guo, Lixin Zou, Yiding Liu, Wenwen Ye, Suqi Cheng, Shuaiqiang Wang, Hechang Chen, Dawei Yin, and Yi Chang. Enhanced doubly robust learning for debiasing post-click conversion rate estimation. In SIGIR, 2021.
Jens Hainmueller. Entropy balancing for causal effects: A multivariate reweighting method to produce balanced samples in observational studies. Political Analysis, 20:25-46, 2012.
Miguel A. Hernán and James M. Robins. Causal Inference: What If. Boca Raton: Chapman and Hall/CRC, 2020.
José Miguel Hernández-Looato, Neil Houlsby, and Zoubin Ghahramani. Probabilistic matrix factor- ization with non-random missing data. In ICML, 2014.
Shanshan Huang, Haoxuan Li, Qingsong Li, Chunyuan Zheng, and Li Liu. Pareto invariant represen- tation learning for multimedia recommendation. In ACM-MM, 2023.
Kosuke Imai and Mare Ratkovic. Covariate balancing propensity score. Journal of the Royal Statistical Society (Series B), 76(1):243-263, 2014.
Guido W. Imbens and Donald B. Rubin. Causal Inference For Statistics Social and Biomedical Science. Cambridge University Press, 2015.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Fan Li, Kari Lock Morgan, and Alan M Zaslavsky. Balancing covariates via propensity score weighting. Journal of the American Statistical Association, 2018.
Haoxuan Li, Quanyu Dai, Yuru Li, Yan Lyu, Zhenhua Dong, Xiao-Hua Zhou, and Peng Wu. Multiple robust learning for recommendation. In AAAI, 2023a.
Haoxuan Li. Yan Lyu, Chunyuan Zheng, and Peng Wu. TDR-CL: Targeted doubly robust collaborative learning for debiased recommendations. In ICLR, 2023b.
10

---

Published as a conference paper at ICLR 2024
Haoxuan Li, Kunhan Wu, Chunyuan Zheng, Yanghao Xiao, Hao Wang. Zhi Geng, Fuli Feng, Xiangnan He, and Peng Wu. Removing hidden confounding in recommendation: A unified multi-task learning approach. In NeurlPS, 2023c.
Haoxuan Li, Yanghao Xiao, Chunyuan Zheng, and Peng Wu. Balancing unobserved confounding with few unbiased ratings in debiased recommendations. In WWW, 2023d.
Haoxuan Li, Yanghao Xiao, Chunyuan Zheng, Peng Wu, and Peng Cui. Propensity matters: Measur- ing and enhancing balancing for recommendation. In ICML, 2023e.
Haoxuan Li, Chunyuan Zheng, and Peng Wu. StableDR: Stabilized doubly robust learning for recommendation on data missing not at random. In ICLR, 2023f.
Haoxuan Li, Chunyuan Zheng. Sihao Ding, Peng Wu, Zhi Geng, Fuli Feng, and Xiangnan He. Be aware of the neighborhood effect: Modeling selection bias under interference for recommendation. In ICLR, 2024.
Jinwei Luo, Dugang Liu, Weike Pan, and Zhong Ming. Unbiased recommendation model based on improved propensity score estimation. Journal of Computer Applications, 2021.
Zheqi Lv, Wenqiao Zhang, Shengyu Zhang, Kun Kuang, Feng Wang, Yongwei Wang, Zhengyu Chen,
Tao Shen, Hongxia Yang, Beng Chin Ooi, al. Duet: tuning-free device-cloud collaborative parameters generation framework for efficient device model generalization. In WwW, 2023.
Zheqi Lv, Wenqiao Zhang, Zhengyu Chen, Shengyu Zhang, and Kun Kuang, Intelligent model update strategy for sequential recommendation. In WwW, 2024.
Benjamin M Marlin and Richard S Zemel. Collaborative prediction and ranking with non-ram non-random missing data. In RecSys, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Stephen L. Morgan and Christopher Winship. Counterfactuals and Causal Inference: Methods and Principles for Social Research. Cambridge University Press, second edition, 2015.
Harrie Oosterhuis. Reaching the end of unbiasedness: Uncovering implicit limitations of click-based learning to rank. In SIGIR, 2022.
Paul R. Rosenbaum. Design of Observational Studies. Springer Nature Switzerland AG, second edition, 2020.
Paul R. Rosenbaum and Donald B. Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70:41-55, 1983.
Yuta Saito. Asymmetric tri- tri-training for debiasing missing-noo not-at-random explicit feedback. In SIGIR, 2020.
Yuta Saito. Doubly robust estimator for ranking metries with post-click conversions. In RecSys, 2020.
Yuta Saito, Suguru Yaginuma, Yuta Nishino, Hayato Sakata, and Kazuhide Nakata. Unbiased recommender learning from missing-not not-at-random implicit feedback. In WSDM, 2020.
Pedro H. C. Sant' Anna, Xiaojun Song, and Qi Xu. Covariate distribution balance via propensity scores. Journal of Applied Econometrics, 1093)1 1 120, 2022.
Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Recommendations as treatments: Debiasing learning and evaluation. ICML, 2016.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to
algorithms. Cambridge University Press, 2014.
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
11

---

Published as a conference paper at ICLR 2024
Harald Steck. Training and testing of recommender systems data missing not at random. In KDD, 2010.
Elizabeth A. Stuart. Matching methods for causal inference: A review and a look forward. Statistical Science, 25(1):1-21, 2010.
Hao Wang, Tai- Rei Chang, Tianqiao Liu, Jianmin Huang. Zhichao Chen, Chao Yu, Ruopeng Li, and Wei Chu. ESCM²: Entire space counterfactual multi-task model for post-click conversion rate estimation. SIGIR, 2022a.
Hao Wang, Jiajun Fan, Zhichao Chen, Haoxuan Li, Weiming Liu, Tianqiao Liu, Quanyu Dai, Yichao Wang, Zhenhua Dong, and Ruiming Tang. Optimal transport for treatment effect estimation. In NeurIPS, 2023a.
Haotian Wang, Wenjing Yang. Longqi Yang, Anpeng Wu, Liyang Xu, Jing Ren, Fei Wu, and Kun Kuang. Estimating individualized causal effect with confounded instruments. In KDD, 2022b.
Haotian Wang, Kun Kuang, Haoang Chi, Longgi Yang, Mingyang Geng, Wanrong Huang, and Wenjing Yang. Treatment effect estimation with adjustment feature selection. In KDD, 2023b.
Haotian Wang, Kun Kuang, Long Lan, Zige Wang, Wanrong Huang, Fei Wu, and Wenjing Yang. Out-of dittr--distribution generalization with causal feature separation. IEEE Transactions on Knowledge 2024.
and Data Engineering. 36(4):1758-))
Jun Wang, Haoxuan Li, Chi Zhang, Dongxu Liang, Enyun Yu, Wenwu Ou, and Wenjia Wang. Coun- terCLR: Counterfactual contrastive learning with non-random missing data in recommendation. In ICDM, 2023c.
Xiaojie Wang, Rui Zhang, Yu Sun, and Jianzhong Qi. Doubly robust joint learning for recommenda- tion on data missing not random. In ICML, 2019.
Xiaojie Wang, Rui Zhang, Yu Sun, and Jianzhong Qi. Combating selection biases in recommender systems with a few unbiased ratings. In WSDM, 2021.
Raymond K W Wong and Kwun Chuen Gary Chan. (ernel-based covariate functional balancing for observational studies. Biometrika, 105(1):199-211 2018.
Peng Wu, Qirui Hu, Xingwei Tong, and Min Wu. Learning causal effect using machine learning with application to china's typhoon. Acta Mathematicae Applicatue Sinicu, 36(3):702-713, 2020.
Min Zhang, Junkun Yuan, Yue He, Wenbin Li, Zhengyu Chen, and Kun Kuang. Map: Towards balanced generalization of iid and ood through model-agnostic adapters. In ICCV, 2023.
Min Zhang, Haoxuan Li, Fei Wu, and Kun Kuang. MetaCoCo: A new few-shot classification benchmark with spurious correlation. In ICLR, 2024.
Qingyuan Zhao and Daniel Percival. Entropy balancing is doubly robust. Journal of Causal Inference, 5(1):20160010, 2017.
Hao Zou, Haotian Wang, Renzhe Xu, Bo Li, Jian Pei. Ye Jun Jian, and Peng Cui. Factual observation based heterogeneity learning for counterfactual prediction. CLeaR, 2023.
12

---

Published as a conference paper at ICLR 2024
A PROOFS
Theorem 1. eu, E H. = spanth (-),. ....... N....H.) (-), then the above learned propensities lead to an unbiased ideal loss estimation term of the IPS method.
Proof. The balancing weight uu,i is learned by solving the following optimization problem
max- On
Σ
Cuse log U.,i
(u,1)EO
8.t.
Ou,eWin, (1) (Iu.i)
1
Σ
j JJ.
D
D
(WN)ED
(uN)ED
1
Ou
Wa. 2 v(u, e E0,
D
(N,))D
thus the learned U.ū satisfying the constraints in the optimization problem, which means that
Σ
(ou (Zw.)) (xu,)) = 0, j {I.....J}.
D
(u,s)ED
Cut E Hy (pan(h()))) (-)) there exist {aylí=ı satisfying cu,i Σy=1 azhl0(zu.)) the empirical bias of the KBIPS estimator for estimating the ideal loss is
Bias (AKKBBI(SS())) =
Σ
(Ou, - 1)eu,i
[D]
(a.i)DD
(ou - 1) Σ (o
D
(a,j)ED
Σ (u,ieD
(1 - 10 (anss))
D
eu,s & H. = span (), ()),,, then for {az})=ı, Cu, Σÿ= (yh(t) (x) ) + c(Fua))
where e(x,,s) is the non-zero residual term. Therefore, we have
2
Bias( (las(CKirrs())))
1
Σ
(ou, 1) 1)ee
D
(a.))D
(Du - 1)e(Fun)) }
* 0.
D
(a.jED
similar argument also holds for the proposed KBDR estimator.
Lemma
(Sriperumbudur al. (201T)). Both the Gaussian and exponential kernels are universal.
Proof. The proof can be found in Sriperumbudur et al. (0011).
Lemma 2 (Representer theorem). If h(llfl) for some increasing function h R4 R. then some empirical risk minimizer must admit the form f(.) = Ei= (,,)), for some a (on, (on,...,0a) E IRn. h is strictly increasing, all minimizers admit this form.
13

---

Published as a conference paper at ICLR 2024
Proof. The proof can be found in Theorem 6.11 of Mohri al. (2018).
and Ben David 2014)). Let F be a family of prediction models mapping from a X la, b, and {uu. (u, 1 E D a fixed sample of size [D] with elements in X. Then, the empirical Rademacher complexity of F with respect to the sample defined as
Definition 2 (Empirical Rademacher Complexity
1
R(F) -Bo
sup JeF
Σ (u.))D
[
where a fuu. (u, E D), and ou,i are independent uniform random variables taking values in +1}. {1]. The random variables Jn,i are called Rademacher variables.
Lemma 3 (Rademacher Comparison Lemma "Shalev-Shwarts and Ben-Daaee 2014)). Let F be family of real-valued functions z E 2 to (a, b), and S = (Tu,i (u, D fixed sample of size [D] with elements X. Then
]
E SPP
E [((()]]
Σ (Bmaa) (u.J)ED
<
E E Bo- 1.11] S-BiZI
Σ
ansl (Zus)
fEF
D
fef
D
(a.i)ED
where o fou,s: (u, E DJ, and Ju,i are independent uniform random variables taking values in {1}. The random variables Tu,i are called Rademacher variables.
Proof. The proof can be found in Lemma 26.2 of Shalev-Shwartz and Ben- David 2014
Lemma (McDiarmid's Inequality (Shalev-Shwarty and Ben-David, 2014 Let V some set and let f m + R. be function of m variables such that for some 0, for all E [m]] and for all Ti. Rm. o V we have
If (I1....,Im)) - (21...., Ds+1 l..... Fm S.
Let X1...., Xm be independent random variables taking values in V. Then, with the probability of at least 1 5 we have
2
(X Xm) - E (X1, Xm)]l s q log m/2.
Proof. The proof can be found in Lemma 26.4 Shalev-Shwarrz and (2014).
Lemma (Rademacher Calculus (Shalev-Shwartz and Ben-David, 2014)). For any C Ih scalar E TR, and vector ag RR, we have
R R(ca an A}) < lc[R(A).
Proof. The proof can be found in Lemma 26.6 of Shalev-Shwartz and BeviDavid (014).
Lemma 6 (Talagrand's Lemma MMorri et al., 2018)). Let $1,..., Im A-Lischite.functiinn from Th to R and 01...., Jm be Rademacher random variables. Then, for any hypothesis set F of real-valued funcuuudfnnttiin functions, the following inequality holds
m
m
E ma
sup
Σ
o.
(
Σ off (x:) fEF
sup
LR(FF).
|EF
m
In particular, & = for all i [m]. then the following holds
R( o F) LR(F).
Proof. The proof can be found in Section 5.4 of Mohri et al. 2018).
14

---

Published as a conference paper at ICLR 2024
Lemma 7. Suppose K is bounded kernel with sup, v K( (xx,z) B < and let F be its RKHS. Let M > 0 be fixed. Then for any {Ius (u, E D),
MB
R ((Bx(M)) <
V
where Bx(M) = [1 E = SM}
Proof.
Fix = {Iuns (u, i) E DD. Then
R R(B((M)) = Eg
sup
Σ (u,
Jusf (Taj)
fEBx (M) [D]
Σ
Jus (S, K (., (us))
sup
[D]
SEBx (M) (u,i)ED
1 (D)
/, Σ JusK (1,
EN
sup SEBx (M)
(u,))D
E E(u.DED TniK (1, Fu,))
1 EG [D]
M
Σ (u.)ED
ouiKK (s, (.,e))))
E(usDED Dnik K Bun)
M
Exr
Σ
Duiik (s,
D
(M,
2
M Es
Σ (u.))D
Juikk Turi)
D
M
E,
Σ
Duik (1, (ur))
D
(u,i)ED
M
| (wa)l)
PD
M
K (Du,i,
PP
(LL)ED
M
B
D
MB
V
Theorem 2 (Generalization Bounds in RKHS). Let K be bounded kernel, sup, v K [xx x) B < 8o, and (M) {f E F |[fl & M) M) is the corresponding kernel-based hypotheses space. Suppose u.ss C, 8(r, is L-Lipschitz continuous for all r, and that Eg := sup, 0(r, 0) oc.
Then with probability at least 1 we have
(0.)) + 2CLMB
log(4/n)
(1deat(0)) S LKBIPS(0,) +
+ 5C + LMB)
VID
2
15

---

Published as a conference paper at ICLR 2024
and
2LMB
log (4/m)
(id) S LKBDR (0,) + (BBo((kBDR( + (1 (1+ + 2C)
+ 5(Eo + LMB)
ViD)
2
Proof. We first prove the generalization bound of the KBIPS estimator, noting that the ideal loss can be decomposed
(0,) LKBIPS (0,) + (O,) E[ (((KBIPs(0)))) + (E(CKBIPs(O))) CKBIPS(O.))
= LKBIPS (0,) + Bias( (ias(CKBIPS(H))) - (E(CkBIPs(B,)) (KBIPS(f,))
S CKBIPS(O, (0,) + [Bias( (CrBIPs(O.))
+
sup (M)
E
Σ
Σ (a.0)D
DD]
D
(u,i)ED
For simplicity, we denote the last term in the above formula as
B(F) = sup (M)
E
Σ
[D]
(u,))ED
(u,i)ED
we then aim to bound B(F) in the following.
Note that
B(F)
EE supim [B(F)), and by Lemma we have
E
B(F) B(F)
[B(})}
[B
S-PEI
where the first term is
1
[B(F)
2 E E [- SMPP
sup (oEBx(M)
Σ Tu (a.i)ED
SwplD
D
2 E S-PE
(R())BIss(.)))..
where
R(LKAIPS(0.)) = Eg sup (M)
Σ
D
(N.))D
By applying McDiarmid's inequality in Lemma 4 and the assumptions that G..i S C, also note that
Aut sup, <K(x, I MB, thus e,,; L(fu,is Tu,a) I Es + LMB, let
2C(Eo + LMB)
[D]
then with probability least 1 2
2C(Eo LMB)
log(4/n) D
R(CKBIPs(O,)) SApID)
E (R(CKBIPS(O.)))
[D]
log(4/m)
-C + LMB),
2
By the assumption that u., & C and 6(r, :) is L-Lipschitz continuous for all r, we have ((C)))Ps((.)) < CLR(F)
CLMB
VIDi
16

---

Published as a conference paper at ICLR 2024
where the first inequality is from Lemma 5 and Lemma 6 with L as Lipschitz constant, the second inequality is from Lemma 7, and (FF) is the empirical Rademacher complexity
R(F) = o (1,+1111
sup (M)x(M)
[D] Σ (a.i)ED
ousl(Tu.))
where a {ou,s (u, i) E D), and uu, are independent uniform random variables taking values in +1). The random variables u,d are called Rademacher variables.
[B(F),, by applying McDiarmid's inequality in Lemma 4 and the For the rest term BFF) S-FIPi
assumptions that W,si C' and Cu.s Eo + LMB, let
C(Bo + LMB)
[D]
then with probability at least 1 - 2.
C(Eo + LMB)
log (4/1)
log(4/n) 2
B(F) [BFF]
<
C(Eo + LMB)
SWp 0i
D
2
We now bound B(F) by combining the above results. Formally, with probability least 7
E [(F)] { ((F)- S-PD1
B(F)=
[((F]]
SApID1
S E SwPiDl
(R(LKBIP((A)))
B(F)
E
[B(F)
SuPID
log(4/1)
< 2R (4(KIIsss(.))) +C LMBB)
B(F)
E
[B(F]]
2|D|
SwPiDi
log(4/n)
< (R((KBIPs(O.)) + 55 + LMB)
2|D
2CLMB
log(4/n)
+ 5C + LMB)
D
2
We now bound the ideal loss by combining the above results. Formally, with probability at least 1 - 17, we have
Cideat (0,) S (O,) + (BBss(CrnIss((.)) + B(F)
2CLMB
log(4/n)
< (KBIPs(O.)) + (Bas(CkBIPs(O.)))
+ 5C + LMB)
VIDI
2/D1
Theorem we have already proved that
BBias(CKBrr(0O)))
Σ
(Ou, - 1)en,
D
(u.i)ED
therefore with probability least 1 77, we have
2CLMB
log(4/n)
Lident(00) S LKBIPS(0,) (0.) + [Biss COAINS((BP)S)))
+ 5C + LMB)
VID
2
17

---

Published as a conference paper at ICLR 2024
We then prove the generalization bound of the KBDR estimator, similarly, the ideal loss can be decomposed as follows.
Lideal (0,) LKBDU (0,) (Lideal (0,) (O.))) + (B(CKEDn(())) (KBDR(0,))
= LKBDR (0,) + Bias( CKBRR (0+)) + (B(CKBDR((.)) (KBDR(O,))
I CKBDR (0,) [Bias (CKBDR(B.))
sup (AF)
E
Cut + 0u, -eans enni)
Σ (u,i))D
@u, + ou (uxt
[
D
(u.i)ED
For simplicity, we denote the last term in the above formula as
(eui + on ou, - cmill)
B(F)= =
sup feEBx(M
E
Eu.s + 20, Ew.id]
Σ (u.))ED
[D]
D
(a,))ED
we then aim to bound (FF in the following.
Note that
B(F)
E
[(F) B(F)
EE
[B(F)]
[B
SupiP [BF)], and by Lemma we have
S-P
where the first term is
SWIID
E [B(F)
2 E
E (-
sup (M)
1
Σ (a.i)ED
oue (Bad + Ou, -
SwPIDI
S-F
[D]
=
E (R(L)))R(f))),
S~P
where
bus + tn - Emsi)]
((CKBDR(O,)) =
sup foEBx
Σ
ouei
[D]
(u,))D
By applying McDiarmid's inequality in Lemma 4 and the assumptions that want S C, ēu, S
Eo + LMB, B, and ea,i S Eo + LM B, let
2 + LMBB (C2))
D
then with probability at least 1 - g.
R(LKBDR(Oo)) - E
(O,))) <
2(E + LMB) + 2C)
V
log(4/n)
S~PIRj
|D]
2
log (4/n)
2( + LMB)(1 + +20)
2
By the assumption that u... S C and 6(r,)) is T---ipschitz continuous for all we have
R(LKndR(0,)) < L(1 + (1 2C) LMB
VID
where the first inequality is from Lemma and Lemma with L(1 + 2C)) as Lipschitz constant, the second incquality is from Lemma 7, and R(F) is the empirical Rademacher complexity
R(F) = E (--(--+))
sup (M
Σ
ou.i((au.)
[D]
(a.))ED
18

---

Published as a conference paper at ICLR 2024
where fo (u, E D), and ou,i are independent uniform random variables taking values in {-1, +1). The random variables Ju,i are called Rademacher variables.
For the rest term (FF) S-
[B(F],, by applying McDiarmid's inequality in Lemma 4 and the assumptions that W.,s S C. Cus S Eo + LMB, and Cu,i S Eo + LM let
E
(Ea (1 + 2C)
(
then with probability least
2
(Eo LMB)(1 20).
llog(4/))
log(4/n)
B(F)-
E
[(F)
(Es+LMBB(L-20)
SNpil1
[D]
2
2/D|
We now bound B(F) by combining the above results. Formally, with probability at least 1
B(F) = [BFF] + B(F)
E SNPiDI
[B(]]]
SuPIDi
2 E (R(CKBDn(O.))) + [(F) S~PiDi
E
[B(F)]
Supiol
log(4/m)
< (2R(CKEDR(0)))+ LMB)(1 (
2
B(F)
E
[BF)]
2/DI
S-P
log(4/n)
< (2R(CKEDR LMBB(1 2
2
LMB
log(4/n)
2111 2C)
+ +( + LMB)(1 + 20)
VDD
2
2LMB
[log(4/))
= (1+20) 2C'
+ 5 + LMB)
VIDI
2/D)
We now bound the ideal loss by combining the above results. Formally, with probability least 1 T/, we have
(Ideat(0)) S (KBDR((,) + [Bias(CKeDR (0.)) B(F)
2LMB
1og(4/1))
< LKBDR((,)) + [Bias(CKBDR (0,)) 2C+
+ 5(Eo + LMBB)
VDD
2
In Theorem we have already proved that
(BiS((KBDRR(.))) D
Σ
(ou,s - 1)(eus - Cus)
(u,i)ED
therefore with probability least 1 77, we have
2LMB
(og(4/1)
(Ode < CKBDR((,) + [Bias(CxnDR(ee))) (1 2C)
+ 5(E, + LMB),
DD
2
which yields the stated results.
19


Reviews:
[{"review_id": "vj5yJYwDz1", "reviewer": "Reviewer_CJCu", "summary": "This study explores the concept of incorporating a balance regularization loss to mitigate selection bias in Recommender Systems (RS). It centers on determining which function class requires balancing. The authors reframe the issue as an optimization problem, contending that the prediction error should result from a linear combination of balancing functions, supported by theoretical analysis. To achieve this, the authors suggest utilizing kernel functions as balancing functions and put forth three approaches for selecting these kernels. Empirical experiments illustrate the benefits of the proposed balancing techniques.", "questions": "Please see the Weaknesses part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The study delves deeper into the challenge of addressing selection bias by examining the specific function that warrants balance. This research problem introduces a novel perspective.\n\n- The concept of employing a linear combination of kernel functions to attain both unbiasedness and universality is intriguing and offers inspiration.", "weaknesses": "I think the idea in this paper is interesting and has some value. However, I have some significant concerns that prevent me from recommending this manuscript for acceptance.\n\n **1. Motivation**\n\n- W1: This paper lacks a sufficient motivation for the importance of carefully selecting the function class for balancing. The authors do discuss the computational cost associated with choosing numerous balancing functions in Section 3.2. However, the original paper [1] suggests that even selecting a single function for balancing can yield performance improvements. It is essential to elucidate why the choice of multiple balancing functions is necessary and why the specific type of function is critical. In my view, the motivation may be derived from Corollary 1 to some extent, which asserts that certain types of balancing functions introduce bias (correct me if I am wrong). Nonetheless, it would be valuable to provide a more insightful explanation in the introduction section. I would like to see an illustrative example, which could enhance comprehension of the motivation.\n\n**2. Clarity**\n\nThis paper contains several areas of ambiguity and insufficient support for its claims, which hinder the comprehension of its ideas. Some key issues include:\n\n- W2: The optimization problems in Sections 4.2 and 4.4 are perplexing. The rationale behind minimizing the sum of $g(\\cdot) \\log g(\\cdot)$ as opposed to a standard cross-entropy loss is unclear and confusing. The purpose of constraining the sum of $o_{u,i}g(\\cdot)$ to be one and the meaning of the third constraint require more detailed explanation and motivation. The authors should clarify the significance and reasoning behind each statement in the proposed optimization problem.\n\n- W3: Several theorems and corollaries, such as Theorem 1, Corollary 1, and Lemma 2, lack supporting proofs. In particular, the proof of Corollary 1, which appears directly relevant to the paper's motivation, is crucial.\n\n- W4: The paper suggests that \"balancing propensity can reduce the generalization bound\", but this claim is not clearly evident from Theorem 2, which seems to provide a bound without a comparative analysis.\n\n- W5: The fourth paragraph in Section 1 references \"the first question\" and \"the second question\", but it is unclear where these questions are presented in the paper.\n\n- W6: The paper does not elaborate on how the parameters within the kernel functions are learned. For instance, Gaussian kernel functions are known to have a parameter, $\\sigma$. The paper should explain the process for selecting suitable parameter values.\n\n- W7: Given that kernel functions are not frequently used for debiasing Recommender Systems, it is recommended that the authors provide more specific definitions and formulations regarding the kernel functions in Section 4.3 to enhance clarity.\n\n- W8: There are some typos in this paper. \n  - Section 1: \"it is the first paper provides ...\", \"Ours theoretical analysis shows...\". \n  - Section 4.4: \"which Random chooses...\".\n\n**3. Experiments**\n\n- W9: The paper does not specify which kernel function was chosen, whether Gaussian or exponential.\n\n- W10: I found that the performance on \"Coat\" you reported in Table 1 is significantly lower than that on [1]. It would be helpful to understand whether this variance is attributed to different experimental settings or other factors.\n\n- W11: The abbreviation \"CB\" for causal balancing is indeed similar to \"Covariate Balancing\" and may cause confusion. A more distinct abbreviation should be considered to prevent any potential misunderstandings. \n\nOverall, the motivation and clarity are my main concerns. I will consider changing my score if I receive a high-quality (concise and clear) rebuttal.\n\n[1] Haoxuan Li, Yanghao Xiao, Chunyuan Zheng, Peng Wu, and Peng Cui. Propensity matters: Measuring and enhancing balancing for recommendation. 2023d.\n\n\n---\n\n*After the rebuttal: the authors address the most of my concerns. Therefore, I am glad to raise my score from 3 to 6.*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4j7PtY6LNM", "reviewer": "Reviewer_4dU2", "summary": "This work contributes to the field of debiased recommendation recommendation by proposing a\nuniversal kernel-based balancing method to balance functions. It also provides theoretical analysis and guidance of balancing property under finite samples. Experimental results on three real-world datasets verify the proposed balancing methods.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.This work discusses the limitations of existing methods including the Inverse Propensity Score (IPS) and Doubly Robust (DR) method for debiased recommendation, showing that the importance of balancing property under finite-dimensional function classes.\n\n2.The authors extend them to CBIPS and CBDR estimators and it is reasonable to proposed kernel balancing method for optimization.\n\n3.The work also provides theoretical analysis and proof of the proposed kernel balancing and proposes three causal balancing methods to effectively balance the kernel functions.\n\n4.Experimental results show the effectiveness of the adaptive kernel balancing method.", "weaknesses": "1.It is advisable to include a discussion of the relationships or distinctions between this work and prior research in the Related Work section.\n\n2.In terms of the Adaptive Kernel Balancing method, I am confused why balancing the kernel functions with maximal $|\\alpha_{s,t}|$ can contribute the most to the $e_{u,i}$. It requires more explanation to improve the readability. Besides, the authors adopt this way to improve the efficiency but there is no corresponding experiment to validate this.\n\n3.Writting of this paper needs improving:\n- The background of debias recommendation is not enough. \n- The definition of $o_{u,i}$ is not clarified clearly.\n- Grammar needs carefully checking:\n  - the usage of “an” such as “Moreover, we propose an causal” \n  - learn an appropriate propensity model that achieve lower estimation bias.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gzJ4RpWpJx", "reviewer": "Reviewer_ptof", "summary": "The paper proposes a unified kernel-based method to balance functions on the reproducing kernel Hilbert space (RKHS) to address the bias in collaborative filtering due to the observational nature of the collected data. Although balancing (i.e., re-weighting the sample loss) is an important technique to address such selection bias, this paper characterizes the effect of balancing low-dimensional functions on the bias of inverse propensity score (IPS) and doubly robust (DR) methods. A novel adaptive causal balancing method that alternates between unbiased evaluation and model training is proposed. Extensive numerical experiments are conducted on real-world recommendation data sets to demonstrate the proposed method could effectively improve prediction performance compared with the existing benchmarks.", "questions": "1. How to update the weights for the problems where the number of items and/or the number of users are large?\n\n2. Modern DL-based recommender system typically generates an embedding for each user and each item for subsequent tasks such as score prediction and recommendation. Is it possible to adjust this method as a means of fine-tuning the item and/or user embeddings?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem studied is important and relevant.\n2. The idea is interesting and novel.\n3. The evaluations are solid and convincing.", "weaknesses": "1. The optimization formulation for balancing may be computationally intractable if the number of items and/or the number of users are large.\n\n2. It is unclear how to incorporate the proposed method into the modern deep learning (DL) based recommender system and to test its effectiveness in a field setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)