Cache-Augmented Inbatch Importance Resampling for Training Recommender Retriever
Authors: Jin Chen
Defu Lian
Yucheng Li
Baoyun Wang
Kai Zheng
Enhong Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Importance ReSampling
Negative Sampling
Recommender Systems
Retrieval

Abstract: Recommender retrievers aim to rapidly retrieve a fraction of items from the entire item corpus when a user query requests, with the representative two-tower model trained with the log softmax loss. For efficiently training recommender retrievers on modern hardwares, inbatch sampling, where the items in the mini-batch are shared as negatives to estimate the softmax function, has attained growing interest. However, existing inbatch sampling based strategies just correct the sampling bias of inbatch items with item frequency, being unable to distinguish the user queries within the mini-batch and still incurring significant bias from the softmax. In this paper, we propose a Cache-Augmented Inbatch Importance Resampling (XIR) for training recommender retrievers, which not only offers different negatives to user queries with inbatch items, but also adaptively achieves a more accurate estimation of the softmax distribution. Specifically, XIR resamples items from the given mini-batch training pairs based on certain probabilities, where a cache with more frequently sampled items is adopted to augment the candidate item set, with the purpose of reusing the historical informative samples. XIR enables to sample query-dependent negatives based on inbatch items and to capture dynamic changes of model training, which leads to a better approximation of the softmax and further contributes to better convergence. Finally, we conduct experiments to validate the superior performance of the proposed XIR compared with competitive approaches.

Cache-Augmented Inbatch Importance Resampling for Training Recommender Retriever
Jin Chen', Defu Lian"; Yucheng Li?, Baoyun Wang", Kai Zheng', Enhong Chen?
University of Electronic Science and Technology of China University of Science and Technology of China, 'Hisense wet.iiinssdd.usteeddue. liandefu wwwsst.edu.co liycuste waaitti@mmil..tteeeeee www..udu.ccccc.... wangbaoyun @ hisense.com, zhengkai @ @usttc.educnn cheneh @ ustc.edu.cc
Abstract
Recommender retrievers aim to rapidly retrieve fraction of items from the entire item corpus when user query requests, with the representative two-tower model trained with the log softmax loss. For efficiently training recommender retrievers on modern hardwares, inbatch sampling, where the items the mini-batch are shared negatives estimate the softmax function, has attained growing interest. However, existing inbatch sampling based strategies just correct the sampling bias of inbatch items with item frequency, being unable to distinguish the user queries within the mini-batch and still incurring significant bias from the softmax. In this paper, propose Cache- EugmenAd Inbatch Importance Resampling (XIR) for training recommender retrievers, which not only offers different negatives queries with inbatch items, but also adaptively achieves more accurate estimation of the softmax distribution. Specifically, XIR resamples items from the given mini-barch training pairs based certain probabilities, where cache with more frequently sampled items is adopted to augment the candidate item set, with the purpose of reusing the historical informative samples. XIR enables sample query-dependent negatives based on inbatch items and to capture dynamic changes of model training, which leads better approximation of the softmax and further contributes to better convergence. Finally, we conduct experiments to validate the superior performance of the proposed XIR compared with competitive approaches.
Introduction
have been prevalently developmented to address the issue of information overload, with the purpose of mining potential preferred items for users, bringing great commercial revenues to enterprises. Recommender retrievers, which retrieve subset of highly relevant items from numerous items, are key component of the commonly-used two-stage architecture
Recommender systems (RS) 10 23
M The two-tower models, where the queries and items are represented with separate models, are representative of retrieval models. Generally, given the similarity scores of user and item embeddings, the models attempt to minimize the loss function 10 17,, i.e., the log-softmax loss, guiding the interacted items having higher similarity scores. However, it is extremely inefficient to calculate the partition function the softmax loss over the item corpus. Negative Sampling, which samples number of items to estimate the partition function the gradient, has attained growing interests in recommender retrievers [6
35
A straightforward method is to take the static uniform distribution as the proposal distribution to sample items from the entire item set. Nevertheless, restricted by the computational resource, more
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

practical strategy is inbatch sampling 111 34], where the other training samples in the mini-batch are shared as negative samples. Considering the complicated features in online systems, it is time- consuming to get the embeddings of users and items via the tower model. Encoding the sampled unseen items outside the batch occupies additional huge computational cost. Thus, the inbatch sampling is more efficient and profitable for online systems under the circumstances of significantly great number of users and items with numerous features. There exists a sampling bias of training data in inbatch sampling, since the interactions are received from user logs and the item exposure follows the long-tailed distribution. Accordingly, several works correct the sampling bias using the popularity of items BS 37
and have been successfully exploited into the online systems.
However, there still exists a huge bias of the approximated gradient from the full softmax with the inbatch sampling. The sampling strategies eventually fit in the sampled-softmax, which approximates the exact gradient of softmax loss depending on the importance sampling. The bias can be eliminated by forcing the proposal distribution, i.e., sampling distribution, to the softmax distribution (2]. indeed correct the sampling distribution for inbatch sampling as the frequency- distribution), which remains a query-independent proposal. The ideal softmax distribution is dependent on different queries and changes dynamically during the training process. Existing studies 112 22
Previous works 64 3
based distribution (or popularity-
in negative sampling for recommender systems have proved that adaptive samplers lead to better convergence of the recommendation quality. Thus, there is urgent need to develop adaptive selection strategy for inbatch sampling to reduce the bias towards the ideal softmax distribution.
33
36
38
To this end, we propose a Cache-Augmented Inbatch Importance Resampling, shorted as XIR, for training recommender retrievers. Concretely, we resample the batch items according to the modified softmax weight over the mini-batch, which offers different negatives to user queries, instead of sharing a same set of batch items. This importance resampling based selection not only distinguish users but also provides more accurate estimation of the full softmax. Furthermore, inspired by the recent work 34 which introduces additional uniformly sampled negatives to tackle the sampling bias, a cache mechanism is utilized to further eliminate the approximation bias caused by the sampling bias of the inbatch sampling. Rather than the uniformly sampled items, we cache the more frequently sampled items into fixed-size set, usually having the same size as the mini-batch. The frequently sampled items tend to have higher similarity scores on average, which can be regarded as hard negative samples for training models. Therefore, the cache plays a role of item augmentation since more informative negatives are introduced to accelerate the model convergence. The proposed XIR is then evaluated on five public real-world datasets, demonstrating the superior performance over competitive baseline approaches in terms of effectiveness.
2 Preliminaries
2.1
Recommender Retrievers
Given the user query, recommender retrievers aim to rapidly response with highly relevant items from M
the full item corpus. Under the paradigm of the two-tower models [5] 21 30], the user queries and items are represented by {q: E IR MM queries and items, respectively. Here, we assume that the number of queries is finite for simplification. The user tower and item tower then map the feature vectors to a k-dimensional embedding space with separate functions ΦQ ch. R and o, Rd: R respectively. A similarity scorer s, such as the widely used inner product function s(u, i) = (øo (qw), (r:))) outputs the relevance of the query and candidate item i. In this paper, we investigate the log-softmax loss for training the two-tower models, where the preference probability of the item i with respect to the query u is calculated exp(s(u.)) with P(ilu) Ejer exp(s(u.j]]' where I denotes the candidate item corpus. By maximizing the likelihood, the objective function follows as:
l==1 and {e, E R4 J where M and N denote the number of
Luoitaa (D,0)
log P(ilu) = [D] (R.I)ED
Σ
1
log (a.))D
exp (s (u)
(1)
(D
Ejez exp (u.
where ② denotes the model parameters in dQ and dr. DD denotes the training data, each tuple of which records an interaction between the user query u and the item The two-tower model is such trained and the interacted items, i.c., positive pairs, are encouraged to get higher scores than

---

uninteracted items. The maximum inner product search (MIPs) then can be fruitfully implemented. such as SPANN H. ScaNN [4 and FAISS [20), to search for the topk items given a user query. meeting the requirements of rapid online response.
When the number of items N becomes extremely large, it would incur substantial computational cost of the partition function, i.c. the denominator in Eq ( Intuitively, the partition function can be estimated by sampling a subset from candidate items. The sampled softmax loss then behaves as the objective function,
exp (s' (u,
saamleed softmax (D,0) - D
Σ (n.i)ED
log
(2)
Ejes exp (s' (u,
where S represents the subset of the sampled items. & (u. i) = a (u, i) log p( (u) denotes the corrected logit with the sampling probability. Obviously, the computational cost considerably reduced, which only depends on the size of the sampled subset rather than the total item corpus.
2.2 Negative Sampling RS
To guarantee the unbiased gradient estimation of the sampled softmax, the softmax distribution the ideal proposal distribution 2 [8, which prohibitively expensive given the huge number of candidates and features. To meet the requirements of quick response, the query-independent sampling distribution, such as the uniform distribution, is applied to sample items. These distributions remain constant during the dynamic model training and they will select easy samples in later training epochs, which contribute a limited gradient to model convergence. The adaptive samplers are further investigated to sample more informative items depending on the model and can be grouped into two categories. One leverages techniques of adversarial frameworks [[]] 26 B2]. where negative samples generated through the complicated networks. The other category attempts to assign higher probability to items with larger similarity scores 19
29 36 or to reduce the bias of the sampling One promising approach is the two-pass sampler II Ko which samples a fixed-sized pool of items from the simple static distribution and then selects the items with the highest similarity scores in the pool calculate the loss. Due to its intractable sampling distribution, it is seldom cooperated within the sampled softmax loss and would perform worse due to its huge approximation bias from the softmax distribution.
distribution from the softmax distribution 4 6
However, in the online service of recommender systems with a huge magnitude of items and features, the query and item embeddings are constantly calculated through the large-scale deep towers. The inbatch sampling becomes popular since it avoids feeding additional negative items to the item tower 34 saving much computational cost. Moreover, the inbatch sampling does not improve the computational costs from the complexity perspective (28] but lowers the time cost on modern hardwares. To reduce the bias caused by the item exposure in online systems, several works correct the bias with item frequency which fits the sampled softmax loss with the item frequency as the proposal
3 Training Recommender Retrievers with Cache-Augmented Inbatch Importance Resampling
The inbatch sampling has attracted more attention due to its high efficiency for deployment on modern hardwares in online systems. Existing works attempt to correct the sampling bias within the mini-batch by the item frequency, which finally acts as the popularity- based proposal distribution in the sampled softmax loss. However, considering the ideal softmax distribution, whose sampling probability is associated with the given query, there still exists bias of gradient estimation from the softmax by just correcting the selection bias of inbatch sampling. To achieve better approximation of the softmax, we propose the inbatch importance resampling (BIR for short) and the augmeed importance resampling (XIR), which not only delivers different negative items to different queries based on the inbatch items but also yields an adaptive softmax estimation during model training.
3.1 Reducing Bias of Inbatch Sampling based Importance Resampling
Items within the mini- actually follow the popularity- -ased distribution since the observed items are exposed to users under the long-tailes tailed distribution in today's 's recommender systems. Thus,
3

---

inere-endependent sampler, i.e., frequency brauuency-baeed based sampler, fits the sampled softmax with the inbatch sampling. However, this query-independent sampler corrects the selection bias of the inbatch sampling but does not improve the estimation performance.
The importance resampling is adopted here to further correct the bias from the ideal softmax distribution. Given the mini-batch B, each item is resampled for the query u based on the weight
exp (s(u, i) log pop(i))
wrillu) = ΣjEB exp (s(u, log pop(i))
where the probability pop(i) here denotes the frequency of the items summarized from the training data. The resampled item set with respect to the query u is denoted as R..
By applying the resampling strategy, items with larger similarity scores have higher chance of being sampled and may appear multiple times. Moreover, the sampled items for different user queries are different while the queries share the same item in inbatch sampling. The following theorem provides the evidence that the sampled items based on the inbatch importance resampling can accurately approximate the softmax distribution.
Lemma 3.1. Assume items follow a distribution P= (pI p2,
..... .......P)) pNN. the item set I sampled from p== p21- 1. } follows the uniform distribution when [T] - Do.
Theorem 3.1. When the batch size |B] oc, items in the resampled set Rr with respect to the query based on sampling weight w(1 u) follow the softmax distribution w.r.f. the query
Proof. Assume pop(i) denote the item frequency over whole item corpus, the probability of appearing in Ry can be obtained according the multiplication rule in the following way:
P(ilic E R.). P(ili B) (ilu)
B
exp(s(u, - log pop(i))
pop(())
D
Σ
jen exp(s(u.j) log pop(j))
B
exp(s(u, i))
D
jEB pop(i) exp(ssuu.))
B
exp(s(u,i))
exp(s(u, i)) ESEz exp(s(u,)
B
Exerexp(s((u
The approximately equal sign x turns to the equal sign when [B] + c0.
According to the resampling approach, the sampled items follows the softmax distribution given the user query. Let's first review the expectation of gradient of the full softmax loss as follows:
N
Laoftmax = Vs(u, vo(u.j)= = Vv(u, ()) Vs(u,j)
where (i(il)) Egez (x,() Since the sampled items follows the softmax distribution, the estimated gradient with the item set R, achieves an asymptotic-unbiased approximation of the expectation of gradient, i.e., ΣieR, Vs(u, i) xe Bjar-())) Vs(u.)) Therefore, the objective function in a mini-batch has the following form:
exp(s(u.i))
exp (s(u, i)) (u.))B Σ ΣjER. exp ( su,,)))
CBIR (B)) =- Σ log
(3)
where R. denotes the resampled item set with the same size as The Algorithm [ketchess the pseudo-code for inbatch importance resampling, Compared with the naive inbatch sampling, BIR has the capability of distinguishing negative samples among different queries within inbatch items and capturing the dynamic changes of softmax, yielding an adaptive and flexible sampler to strengthen recommender retrievers. Note that the asymptotic-unbiased estimation achieved when the batch size becomes extremely larger. A non-asymptotic bound can be attached with the following theorem.

---

Algorithm 1: Inbatch importance resampling (BIR)
Input: Training data = {(u, i)), Number of epochs
Output: Model parameters θ
Statistically get item popularity P {pop(i) E IJ from D;
for 1, ..., 2..,..., T'. do
for mini-batch B do
U = (u](u, E B). (i)( BJ:
Map query feature vectors into embeddings Fay Bx based dq:
Map item feature vectors into embeddings E₁ Bx based on Φr;
Calculate the matrix of similarity S = for u E U do
Calculate the sampling probability w () Eeer exp(=(u_)) pop
(pp(=((ui))lu Vi
10
Resample set of items R. based w(ilu);;
11
Update model parameters based on the objective function, i.e., Eq
Theorem 3.2. Assum that the gradients of the logits Ves(u, have their coordinates bounded by G, the bias of V LBIR satisfies:
CiEB ex(u.) p(i) -
B[V e[VoLan(u) 5 V Ve (u) + BUU]-
+ to
+
13
[
2G
maxjte B (p(i) - p(1)
ZB
B
72 + +iEB (((n.))p(i)
B
where E(U] = Eiez (s(u, i)) Ves(u, 1). BBp = ΣjEB exp (s(u,j) log)(j)), 7B
EjeB exp (s), Z EiEr exp (s(u, i)). The probability p(i) refers to the popularity pop(t).
This theorem can be proved according Rawat's work and more details can be attached in Appendix A.2 According to the theoretical results, with a larger batch size, the upper bound gets smaller, indicating that the estimated gradient is less biased. terms of the popularity distribution, the value of the popularity differs greatly, i.e., max pop(-] has a greater value, it would get a larger bias min pop(.)
of the gradient.
3.2 Reusing Historical Informative Items with Cache-Augmented Resampling
Increasing the sample size is another crucial approach to controlling the bias and variance. Inspired by the recent work, MNS Rd), which uses a mixture of inbatch negative samples and additional uniformly sampled negatives, design paradigm with siche-augmented samples, with the aim of reusing highly informative items previous training epochs.
MNS feeds the model with additional uniformly sampled items, alleviating the Matthew effect to some extent. However, both the uniform distribution and ropularity-based distribution are static from beginning to end, which may oversample the easy samples after several epochs. In order to reduce the bias of the query-based softmax during model training, we intuitively cache the items with averagely higher scores, depending which historical harder negatives have the chance of being more trained.
count the occurrence number of times the items have been sampled into a vector {01, 02 ..., oN J. If the item has been sampled for more times according to the aforementioned BIR, it has an averagely higher similar score among user queries, indicating that it has higher probability of being hard negatives. The cache C is generated and updated by sampling items based on 0;, which serves an additional candidate set to be resampled and augments the items from the original batch. Since the mache-augmented items follow a different distribution from the inbatch items, they can not share a unified normalization function. Thus, the items are resampled independently from the cache and the batch, and fit in two parts of loss as follows:
More concretely,
log exp(s(u, i)) (u.))B
exp(s(u, i))
EXR ( B, 0) = - Σ
Ljek. exp(s(u,j) (1 -)-)) Σ log
LjER., exp(s(u, (4)
(u,)E
5

---

where À denotes a hyperparameter to control the influence of two separate parts. Ky denotes the item set resampled from the cache C based the weight of we Eeee (opp(=((.))-log((( where (t) pop(i). Note that the newly seen items are affected by a long-tailed distribution, we, therefore, correct the sampling bias for computing the normalized resampling weight. R. refers to the resampled item set according to the inbatch importance resampling. In order to maintain a final resampled set with size [B). we simply resample items from the cache and batch respectively, i.e.,
exp(e(u,)) v(0)
When newly resampled items generated, the occurrence of items in the resampled set is updated. The cache-augmented item set offers more historical informative samples for training retrievers, being beneficial to getting rid of the sampling bias caused by the exposure bias. The Algorithm 2 details the procedure of the cache-augmented inbatch importance resampling.
|Ku] = R
Algorithm 2: Çache- Inbatch Importance Resampling (XIR)
Input:
Training data = {(u, i)), Number of epochs T, Cache size C, Hyperparameter
Output: Model parameters θ
Initialize the occurrence vector o = {0)_ and the cache with uniformly sampled items; Statistically get item popularity P {pop(i) (vi I) from D;
3 for e - 1, 1.,....,
...,,. T do
for mini-batch B D do
-= (u](u, i) E [ B):
Map user feature vectors into embeddings Ey E BB based on éQ:
Map item feature vectors into embeddings E, E Bxb based on Φr: Map feature vectors for items in the cache C into embeddings Eg E CC based on Φy; Calculate the similarity matrix S EJ and S' E.
10
for u E U do
log Vi I; Resample set of items R2 based on w(ilu) Eyer exp( (((])((())))))))))))))))))))())) log pop(i))
11
12
Resample set of items K.,, based on wa(ilu)= Exec (xp(=((u.))
expld' (u.i) g(1)
ViE;
// Update the cache and occurrence vector O {ili E Ky, R,, Yu E U} 0; o, + C ] i]
13
14
Sample C items based on w = o; to update the cache C:
15
Update model parameters based on the objective function, i.e., Eq
3.3 Complexity Analysis
Compared with the inbatch sampling, BIR introduces additional computational cost for each training mini-batch of calculating the resampling weight (Line in Alg I and resampling items according to the multinomial distribution (Line 10 in Alg which has a time complexity of O( B| [B).. Such time complexity is acceptable compared with the computational cost of embedding functions (Ø())) and (()r)) and similarity matrix computation ( x B x k). Regarding XIR, feeds the items of the cache into the item tower (Line g in Alg 2). taking the additional cost of embedding them. The time complexity
resampling is the same as that of BIR. Updating the cache and occurrences
Alg 2 takes (NN time complexity, where N is the number of items. BIR introduces additional O X Bl) space to compute the similarity scores in a mini- batch, while XIR further requires space complexity of O(IC) + N) to save the cache and occurrence vector.
(Line 13 14
4
Experiments
The proposed BIR and XIR are then evaluated on five public real-world datasets in recommender retrievers to answer the following questions: (1) Can the inbatch importance resampling outperforms competitive strategies in inbatch sampling? (2) How do the eache-augmented items improve the performance of recommender retrievers?

---

4.1
Experimental Settings
4.1.1 Dataset
The experiments are conducted on the Gowalla, Amazon, Ta-feng, Echonest and Tmall datasets summarized in Table 1 The rated books in Amazon dataset with higher ratings than average ratings are considered as positive ones, while the interactions in other datasets are regarded as positive ones. 80% of items for user are sampled for training and the other 20% of items constitute the test set. The performance of recommender retrievers is evaluated on the NDCG (Normalization Discounted Cumulative Gain) and RECALL at cutoff of 10 by default.
Table 1: Statistics of Datasets
Dataset
#User
#ftem
#Interaction
Density
Gowalla
29,858
40,988
1,027,464
8.40e-4
Amazon
130,380
128,939
2,415,650
1.44e-4
Ta-feng
19,451
10,480
630,767
3.09e-4
Rchonest
217,966
60,654
4,422,471
3.35e-4
Tmall
125,553
58,058
2,064,290
2.83e-4
4.1.2 Baselines
In this work, we investigate the inbatch sampling for retrievers and we compare the proposed BIR methods. All the methods attempt to minimize the log sampled softmax loss (i.e., Eq 2). namely SSL), varying in the selected negatives and the proposal distributions. (1) SSL utilizes the inbatch samples as negatives without the bias correction. (2) SSL- uses the inbatch items and adopts the item popularity as the proposal distribution. (3)
and [ with competitive inbatch-sampling-basse
34 refers to the mixed negative sampling, which uses mixture of batch and uniformly sampled negatives. We set the number of uniform samples B' to be the same as the batch size. (4) G-Tower 35 corrects the selection bias in batch sampling by streaming frequency estimation. records the last number of steps for each item in fixed-length hash arrays and reduces hash collision errors by using multiple hash arrays. In this way, the frequency is estimated as the reciprocal of the average number of steps. We use 5 different hash arrays estimate.
MNS
4.1.3 Implementation Details
The proposed methods, including baseline methods, are implemented with the PyTorch learning framework in a Linux operating system and Tesla V100 GPU. The Adam optimizer utilized with a discount of 0.95 on learning rate at every 5 epochs. We use the ID features for users and items by default and the embedding size is the learning rate is set to 0,001, where each dataset is training with 100 epochs. The coefficient of the (g-regularization is tuned over {le
32. For each dataset, the batch size is fixed 2048 and
le 5, - 6). The item popularity is calculated by the normalized item frequency, i.e., p(i) = J statistically summarized from training data. The hyperparameter for XIR is tuned over (0.0, 0.2, 0.5, 1.0)
4.2 Performance Comparisons with Baseline Methods
Each method is run for 5 times with different random seeds and we report the average scores with their standard deviations in Table 2 The proposed BIR and XIR considerably outperform the competitive baselines. BIR achieves relative 2.47%. 6.57%, 6.58%, 2.04% and 5.17% improvements of NDCG@ 10 on the five datasets respectively while the relative improvements for XIR are 3.81 %, 12.23%. 15.24% 11.73% and 12%. Both BIR and XIR show superior performances, indicating the efficient and preferable utilization of the inbatch samples. addition to correcting the selection bias by the item popularity, BIR and XIR can dynamically select more informative negative samples for different queries within the mini-batch, contributing to better model convergence. According to the importance resampling paradigm, the items with higher similarity scores with the corrected
2 Datasets: https:/rechole,ineeee int////aainee//aattsetttt (icddattts___sssshmmm IImplementation for BIR and XIR: https//github.com//EEEECCC
7

---

Table 2: Comparison with Baselines. 5 = le
Gowalla
Amazon
Ta-feng
Echonest
Tmall
Method
NDCG@ 10
NDCG@ @ 10
NDCG@ 10
NDCG@ @ 10
NDCG@ 10
SSL
0.1381
0.0718:13.7
0.043719.46
0.1436:13.16
0.034013.16
SSL-Pop
0.1479:19.18
0.0764+1.26
0.0625+11.56
0. 0.1609:11.6
0.05471:5.6
MNS
0.148618.98
0.0781#4.96
0.0634+1.46
0.1648+2..6
0.0561#4.98
G-Tower
0.1500=1.66
0.0764+1.00
0.049618.76
0.1600=5.16
0.0429=2.16
BIR
0.1523=7.96
0.0833+2.76 0.0877+3.46
0.0675+1.36
0.1682:13.46
0.059013.228
XIR
0.154
0.0730=1.16
0.1842:12.46
0.0658:12.26
RECALL@10 10
RECALL 10
RECALL@ 10
RECALL@ 10
RECALL@ 10
SSL
0.1105:L4.18
0.0753+1..5
0.0375+1..5
0.1350:3..6
0.03544:3.66
SSL-Pop
0.112414.48
0.0777=4.36
0.050619.26
0.1502+22.48
0.0544 18
MNS
0.1130::4.28
0.0796=16.15
0.051418.56
0.1537+2.96
0.0558
G-Tower
0.1176=1688
0.0798
0.0415
0.150445.16
0.0440
BIR
0.1157:1..68 0.084813.56
0.054918.66
0.156813.46
0.0588
XIR
0.1169-1..1
0.0895:14.16
0.058916.16
0.1703
0.0651+2.86
0.036
0.08
0.86
0.034
SSL
0.04
SSL
00033
SSp-Hop
0.04
MNS
MNS
G-Yower
G-Tower
0.02
XIR
XIR
0.090
2065
Figure 2: Occurrence of items. Items are sorted in descending or- der of popularity
Amazon
(b)
Tmall
Figure NDCG@ 10 vs. number of epochs on two datasets
sampling bias have a higher probability of being resampled, where a more accurate estimation the query-dependent softmax is achieved. In addition, we have the following findings.
Finding 1: Reducing the selection bias within the mini-batch by item popularity is beneficial to reducing the approximation bias from the softmax distribution. SSL, which does not adjust the proposal distribution, performs the worst among the baseline methods in terms of both NDCG and RECALL. Thus, such a method raises inconsistency between the real sampling distribution and the proposal distribution, resulting in poor performance of the sampled softmax loss.
Finding 2: Introducing negative items outside of the mini-bater expands the candidate set, facilitating the learning of retrievers. The result, that MNS outperforms SSL-Pop with average 1.84% relative improvement of NDCG@ 10 and XIR outperforms BIR with a 7.12% improvement, demonstrates that the model has better resolution towards long-tailed items with the additional sampled items.
Finding 3: Caching the frequently sampled items helps improve the retriever performance, indicating that the frequently sampled items are more informative than uniformly sampled items. XIR signif- icantly improves the performance BIR, where historical informative items have a tendency to remain in the cache with more training.
Furthermore, we investigate the recommendation performance during training epochs with different inbatch- inbatch-sampling sampling sampling-based based methods to verify the effectiveness of the BIR and xIR. The changing curve of NDCG@ on the Amazon and Tmall datasets are shown in Figure Both BIR and XIR contribute to faster convergence compared to the baselines. The model's NDCG quickly reaches relatively high level under BIR and XIR, particularly on the Amazon and Tmall datasets, implying that more informative items are selected for training.
8

---

4.3 Item Distribution in Cache
In order to intuitively figure out the item distribution in the cache, experiments are conducted to summarize the occurrence vector, since the cache is updated by sampling based it. We summarize the occurrence after 100 epochs on the Gowalla dataset and normalize the item occurrence, as shown in Figure 2 where items sorted by their popularity in descending order.
The distribution of items the cache performs significantly different from the popularity-based distribution. The huge bias from the popularity-basee distribution suggests that the cache can alleviate the long-tailed items becoming more popular according to the corrected sampling probability, i.e., the popularity, Moreover, the unpopular items have greater chance of being sampled, whereas more informative items are encouraged be more sampled, rather than treating full items as equivalent.
4.4 Adaptive Query-Dependent Estimation
Compared with MNS and G-Tower, where the items within the mini-batch are shared between user queries, the proposed BIR selects different samples, being able to approximate the softmax distributions for different queries and capture the dynamic changing of softmax distribution during the training process. In this chapter, we conduct experiments by resampling smaller numbers of items from the mini-batch and compare the performances with SSL-Pop. We report the relative improvements in terms of NDCG@ @ 10 and RECALL @ 10 in Figure ((a) and 3(b)
1056
5%
1.0
N0008000
(16
Gewalls Taffnaa
Gowalla
Gunolla
Tafera
To-frg
10%
Amazon
1054
Amsenn
Trall
Trull
-15%
-2056
120
15
35
Butch
(a) NDCG@ 10
(b) RECALL@@ 10 (c) Gradient Summarized Time
Figure 3: Performances vs. |R
1 From the figures, resampling nearly 64 of items in the batch can achieve comparable performances of SSL-PPo with full batch items. Specifically, for Tmall, Amazon and Ta-feng datasets, it takes fewer samples to surpass SSL-Pop. This demonstrates the superiority of distinguished negative samples over different user queries, which performs a query-dependent approximation for softmax distribution and benefits the model training.
This series of experiments provides the potential for more efficient training with much fewer samples. Thus, we further compare the running time of summarizing the gradient under various sizes of the resampled item set Figure ((c) We run for 10 epochs for each setting and report the average time compared with SSL-Pop. Since data IO and feature embedding take considerably computational cost, we just compare the calculation on the gradient, As fewer items are selected, the summarized gradient receives fewer calculations.
4.5 Introducing Features into Item Tower
In online recommender retrievers, two tower models with deep networks offer the capacity of capturing complicated features. Thus, we further encode the categorical features SellerID and CatelD in the Tmall dataset and build the item tower as two fully-connected layers with 32 and 16 units, using Relu as the active function. As shown in Table 4 BIR and XIR outperform SSL-Pop, achieving relative 3.06% and 4.87% improvements in terms of NDCG @ 10 respectively. This indicates the effectiveness the proposed importance resampling based methods given more features, implying the possibility of deploying deeper retrieval towers.

---

Figure Performances on Tmall
15%
Gowalla
N@ 10
R@10 10
N@20
R R@ 20
NnCoggto
10%
Amoous
Twslan
SSL SSL-Pop
0.0311
0.0329
0.0524
0.0568
Fehoroo
0.0720
0.0712
0.0999
0.1022
0%1
BIR
0.0742
0.0735
0.1032
0.1057
Cathe Son
XIR
0.0755
0.0750
0.1067
0.1099
Figure 5: Performances vs, cache size
4.6 Effect of Cache Size
To figure out the influence of the cache size, we conduct experiments with various sizes, including 0.5x. 1x, 2x and 4x of the batch size (2048). We report the relative improvements compared with BIR in Figure 5 As the batch size gets larger, more items participate in the approximation of softmax, achieving more accurate estimation and better performance of recommendation quality.
4.7 Effect of
Since the coefficient plays a vital role in Eq we conduct experiments by varying the value of À to figure out the influence of this hyperparameter. Experiments are conducted on all five datasets with XIR, as shown in Figure
0.000
11150
1.150
0.873
0.147
01130
0.565
6,170
0.022
600
0.00
RSCALLS
XDCO1210
0.3
23
02
1.0
0.0
0.6
02
93
(a) Gowalla
(b) Amazon
(c) Ta-feng
(d)
EEchneet
(e) Tmall
Figure Effect of X
As shown in the figure, both the NDCG@ 10 and RECALL@ 10 have the same changing curve under different X. A smaller value of indicates the inbatch items contributes more gradient, whereas lager value corresponds with that the cache plays a more important role. When À 0.5. the cached items and inbatch items contribute equally to convergence. For further study, we may link the resampled ratio with X, instead of resampling half of the items from the cache and the batch.
Conclusion
In this paper, we propose a cache-augmented inbatch importance resampling for training recommender retrievers, which achieves more accurate estimation of softmax for different queries using the inbatch items. The proposed BIR resamples items based on the similarity scores with popularity- based debias and thus different queries are trained with different sampled items, achieving a more accurate estimation of the softmax distribution. XIR is further proposed to encourage historical informative items to be more trained, which augments the inbatch items and thus helps retriever training. Experiments are finally conducted on five real-world datasets to validate the effectiveness of the proposed BIR and XIR.
Acknowledgments and Disclosure of Funding
The work is supported by the National Natural Science Foundation of China (No. 61976198, 61972069, 61836007 and 61832017), and Shenzhen Municipal Science and Technology R&D Funding Basic Research Program JCC110021032411367002)
10

---

References
[1] Yu Bai, Sally Goldman, and Li Zhang. Tapas: Two-pass approximate adaptive sampling for softmax. arXiv preprint arXiv:1707.03073 2017.
[2] Yoshua Bengio and Jean-Sébastien Senécal. Adaptive importance sampling to accelerate training of a neural probabilistic language model. IEEE Transactions on Neural Networks, 1944:713-722, 2008
[3] Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
[4] Guy Blanc and Steffen Rendle. Adaptive sampled softmax with kernel based sampling, In International Conference on Machine Learning, pages 590-599, PMLR, 2018.
[5] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 6, 1993.
[6] Jin Chen, Defu Lian, Binbin Jin, Xu Huang, Kai Zheng, and Enhong Chen. Fast variational autoencoder with inverted multi-index for collaborative filtering. In Proceedings of the ACM Web Conference 2022, pages 1944-1954 2022.
[7] Jin Chen, Defu Lian, Binbin Jin, Kai Zheng, and Enhong Chen. Learning recommenders for implicit feedback with importance resampling. In Proceedings of the ACM Web Conference 2022, pages 1997-2005, 2022.
[8] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. Spann: Highly-efficient billion-scale approximate nearest neighborhood search. Advances in Neural Information Processing Systems, 34:5199-5212, 2021.
[9] Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. Wide & deep learning for recommender systems. In Proceedings of the 1st workshop deep learning for recommender systems, pages 7-10, 2016.
[10] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommenda- tions. In Proceedings of the 10th ACM conference on recommender systems, pages 191-198, 2016.
[11] Jingtao Ding, Yuhan Quan, Xiangnan He, Yong Li, and Depeng Jin. Reinforced negative sampling for recommendation with exposure data. In IJCAL, pages 2230-22202 22362 2019.
[12] Jingtao Ding, Yuhan Quan, Quanming Yao, Yong Li, and Depeng Jin. Simplify and robustify negative sampling for implicit collaborative filtering. arXiv preprint arXiv:2009.03376, 2020.
[13] Carlos A Gomez-Uribe and Neil Hunt. The netflix recommender system: Algorithms, business value, and innovation. ACM Transactions Management Information Systems (TMIS), 6(4):1- 19, 2015.
[14] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
[15] Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk. Session-based recommendations with recurrent neural networks, arXiv preprint arXiv:1511.06933 2015.
[16] Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giuseppe Ottaviano, and Linjun Yang. Embedding- retrieval facebook search. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 2553-2561, 2020.
[17] Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 2333 2238, 2013.
11

---

[18] Sébastien Jean, Kyunghyun Cho. Roland Memisevic, and Yoshua Bengio. On using very large target vocabulary for neural machine translation. arXiv preprint 1rXiv:141..2007, 2014.
[19] Binbin Jin, Defu Lian, Zheng Liu, Qi Liu, Jianhui Ma, Xing Xie, and Enhong Chen. Sampling- decomposable generative adversarial recommender. Advances in Neural Information Processing Systems, 33:22629-22639 2020.
[20] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Trunsuctions on Big Data, 7(3):535-547, 2019.
[21] Walid Krichene, Nicolas Mayoraz, Steffen Rendle, Li Zhang, Xinyang Yi, Lichan Hong, Ed Chi, and John Anderson. Efficient training on very large corpora via gramian estimation. arXiv preprint arXiv: 1807.0787 2018.
[22] Defu Lian, Qi Liu, and Enhong Chen. Personalized ranking with importance sampling. In Proceedings of The Web Conference 2020, pages 1093-1103, 2020.
[23] Defu Lian, Haoyu Wang, Zheng Liu, Jianxun Lian, Enhong Chen, and Xing Xie. Lightrec: A memory and search-efficient recommender system. In Proceedings of The Web Conference 2020, pages 695-705, 2020.
[24] Defu Lian, Yongji Wu, Yong Gc, Xing Xie, and Enhong Chen. Geography-aware sequential location recommendation. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2009-2019, 2020.
[25] Erik Lindgren, Sashank Reddi, Ruiqi Guo, and Sanjiv Kumar. Efficient training of retrieval models using negative cache. Advances in Neural Information Processing Systems, 34, 2021.
[26] Dae Hoon Park and Yi Chang. Adversarial sampling and training for semi-supervised informa- tion retrieval. In The World Wide Web Conference, pages 1443-1453, 2019.
[27] Ankit Singh Rawat, Jiecao Chen, Felix Xinnan X Yu, Ananda Theertha Suresh, and Sanjiv Kumar. Sampled softmax with random fourier features. Advances in Neural Information Processing Systems, 32, 2019.
[28] Steffen Rendle. Item recommendation from implicit feedback. Recommender Systems Handbook, pages 143-171. Springer, 2022.
[29] Steffen Rendle and Christoph Freudenthaler. Improving pairwise learning for item recommen- dation from implicit feedback. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 273-282, 2014.
[30] Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. Learning semantic representations using convolutional neural networks for web search. In Proceedings of the 23rd international conference on world wide web, pages 373-374, 2014.
[31] Jinpeng Wang, Jieming Zhu, and Xiuqiang He. Cross-batch negative sampling for training two-tower recommenders. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1632-1636, 2021.
[32] Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong. Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. Irgan: A minimax game for unifying generative and discriminative information retrieval models. In Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 515-524. ACM, 2017.
[33] Jason Weston, Samy Bengio, and Nicolas Usunier. Wsabie: Scaling up large vocabulary image annotation. In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
[34] Yang, Xinyang Yi, Derek Zhiyuan Cheng, Lichan Hong, Yang Li, Simon Xiaoming Wang, Taibai Xu, and Ed H Chi. Mixed negative sampling for learning two-tower neural networks in recommendations, In Companion Proceedings of the Web Conference 2020, pages 441 441-447, 2020.
12

---

[35] Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. Sampling-bias- bias-corrected neural modeling for large corpus item recommendations. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 269-277, 2019.
[36] Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu. Optimizing top-n collaborative filtering via dynamic negative item sampling. In Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval, pages 785-788, 2013.
[37] Chang Zhou, Jianxin Ma, Jianwei Zhang, Jingren Zhou, and Hongxia Yang. Contrastive learning for debiased candidate generation in large-scale recommender systems. In Proceedings the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 3985-3995, 2021.
[38] Qiannan Zhu, Haobo Zhang, Qing He, and Zhicheng Dou. A gain-tuning dynamic negative sampler for recommendation. In Proceedings of the ACM Web Conference 2022, pages 277-285, 2022.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See the abstract and the introduction.
(b) Did you describe the limitations of your work? [Yes] We propose the adaptive sampler under the paradigm of recommender retrievers and inbatch sampling. There still exists bias from the ideal softmax distribution in this case.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work does not have any negative societal impacts
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We states the assumptions for theoretical results.
(b) Did you include complete proofs of theoretical results? [Yes] All proofs can be attached in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material datasets and codes are accessible in Section
URL)? [Yes] The links of
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Data splits can be referred in Section 4 Details about hyperparameters can be attached in Appendix. The provided codes covers the whole process and all baselines.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Each algorithm is run for 5 times and report the error
(sttanadd deviation) in Table 2
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide the empirical environment in 'Implementation details' in Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cite the resources
in Section g
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you 'rere using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rExhbl85t1j", "reviewer": "Reviewer_mWFy", "summary": "This work designs an inbatch negative sampling method for improving both effectiveness and efficiency of contrastive item recommendation task.", "questions": "1. Could you please compare baselines like DNS, LambdaFM, PRIS?\n2. It should be essential capacity of negative sampling method to deal with false negative samples. Please justify how the proposed method can make it?\n3. Please give more discussion on the superiority of the proposed method comparing with the other kinds of sampling method which does not attempt to sample from a softmax distribution in the introduction section.", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed method is well formalized with theoretical support.\n2. The presentation is overall good enough.\n3. Experiments are conducted on large-scale datasets to evaluate the performance of the proposed approach.\n\nWeakness:\n1. The proposed method ignores the false negative sample issue if sampling from the full softmax distribution. An item with large similarity does not have to be a hard negative sample. \n2. This work mainly focuses on how to improve the sample efficiency from softmax distribution. However, it does not present the superiority of the proposed method comparing to previous works that are not based on importance sampling from softmax distribution, for example, dynamic negative sampling (DNS, Weinan Zhang et al. SIGIR 2013), lambdaFM (CIKM 2016), PRIS (The WebConf 2020), AOBPR (WSDM 2014) etc. It deserves more words to compare with methods beyond estimating softmax distribution.\n3. The baselines are not fully compared to validate the superiority of the proposed method. At least, the typical method PRIS should be a strong baseline which also estimates the softmax distribution with importance sampling method.  ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ndWegZgBPA", "reviewer": "Reviewer_rEcV", "summary": "The paper discusses the drawback of traditional negative sampling methods for the retrieval task for general recommender systems, and then proposes a new method which samples negative data points specifically for each user/query input, and illustrates why it could better approximate the gradient during model training. Experiments are provided to support the advantage of the proposed method.", "questions": "1. I want to understand the value proposition of this paper. Are we designing a practically useful algorithm or it's about some innovations behind the theorem? In its current shape, the paper seems a mixture of both. As a result, the level of contribution cannot be well estimated. For example, if it's about theoretical innovation, then the techniques behind the proof should be highlighted; if it's about practically useful algorithms, then I don't think there are enough material in the experiments and the discussion of real-world IR system.\n\n2. The paper repeatedly mentioned about characteristics and contraints of modern hardware, which also guided the design of the new method. I suggest to explicitly talk about related details. Does it mean the new method is only useful for a particularly implemented system under certain architecture?\n\n3. Discussion of the theorem. We do have the real-world data. Does the theorem lead to a significant difference under the usually used batch size?\n\n4. It's now very clear about the usefulness of the cache. I feel the advantage is again a mixture of implementation and algorithm. I didn't find much discussion on this. It seems to me that the assumption is that getting the representation is slow.", "limitations": "Though not very explicitly mentioned, the new method still has bias for the estimate of the gradient. This can be considered as the limitation.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The problem itself is important. For extremely large scale retrieval system, the negative sampling is the key for training. The authors also capture the critical drawbacks of existing negative sampling method.\n\n2. The bias reducing theorem is a highlight of the paper.\n\n\nWeakness:\n\n1. I also want to mention theorem 3.1. Thought I don't know how difficult it is, but a finite batch size theorem would make the paper much stronger because it would be far more practical. In reality, other factors could dominate the training performance which the benefit of the new method cannot be revealed when the batch size is not big enough.\n\n2. For the experiments, one missing piece is the discussion of dataset sizes. The sizes are illustrated but are they large enough to fit the motivation behind the new method? Given the size, it seems naive global negative sampling can work.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ji-39VpOiau", "reviewer": "Reviewer_94bj", "summary": "Large-scale two-tower recommendation systems are the norm in the industry. One of the biggest challanges in model training is the growing data set sizes. This even makes constructing the training set somewhat tricky--often pushing the modelers randomly sample their data set. This is sub-optimal. The paper proposes a new model training process that uses an in-batch importance sampling in distributed systems to train large-scale recommender systems. The proposed techniques have been viewed in two segments--1) importance sampling 2) cache-augmentation. The authors compare their methods with appropriate and standard baselines and analyze the parameters to inform future users.", "questions": "Along the lines of relating the literature to baselines and final learnings/findings: \nWhat would be the recommendation of the authors to readers on which techniques to use under what conditions?  \n", "limitations": "There could be more such discussion. The importance of sampling, particularly the one done through learned embeddings, can result in significant biases in the systems. Depending on the learned embeddings, any such bias could be heavily boosted in certain scenarios. On the other hand, the competition hypothesis such as popularity-based techniques are not necessarily better (which is shown) and potentially in many scenarios, they could be even worse. This is not a critique of the proposed technique but this aspect of the problem is not well studied in the paper. \n\nOn the other hand, I understand the fact that this itself could be a separate paper.  However, the paper proposes a weighting technique alternative to random sampling, this topic is at the heart of the problem. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A) Strengths\n\n-The paper touches on a simple but essential step of model training that is often neglected and, via a simple idea, dramatically improves model performance as well as provides the ability to increase model complexity or gain training time potentially.\n\n-The authors demonstrate that a modern ML production system should think about every single step end-to-end holistically and use the power of systems and algorithms jointly to optimize the whole process.  \n\n-The paper is written well and rigorously explained, and enough technical details are provided. Given the space, the experimentation depth (both baseline comparison and analysis of algorithms) and findings/learnings are pretty detailed.\n\nB) Weaknesses (I don't have any major concerns. Just nit-picking):\n\n-There might be some weaknesses in the literature review and how they do relate to the baselines picked. \n\n-Not enough discussion on how these techniques would provide biases and affect the populations/society. \n\n-It might be good to discuss future work, particularly along the lines of candidate generation and retrieval for inference stages. I suspect several such learning could inform the research in this direction. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D8Op6AL27UU", "reviewer": "Reviewer_mU7B", "summary": "This paper studies an important research problem of in-batch negative sampling for recommender systems, which aims to efficiently train recommender retrievers (also known as recall-stage models) by choosing the items in the mini-batch as negatives to estimate the softmax function. This is also highly practical and thus widely adopted in today’s industrial recommender systems. The authors first analyze and discuss two main weaknesses of existing solutions. One is a huge bias of the approximated gradient from the full softmax with the in-batch sampling. The other is a query-independent sample selection strategy that is less effective for convergence of the recommendation quality. To tackle the above two problems, the authors propose to simultaneously eliminate approximation bias caused by in-batch sampling and improve sampling quality by favoring hard negative samples. Specifically, the authors propose to resample the batch items according to the modiﬁed softmax weight over the mini-batch, which offers query-dependent negatives and theoretically provides a more accurate estimation of the full softmax. Moreover, the sampling process is augmented with hard negative samples by caching frequently sampled items. The designed Cache-Augmented In-batch Importance Resampling (shorted as χIR) significantly outperforms state-of-the-art baselines by 3.81%~17.12% on ﬁve public real-world datasets.", "questions": "1. The authors have analyzed time complexity in Sec. 3.3 and plotted empirical results in Figure 3(c). Is it possible to provide space complexity results, too?\n2. Since updating the cache and occurrences takes O(N) time complexity, and item numbers can be enormous in industrial recommender systems, I suggest considering updating the cache in a less-frequent manner and also analyzing its possible impact on recommendation quality.", "limitations": "Yes.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.    The studied problem is important and interesting. In-batch negative sampling is one of the most prevalent techniques for recall-stage recommendation models in real-world applications. Besides, it is more challenging than the traditional negative sampling problems.\n2.    The proposed method is novel. The cooperation of importance resampling and hard sample caching can address the two remaining issues of existing in-batch sampling solutions. It is the first work to achieve query-dependent and hard in-batch negative sampling simultaneously.\n3.    The two main designs are technically sound. First, a non-asymptotic bound of the proposed importance in-batch resampling method is derived and analyzed rigorously. Second, the designed cache constantly updated by frequently sampled items can capture more informative negatives.\n4.    The authors conduct extensive experiments. State-of-the-art methods are compared on five real-world datasets, and the results show a significant improvement achieved by the proposed method. The ablation studies, applicability studies, and hyper-parameter studies are solid. \n5.    Overall, the presentation is nice. I enjoy the reading, and I believe most readers of the NeurIPS community will, too.\n\nWeaknesses:\n1.    Table 2 presents many results of the performance comparison. But, there is too much information in a single table. I suggest bolding and underlining the best and second best, respectively.\n2.    I appreciate the derivation and analysis of the non-asymptotic bound (Theorem 3.2). However, It would be more informative and instructive if the authors could provide a more thorough analysis of the impacts of batch size and popularity distribution.\n3.    A few typos. e.g., “Assum that the gradients of the logits” in Line 162. And y-label for Figure 3(c).", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept