Solving the Cold Start Problem on One's Own as an End User via Preference Transfer
Authors: Ryoma Sato
Venue: Accepted by TMLR ()

Abstract: We propose a new approach that enables end users to directly solve the cold start problem by themselves. The cold start problem is a common issue in recommender systems, and many methods have been proposed to address the problem on the service provider's side. However, when the service provider does not take action, users are left with poor recommendations and no means to improve their experience. We propose an algorithm, Pretender, that allows end users to proactively solve the cold start problem on their own. Pretender does not require any special support from the service provider and can be deployed independently by users. We formulate the problem as minimizing the distance between the source and target distributions and optimize item selection from the target service accordingly. Furthermore, we establish theoretical guarantees for Pretender based on a discrete quadrature problem. We conduct experiments on real-world datasets to demonstrate the effectiveness of Pretender.

Published in Transactions on Machine Learning Research (10/2025)
Solving the Cold Start Problem on One's Own as an End User via Preference Transfer
Ryoma Sato National Institute of Informatics
rsato@nti.cc.p
Reviewed on OpenReview: https: // openreview. net/ formm? id Sgj0ZdoVWi
Abstract
We propose new approach that enables end users to directly solve the cold start problem by themselves. The cold start problem is common issue in recommender systems, and many methods have been proposed to address the problem on the service provider's side. However, when the service provider does not take action, users are left with poor recommen- dations and no means to improve their experience. We propose an algorithm, PRETENDER, that allows end users to proactively solve the cold start problem on their own. PRETENDER does not require any special support from the service provider and can be deployed inde- pendently by users. We formulate the problem minimizing the distance between the source and target distributions and optimize item selection from the target service accord- ingly. Furthermore, we establish theoretical guarantees for PRETENDER based on a discrete quadrature problem. We conduct experiments on real-world datasets to demonstrate the effectiveness of PRETENDER.
1 Introduction
Recommender systems have become essential component of many online services, such e-commerce
These systems analyze user preferences and recommend items that the user may like. A common problem in recommender systems is the cold start problem, where the system cannot provide good recommendations for new users due to lack of historical data. Many methods have been proposed to address the cold start problem, such as content-based filtering utilizing side information
28 31,
social media g 5,59, and vidco streaming platforms 15 52
2
60
meta learning 25
53
and active learning 10
However, all of these methods are designed to be implemented on the service provider's side, and require the service provider to take action. When the service provider does not take action, c.g., due to lack of resources, lack of incentives, or simple negligence, users are left with poor recommendations and no immediate way to improve their experience. This can be particularly frustrating for users who are eager to adopt new service but struggle to discover relevant items due to the cold start problem.
In this paper, we propose a new problem setting that enables users to address the cold start problem on their own. We consider scenario where a user has been using a source service (e.g., Netflix) for a long time and has history of preferences for items. The user has just started using target service (e.g., Hulu) but lacks any preference history that platform. The user receives good recommendations from the source service but poor recommendations from the target service due to the cold start problem. The user wants to transfer the preferences from the source service to the target service so that the user can enjoy good recommendations from the larget service as well. If the larget service offers a built-in functionality to import preferences, this problem can be easily solved. However, in many cases, such functionality is not provided, leaving the user with no direct means to improve their recommendations. To address this, we propose an algorithm, PRETENDER, that enables users overcome the cold start problem independently, even when neither the source nor the target service provides dedicated support for preference transfer.

---

Published in Transactions on Machine Learning Research (10/2025)
We formulate the problem minimizing the distance between the source and target distributions and optimize the selection of items from the target service accordingly. A key strength of our method is that it provides strong theoretical guarantees even when the way the target service uses the data is unknown. We prove this by solving a new quadrature problem that arises in the optimization process, which is of independent interest. We conduct experiments on real-world datasets to demonstrale the elfectiveness of PRETENDER. Our experiments show that PRETENDER can transfer the preferences effectively.
The contributions of this paper follows:
We propose a new problem setting that enables users to independently address the cold start problem on their own.
We propose PRETENDER, algorithm that allows users to overcome the cold start problem with theoretical guarantees, even in the absence of support from the service provider.
We conduct experiments real-world datasets to validate the effectiveness of PRETENDER.
Reproducibility: Our code is available at htttp:///gtaab..cco///allao//pps
2
Problem Setting
Suppose we are an end user of the source service (o.g., Netflix) and the target service (e.g., Hulu). We have been using the source service for a long time and have a history of preferences for items (e.g., thumbs-up or thumbs-down for videos). We have just started using the target service and lack any preference history on that platform. We receive poor recommendations from the target service due the cold start problem. Our goal is to transfer preferences from the source service to the target service that can enjoy good recommendations from the larget service as well. The problem is formally defined as follows:
Problem (Preference Transfer).
Input: Sets of source items 1g and target items lr. Features æ; of items E ls Lr. set Dş = {(i, w:) C Is x {0, }} user preferences on source items. positive integer E 2,4 representing the number of target items interact with.
Output: A set Dr = ((i, 9:)) C Ir (0, with [Drl K such that clicking items following Dr results in good recommendations from the target service.
A method outputs a set of preferences for the target itemss denoted as Dr {(i, y:)), Following this output, the end user clicks thumbs up for each item i E fi E Ir (i, Dr} and thumbs down for each item i E (i E IT 0i E Dr}. A good method should output Dr such that the user can enjoy good recommendations from the target service after this process. Note that the clicking process (and thus the entire process) may be automated by a Web agent.
This problem presents three main challenges:
Items are not shared between services. A naive approach might simply "copy" the history to the target service, but this approach fails because the corresponding items may not exist in the target service, i.e., Is + Ir.
Clicking many items tedious. The user may not want to interact with many items just for preference transfer, i.e., K is small. Even when the clicking process automated, too large may take long time and/or impose heavy load the target service.
The target service's use of the data is unknown. The target service may process preference data Dy differently from the source service or in an unexpected manner, making it difficult to predict how the transferred preferences will influence recommendations.
2

---

Published in Transactions on Machine Learning Research (10/2025)
3 Pretender
We propose PRETENDER (PREference Transfer by END usERs) to solve the preference transfer problem. We first describe the general framework and then provide variants for specific scttings.
3.1 Formulating the Problem as Distance Minimization
The goal of PRETENDER is to select items from the target service such that its empirical distribution PT is close to the source distribution (as; which are defined as
PT
Σ (b.:)EDr
PS
8(3),91)
(1)
K
Ds
(f.
where 82 denotes the Dirac measure al x. We the integral probability metric (TPM) 35 51 to quantify the discrepancy between the distributions, which is defined for function class F as
/ dp -f f dv.
IPM sup /e
fdv.
(2)
When FF is the class of functions with a reproducing kernel hilbert space (RKHS) norm at most 1, the IPM equivalent the maximum mean discrepancy (MMD) [6] and when F the class of 1-Lipschitz
functions, the IPM corresponds to the I-Wasserstein distance 39 54. PRETENDER selects items such that
IPM, is small, ensuring that the target distribution closcly aligns with the source distribution.
This formulation addresses the third challenge. Suppose the target service uses unknown model fr(::0 0) and unknown loss function (r(--) to train the model. We only know that the loss (r(f((x;)) is L- Lipschitz in (). Then, the model incurs the following loss on the source preferences:
(loss on the source data)
1
Σ (r(Jr(a;:):.,))
(3)
[Dsl
(s.v))Ds
/ (r(fr(e;)) (a)(
(4)
f (r(ff(=;)) (1:00) d (x, v) + L- L WI Dr us))
(5)
(training loss the target data) + L Wi(H (s))
(6)
where W1 denotes the 1-Wasserstein distance. The inequality follows from the definition of IPM (Eq. Therefore, if we minimize the Wasserstein distance Wi (H() between the source and target distributions, and the target service effectively minimizes the training loss on the target data, the model trained on the target preferences will also generalize well to the source preferences, thereby accurately reflecting the user's preferences
2
The crux of this approach is that its guarantee is agnostic to the model, loss function, and the training method the larget service employs, which are typically not known to the user. Regardless of how the target service uses the data, the user can ensure that the recommendation model trained on the target preferences reflects the source preferences as long as the distributions are close.
The use of TPM also addresses the first challenge. TPM exploits the geometry of the data space through the smoothness of the function class F (c.g., Lipschitz continuity and small RKHS norm) and can be used even when the items are not shared between the services. This is in a stark contrast other discrepancy measures such KL divergence and Hellinger distance.
Although we have formulated the problem as distance minimization between distributions, this problem remains challenging because selection of items is combinatorial. This is in contrast. to other minimization problems, where optimization is performed over weights and/or coordinates of data points, making the problem continuous and often convex. However, end users cannot "thumbs up 0.2 points" or alter the features of the items in the service, meaning that we cannot sidestep the combinatorial nature of the problem. We address this challenge in the following.
3

---

Published in Transactions on Machine Learning Research (10/2025)
3.2 Optimization
The optimization framework of PRETENDER is follows:
1. (Ttem Preparation) Prepare the set of labeled target items Jr = ((i,v) Ir E {0,1)). We rearrange the itemss such that they are indexed by 1,2,..,, 2m and redefine Jr = {(i,, |j E [2m]] where m = |rl is the number of items in the target service.
2. (Continuous Optimization) Optimize the weights E [0,
1 n n2mm of the items in the target K service such that the weighted empirical distribution μr Σك w,d(m.,..)) is close to the source distribution μss where Aa denotes the (d 1)- dimensioona probability simplex. This is achieved by solving the following optimization problem:
2m
min 2a
D
Σ
wid Ms HB
(7)
2m
s.l.
Σ wj 1,
05 OSw; S K
11=1,2.... 2m.)
3. (Random Selection) Sample itemss according the optimized weights. For each [2m], sample
1 Bernouli(Kw.)) for j E [2m], and define the selected set as Dr {(1j, 1].
4. (Postproccssing) If [Dr] < K, greedily inscrt additional items, and if |Dx| K, greedily remove items to obtain the final preference set Dr salisfying |Dr] K.
Item Preparation. We construct the set of labeled target items Jr ((ij. 1 E [2m]] Since the user can choose the label for each item (e.g,, thumbs up or thumbs down), we include both possible labels (i,0) and (i, in the candidate set, making the total number of items 2m.
Continuous Optimization. We first solve the contimuous relaxation of the problem. This problem is continuous and convex for MMD and the Wasserstein distance. Therefore, we can employ standard methods such as the Frank- Wolfe algorithm problem. By standard results in convex optimization, we can obtain eó such that
22 or the projected subgradient descent algorithm 4 to solve the
D(uT, us) Opreontimous +
(8)
min
D (uT us) +
(9)
we 0.
7d2m
min Dr 0y=((i00) PDrl=K
D
Σ
((o.)): us +
(10)
K
(LN)))DT
OPTsombinatorial
(11)
where (a) follows because the weight (I/K,..., 1/K) of the empirical measure is in the feasible set. Therefore, the continuous solution is least as good as the combinatorial solution. However, we need carefully round the solution to obtain the final output ensure that the rounding process does not degrade the quality of the solution much. This is the main challenge from theoret ical perspective.
Random Selection. We employ randomized approach. We first point out that the distribution Bernoulli( w,) is well-defined as set the optimization domain to E [0, 1 n A2m and 0 < Kw, S holds. Let to E 10,1/K) be the sample weights after the random selection, i.c., B. K I,- Then,
E B[w,]
- E K
1
(8)
1
Kw, W.j.
(12)
K

---

Published in Transactions on Machine Learning Research (10/2025)
where (a) follows from I Bernoulli(Kw,,) Therefore, the expected weight is the same as the continuous solution. This implies that D distributes around that of the continuous solution D(1T us) 2 OPT Next, we analyze the number of selected items, which is given by, in expectation,
2m
(a)
E
K Kwy
K,
(13)
where (a) follows from the fact that Σ
2j=1 wy = 1, I.C., u E A2m- In addition,
2m
2m
2m
(b)
2m
(0)
2m
(d)
Var
Var
Kwz (1 Kwy) S
K Kwj
K,
(14)
J=1
J=1
j=1
where (a) follows from the independence of the Bernoulli random variables, (b) follows from the variance of the Bernoulli random variables, (c) follows from w, 2 O, and (d) follows from Σimh wj = Therefore, the standard deviation is the order of VK, and the number of selected items concentrated around [K O(vK), K + K O(VK)) This implies that the selection process does not blow up the error too much. We will elaborate this discussion in the following sections.
Postproccssing. Since the number of selected items may deviate from K, we may need to insert or remove items to make exactly K. As the number of over- or under-selected items on the order of v K, the error introduced by this step is also the order of /K = K-1/2
In the following sections, we will elaborate on the method and provide theoretical guarantees for MMD and the Wasserstein distance.
3.3 Pretender for MMD
We consider the case where we quantify the discrepancy between the distributions with MMD, defined as
/ du [idu-
f fdv,
MMD(H,V)
sup llfl
(15)
where H is the RKHS with the kernel k. Equivalently, the MMD can be expressed
MMD(H, |f ((())d(x)) f ((x) du(z))
(16)
E [Kx,, x')] 2E (xx,
Ex, x')),
(17)
where ((x) k(x,,) is the feature map. Now, consider the empirical distributions
2m
n
w urjdoy
(18)
n
where By (Zi 8i) is concatenation of the feature and label. Substituting these into Eq.
we obtain
MMD(" " ,D2 Σ
w,W.kkK,,,
w
kl 2b )
1
Σ k(rr,,
(19)
n²
=='=1
=1
2
1 n²
=w K"" TT w
1
K
ST
+
K
581
(20)
n
w
KTT w
2
1
T
K
ST
+ const.,
(21)
5

---

Published in Transactions on Machine Learning Research (10/2025)
where KTT 2m222 K R 2mxn and K E R are the kernel matrices with K = kfz.. KST 33' = k(z,,,z)) and KSS- k( dgy)
These matrices are positive semi-definite, and MMD is convex w. Thus, the optimization problem to minimize MMD reduces to the following convex quadratic program:
"ز
2 1
TT
ST w;
min WERaa
w
w
n2
2m
(22)
s.t.
Σ 2 =
0 w S 11..,2...,,2
This problem be solved with the Frank-Woor Wolfe algorithm. We initialize then iteratively update w by the Frank- Wolfe algorithm with step size र+z for t = 0, ,, L 1. As the objective function is convex quadratic, we obtain the following guarantce.
which is feasible. We
2 for t = 0, 1, o,.,,.., L 1, Proposition 3.1. When we the Frank- Wolfe algorithm with the step size 142 obtoin vú such that
MMD(μT 2h us) S OPTenttnuous C1,-1/2
(23)
for some constant C' E RR4.
Proof- Since the objective function is quadratic, it is 8-smooth. The Frank- Wolfe algorithm with step size 2
t+2 achieves a convergence rate of O(L-1) 22]. Given that the objective function is the squared MMD, the error in MMD is on the order of (T.-1/2)
As discussed Section 3.2 we then round the solution by selecting items with probability Kwy. To analyze this step, we make the following mild assumption.
Assumption 3.2 (Bounded Kernel). The kernel is bounded by in the sense that k(x, (6(x),((z); [0xx) B for all E
This assumption mild and holds for many kernels such as the Gaussian, Laplacian, and Matérn kernels. We have the following guarantee for the random selection step.
Proposition 3.3. Let w, = k with I ~ Bernoulli K ())). Then,
2m
2m
B ÖK
Σ
7 - Σ w xxx,)) j=1
S
(24)
with probability at least 6.
This can be bounded by B by similar argument to Eq. 14 Then we obtain the desired result by Markov's inequality. The full proof is provided
Proof Sketch. We evaluate E, [ ú, u +
#1
in Appendix
We then analyze the postprocessing step. We have the following guarantee.
Proposition 3.4. Let vi// = 1 if the j-th item is in the final output Dr and 0 otherwise. We have
2m
2m
B
Σ t
Σ
S
(25)
JK
with probability at least 1 - 8.
Proof Skelch. This also follows from similar argument to Proposition 3.3
The proof is in Appendix
B
7

---

Published in Transactions on Machine Learning Research (10/2025)
By combining the above guarantees, we have the following guarantee for the final output.
Theorem 3.5. Under assumption 3.2. when run the Frank- Wolfe algorithm with the step size 2 for 1=0,1 0. I- and select ilems wilh the probability Kwj, oblain DD such that
B M us) OPTrombinntorial CL-11/2 +2 -2 5K
(26)
with probability at least 28.
Proof Sketch. This follows from the triangle inequality and union bound. The proof Appendix C
Corollary 3.6. Under assumplion 3.2 for any e 0 and Z4,, there exists and R such that by running the Frank- Wolfe algorithm with L iterations and repeating the rounding process R times and choose 25 the best Dj with smallest MMD(PT ps), we have
2B MMD(PT D7 us) S OPTrmbinntooiial + +2V K
t
(27)
OPT
-K122
(28)
with high probability.
2
Proof. We 402 and 8
then we have
tVR V2+ LvB
B
2B K
OPToombinatorial CI.-1/2 +2 2
OPTeombinatorial
+ +//
(29)
5K
with probability at least 0 because 8 < }.- Repeating the rounding process R 0 - 25)- times, we can obtain the final output with the desired guarantee.
Note that the rounding process can be de-randomized by dynamic programming and the conditional proba- bility method.
We can also bound OpT under the following assumption.
Assumption 3.7 (Bounded Density Ratio). The source items Ds and target candidate items Jr are sampeled from distributions P and Q, respectively, and the density ratio r* = sup, Q(a)
P(w) is bounded.
The items Ds and JT are not neccearily common (i.e., the first challenge), and the distributions are not necessarily identical. Instead, we assume that the target service has chance to provide items similar to the source items with this assumption. Without this, it would be unlikely to find relevant items in the target service, making impossible to transfer user preferences with a vanishing error. Under this assumption, we establish the following guarantee.
Thcorem 3.8. Under Assumptions 3.2 and 3.7
there erists C1, C2 R4 such that when K < C |Jrl
B
B
B
B
MMD(P, Pr) S C2
21
[2s
+
K
and OpTrmbinnatoiial I C2
1
Ds
+
K
(30)
with high probability.
Proof Sketch. Under Assumption 3.7 P < Q and Q can be written as J.- P+ )² for some distribution
Pt. We essentially have μJ samples from P the target service. We bound the convergence rate of the empirical measure to the true measure by standard argument of MMD. The proof is in Appendix [
By combining the above guarantees, we have the following guarantee for the final output.

---

Published in Transactions on Machine Learning Research (10/2025)
Corollary 3.9. Under the assumptions of Corollary 3.6 and Theorem 3.8
can obtain Dr such that
MMD(UTT Pi us) ,us) - O(DDs K-
(31)
with high probubility.
Therefore, if we prepare sufficient number of souree items, the target service provides sufficiently rich set of items, and we click sufficiently many items, we can transfer the preference to the target service with a vanishing error in the order of O [D/2 + K-1/2).
With the same argument as Section 3.1 we can bound the error on the source items.
Corollary 3.10. If the target service uses an unknown model fr(:;) and unknown loss function Er(:,) to Irain the model, and the RKHS norm of loss (r(r((r;)) v) is bounded by Re, then the trained model incurs the Error
Epl(r(fr(x:0)),)) -
Σ
(T(r((z0)) Rs MMD(P, Dr).
(32)
DD
(x.w))Dr
Under the assumptions of Theorem 3.8
we have
(p(er(fr((x;)) S
Σ (a.y)EDr
()( + -1/2 K-1/22)
(33)
Dr
This corollary shows that the target service trains the model sufficiently well so that the training error Drl (( (r(fr (x; 0),8) y) is small and if we prepare a sufficient number of source items and click suffi- ciently many items following PRETENDER, we can make the right hand side of Eq. 33 arbit small and we can ensure that the trained model incurs a small error on the source items, meaning that it effectively captures the users preferences from the source service.
3.4 Pretender for the Wasserstein Distance
We now consider the case where we quantify the discrepancy between the distributions with the 1- Wassersttin distance. Consider the empirical distributions po and μs defined in Eq. 18 The 1-Wasserstein distance is
Wi inf Σ
Eirll x'ylll
(34)
7EII(H" w)) 35"
where
I1p v) = {or
R
2mxn 20
T T 1- y
w. w.
(35)
is the set of coupling matrices. The I-Wasserstein distance also admits the following dual formulation:
2m
w - 1 I
Wi( sup JEFLiP j=1
Σ
(36)
where Frip the set of 1-Lipschitz functions. We solve the following convex optimization problem:
min W
W1 W1 vv),
2m
(37)
s.t.
Σ w = 1,
0 S w < K (j = 11,,,...,,2m
j=1
8

---

Published in Transactions on Machine Learning Research (10/2025)
By substituting the primal formulation (Eq.
34
and the definition of I1""", ; v), we have
min Ens WER 7ER2m
[|,, E'yell
3.
s.b. w T = 1,
71 ww
11 1
(38)
n
1 K 11=1.2..... 2m)) Yo8 2 2 1,2......... 2m, 11,
0 w S
This problem is linear program with optimization variables and 7. We solve this problem by linear program solver in a polynomial time. Let v be the solution of this problem. We then select items with the probability Kú and analyze the rounding process. To analyze this step, we make the following mild assumption.
Assumption 3.11 (Compact Domain). Each element 2j lies the unit cube [0, 1] and the cost function || x''l is the Euclidean distance.
If the data are not originally in the unit cube, they can be standardized to satisfy this assumption. To bound the Wasscrstein distance, we need the following lemma, which is shown in Appondix E
Lemma 3.12. Let FLsp be the set of 1-Lipschitz functions with f()) 0. FLip can be Loveeeeeeed by Fe, i..,, for any E FLip, there erists f E Fe such that |If - flx S e, with If(x)) S [ S exp log(3) 2vd
v 2, vs E Fe and
We first analyze the postprocessing step. We have the following guarantee. Proposition 3.13. Let v Ω the j-th item is in the final oulput Dy and 0 otherwise. For any 0,
2m
d
log + vd log
sup Σ ((a))(1)) w)y) S V 2K 8 JEF, 1=1
(39)
3K
8
with probability al least 1- 6. 6.
Proof Sketch. The proof is similar to Proposition 3.4 and we obtain the bound with Bernstein's inequality. The full proof in Appendix F
We then analyze the random selection step. We first bound each test function.
Lemma 3.14. Let ú, = K with I, ~ Bernoulli( Kwt;). Then, for any f with If(x)) s 2
va
Σ f(z))(10,- - -0²)) s V 2K 8 + vd
2m
/ log
log
(40)
3K
with probability at least 1 - 6.
Proof Sketch. We bound the variance of independent random variables f(z;)(10 ()y) (i = 1,2, 2m))
and apply Bernstein's inequality. The full proof is in Appendix C
By combining Proposition 3.13 Lemma 3.14 and Lemma 3.12 we have the following guarantce.
Theorem 3.15. For any 8 0, the 1- Wasserstein distance between the final output Dr and the source distribution is
1 Vd
WT ps) < OPTrmmiinatorial +3/ K 5
log + log + +8VdK aia + 11VdK d + +6 g
d d
K ata
K
(41)
OPTromiinaterial + +0 00kK (Katt)
(42)
with probability at least 1 28.

---

Published in Transactions on Machine Learning Research (10/2025)
Proof Sketch. We set E = vd (2 d-2
a+ logo+a (3)K aia + / R log log in Lemma 3.12 We bound [F set
8
Fe in Proposition 3.14 and apply the union bound. We then apply Proposition 3. 13 Lemma
3.14
Lemma 3.12 and the -chrroiich-ubbisteenn duality to obtain the desired result. The full proof is in
Appendix
We can also bound the error of the trained model on the source items by the same argument as in Theorem 3.8 and Corollary 3.10 The difference is that the sample complexity of the Wasserstein distance is ( 12 instead of ((+) of the MMD. This is a fundamental property of the Wasserstein distance. Consequently, the optimal value OPT and the loss bound scale as ( in the case of the Wasserstein distance,
compared to (+)) for the MMD. This difference implies that the error bound can be significantly larger
when the data dimension d is high, making the Wasserstein distance less practical for high-dimensional settings.
4 Discussions
4.1 Discussion on Variants
We have presented the variants for MMD and the Wasserstein distance. Each has its own advantages and disadvantages. The primary advantage of MMD is its sample complexity. MMD is not affected by the number of dimensions of the feature space and sidesteps the curse of dimensionality while the Wasserstein distance suffers from it [2] The advantage of the Wasserstein distance is its generality. The assumption that the loss function (fr((x;; 0). v) is Lipschitz continuous is very mild and holds in many settings, such logistic regression, matrix factorization, and neural networks. MMD requires the loss is in the RKHS, which may not hold in practice.
We also note that our analysis can be extended to other metrics as long as the continuous optimization problem (Eq. 7 is tractable and the covering number of the test function class F bounded by the same argument of Section 3.4 For example, our analysis can be applied to the discrepancy distance 30,, yielding sharp generalization bound when the model is linear and the loss is the squared loss. Practitioners choose metrics that best suits their specific application.
4.2 Optimum Value Not Monotone
It should be noted that the optimum value of the combinatorial problem not monotonic in K. Proposition 4.1. OPTrmmiinatoria is not monotonic in K.
Proof. We prove the proposition by counterexampl. Let Is = (1},77 = [1,2),z; = 0, = and D5 = {(1, 1)}. When K = 1, the optimum value is 0 by selecting Dr = {(1, 1)}. When K = 2, the optimum value is non-zero because we noed to select items other than (1, and D3 + Dr.
One might intuitively expect that increasing K would lead to better at least worse solution. However, the above proposition shows that this is not always the case. In many practical situations, the goal is not to click exactly items, but rather to minimize the number of interactions while effectively transferring preferences. To address this issue, we can parallelly run the algorithm with K' 1,2,.... ....... K and select the best solution with smallest D(ur.us) among them.
4.3 Limitation: Inconsistent Features
We have assumed that we have access to the features æ; of the items in the problem setting, In practice, rich feature representations may not always be available, or the target service may utilize a different feature space than what we expect for training its recommendation model. This issuc is particularly relevant when the target service employs collaborative filtering, widely used approach in recommender systems. In such cases, the service may use explicit features such text, tags, visual information, but use collaborative
10

---

Published in Transactions on Machine Learning Research (10/2025)
features, which are not available to end users. In such case, our approach and analysis cannot be directly applied. Nevertheless, we argue that our approach remains valuable even in such scenarios. First, explicit features often serve as good surrogates for implicit features. For example, movies with similar descriptions tend to attract similar audiences. Second, recent studies have demonstrated that even end users can estimate implicit features from recommendation networks approach. Extending our analysis to cases where feature spaces are inconsistent an important direction for future work.
E5 These estimated features can then be fed inlo our
5 Related Work
5.1 Cold Start Problem
The cold start problem is a fundamental problem in recommender systems. It arises when a new user (or a new item) enters the system, and the system lacks sufficient information to provide accurate recommendations. all of them
Although many methods have been proposed to address the cold start problem 14 require the service providers to implement the method. In contrast, our approach is unique in that it can be applied directly by end user without requiring any modifications to the service itself. This charactoristic broadens the applicability of our method, allowing it to be used in services that lack built-in functionalities to address the cold start problem.
26 B3
55
5.2 Quadrature
Quadrature a technique to approximate the integral of function by summing the function values at a finite number of points [1 I 19 [ This essentially equivalent to finding discrete measure that approximates the given measure. Quadrature is widely used in numerical analysis and machine learning. One
500, which is a small set of training points that approximates the loss of the model on the entire training set. Our approach can be seen as a quadrature of fy dus with points Dr. The main difference is that standard quadrature methods use arbitrary points and/or weights and sidestep combinatorial problems 2 5 while our approach uses only the items in the target set, which naturally Icad to the combinatorial optimization problem. For example, quadrature methods based on the Frole algorithm
of the common applications is coresets G 23
33
5S outpul sparse weights, but they may choose the same items repeatedly in general, and the resulting weights are not uniform. Such output cannot be applied to our setting because users cannot thumbs up the same item multiple times in most services. Some approaches [3] 23 such as Kernel thinning [3 output a subset of the input points with uniform weights, which is similar to our approach. However, these hethods assume that the candidate points are sampled according to the distribution being approximated. If this assumption docs not hold, as in our caso, these mothods cannot be directly applicd. Our proposed method can be used even when the input points are arbitrary. Other methods |66 57 employ submodular optimization and greedy algorithms, achieving a (1 1 aaapprooimationn ratio. However, the gap of 2) does not vanish as the number of items increases. By contrast, our approach can achieve the vanishing error as Corollary 3.10 shows thanks to the continuous optimization approach and the careful rounding process. To the best of our knowledge, our work is the first to provide theoretical guarantee for such a general and combinatorial setting. We believe that this result is of independent interest.
5.3 User-side Realization
User-side realization refers the concept in which end users implement desired functionalities on their own without requiring modifications to the service itself. Many users experience dissatisfaction with services. Even if they want some functionalities and request them to the service provider, the provider may not implement them due to various reasons such as cost, complexity, and simple negligence. After all, service providers are not volunteers but businesses. In such cases, the only options users have are not satisfactory, keep using the service despite their dissatisfaction or leave the service. User-side realization provides a proactive alternative to this dilemma. This concept has been explored in various fields such as recommender
42 44, and privacy 46. The main advantage of the user-side realization is that it can be used in services that do not have special functionalities to address the problem,
systems 3 45 Arl search engines [1] 36 40
11

---

Published in Transactions on Machine Learning Research (10/2025)
0.8
Continuous Solution
Continuous Solution
Final Output
Final Output
0.6
MMD
MMD
0.4
0.4
0.2
0.2
0.0
0.0
0
20
40
80
100
120
20
40
60
80
100
120
K
K
(a) User 308 (10 thumb ups and thumb downs)
(b) User 21 (74 thumb ups and thumb downs)
Figure 1: MMD as a function of the number of selected items K. The optimal value of the combinatorial optimization problem is intractable but is guaranteed to lie somewhere between the red and blue lines. We can see that the difference between the proposed method and the optimal value decrcases as K increascs. As we discussed in Section 4.2 the optimal value is not monotonic in K, and the sweet spots lie around 32 to 64 in both cases. We can also see that the optimal values get worse more quickly in (a) because the source data contain fewer items, the relevant items in the target set are exhausted more quickly, and are forced to select less relevant items when increase K.
and it broadens the scope of the applicability of the solution. For more comprehensive discussion user- side realization, refer the reader to the Ph.D. thesis by 48. Our approach constitules novel application of sier-side realization to the cold start problem in recommender systems.
6
Experiments
6.1 Convergence Analysis
We first confirm that the regret of PRETENDER converges to zero as the number K of selected items increases.
Experimental Setting. We use the MovieLens 100K dataset 1ir We consider rating 2 4 positive feedback (i.c., thumbs up) and rating < 4 negative feodback (i.c., thumbs down). We create two virtual services S and T. We include each movie in S with probability 0.5. We carry out the same process independently to create T. As a result, these services share about half of the movies. We use genres (e.g.. Action, Adventure, Animation) and the release year as the features the movics. They are encoded as a g0-dimensional multi-hot vector. We concatenate Cy E C) to the feature vector define the discrete dist distribution, where y E {0, 1} indicates thumbs up or thumbs down, and C= 10 the hyperparameter that controls the emphasis on the label when we measure the distance between two data points. We focus on user 308, who is the first user who has 10 thumbs up and 10 thumbs down, and user 21, who is the first user who has more than 100 ratings. For each user u, aim to transfer the preference D, DDs by choosing K items from Dr. We use MMD with the Gaussian kernel and bandwidth a = 1 as the distance measure. We use L = 1000 iterations of the Frank- Wolfe algorithm and R = 100 trials of the rounding process. We set K = 1,2,4,8,
128 to see the convergence behavior.
The goal of the experiment is to confirm that the regret of the proposed algorithm, i.c., the MMD of the proposed method minus the MMD of the optimal solution, converges to zero the number of selected items K increases. However, computing the true optimal solution is intractable due to the combinatorial nature of the optimization problem. Instead, we use the optimal value of the continuous relaxation as benchmark, which serves as a provable lower bound for the optimal value of the combinatorial optimization problem.
Results. Figure| [ shows the regret of PRETENDER as a function of the number of selected items K. The optimal value of the combinatorial optimization problem intractable but guarantced to lie somewhere between the red and blue lines. We observe that the difference between the proposed method and the optimal value decreases K increases. As discussed in Section 4.2 the optimal value is not monotonic in K, and
12

---

Published in Transactions on Machine Learning Research (10/2025)
Table 1. Performance Comparison. Each value represents the average MMD across all users. Lower is better. The standard deviation computed across users. The proposed method is much better than the bascline methods and is close the optimal continuous solution.
MovieLens with intersection
MovieLens no intersection
Last.fm no intersection
Amazon no intersection
Random
0.2537 + 0.075
0.2672 + 0.085
0.3394 + 0.059
0. + 0.023
Greedy
0.2978 0.074
0.3401 = 0.086
0.3555 + 0.098
0.3043 = 0.069
Pretender
0.1033 0.040
0.1250 + 0.045
0.0927 + 0.026
0.0774 + 0.010
Continuous
0.0876 + 0.049
0.1113 = 0.053
0.0872 = 0.026
0.0707 = 0.011
(unfcasible)
Our proposed method, Pretender, performs much better than baselines.
Pretender gets close to the (unfeasible) lower bounds. They provide provable certificates of Pretender's performance.
the sweet spots lie around 32 to 64 in both cases. We can also see that the optimal values get worse more quickly in (a) because the source preferences contain fewer items, and the relevant items in the target set are exhausted more quickly. Consequently, when K increases, the algorithm forced select less relevant. items in (a).
6.2 Quantitative Evaluation
Datasets. We evaluate our method using datasets from three domains: MovieLens 100k (movies), Last.fm (music) [7] and Amazon-Home--nd-Kiinn
(e-commerce) 20 82]. We use the same setting the conver- gence analysis for the MovicLens 100K dataset except that we use all users. For the Last.fm dataset, we consider musicians with positive weights as thumbs up and we sample the same number of random musi- cians for thumbs down. We use the tags (e.g,, metal, 80's, chillout) as the features of the artists. As the number of tags large, we apply the principal component analysis (PCA) to reduce the dimension to 50 and standardize the variance. For the Amazon-Homee Coemme-nd-Kittheee dataset, we consider ratings 2 as thumbs up and ratings < 4 as thumbs down. We the bag-of-words representation of the product reviews. We apply PCA to reduce the dimension to 50 and standardize the variance. We consider two different settings for delining source and targel services. The first setting, with int intersection, is identical to the one used in the convergence analysis. The second setting, no intersection, is that we split the items into source and target services without any intersection. This setting is more challenging because the methods cannot copy any source items the larget service. For Last.fm and Amazon-Home--n Kitchen datasets, we use the Gaussian kernel with the bandwidth = 10 to reflect the scale of the features. We set K 100 for all datasets.
existing methods that solve the cold start problem by an end user, use two simple baselines to validate that the proposed method is reasonably effective. The first baseline is random selection, which randomly selects K items from Dr. The second baseline is the greedy selection, which selects K items in Jr that have the smallest distance d(r, Ds) = min ||æ- to the source items Ds. Additionally, we report the performance of the optimal solution of the continuous optimization problem.
Baselines. Since there
Results. Table 1 shows MMD values between the source preference and the output of the methods. Lower is better. PRETENDER is much better than the baseline methods and is close to the optimal continnous solution. Note that checking the closeness is useful in practice well. The continuous solution is obtained as byproduct of PRETENDER. After we obtain the final output, we can verify that the final solution is indeed a reasonable one just by comparing the two values. We observe that the greedy method is worse than the random method. We hypothesize that it is because the greedy method chooses items that are too similar to some source items and the diversity lost. We also observe that PRETENDER is robust to the setting with no intersoction. The performance slightly worse than in the setting with intersection but is still reasonablly well.
13

---

Published in Transactions on Machine Learning Research (10/2025)
Table 2: Case Study. The source items the user interacted with and the K = 20 target items selected by PRETENDER. PRETENDER selects the very items that the user interacted with in the source service as shown in red. The user interacted with movies in 1996 and 1997, and PRETENDER mostly selects movies in 1996 and 1997. Notable exceptions are Alice in Wonderland (1951) and Fantasia (1940) selected by PRETENDER, as shown in blue. We hypothesize that this reflects the fact that the user thumbed down Cats Dont Dance (1997), which is an animated movie for children. Since Cats Don't Dance (1997) is not in the target service, PRETENDER selects similar movies from the target service and sends a signal that the user does not like this type of movics.
Source Thumbs Up
Source Thumbs Down
Pretender Thumbs Up
Pretender Thumbs Down
Kolya (1996)
Ulee's Gold (1997)
Shall We Dance? (1996)
Absolute Power (1997)
The English Patient (1996)
Fly Away Home (1996)
The English Patient (1996)
Breakdown (1997)
G.I. Jane (1997)
Mrs. Brown (1997)
G.I. Jane (1997)
Fly Away Home (1996)
The Edge (1997)
Lost Highway (1997)
The Edge (1997)
Lost, Highway (1997)
A Smile Like Yours (1997)
The Game (1997)
Dus Boot (1981)
Alice in Wonderland (1951)
Seven Years in Tibet (1997)
Addicted to Love (1997)
Fantasia (19-10)
Cats Don't Dauce (1997)
The Pest (1997)
The Jackal (1997)
Stag (1997)
Seven Years in Tibet (1997)
Paradise Road (1997)
'Til There Was You (1997)
Le Bonheur (1965)
All Over Me (1997)
Rough Magic (1995)
6.3 Case Study
As a case study, we use the MovieLens dataset and focus user 308, who is the first user who has 10 thumbs up and 10 thumbs down. We investigate the target items selected by PRETENDER under the same experimental setup as Section 6.1 and with K = 20. Table 2 shows the source items the user interacted with and the target items selected by PRETENDER. Overall, PRETENDER suceeds transferring the user's preferences. PRETENDER selects several items that the user previously interacted with in the source service, as highlighted in red. Note that the virtual services S and T share some items but not all items, and thus we cannot copy all items. We can also see that the user interacted with movies in 1996 and 1997, and PRETENDER mostly selects movies from the same period. This leads to similar preferences between the source and target services. Notable exceptions are Alice in Wonderland (1951) and Fantasia (1940) selected by PRETENDER, as shown in blue. We hypothesis that this reflects the fact that the user thumbed down Cats Don't Dance (1997), which is an animated movie for children. Since Cats Don't Dance (1997) is not in the target service, PRETENDER selects similar movics from the target service and sends a signal that the user does not like this type of movies to the terget service. This case study illustrates that PRETENDER effectively reflects the user's preferences.
7 Conclusion
In this paper, we made the following contributions.
We proposed a new problem sctting, solving the cold start problem on the user's side (Section 2
We proposed PRETENDER to solve the problem by formulating it as metric minimization between
distributions (Sections 3.1 3.2
We formally showed that the regret of PREDENTER converges to zero the number of selected
items increases (Sections 3.3 and 3.4
We showed that the regret converges at a rate of Of VR for the Wasserstein distance (Theorem 3.15).
for MMD (Corollary 3.6 and O(K क
We also showed that the optimal value also converges to zero as the number of source items and the number of selected items increases (Corollary 3.10
14

---

Published in Transactions on Machine Learning Research (10/2025)
We empirically validated the effectiveness of PRETENDER through experiments (Sections 6.1 6.3
We confirmed that the regret of the proposed algorithm converges to zero with a reasonable number of selected items (Section 6.1
We showed that the proposed method is much better than baseline methods and is close to the optimal contimuous solution with movie, music, and e-commerce datasets (Section 6.2)
We presented case study, illustrating that the items selected by PRETENDER effectively reflect the user's preferences (Section 6.3)
We believe that this work introduces a new research direction for addressing the cold start problem from the users' perspective. We hope that our work will inspire further research in this area.
Acknowledgements
We thank Yuki Takezawa and Satoshi Hayakawa for helpful discussions.
References
[1] F. R. Bach. On the equivalence between kernel quadrature rules and random feature expansions. J. Mach. Learn. Res., 18:21:1 21:38, 2017.
[2] F. R. Bach, S. Lucoste-Julien, and G. Obozinski. On the equivalence between herding and conditional gradient algorithms. In Proceedings of the 29th International Conference on Machine Learning, ICML, 2012.
[3] R. M. Bell and Y. Koren. Lessons from the netflix prize challenge. SIGKDD Explor., 9(2):755 79, 2007.
[4] S. Boyd, L. Xiao, and A. Mutapeic. Subgradient methods. lecture notes of EE3920, Stanford University, Autumn Quarter, 2004(01), 2003.
[5] F. Briol, C. J. Oates, M. A. Girolami, and M. A. Osborne. Frank-wolfe bayesian quadrature: Proba- bilistic integration with theoretical guarantees. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, NeurIPS, pages 1162-1170. 2015.
[6] T. Campbell and T. Broderick. Automated scalable bayesian inference via hilbert coresets. J. Mach. Learn. Res., 20:15:1-15:38, 2019.
[7] I. Cantador, P. Brusilovsky, and T. Kuffik. 2nd workshop on information heterogencity and fusion recommender systems (hetrec 2011). In Proceedings of the 5th ACM Conference on Recommender
Systems, RecSys. ACM, 2011.
[8] Y. Chen, M. Welling, and A. J. Smola. Super-samples from kernel herding. In Proceedings of the twenty-Sirth Conference on Uncertoinly in Artificial Intelligence, UAI, pages 109 116, 2010.
[9] U. Chitra and C. Musco. Analyzing the impact of filter bubbles on social network polarization. In Proceedings of the 13th ACM International Conference Web Search and Data Mining, WSDM, pages 115-123, 2020.
[10] K. Christakopoulon, F. Radlinski, and K. Hofmann. Towards conversational recommender systems. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 815 824. ACM, 2016.
[11] M. Diligenti, F. Coelzee, S. Lawrence, C. L. Giles, and M. Gori. Focused crawling using context graphs. In Proceedings of 26th International Conference on Very Large Data Bases, VLDB, pages 527-534, 2000.
[12] R. M. Dudley. The speed of mean cabrenko-cantelll convergence. The Annals of Mathematical Statistics, 40(1):40-50, 1969.
[13] R. Dwivedi and L. Mackey. Kernel thinning. J. Mach. Learn. Res., 25:152:1-152:77, 2024.
[14] Z. Gantner, L. Drumond, C. Freudenthaler, S. Rendle, and L. Schmidt-Thieme Learning attribute- to-feature mappings for cold-start recommendations. In Proceedings of the 10th IEEE International Conference on Data Mining, TCDM, pages 176-185, 2010.
15

---

Published in Transactions on Machine Learning Research (10/2025)
[15] C. A. Gomez- Uribe and N. Hunt. The netflix recommender system: Algorithms, business value, and innovation. ACM Trans. Manag. Inf. Syst., 6(4):13:1 2016.
[6]] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. J. Smola. A kernel two-sample test.
J. Mach. Learn. Res., 13:723 773, 2012.
[17] F. M. Harper and J. A. Konstan The movielens datasets: History and context. ACM Trans. Interacl.
Intell. Syst., 5(4):19:1-194) 19:19, 2016.
[18] N. Harvey and S. Samadi. Near-optimal herding. In Proceedings of The 27th Conference on Learning Theory, COLT, pages 1163-1182, 2014.
[19] S. Hayakawa, H. Oberhauser, and T. Lyons. Positively weighted kernel quadrature via subsampling.
In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS, 2022.
[20] R. He and J. McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In Proceedings of the 25th International Conference on World Wide Web, WWW, pages 507-517. ACM, 2016.
[2] F. Huszar and D. Duvenaud. pptimally-weighteer herding is bayesian quadrature. In Proceedings of the 28th Conference on Uncertainly in Artificial Intelligence, UAI, pages 377-386 2012.
[22] M. Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, ICML, volune 28, pages 427 435, 2013.
[23] Z. S. Karnin and E. Liberty. Discrepancy, coresets, and sketches in machine learning. In Proceedings of the 32nd Conference Learning Theory, COLT, volume 99, pages 1975 1993, 2019.
[24] X. N. Lam, T. Vu, T. D. Le, and A. D. Duong. Addressing cold-start problem in recommendation systems. In Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication, ICUIMC, pages 208 211, 2008
[25] H. Lee, J. Im, S. Jang, H. Cho, and S. Chung. Melu: Meta-learned user preference estimator for cold-start recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 1073 ACM, 2019.
[26] B. Lika, K. Kolomvatsos, and S. Hadjjefthymiades. Facing the cold start problem in recommender systems. Expert Syst. Appl., 41(4):2065 2073, 2014.
[27] J. Lin, K. Sugiyama, M. Kan, and T. Chua. Addressing cold-start in app recommendation: latent user models constructed from twitter followers. In The 36th International ACM SIGIR conference research and development in Information Retrieval, SIGIR, pages 283-292, 2013.
[28] G. Linden, B. Smith, and J. York. Amazon.com recommendations: Item-to-item collaborative filtering. IEEE Internel. Comput., 7(1):76-8)) 80, 2003.
[29] Y. Lu, Y. Fang, and C. Shi. Meta-learning on heterogeneous information networks for cold-start recom- mendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 1563-1573. ACM, 2020.
[30] Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Proceedings of the 22nd Conference on Learning Theory, COLT, 2009.
[31] J. J. McAuley and J. Leskovec. Hidden factors and hidden topics: understanding rating dimensions with review text. In Proceedings of the 7th ACM Conference on Recommender Systems, RecSys, pages 165 172, 2013.
[32] J. J. McAuley, C. Targett, Q Shi, and A. van den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR, pages 43-52. ACM, 2015.
[33] B. Mirzasolciman, J. A. Bilmes, and J. Leskovee. Corcsets for data-cfficient training of machine learning models. In Proceedings of the 37th International Conference on Machine Learning, ICML, volume 119, pages 6950 00-06960000 2020.
16

---

Published in Transactions on Machine Learning Research (10/2025)
[34] R. J. Mooney and L. Roy. Content-based book recommending using learning for text categorization. In Proceedings of the 5th ACM Conference on Digilal Libraries, DL, pages 205-204. ACM, 2000.
[35] A. Müller. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29(2):429 443, 1997.
[36] R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders,
X. Jiang K. Cobbe, T. Eloundou, G. Krueger, K. Button, M. Knight, B. Chess, and J. Schulman. Webgpt: Browser-assisted question-answering with human feedback. arXiv, 2021. URL https://
arxiv. Dwrri.org/abs/2122.083
[37] S. Park and W. Chu. Pairwise preference regression for cold-start recommendation. In Proceedings of the 3rd ACM Conference Recommender Systems, RecSys, pages 21-28, ACM, 2009.
(38) S. Park, D. M. Pennock, O. Madani, N. Good, and D. DeCoste. Naïve filterbots for robust cold-start recommendations. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pages 699-705, 2006.
[39] G. Peyré, M. Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trendst in Machine Learning, 11(5-6):355 607, 2019.
[40] F. Radlinski and S. T. Dumais. Improving personalized web search using result diversification. In Proceedings of the 29th Annual International ACM SIGIR Conference on Reseorch and Development in Information Retrieval, SIGIR, pages 691 692, 2006.
[41] C. E. Rasmussen and Z. Ghahramani. Bayesian monte carlo. In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NewrIPS, pages 489-496, 2002.
[42] R. Sato. CLEAR: A fully user-side image search system. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, CIKM, pages 4970-4974 2022.
[43] R. Sato. Private recommender systems: How can users build their own fair recommender systems without log data? In Proceedings of the 2022 SIAM International Conference on Data Mining, SDM, pages 549-557. SIAM, 2022.
[44] R. Sato. Retrieving black-box optimal images from external databases. In Proceedings of the 15th ACM International Conference on Web Search and Data Mining, WSDM, pages 879-887, 2022.
[45] R. Sato. Towards principled user-side recommender systems. In Proceedings of the 31st ACM Interna- tional Conference on Information & Knowledge Management, CIKM, pages 1757-1766, 2022.
[46] R. Sato. Making translators privacy-aware on the user's side. Trans. Mach. Learn. Res., 2024, 2024.
[47] R. Sato. Overhead-free user-side recommender systems. arzin, abs/2411.07552 2024. URL https:
//arxiv. /arriv.org//bb///11107755
[48]
R. Sato. Uscr-side rcalization. Doctoral Thesis, 2024. URL hutpsss/aarriiv..rg/abb/////
[49] A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock. Methods and metrics for cold-start
recommendations. In Proceedings of the 25th Annual International A CM SIGIR Conference on Research and Development in Information Retrieval, SIGIR, pages 253 260, 2002.
[0]] O. Sencr and S. Savaresc. Active learning for convolutional neural networks: A core-sct approach. In Proceedings of the 6th International Conference on Learning Representations, ICLR, 2018.
[51] B. K. Sriperumbudur, A. Gretton, K. Fukumiizu, G. R. G. Lanckriet, and B. Schölkopf. A note integral probability metrics and d-divergences. arXiv, abs/0901 2698, 2009. URL http://aaxxiv.rr
aba/0901.288
[2] H. Steck. Calibrated recommendations. In Proceedings of the 12th ACM Conference on Recommender Systems, RecSys, pages 154-162. ACM, 2018.
[33 M. Vartak, A. Thiagarajan, C. Miranda, J. Bratman, and H. Larochelle. A meta-learning perspective on cold-start recommendations for items. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, NewrIPS, pages 6904-6914, 2017.
[54] C. Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
17

---

Published in Transactions on Machine Learning Research (10/2025)
[55] Q. Wang, H. Yin, H. Wang. Q. V. H. Nguyen, Z. Huang, and L. Cui. Enhancing collaborative filtering with generative augmentation. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD, pages 548 556. ACM, 2019.
[6] K. Wei, Y. Liu, K. Kirchhoff, and A. Bilmes. Using document summarization techniques for speech data subset selection. In Proceedings of the 2013 Conference of the North American Chapter of the As- sociation for Computational Linguisties: Human Language Technologies, NAACI.HHIT, pages 721-726, 2013.
[7]] K. Wei, R. K. Iyer, and J. A. Bilmes. Submodularity in data subset selection and active learning. In Proceedings of the 32nd International Conference Machine Learning, ICML, volume 37, pages 1954 1963, 2015.
[58] M. Welling. Herding dynamical weights to learn. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML, volume 382, pages 1121-1128, 2009.
[59] J. Weng, E. Lim, J. Jiang, and Q. He. Twitterrank: finding topic-sensitive influential twitterers. Proceedings of the 3rd International Conference on Web Search and Web Data Mining, WSDM, pages 261 270, 2010.
[60] W. X. Zhao, S. Li, He, E. Y. Chang, J. Wen, and X. Li. Connecting social media to e-commerce: Cold-start product recommendation using microblogging information. IEEE Trans. Knowl, Data Eng., 2814):1147-115, 2016.
[61] K. Zhou, S. Yang, and H. Zha. Functional matrix factorizations for cold-start recommendation. In Pro- ceeding of the 94th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR, pages 315 324. ACM, 2011.
A Proof of Proposition 3.3
Proposition A.1. Let úH : with I3 (ernoull((Kūū,)) Then,
2m
2m
B
Σ
w (x²z) - Σ ((1
S
(43)
OK
j=1
7
with probability at least - 6.
Proof.
E
Σ (1 - 20, ((T))
(44)
E, |ú0 in 1 (0(1))))))))))))))))))))())))( ((zr)))
>
E, t0 (( + Σ
E, ( ((.))
(45)
3.
3.'
3.
(a)
Ey
1 1p'
((z))) - 2
>
E
K in (6(1)). +
1
By u0 (((3))
(46)
K K
3.
3.3"
3.3
(b)
Ko11,1, o(x)))
Σ
Σ
(47)
K
3.
j.j
((1]))))0())) -2 Σ
i (
Σ
u ( ,(z,))
(48)
K2
Σ
Σ
i u. ((z)))
(49)
K
33
3
18

---

Published in Transactions on Machine Learning Research (10/2025)
(( + E1l1) - (
1
Σ
(50)
K
K2
35
(4)
[B[[)EE[[[Ko0000).0.0000 Σ
(51)
2
K²
j+1
i
(0)
1
Σ (,,
Σ
(52)
K
Σ
Σ [0)3(((z)))00z;))
(53)
K2
(
1
Σ (
(54)
K
Σ
/6 10(((1, 11 Σ E0)llo(a))11
(55)
K
8
$
Σ
20 0)11((z))1
(56)
00
B
Σ
(57)
K
① B
(58)
K
where (a) follows from the definition of w. (b) follows from the fact that * and v are deterministic, (c)
follows from [4] Kw,, (d) follows from the fact that 13 = 1y and that 1n and 1y are independent, (e)
follows from [r K Kdj, (I) follows from Er[[y] K ub (g) follows from ( 2 O, (h) follows
from Assumption 3.2 i.e., [1,( S B, and (i) follows from Σ, B, 1. From Markov's inequality, we
have
2m
2m
B
P Σ
Σ w p(zz)
2 V
S 6.
(59)
ÖK
==1
B Proof of Proposition 3.4
Proposition B.I. Let v = R is the j-th item is in the final output Dr and O otherwise. We have
2m
2m
B 5K
Σ
Σ +
S SV
(60)
==1
with probability at least 1 - 8.
Proof.
2m
2m
Σ e ((,))
Σ
u م (fx,))
= Σ
100/ r0,) o(13))
(61)
74
(4) 2m
S
Σ
( w ,(
(62)
19

---

Published in Transactions on Machine Learning Research (10/2025)
2m
Σ ]=1
(63)
(b)
2m
B
00
(64)
2m
VB B
[ is in the final output]
1
(65)
K
K
j=1
VB 2m
[ is in the final output] - 1pl
(66)
K
==1
B K
K ΣΤ
(67)
where (a) follows from the triangle inequality, (b) follows from Assumption 3.2 and (c) follows from the fact that the elements of w and differ only when the corresponding items are included or removed in the postprocessing step, and the items included or removed until the number of selected items is exactly
K. From Eq. 13 E, Σ
K, and from Eq. 14 Vary
Σ 2m
S K. By Chebyshev's inequality to
the right. hand side of Fq. 67
we have
2m
2m
B
Σ
Σ
2
S 6.
(68)
5K
1=1
1=1
C Proof of Theorem 3.5
Theorem C.1. Under assumption 3.2. when we run the Frank- Wolfe algorithm with the step size 0, 1=0,1,
t42 for
2
1-0,,...,11
L 1 and select items with the probability Kw;, we oblain Dr such that
B
MMD(ET" Pr us) OPTrombinatoria CCL-1/2 +2 8K
(69)
with probability at least -
Proof.
Dr (us) ,us) MMD(EE"
(70)
2m
Σ (),)(1z)) - 6(0) o(0) dus(z) 1=1
(71)
H
2m
2m
2m
2m
Σ ,0,(( / ((x) dus(x)
2m
Σ e (Zzz)
Σ
2 (z,)
Σ
v. p(z,)
+
jml
#
1
1
(72)
2m
2m
2m
2m
1. p(zz)
+
Σ
e (2z)
+ MMD( (AMD((Fspps)
(73)
1=1
i=1
H
j=1
1=1
11
2m
2m Σ
2m
2m
w ((.))
+
Σ w w ((zz))
Σ
i
2.,0(0 (xx))
+ OPTroominazooiall -1/2
(74)
j=1
j=1
7
20

---

Published in Transactions on Machine Learning Research (10/2025)
10
B
B OK
OPPooombinatoiiall C/2
(75)
6K
B OPTcombinatorial + CL- + 2/ 6K'
(76)
where (a) follows from the triangle inequality, (b) follows from Proposition 3.1 (c) follows from Propositions
3.3 and 3.4 and the union bound with probability at least
26.
Proof of Theorem 3.8
Theorem D.1. Under Assumplions
3.2 and 3.7
there erisls C₁ C2 R,, such that when S
Ci
p"
B
B K
MMD(P, pP) S2
21
+
and OPT CO₂
+
(77)
Ds
K
D2
with high probability.
Proof. Under Assumption 3.7
1 P Q and Q can be written as (1- --) for some distribution
Qcan
Q'. Let Z with probability 1 and Z4 0 with probability 1 7,, and let sample X, from P if X with Jr- Let J1 (X Z. 1}. E [1i] = |لب| and | 2 Cildrl for some constant C₁ with high probability by
Z: =1 and Q' if Z, = for = -.r...,/rrl X; follows distribution Q. We identity
Markov's inequality. We assume this holds in the following. Suppose that K S Ci 7 then K S [Jil- Let J2 be the first K samples from J1. Elements in J2 are independent and follow the distribution P. As the empirical distribution converges to the true distribution with rate O(V B in MMD [6] we have
B
MMD(P, S C2
and
(78)
B
MMD(P,Ds) S Cay/ [Ds]'
(79)
for some constant C2 with high probability. By the triangle inequality, we have
MMD(J2, Ds) s MMD(P, + MMD(P, Ds)
(80)
(v
B
B K
C2
(81)
Dss
As J2 C JT and |J2] = K, J2 is a feasible solution of the combinatorial problem, and the optimal Df C JT has no worse MMD than J2, and we have the desired guarantee.
E Proof of Lemma 3.12
Lemma E. Let. Flip be the set of 1-Lipschitz functions with f(}) = FLóp can be -ooeeree by Fcr i.e., for any f FLip, there exists f F. such that |l flloo S e, with If(x)) s La E Fs and Je. < exp log(3) (2va) d)
(2va)")
Proof. We devide the domain [0, 11dt into [ hypercubes with diameter most s. For each hypercube C and f Flip, let fe max.ce f(z) min f(a) and fo be its nearest point in {KE k E Σ}. We then define f(x) fe for x C. We have If(x) f(x)) < æ since the diameter of is most E and f 1-Lipschitz. We count the number of possible f. For the hypercube Ceenter with Coenter, Scana since s()) 0.
2
21

---

Published in Transactions on Machine Learning Research (10/2025)
Given the value of fc: possible values of an adjacent hypercube C' are fc- fe, fc te. We reach all the hypercubes by repeating this process. Therefore, the possible values of are at most 30-1, where [
is the number of hypercubes. When Ld 2 1, we have X < ydd +1 2vd and | S exp logg(3) (2/d d)
When vd 1, we have [F] = in which case the lemma holds trivially.
F Proof of Proposition 3.13
Proposition F.1. Let w/j ke if the j-th item is in the final output Dr and 0 otherwise. For any 0,
d
1
vd
1
sup FEF,
(az w,,) s
2K
log
8
3K
log
6
(82)
with probability at least - 6.
Proof.
2m sup i w5 (.,)) $ 1I feFx j=1
2m
w
(83)
j=1
(84)
2
j=1
Vd 2m
1
[ is in the final output]
(85)
2
K
K
j=1
Vd
2m
Σ
[[]
in the final output] T51
(86)
2K
Vd
2m
K
Σ1
(87)
2K
==1
I are independent Bernoulli random variables with [Ty] S 1, and from Eq.
13 E,
Σ "m Ij
K, and from
Eq.
14
Vary
Σjm
< K. By Bernstein's inequality, we have
2 log
P
K
I
2K 2K log
3 S
(88)
By combining with Eq.
87 we have the desired guarantee.
G Proof of Proposition 3.14
Lemma G.1. Let w6 R
1g
with 1 ~ Bernoulliç Kto;).
Then, for any f with [f()) va
2m
Σ
[a,)) - wt,)) 5 V
2k log
log
(89)
3K
with probability at least 1 8.
22

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. Since S ,, w 1o have 1(0, (z))[(z)) /d 2k
Here, (w, (x)){(zz)
independent
random variables with mean Ey(( (x)))((s;}) and variance
f(xz)2
Varr f(zz) K ú0 KwØ,
- [(o
[
(xx 2 Varr
K²
K²
(90)
The sum of the variances is
f1,) 2 K ú KwØ,)
1
Σ (3x ( KwØ
(91)
K2
K
2m
Σ
أر (1 - KTo;)
(92)
4K j=1
(b)
d
2m
w
(93)
4K
j=1
(c)
(94)
4K
where (a) follows from f(z)) v vi 20 (b) follows from the fact that 1 2 KrØ, and (c) follows from Σ3 10 =
By Bernstein's incquality, we have
d
vd
P
2 [6 - 0,)f((z))
2
log
log 3
8. 8.
(95)
2K
8
3K
H Proof of Theorem 3.15
Theorem H.1. For any > O, the 1- I-Wasserstein distance between the final output Dr and the source
distribution
d 1 à W1 Dr .ps) & OPTcombinatorial + log + log + +VVKK a 11Vdk 2 + +69 dlog 1 g 242
Vd 1
(96)
with probability at least 25.
Proof. We use
Vd 2 2 log
+
log
1
(97)
21 K
in the following. Then,
4K
d+2
d42
4kd
(2
log 1og=+>33)K~* オ
(98)
dd log(3)
(99)
and thus
d
2vd
4K
log(3) <
(100)
d
23

---

Published in Transactions on Machine Learning Research (10/2025)
In addition,
2
4K
1
1 8
2²
4K
log
(101)
2
log 6"
(102)
By combining Eq. 99 and Eq.
102
we have
2vd
1 8K
log(3) + log
ea.
(103)
E
8
d
By Lemma 3.12
[Fll < exp 1og(3)
2v =
)))
We have
F
log
(log
[Fel + log
8)
(104)
2K
6
2K
d
2vd
log(3)
+ log
(105)
2K
8
(a)
d
8K
2
(106)
2K
4s²
(107)
where (a) follows from Eq.
103
In addition, we have
dd
F
vd
log
(log [Fll log })
(108)
3K
3K
d
Vd
22d
log(3)
+ log
(109)
3K
8
Vd
8K
2
(110)
3K
8
2
(111)
3v d
where (a) follows from Eq. 103
We set 8 + 5/1 in Proposition 3.14
and apply the union bound, then, we
have
2m (w0 (b,){(z))) <
-
log
log
(112)
2K
5
3K
1=1
(a)
8
25
2
(113)
3vd
for all f F with probability at least 1 - 8, where (a) follows from Eq. 107 and Eq.
111 In the following,
we assume that Eqs.
39
and 113 hold, which is true with probability at least 1 - 26. Then, we have
2m
2m
2m
w - w1)f(1z)))))))))))))))){)))))0 = Σ -w (z,)
+ -10
Σ
(114)
j=1
1=1
Vd
1
<
log
+
log
+
25 +
(115)
2K
8
3K
8
3vd
24

---

Published in Transactions on Machine Learning Research (10/2025)
For any f FLip, there exists E F such that Il fllo E, and we have
2m
Σ
w
(z))(zz)
(116)
2m
2m
( (xz) +
w ()){{((;))))))))))))))))))){)))) j(x,))
(117)
j=1
(a)
2m
2m
i w. (z)){(z})
+ E
| w0
(118)
j=1
1=1
(b)
w/j- 16,) (x0)) 28
(119)
j=1
Vd
8
log
log
+
2s
2
+
28
(120)
2K
8
3K
0
3vd
d
Vd
1
8
log
+
log
+ 46
(121)
2K
8
3K
3vd
(
d
log
1
vd
log
1
+
4vd
2d+z
d-2
log
442 (3)K dia +
1
1
log
1
(122)
2K
3K
8
2
K
2
8
+
3
Vd
2242
1og
गमा (3)
शेे +
2V
K
log
(123)
log 3
242
1
log
log + Avd
2
K
+
log
(124)
2K
8
3K
21
2
K
+
3
8
Vd
log 3
2/2
K पोे
+
2
1
K
1
log
2
(125)
d
Vd
1
log 1
2K
log
8
3K
log
+
4vd
2K उे.
+
2\
8
(126)
+ 3
8
Vd
d
2K
dl2
+
1
log
I
(127)
2
K
))
Vd
< 3V
log
8 +
log + svak पोड + 11V0k 2ीअ + oolloo j K utz
(128)
K
K
where (a) follows from ||ʃ - Ílloc & & and (b) follows from w E A2m-1 (c) follows from the definition of s, and (d) follows from d 2 1. From the Cantorovich-Ruuinste duality, we have
W1 Pr (T) S 3 log 8
/ d 1 Vd
+ log _ +Vvak-ala ala 11VdK dis + Bydlog 1 K j
-22-1
(129)
Note that restrected test functions to f(b) 0 but this does not affect the bound by adding bias. As ie is the optimal solution of the linear program, we have W, (10), us) = Oonooutimoou < OPToombinstorial By the triangle incquality, we have the desired guarantec.
25


Reviews:
[{"review_id": "JzhVLgsu8n", "reviewer": "Reviewer_ySxV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nS1. The paper shifts the cold start paradigm to the user side, which is novel and addresses a practical problem when service providers don't implement solutions.\n\nS2. The empirical results across 3 domains (MovieLens, Last.fm, Amazon) demonstrate that the approach works better than baselines and comes close to theoretical bounds.\n\n**Weaknesses**\n\nW1. The paper motivates the problem with examples like transferring preferences from Netflix to Hulu, but these services likely have different feature spaces and recommendation mechanisms. The assumption that minimizing distribution distance would improve recommendations across different recommendation mechanisms is not validated.\n\nW2. The scenario of service provider inaction lacks realism in certain contexts.\n\nW3. The algorithm only works under the assumption that \"source/target items may not overlap but features exist.\" There are questions about its robustness when feature spaces completely mismatch (class, type inconsistencies, etc.) or when feature quality or granularity differs across services.\n\nW4. The paper does not theoretically formalize or discuss the limitations of the proposed method when distribution shift (failure mode) occurs.\n\nW5. The paper only uses distribution distance (MMD, Wasserstein) as performance metrics – i.e., only evaluates \"whether the distribution of results I selected/clicked is close to the source.\" However, the correlation between actual recommendation quality metrics (precision@k, recall, NDCG, etc.) and distribution distance is not proven, making it unclear whether the paper's objective ('receiving good recommendations') is sufficiently guaranteed by merely reducing distance.\n\nW6. The comparison is limited to intuitive baselines like Random and Greedy, omitting comparisons with implementations similar to transfer learning, domain adaptation, or direct user data transfer.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission presents a novel approach to the cold start problem by empowering end users to transfer their preferences from one service to another without requiring any special support from service providers. The authors introduce Pretender, an algorithm that minimizes the distance between source and target distributions. Pretender provides theoretical analysis based on a new quadrature problem even when the target service's data processing is unknown. Through extensive experiments on real-world datasets, the authors demonstrate that Pretender transfers user preferences across services, outperforming baseline methods and achieving results close to the theoretical optimum.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Q1. How practically applicable is the MMD/Wasserstein-based dist. matching proposed in this paper? Especially considering scenarios where text/image/latent features are completely different. Also, I'm curious whether there are approximations or alternatives when explicit features are unavailable. I would appreciate more explanation about which implicit feedback and features the authors used in their experiments.\n\nQ2. The authors define success as \"minimizing the distance between source and target distributions,\" but this may not necessarily lead to better recommendations in practice. It could result in a perfectly distributed but irrelevant set of recommendations. Could you discuss case studies or limitations regarding such scenarios?\n\nQ3. How consistently does the correlation between actual recommendation quality (Top-N recommendation NCDG/recall, etc.) and distribution distance reduction hold, either theoretically or empirically?\n\nQ4. Can you analyze the actual gap between the continuous relaxation solution and the combinatorial solution?\n\nQ5. Could you further discuss the differences from existing domain adaptation research? Also, recommendation systems have cross-domain recommendations in addition to cold-start problems. Could you further discuss the methodological differences with these studies?", "broader_impact_concerns": "This paper does not raise significant broader impact concerns that would require a dedicated statement. While there are minor considerations around privacy, terms of service compliance, and potential digital divide implications, these are common to recommendation systems research generally.\n\nHowever, the paper's approach of transferring user preferences across services raises privacy considerations, as it involves collecting and processing personal preference data. Users implementing this method may inadvertently expose their preference profiles across platforms, potentially compromising their privacy expectations.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uooScDoMX9", "reviewer": "Reviewer_cDQs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic (solving the cold start problem by learning from the user’s data on a different service and rating items on a new service accordingly) is novel to the best of my knowledge and is certainly of potential interest. \n\nThe paper has a good balance of theory and experiment. Although I think the experiments are lacking in some ways, testing on 3 separate real-world datasets and looking both at with-overlap and no-overlap for MovieLens is a respectable scope of experimentation.\n\nIn some ways, the paper is reasonably well written, although there are far, far too many spelling mistakes and a few other sloppy errors which I will note in the ‘requested changes’ section. \n\nI have several concerns which prevent me from recommending acceptance as is, although I am open to acceptance after a significant revision.\n\nThere are various ways in which the experiments seem insufficient.\n\n1)\tI am not convinced that random and greedy selection are the only possible benchmarks. Can’t this source/target transfer problem be cast as something close to a semi-supervised learning problem (e.g. self-training or label propagation)? I believe self-training with constraints on which unlabelled points in the input space can be labelled after training  is more or less what is going on here, except that the the target service model that is trained is an unknown black box. We are taking training data from a source service, training on it, and then labelling items from the target service using what is essentially a best guess of whether the user would like the item, based on what was learned from the source training data.\n2)\tHyperparameters seem to be arbitrarily chosen in the experiments in areas where  I would have expected some tuning or discussion of how they were chosen. Section 6.1 shows sensitivity to K, sweet spots, etc, but then K is chosen to be 100 in Section 6.2 without any explanation as to how it was chosen. Kernel bandwidth (sigma=10) is also chosen nearly arbitrarily…there’s a brief mention of ‘scale of the features’ but I would have expected it to be tuned more carefully than that. \n3)\tThe discussion of the decomposition of equation 6 on page 3 argues that we don’t need to know the target service’s recommendation training model since it will just do its best to minimize training error regardless and we only need to minimize the difference between the 2 distributions. I am not totally convinced here. It seems that you could pick target items which would make minimizing the training error difficult. For instance, sequels to movies may be nearly identical in feature space but may be much less liked than the original movie. In the experiments, I would have appreciated some demonstration of robustness to (unknown, in practice) target recommendation algorithm. For instance, \"we tested the results when feeding the chosen target items to both a nearest neighbor method and a matrix factorization method\", or whatever.  Instead, as far as I can tell there is no implementation of a target recommendation algorithm at all. The results are solely evaluated in terms of MMD distance. So it doesn’t seem to be that the experiments fully simulate what would go in the real world.\n4)\tThe analysis of content of items (genre, etc) feels a little bit behind the times (bag of words, PCA). Given the dominance of LLMs and other sophisticated language techniques, I wonder if some sort of embeddings could have been used.\n\nFurthermore, while I agree that PRETENDER is potentially useful, I also see some obstacles to its adoption in the real world:\n1)\tThe authors are more-or-less asking the user to lie to the target service by rating target service items which the user may not have actually experienced, for the sake of getting good recommendations in the future. Whether or not this is done by a web agent, the user is likely to know what is going on and may object to it on a gut, emotional level. User tastes in movies, music, etc are often highly personal and tied up with a user’s core identity. Users may find it either strange or offensive to represent to the target service that she/he liked an item which has not actually been experienced.\n2)\tIf a user does implement the PRETENDER process and rate some items which the user has not actually experienced, then the target service will believe the user has e.g. watched that movie and won’t recommend that movie in the future. So in addition to the user clicking on such items, this item list should also be preserved somewhere as an additional list of recommendations (if the item was supposed to be thumbs-upped). This is doable but also awkward. The authors may want to address this scenario (telling the target service they’ve seen a movie they  haven’t actually seen and therefore never getting recommended a movie they would like). \n3)\tIt’s also not clear to me how easy it is to download historical item preferences from the source service. I am a longtime Netflix user. In the most concrete, real-life sense, I would like to know how I would download the list of Netflix movies I’ve watched and liked.  I poked around the Netflix site and couldn’t see how to do it. I realize this is an academic paper but it nonetheless would be implemented in real-world commercial context, so the authors should spend some time explaining that it's possible to download preferences of longtime users.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the cold-start problem for recommendation systems, where a new user’s preferences are unknown to a service (e.g. Hulu, the “target” service), making high-quality recommendations difficult. The authors aim to solve this problem in the scenario where the user has a substantial history on a different but related “source” service (e.g. Netflix ) but where the target service provides no special accommodation for transferring preferences from other services and where the target service’s recommendation algorithm (model) is unknown. The proposed solution, PRETENDER, is to transfer the information contained in the item preferences expressed on the source service by expressing preferences for target source items (via e.g. clicking/thumbs-up), where such items may or may not be the same as the source service items and the users may or may not have actually experienced such items. Clicking on the target items could be automated via a web agent to save time. Items are represented in a feature space representing the item content (genre, style, actors, etc).  Although the target service’s recommendation model is unknown, its loss on the data comprised of source service feedback-labelled items can be decomposed into the target service model’s training error on such items plus a term measuring the distance between the  source and target empirical distributions in the joint feature-vector-and-feedback-label space. The authors argue that without even knowing the target service’s training algorithm, good results can be achieved by minimizing this second term. They present an algorithm for doing so, by selecting, labelling and weighting target service items so as to minimize the distance between the 2 distributions.  2 possible distance measures are considered: maximum mean discrepancy (MMD) and 1-Wasserstein distance. Theoretical guarantees for both distance definitions are presented. The method’s performance is shown to be non-monotone in the number of labelled target source items, since labelling items with little similarity to source items may be counterproductive. Experiments are conducted on MovieLens, Last.fm and Amazon-home-and-kitchen, where source and target services are simulated by randomly selecting subsets of items. Some experiments simulate the case of overlap of items between source and target services while other experiments have no overlap. The regret of PRETENDER converging to 0 on the MovieLens is shown to occur for 2 users employed as case studies. In terms of MMD, PRETENDER outperforms 2 benchmarks on all 3 datasets by a wide margin. The benchmarks are random selection of target items and greedy one-by-one selection of the target item closest to the source item dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes are mostly outlined in the previous section, but to recapitulate:\n1)\tCould the authors investigate whether a semi-supervised-learning method like self-training could be a benchmark, or if not, explain why not?\n2)\tCould they do more hyperparameter tuning or illustration of sensitivities to hyperparameters?\n3)\tCould they do experiments where they actually feed the selected target items to a couple of different recommendation algorithms and then examine the effect of the recommendation algorithm?\n4)\tCould they examine whether users will find it problematic to ‘lie’ to the target service regarding items they haven’t actually experienced?\n5)\tCould they note that special care will need to be taken to make sure the unseen-but-rated target items are not inappropriately suppressed by the target service?\n6)\tCould they explain in a concrete real-life way how to download historical item preferences from services such as Netflix?\n\n**** Update after author response ****\n\nIn light of the additional author experiments and explanations, I have changed my claims-and-evidence rating to 'Yes'.\n\nThe paper also has far, far too many spelling errors. In the future, the authors need to make sure to run spellchecker before submitting a paper. This is particularly true for a  journal submission…spelling error are slightly more forgivable for conference papers where authors may be writing last-minute to hit a deadline, but I see no excuse for having some may spelling errors in a journal submission. It undermines my confidence a bit that the experiments were done with care. \n\nHere is a list... there are probably more errors than this, but this is what I noted:\n-\tP3 line 2 gerneral\n-\tP3 smoothnessof\n-\tP3 sidesitep\n-\tP4 meassure\n-\tP5 I believe equation 11 is a definition…should you use 3-line equals sign?\n-\tP8 PREDENTER\n-\tP10 as longs as\n-\tP10 convering number\n-\tP11 rouding process, functionoalities\n-\tP13 “We apply PCA to reduce the dimension to 50 and standardize the variance”..this sentence is repeated.\n-\tP13 reasonablly\n-\tP13 We hypothesis -> We hypothesize\n-\tP13 The reference to Table 2 at the start of the ‘Results’ paragraph is wrong, it’s actually Table 1\n-\tP14 Table 2 caption ‘the source items the user interacted’ -> ‘the source items the user interacted with’", "broader_impact_concerns": "No concerns here", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "H54ADDSPPk", "reviewer": "Reviewer_y8Ay", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "pos:\n+ This paper is well-written and easy to follow.\n+ The proposed method is significant and deserve to explore.\n+ The problem is well-formulated.\n+ The problem is addressed with extensive mathematical support.\n\ncons:\n- It assumes the users' bias can be modelled by \n- Although theoretically analysed, the Wasserstein-based version is not empirically validated.\n- The number of selected items K is fixed manually; no guidance is provided for choosing it effectively.\n- Constructs synthetic source/target services and doesn't evaluate in real cross-platform scenarios. More experiments are needed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes Pretender, a user-side algorithm to address the cold start problem in recommender systems by transferring preferences from a source service to a target service without any support from the provider. By selecting a small number of target items whose distribution closely matches the user's historical preferences, Pretender minimises distributional discrepancy using metrics like MMD or Wasserstein distance. The method involves convex optimisation, randomized rounding, and postprocessing, and is supported by theoretical guarantees. Experiments show that Pretender effectively improves recommendation quality and outperforms baseline approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The current experimental setup relies on synthetic splits. It would be beneficial to include more real-world cross-platform datasets to validate the practical feasibility of the proposed method.\n\n2. Additional case studies—including those highlighting failure cases—would strengthen the empirical support for the method and clarify its limitations.\n\n3. While the formulation is compelling, the assumption that user preference data can be transferred across platforms (e.g., Netflix to Hulu) raises important concerns about privacy and data accessibility. In many real-world settings, only a source model (e.g., user embeddings) and target items may be available. A discussion on whether Pretender could still function under such constraints would be valuable.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)