Consistent Data Distribution Sampling for Large-scale Retrieval
Authors: Hongyu Ou
Jun Yin
Huanqin Wu
ANAN LIU
Lin Zhao
Tao Chen
Yuekui Yang
TAO YANG
Venue: Submitted to ICLR 2023 (2023)
Keywords: Retrieval
Neural Networks
Deep Learning
Recommender Systems
Information Systems

Abstract: Retrieving candidate items with low latency and computational cost is important for large-scale advertising systems. Negative sampling is a general approach to model million-scale items with rich features in the retrieval. The training-inference inconsistency of data distribution brought from sampling negatives is a key challenge. In this work, we propose a novel negative sampling strategy Consistent Data Distribution Sampling (CDDS) to solve such an issue. Specifically, we employ a relative large-scale of uniform training negatives and batch negatives to adequately train long-tail and hot items respectively, and employ high divergence negatives to improve the learning convergence. To make the above training samples approximate the serving item data distribution, we introduce an auxiliary loss based on an asynchronous item embedding matrix over the entire item pool. Offline experiments on real datasets achieve SOTA performance. Online experiments with multiple advertising scenarios show that our method has achieved significant increases in GMV. The source code will be released in the future.

Under review as a conference paper at ICLR 2023
CONSISTENT DATA DISTRIBUTION SAMPLING FOR LARGE-SCALE RETRIEVAL
Anonymous authors Paper under double-blind review
ABSTRACT
Retrieving candidate items with low latency and computational cost is important for large-scale advertising systems. Negative sampling is a general approach model million-scale items with rich features in the retrieval. The training- inference inconsistency of data distribution brought from sampling negatives is a key challenge. In this work, we propose novel negative sampling strategy Con- sistent Data Distribution Sampling (CDDS) to solve such an issue. Specifically, we employ relative large-scale of uniform training negatives and batch negatives to adequately train long-tail and hot items respectively, and employ high diver- gence negatives to improve the learning convergence. To make the above training samples approximate the serving item data distribution, we introduce auxil- iary loss based on an asynchronous item embedding matrix over the entire item pool. Offline experiments real datasets achieve SOTA performance. Online ex- periments with multiple advertising scenarios show that our method has achieved significant increases in GMV. The source code will be released in the future.
INTRODUCTION
Industrial search systems, recommendation systems, and advertising systems generally contain large scale of users and items. To handle the millions and even billions of items, such systems usually comprise the matching stage and the ranking stage. The matching stage, which is also called retrieval, aims retrieve a small subset of item candidates from the large item pool. Based on the thousand-scale retrieval subset, the ranking stage concentrates on the specific ranks of items for the final display. Since the retrieval task should consider both accuracy and efficiency, the two- tower architecture is the main-stream matching method widely used in most industrial large-scale systems Yi et al. 2019).
In two-tower retrieval mechanism, a million-scale to billion-scale item embedding can be prepared in advance and updated in a regular cycle when serving. FAISS (Johnson et al. 2019) is usually employed to quantize the vectors. With the efficient nearest neighbors search mechanism, retrieving top similar items from the entire item pool for given query can be low latency. But the same procession is extremely expensive in the training phase. Especially entire item embeddings change a lot along with the training steps and are hard to feed-forward in every training step. On this condition, the inconsistency between the training data distribution and inference data distribution can not be ignored. What's more, the inconsistency is much more serious when the scale of the items grows.
Since the training- -nferrnce inconsistency has a great impact in practice, recent research explored various ways construct negative training instances alleviate the problem. Faghri al. (2017) employ contrastive learning to select hard negatives in current or recent mini-batches. [iiog et al. (2000) construct global negatives using the being-optimized dense retrieval model to retrieve from the entire corpus. Grbovic & Cheng (2018) encode user preference signals and treats users' rejec- tions as explicit negatives. Yang et al. (2020) propose mixed negative sampling to use a mixture of batch and uniformly sampled negatives to tackle the selection bias.
Totally, uniform sampling negatives are often easy to distinguish and yield diminishing gradient norms (Xiong al. 2020). Batch negatives lead to an insufficient capability when retrieving long- tail items and over-suppress those hot items which are interacted frequently. The current mixed sampling method does not clarify the role and sampling distribution between easy negative samples

---

Under review as a conference paper at ICLR 2023
and hot negative samples. The combination of various sampling methods is usually well-designed for the respective case rather than a general situation.
Although previous work sought to empirically alleviate the training-inferee inconsistency problem in the matching stage, directly approximating the matching probability over the entire item data distribution is absent. Complex sampling methods make it difficult to analyze the effect of a single negative sample on the selection bias. Empirical approaches which have achieved improvement in efficiency metrics are uncertain about whether the selection bias is actually reduced due to the difficulty of analysis. Since only the non-sampling method is truly free of selection bias, optimizing the selection bias becomes possible if the retrieval probability of a single item can be approximated over the entire item pool.
To this end, we propose novel negative sampling approach called Consistent Data Distribution Sampling, CDDS for brevity. To adequately train long-tail and hot items respectively, we employ relative large-scale of uniform training negatives and batch negatives. To improve the learning con- vergence, we employ global approximate nearest neighbor negatives as high divergence negatives. By maintaining an asynchronous item embedding matrix, we calculate the loss not only between the query embedding and the sampled items but also over the entire item pool. Directly approximating the matching probability over the entire item data distribution, our theoretical analysis and exper- iments show that CDDS achieves consistent training-inferenee inference data distribution, fast learning convergence, and the state-of-the-arr performance.
In summary, the main contributions of this work are follows:
We analyze the bottlenecks of different negative sampling strategies and show that introduc- ing those unsampled vast majority items can alleviate the training-inte inference inconsistency and resolve the bottlenecks.
We propose CDDS which adequately trains long-tail items. improves the learning con- vergence, and directly approximates the matching probability over the entire item data distribution.
Our theoretical analysis proves that CDDS achieves a consistent training-inferrncee data distribution. Extensive experiments on real-world datasets achieve the sults. Online experiments with multiple advertising scenarios show that our method has achieved significant increases in GMV and adjust cost.
2 RELATED WORK
2.1 TWO-TOWER MODELS
The two-tower architecture is popular in industrial retrieval, which learns query and item vector representations separately in two forward networks. This framework has been widely used in text retrieval (Huang et al.] 20133] Yang et al. 20200 Hu et al. al. (2014), entity retrieval (Gillick et al.) 2019), and large-scale recommendation (Cen et al. 2020 Covington et al. [016 Li et al.) 2019). Our work is orthogonal to existing complex user representation network architectures such as CNN (Hu et al.,
2014 (heen et al., (014) and mulli-interestt models (Li et al. 2019 Cen al. 2020). which can also benefit from our optimal sampling strategy.
2.2 NEGATIVE SAMPLING METHODS FOR TWO-TOWER MODELS
Covington et al. (016) and Li et al. 2019) formulate the retrieval task extreme multi-class classification with a sampled softmax loss. Although the challenge of efficient training and the Kaining-inferene inconsistency seems be solved, these methods rely on a predetermined item pool and are not applicable when sampling with complex distributions (Yang et al. 2020).
Chen al. (200)) show that an enlarged negative pool significantly benefits sampling. In text re- trieval, ANCE (Xiong et al. 2020) constructs global negatives from the entire corpus by using an asynchronously updated ANN index, theoretically showing that uninformative items yield dimin-
will release the code once the paper is accepted.
2

---

Under review as a conference paper at ICLR 2023
ishing gradient norms. negative pool.
That is to say, diminishing gradient norms matter in introducing an enlarged
MNS Yang al. 2020) finds it important to reduce the selection bias brought by batch negative sampling and reduces such bias by additionally sampling uniform negatives from the item pool. All items in the item pool have chance to
training negatives and the sampling distribution is more flexible. Although the performance of fresh and long-tail items is better, a small scale of sampling uniform negatives is insufficient with a huge-scale item pool and large scale of sampling uniform negatives easily leads to high latency and computational cost. Meanwhile, batch negatives are not a complete substitute for hard negatives to achieve fast learning convergence.
PROBLEM FORMULATION
We consider a recommender/scacc//aateetttt an item set V = {v1, U2...., ) where M is the number of users and N is the number of items. Given a query u, its positive feedback on items forms the training positive set V+. For the given query, the matching stage aims at efficiently retrieving possible subset 7 from the universe set V, where the desired candidate items number | << |.
system with query set U {wi, W2,...; uM} and
In industrial-scal applications, the number of items can be enormously large and the training data likely to be very sparse for most queries and items. To tackle the above challenges, the two-tower model with towers referring encoders based on DNN is usually applied (Yu et al. (021). The two-tower model learns latent representations of the given query and item separately. We denote the two towers by functions f 0) and g(I;; 0), where f() is the query tower model, 9() is the
item tower model, Ti and Fu map query and item features, and O is the whole parameters. Then the matching score of the corresponding item becomes:
stu, v) = sim u, v),
(1)
where u = f(r 0), = g(,,;; 0), and the similarity function (sim()) is often simply cosine or dot product. Then we can calculate the matching score of the item in softmax probability:
(a,,)
P(wvlu)= Enev (((w))))
(2)
and the items with top values will be the candidates.
METHODOLOGY
In this section, discuss what difficulties encountered in calculating the matching score P(vlu) and provide theoretical analyses of how CDDS approximates the P(ulu) with the sampled negatives and the universe set V.
4.1 TRAINING- INCONSISTENCY
Constructing the positive feedback items V as training positives and the other exposed items V,- as training negatives is a common approach in the ranking stage. With a well-working ranking model, the items exposed are often with top ranking scores and is not proper matching training negatives consider that:
Plulu,t E V+) P(olu, E V77)
VVVANV))
(3)
V and V. are all come from the matching stage and are the top part of the matching candi- dates. Training retrieval model like a ranking model becomes increasingly unacceptable as the VVVV V. grows. Due to the ambiguity of user feedback, an item without positive feedback is not an exactly undesired candidate. Sometimes, to serve the ranking model better, useful to define the ranking tops training positives V U V. in the matching stage. Since the number of positive items is not much bigger, is feasible to pick positive samples that are close to the specific applica- tion. In this condition, define the will-picked training positives as V that are better than all the others in the item pool. As result of retrieving possible subset V from the universe set V in the
3

---

Under review as a conference paper at ICLR 2023
serving phase, the training negative set corresponding to the training positive set is V- ViV+. To describe the training positives accurately, we must focus on the long-tail majority V-
When the number V not extremely enormous, training retrieval model task with the whole V is an alternative approach. But as the number of the training negatives grows, training with V becomes high computational cost. In the inference, all items V can be prepared in advance and updated in a regular cycle even the number is millions to billions. Thanks to the efficient library for similarity search in billions of vectors, FAISS (Johnson al., (019) for example, embedding search with all items in V is fast and accurate. Since the same procession extremely expensive the training phase,
mulli-classificaale
impossible to train with all negatives. Sampling a negative
subset -ー becomes natural choice and leads to the training-inferene inference inconsistency on the data distribution. The training-inference inconsistency can be represented as
CVV
(4)
V <
4.2 IMPACT OF INCONSISTENT DATA DISTRIBUTION
Given the query u, the best parameters l with the ideal training negatives V- is:
0 argming Σ ΣΣ
I(E(u, E,),, v)).
(5)
8 VTEV -V
where I() denotes the loss function. After adopting negative sampling, the optimization goal be- comes:
0- argming ΣΣΣ I(s(u, o* e*)),((;))))
(6)
--E-
Without sampling, for every positive item at trained, the negative item v is also trained once. In the uniform sampling case, for every time the u is trained, x' is trained with an expectation of 1
|V-1
times. As a result of | < VV most items are not trained enough. When calculating softmax loss function, most items are trained adequately, the time and computational cost are not acceptable.
apply weight to adjust the loss of training samples. However, ensure that
In order to make the -ー as close as the V= it seems that we should increase the number of uniform samples as much as possible. But Xiong al. (2020) show that negative instance with a larger gradient norm is more likely to reduce the training loss. Let 1(x+ v Xiong al. (2020) and Katharopoulos & Fleuret (2018) proved that
u )),
1(v (()tv))) + 0 + [Vollutt, Ill + + [[Vo,((t,, 20) - 0,
(7)
where | Vo,, 1(+ ll2 denotes the gradient with respect of the last layer and | I(ut -r)l22 denotes the gradient at training step t. As the number of desired candidates is small, a large scale of sampling uniform negatives is easily be uninformative and yields diminishing gradients.
4.3 NEGATIVE SAMPLING APPROACH
Based on the above analysis, we propose a Consistent Data Distribution Sampling approach that aims alleviate the training-inference inconsistency and achieve fast learning convergence.
In order to close to the serving item data distribution, we employ relative large-scale of uniform negatives. The number of uniform negatives determined by both the number of queries and the number of items to ensure each item is trained as much possible when the training phase is complete. larger number of training negatives means higher computational cost. So we make uniform sampling during the training period and share the same uniform negatives in mini-batch.
In order to achieve a fast learning convergence, hard negatives sampling is useful. A simple but effective approach is using the positive items in query batch {u,, U2....... ,u) } as shared negatives for all queries in the same batch (if a shared negative happens to be the positive item of the given query, it is filtered for the given query). Yang et al. (220)) show that mixture of batch and uniformly sampled negatives significantly improves retrieval quality. However, the batch negatives are mainly those items that are frequently interacted with and are popular rather than hard.
4

---

Under review as a conference paper at ICLR 2023
fow goddeste
0.
Boe wihust gradiests
update ttre embedditge
ponkiio Iine collodiiiss
ssyacamosely opdate frem cxieeding eack chedppiia
6
c(MB.
Fosts reslecellag
8
gvey enteediing
marge
lecfouel) to cin top
(6.)
1/
1eytaknoorraly sgdtated cuabecidaap
<(tb +5
Figure 1: The workflow of the proposed CDDS method. We employ relative large-scale of uniform training negatives, batch negatives, and high divergence negatives as mixture negatives. By updating item embeddings with higher gradients higher frequencies, approximate the similarity score over the entire item pool. With the auxiliary loss function L' refine the loss function L among the sampled items.
Similar to Xiong et al. (020)) to train truly hard and informative samples, we imply asyn- chronously updated ANN index of the item pool and maintain an inferencer that parallelly computes the item embedding with a recent checkpoint. We introduce the top items for each query as high divergence negatives. The difference that we de-duplicate these top items and use them as shared negatives within the batch. That is, guarantee that each query is trained with high divergence items, but we do not strictly limit that is only trained with hard negatives.
A mixture of uniform negatives Vp {Up "p ................................ up }. batch negatives V7 = (ut 2 ...... et
and high divergence negatives V7, = (1 "hy..... "n form the final negatives Vー All negatives are shared in a batch. Let yi be the label of item uy and the loss function with inconsistency as follows:
L
Σ -EE
-lm (og( (1 v.) log(1 0;)],
where
(F(M,))
0:
Σ E..vi ef(um))
When we use a large-scale uniform negative sampling, our training negatives are close to the serving data and it is inefficient in gradient updating. When we introduce items with high training divergence negatives, training-infee inference inconsistency inevitable. From the training-inferent inference inconsistency perspective, desire the loss function to be:
Σ -(P())lu) log( (P(s)))) (1 1 log(1 P(us|u))). V.EV
(10)
To approximate the matching score of the item in softmax probability P(u (u), we need to find approach to approximate the similarity score e(u, v) and the item embedding 0). On coarse-gne coarse-grained approximation, we can decompose the similarity score E(u, v) into two components:
f(u, u) = (zu; 0), (z 0)), if V orve
(11)
(z. 0), g( 0')). else
where 0' is the parameters of the recent checkpoint. Along with the training, the difference be- tween 0 and 0' becomes larger (g(z,;;)) 0) g( 0')), so we cannot directly replace the retrieval probability e(u, v) with sim([( (1::
5

---

Under review as a conference paper at ICLR 2023
Let's consider a SGD step with importance sampling (Alain al. 2015):
0++1 0, Pe-
Ve, M(+ v ,0),
(12)
where Or denotes the parameters I-th step, Oz+1 denotes the parameters one step after, v denotes the learning rate, and po- denotes the sampling probability of negative instance. From equation and equation 12 to make É(u, 2) E(u,,) e):
We apply threshold 8 and ignore the uninformative negatives (1(vt,0) < 8) which yields diminishing gradient norms.
I(o v - 0 -0 E(u,
E(u,), = c(u,
(13)
We introduce the top items with high (i 0) g 0¹)) high divergence negatives every batch. Meanwhile, all high divergence negative item embeddings (o,, hhy......................... ........ V/
are updated to the asynchronous item matrix [v1,
So the item embeddings
with high variation 0.+1 0, are updated every batch.
We make uniform sampling only from the remained subset. Embeddings with relatively high variation 0 0, are updated with stable frequency.
With such process. hot item embeddings, high divergence item embeddings, and relative large- scale uniform item embeddings are all updated along with the variance of the parameters. Further, the approximated retrieval probability is
eL(,,))
P(velu) = Eneyy (M,,s))
(14)
and the desired loss function L transformed into an auxiliary loss function
Č = Σ (og( + (1 11) log(1 P(u)()))
(15)
VLEV
Considering that we cannot apply the backpropagation to the unsampled items (e & V-), we calcu- late the auxiliary loss without gradients and refine the loss of item i; with weight
- -[P(eu)uu log(P(u; + (1 - y1) log(1 P(vs/u))] W Ensey - log (P ()) - (1 vs) log(1 P(valw))]
(16)
Then we can refine the loss function as:
L = Σ -w;ly log(úr)) + (1 y.) log(1 0t)l
(17)
-LEV+UP
Items with greater loss over the entire item pool will be taken into account more. Sampled items that used to have higher softmax probabilities have also been corrected.
EXPERIMENTS
In this section, conduct two offline experiments real-world datasets and compare CDDS with existing methods. In addition, online experiments by deploying our method in an industrial advertising system demonstrate effectiveness and efficiency.
5.1 DATASETS DESCRIPTIONS
We choose public representative dataset ML-25M (Harper & Konstan 2015) and a real-world industrial advertising dataset for evaluating retrieval performance.
ML-25M This dataset describes 5-star rating and free-text tagging activity from movie recommendation service.

---

Under review as a conference paper at ICLR 2023
Table 1: Statistics of datasets
Statistics
ML-25M
Industrial advertising dataset
# of training examples
3,215,856
32,189,155 152
# of test examples
355,406
332,344 1, 1,249,013
# of items
62,423
Industrial advertising dataset. This dataset contains click, downloading, activation, and purchase behaviors an online advertising system that serves more than a billion users.
Preprocessing on ML-25M. Given a user, its ratings on items in chronological order form the session sequence. We split each session to generate feature sequences and labels. For example, for a session [u("), un ( we generate a series of sequences and feedbacks ([uf I,05
(x) (1) " "/=,,_%" where [u("), ,12 _..,[([]]] is the generated input ([v]"), , lug ([u] .22 ...
(s)
quence and en is the feedback item. 5-star rating items are treated as positive feedback items and training positives. We construct the examples with only training positives while training negatives are sampled in the training phase. The movie tags applied by the given user before of rated form the tag sequence feature. User id feature, rating sequence feature, and tag sequence feature form user features. Item id feature, genres feature, genome scores, and genome tags form item features. We use all 62, 423 items in the training and testing, and filter out the training examples that have neither rating sequence nor tag sequence. Samples with timestamps before 15 1514500000 are training samples and samples after 1514500000 are test samples, as the test samples account for about 10 percent of the total samples.
Preprocessing on industrial advertising dataset. We classify user feedback into three categories: exposure, click, and conversion. Conversion is kind of feedback with less ambiguity, such as download, registration, and purchase. The user's most recent conversion collected as the training positive. Same with the preprocessing on ML-25M, only positive samples included. Our adver- tising dataset has richer and more sparse features. We select the examples certain day as the training set and sample percent of the examples from the next day the test set.
The statistics the datasets are shown in Table [
5.2 EVALUATION METRICS
We use different metrics for the offline and online phase. For the offline evaluation, we apply the widely used metrics hit ratio (HR) and mean reciprocal rank (MRR) to measure the performance of the retrieval. In the online phase, the metrics are listed as follows:
Gross Merchandise Volume (GMV). GMV is the total amount of sales on the advertisers' platform. This metric measures the real income of advertisers.
Adjust Cost. The cost is the money that advertisers need to pay for advertising platform. The Adjust Cost can be regarded as the real income brought by the experimental strategy after adjustment based on the actual cost.
5.3 COMPARISON METHODS
To demonstrate the performance of our proposed method, we use the same two-tower architecture to encode all queries and items. We compared our method with other baseline methods as well as recent ofate-of-thh-ar methods:
MLP with Sofxmax. MLP with sofxmax uses a extreme multi-class classification archi- tecture and outputs item probability with a two-layer DNN. This approach only uses the id feature.
Batch negatives sampling. Batch negatives sampling uses the positive items a mini- batch as shared negatives for all queries in the same batch.
Uniform sampling. Uniform sampling uniformly samples negatives.

---

Under review as a conference paper at ICLR 2023
Table 2:
The performance comparison
ML-25M dataset.
Best scores highlighted in bold-
face.
@ (MRR@) I)
HR@
HR@ 100
MRR@ 10
MRR@ 100
MLP with softmax
0.0257
0.1072
0.3420
0.0462
0.0538
Batch negatives sampling
0.0243
0.0974
0.3006
0.0428
0.0495
Uniform sampling
0.0144
0.1197
0.4588
0.0395
0.0507
MNS
0.0311
0.1369
0.4474
0.0572
0.0675
ANCE
0.0309
0.1404
0.4509
0.0582
0.0685
CDDS w/o L
0,0302
0.1364
0.4462
0.0567
0.0669
CDDS
0.0324
0.1425
0.4637
0.0603
0.0685
MNS. Yang et al. (2020) improve the in-batch sampling by additionally sampling global uniform negatives.
ANCE. Xiong et al. 2020)) construct global negatives from the entire item pool by using asynchronously updated ANN index.
CDDS w/o Ż. The comparison method introduce uniform negatives, batch negatives, and high divergence negatives. Compared with CDDS, the loss function is L which doesn't 't alleviate the inference inconsistency.
5.4 PARAMETER CONFIGURATION
The embedding dimension is set 64 and the size of mini-batch is set to 512. We use Adam Optimizer (Kingma & Ba 2014) with the learning rate 0.001. The number of uniform negatives set to 512 on ML-25M and set 16384 on the industrial advertising dataset for Uniform sampling, MNS, and CDDS. With the relative large-scale of uniform negatives, most items are trained adequately on ML-25M. Due to the limitation of GPU allocation, we cannot sample more negative samples to achieve the same effect on the industrial advertising dataset. The number of high divergence negatives is set to 64 for ANCE and CDDS. We use Transformer (Vaswani et al. 2017) to model the sequence feature.
5.5 PERFORMANCE COMPARISON
Table 2 illustrates the overall performance on ML-25M dataset, with the best results highlighted in boldface. Table illustrates the performance on the industrial advertising dataset and only HR is shown while the online service applies a pre-ranking stage to sort the candidates from different retrieval models. Compared to other methods, our method achieves the best performance.
From table 2 and we observe that batch negatives sampling performs poorly as result of the vast majority long-tail items have not been adequately learned. Uniform sampling with rich features achieves the best HR @ 100 among the comparison methods ML-25M.. The above phenomenon shows that uniform sampling works well on an item pool with 64, 263 movies. As items are trained adequately, the uniform sampling successfully solves the training-inference inconsistency and performs well small-scale retrieval. Since popular items and high divergence negatives are good enough.
specifically trained, the MRR metrics of the uniform sampling method With a million-scale item pool, the uniform sampling method does not achieve a good performance on the industrial advertising dataset as the items can be trained adequately. MNS performs better than all of the existing methods at HR@1 1, which indicates the importance of mixture negatives. ANCE learns high gradients negatives from the entire item pool and achieves a good performance at MRR @ 10 and MRR @ 100. This means that learning with high divergence negatives helps to distinguish the rank order in the retrieval candidates. CDDS without L shows that the simple mixture of negatives is not enough and alleviating the
inference inconsistency is important. From table 3 observe that CDDS achieves a fast learning convergence while the uniform sampling has not converged over 12 hours to solve the training- inference inconsistency.
training-inferenee
observe that the popular items minority and the long-tai tail items major- ity with a Gini index 0.97 on the ML-25M training dataset. The hot items are with higher HR @ 100 the hit number at top 100 is closer the number of testing samples while the long-tail items
From Figure 2
8

---

Under review as a conference paper at ICLR 2023
Table 3:
The performance comparison industrial advertising dataset.
Best scores high-
lighted in boldface.
HR@1
HR @ 100
HR @ 1000
HR @ 2000
Convergence time
MLP with softmax
Batch negatives sampling
0.0314
0.1683
0.3531
0.4147
4.3h
Uniform sampling
0.0321
0.1916
0.3946
0,4613
over 12h
MNS
0.0492
0.2394
0,4496
0,5162
6.0h
ANCE
0.0489
0.2360
0.4561
0.5224
6.6h
CDDS w/o
0.0476
0.2385
0,4531
0.5225
7.4h
CDDS
0.0528
0.2443
0.4629
0.5269
5.6h
with lower HR@ 100. CDDS a high recall accuracy for popular items and large hit number for long-tail items, which shows that our method does not purely retrieve popular items.
Atoilcaeaa EB acubbe AOletzand
Figure 2: The left part is the Lorenz curve which represents the cumulative proportion of ordered items from lowest to highest terms of the cumulative proportion of their positive feedback number on MI-255M training dataset. The right part is the CDDS performamce of long-tail items and hot items on the ML-25M test dataset.
5.6 ONLINE EXPERIMENTS
We conduct online experiments by deploying our method handle real traffic in industrial adver- tising system. Our experiments start with 1% randomly selected users and finally take effect across the entire traffic. There are two thousand candidate items retrieved by our method. GMV and adjust cost are used to measure the performance of serving online traffic. With the control group consist- ing of 50% randomly selected users, the experiment in scenario achieved 0.30% improvement on GMV and 0. 0.14% improvement on adjust cost, and another scenario achieved 0.47% 7% improvement on GMV and 0.27% improvement on adjust cost.
CONCLUSION
In this work, we propose a novel negative sampling strategy Consistent Data Distribution Sampling to solve the training-infee sonning-ifferenee inconsistency of data distribution brought from sampling negatives. Specifically, we employ a relative large-scale uniform training negatives and batch negatives to adequately train long-tail and hot items respectively, and employ high divergence negatives to improve the learning convergence. To make the above training samples approximate the serving item data distribution, we introduce auxiliary loss based on asynchronous item embedding matrix over the entire item pool. Offline and online experiments show the effectiveness and efficiency of CDDS.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. arXiv preprint arXiv: 1.06481, 2015.
Yukuo Cen, Jianwei Zhang, Xu Zou, Chang 7hou,, Hongxia Yang. and Jie Tang. Controllable multi- interest framework for recommendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2942-2951, 2020.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003. 04297, 2020.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations In Proceedings of the 10th ACM conference on recommender systems, pp. 191-198, 2016.
Fartash Faghri, David J Fleet, Jamie Ryan Kiros, and Sanja Fidler. Vse++: Improving visual- semantic embeddings with hard negatives. arXiv preprint arXiv: 1707.05612 2017.
Daniel Gillick, Sayali Kulkarni, Larry Lansing, Alessandro Presta, Jason Baldridge. Eugene le, and Diego Gareia-Olano. Learning dense representations for entity retrieval. arXiv preprint arXiv:199..10506, 2019.
Mihajlo Grbovic and Haibin Cheng. Real-time personalization using embeddings for search ranking at airbnb. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 31 3-1-020, 2018.
Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm transactions interactive intelligent systems (tiis), 5(4):1-19, 2015.
Baotian Hu, Zhengdong Lu, Hang Li, and Qingeai Chen. Convolutional neural network architectures for matching natural language sentences. Advances in neural information processing systems, 27, 2014.
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. Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pp. 2333-2338, 2013.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):335-547, 2019.
Angelos Katharopoulos and François Fleuret. Not all samples created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525 22344253. PMLR, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 2014.
Chao Li, Zhiyuan Liu, Mengmeng Wu, Yuchi Xu, Huan Zhao Pipei Huang, Guoliang Kang, Qiwei Chen, Wei Li, and Dik Lun Lee. Multi-interes network with dynamic routing for recommen- dation at tmall. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 2615-2623, 2019.
Yelong Shen, Xiaodong He. Jianfeng Gao, Li Deng, and Grégoire Mesnil. Learning semantic rep- resentations using convolutional neural networks for web search. In Proceedings of the 23rd international conference on world wide web. pp. 373-374, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. arXiv preprint arXiv:2007.00808 2020.
10

---

Under review as a conference paper at ICLR 2023
Ji 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 recom- mendations. In Companion Proceedings of the Web Conference 2020, pp- 441-447, 2020.
Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. Sampling- Sampling-bias-coree biws--icrssttteeeeeeeeeeeeeeee-e neural modeling for large corpus item recom- mendations. Proceedings of the 13th ACM Conference on Recommender Systems, pp. 269-277, 2019.
Yantao Yu, Weipeng Wang, Zhoutian Feng, and Daiyue Xue. A dual augmented two-tower model for online large-scale recommendation. DLP-KDD, 2021.


Reviews:
[{"review_id": "kEG2-NGALiI", "reviewer": "Reviewer_sTd5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Long-tail distribution of items is an important factor which affects the user’s experience in industrial search systems, recommendation systems, and so on. This submission tries to address the training-inference inconsistency due to the long-tail distribution. Concretely, the authors comprise a relatively large-scale of uniform negative sampling and batch negative sampling to make sure that long-tail items and hot items can be trained adequately. To faster the convergence of training, the proposed model also searches some hard negative items based the ANN index for the training queries. The main contribution of this submission is to propose a new loss function which considers the weight of each positive and negative training items. Both the offline and online experiments validate the effectiveness of the proposed model.", "summary_of_the_review": "The submission focuses on the training of long-tail distribution of items which is important to improve the user’s experience in real search systems and recommendation systems. However, the novelty and the original contribution are incremental. Additionally, the experiments are not adequate.", "strength_and_weaknesses": "Strength:\n1. The topic is interesting and important to improve the user’s experiences in industrial system.\n2. The submission has an online experiment to validate the effectiveness of the model in real industrial system.\n\nWeakness:\n\n1. The novelty and contribution are incremental. The main contribution is to propose the loss function based on the classical binary-cross entropy by weighting each training items.\n2. The experiments are not adequate. Please conduct more experiments on other datasets and make up some ablation studies.\n3. Please give more explanations for the auxiliary loss (i.e. e.q. (10) and e.q. (15),). What’s the intuitive meaning of the auxiliary loss?  How about the training efficiency as the auxiliary loss and the weight (i.e. e.q.(16)) consider all the items?\n4. In the last paragraph on page 5, the sentence ‘Along with the training, the difference between $\\theta$ and $\\theta^{‘}$ becomes larger. Intuitively, the difference between $\\theta$ and $\\theta^{‘}$ should be smaller as the model converges. Please elaborate on how to set the checkpoints and how to update the checkpoint in your experiments. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TfK4eKYdHSj", "reviewer": "Reviewer_ExGn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work tries to tackle negative sampling in embedding model training for retrieval. Consistent Data Distribution Sampling is proposed by combining large-scale uniform training negatives with batch negatives. High divergence negatives are employed to improve the learning convergence. The sampled negatives are fused in a proposed auxiliary loss based on the asynchronized embedding matrix over the entire index set. The experiments show SOTA performance.", "summary_of_the_review": "The technical part of the paper is somewhat sound, but the presentation of the work needs improvement (not only grammatically). The skeleton of the work lies on prior works, unless authors clarify the difference from prior works, I think the novelty is limited.  ", "strength_and_weaknesses": "*Strength*\nOffline experiments compared with related approaches and peer work show SOTA\nCombining multiple sampling strategy and the auxiliary loss is somewhat novel\n\n*Weaknesses*\n- The experimental results are thorough, but lack of some ablations, see clarity section, and it is also necessary to support the claim that \"high divergence improves the learning convergence\".\n- The results seems marginal, authors can clarify what is the typical gain in published papers for such datasets as an auxiliary support.\n- The difference and novelty of the proposed approach is not highlighted, and it is confusing that what makes a difference. Please include concrete technical contribution in the introduction section, current presentation is a bit high level. e.g. \"We proposes CDDS which .... by tech 1, tech 2, tech 3......\"\n- The writing of the paper needs improvement. Especially the incorrect clause usage/unnecessary inverted order sentence improve the difficulty of reading. Simple and short SVO sentences are fine. And please use accurate words to express.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JJdYf-ywK4", "reviewer": "Reviewer_WYde", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method for consistent distribution sampling in latent two-tower models for recommender system. The method adds weights sampling in the loss calculation (on the mix of subsampled random negatives and negatives from a hard negative mining) to better approximate the overall sampling distribution which seem to help on few open-sourced datasets and in a/b tests in production.", "summary_of_the_review": "I think the paper has big problems with presentation, so it should be rejected on this basis. I also feel like this paper would be a better fit for a recsys conference (or a workshop), rather than ICLR.", "strength_and_weaknesses": "Strengths:\nThe paper shows a positive effect of the solution in the experiments.\nWeaknesses:\n1) Paper quality is has big issues. It needs to be proofread, the plots are hard to understand, terminology is not clear.  I think it is enough for rejection by itself.\n2) I am not sure if the uniform weight sampling is actually a desired outcome. E.g. in simclr the quality of the results dropped with the batch size after certain batch size.\n3) it is not clear what is the baseline in the a/b test. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AVjnW3dq_q", "reviewer": "Reviewer_RorQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Online ML systems usually have explicit positive samples (E.g., ads conversion, click, buy, like, etc.) to train on. However, negative samples are often implicit and have a much higher volume concerning positives. A common technique in constructing a training data set is to sample from the negatives to having more reasonably balanced data sets. However, the sampling process introduces problems concerning selection bias, not considering the long tail, etc. The paper presents a new negative sampling strategy called consistent data distribution sampling to improve this process. It focuses on the long tail and hot items specifically and provides mechanisms to improve convergence.\n", "summary_of_the_review": "I am borderline with this paper. The novelty and results are not impressive. It is an important problem and has strength in analytical analysis. But in such a practical problem, we either need a more thorough practical evaluation or a stronger algorithm with stronger results to pass the bar. so my rating is a marginally below acceptance.", "strength_and_weaknesses": "Strengths:\n\n-It provides a good overview of the problem analytically and why we need to be mindful in sampling negatives. It also provides a rigorous analysis of the convergence.\n\n-The results are decent. Particularly close to the ANCE. It is not surprising since it also provides a similarity/distance-dependent process. \n\nWeakness:\n\n-It is not clear the complication and analysis of what similarity check brings concerning complexity (as an incremental unit) and how it grows with the dimensionality of data and representation size. For example, how much does it worsen the training time? What is the trade-off with respect to increased training time (so in an online system, maybe you will be able to retrain 4 times instead of 10 times a day).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject