Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1.    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.
2.    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.
3.    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.
4.    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. 
5.    Overall, the presentation is nice. I enjoy the reading, and I believe most readers of the NeurIPS community will, too.

Weaknesses:
1.    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.
2.    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.
3.    A few typos. e.g., “Assum that the gradients of the logits” in Line 162. And y-label for Figure 3(c).
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?
2. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work designs an inbatch negative sampling method for improving both effectiveness and efficiency of contrastive item recommendation task.
strengths_and_weaknesses: Strengths:
1. The proposed method is well formalized with theoretical support.
2. The presentation is overall good enough.
3. Experiments are conducted on large-scale datasets to evaluate the performance of the proposed approach.

Weakness:
1. 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. 
2. 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.
3. 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.  
questions: 1. Could you please compare baselines like DNS, LambdaFM, PRIS?
2. It should be essential capacity of negative sampling method to deal with false negative samples. Please justify how the proposed method can make it?
3. 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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength:

1. 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.

2. The bias reducing theorem is a highlight of the paper.


Weakness:

1. 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.

2. 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.
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.

2. 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?

3. 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?

4. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: A) Strengths

-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.

-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.  

-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.

B) Weaknesses (I don't have any major concerns. Just nit-picking):

-There might be some weaknesses in the literature review and how they do relate to the baselines picked. 

-Not enough discussion on how these techniques would provide biases and affect the populations/society. 

-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. 
questions: Along the lines of relating the literature to baselines and final learnings/findings: 
What would be the recommendation of the authors to readers on which techniques to use under what conditions?  

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. 

On 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.
review_title: null

Meta-review: metareview: The idea of more representative mini-batches sounds like a natural extension of the work done on stratified sampling. The reviewers were convinced the idea is both new and effective on real data. In particular, the discussion with mWFy clarified that this work is alternative way to explore the capacity of ranking optimization by leveraging the samples shared in the batch data by comparing it to other relevant work. 
confidence: Certain
Decision: Accept