On the Theories Behind Hard Negative Sampling for Recommendation

Abstract

Negative sampling has been heavily used to train recommender models on large-scale data, wherein sampling hard examples usually not only accelerates the convergence but also improves the model accuracy. Nevertheless, the reasons for the effectiveness of Hard Negative Sampling (HNS) have not been revealed yet. In this work, we fill the research gap by conducting thorough theoretical analyses on HNS. Firstly, we prove that employing HNS on the Bayesian Personalized Ranking (BPR) learner is equivalent to optimizing One-way Partial AUC (OPAUC). Concretely, the BPR equipped with Dynamic Negative Sampling (DNS) is an exact estimator, while with softmax-based sampling is a soft estimator. Secondly, we prove that OPAUC has a stronger connection with Top-K evaluation metrics than AUC and verify it with simulation experiments. These analyses establish the theoretical foundation of HNS in optimizing Top-K recommendation performance for the first time. On these bases, we offer two insightful guidelines for effective usage of HNS: 1) the sampling hardness should be controllable, e.g., via pre-defined hyper-parameters, to adapt to different Top-K metrics and datasets; 2) the smaller the $K$ we emphasize in Top-K evaluation metrics, the harder the negative samples we should draw. Extensive experiments on three real-world benchmarks verify the two guidelines.

arXiv commentAccepted by WWW'2023; Code is available at https://github.com/swt-user/WWW_2023_code

References in corpus (12)

• BPR: Bayesian Personalized Ranking from Implicit Feedback
• IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models
• Reinforced Negative Sampling over Knowledge Graph for Recommendation
• Bias and Debias in Recommender System: A Survey and Future Directions
• Boosting the Speed of Entity Alignment 10*: Dual Attention Matching Network with Normalized Hard Sample Mining
• Adversarial Sampling and Training for Semi-Supervised Information Retrieval
• Simplify and Robustify Negative Sampling for Implicit Collaborative Filtering
• Top Rank Optimization in Linear Time
• Word2Vec applied to Recommendation: Hyperparameters Matter
• Large-Scale Methods for Distributionally Robust Optimization
• On the Consistency of AUC Pairwise Optimization
• When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee

Cited by in corpus (8)

• Augmented Negative Sampling for Collaborative Filtering
• SPRec: Self-Play to Debias LLM-based Recommendation
• Unlocking the Hidden Treasures: Enhancing Recommendations with Unlabeled Data
• Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendation
• Breaking the Top-$K$ Barrier: Advancing Top-$K$ Ranking Metrics Optimization in Recommender Systems
• Improved Estimation of Ranks for Learning Item Recommenders with Negative Sampling
• Evaluating and Addressing Fairness Across User Groups in Negative Sampling for Recommender Systems
• Don't Contrast the Impossible: Region-Constrained Batching for Contrastive User Modeling on a Local Community Platform