# On the Theories Behind Hard Negative Sampling for Recommendation

arXiv: https://arxiv.org/abs/2302.03472 · HTML: https://mlsanity.com/paper/2302.03472/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Builds on (most cited first, 21 of 21)

- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Bias and Debias in Recommender System: A Survey and Future Directions](https://mlsanity.com/paper/2010.03240/) (2020)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Fast Matrix Factorization for Online Recommendation with Implicit Feedback](https://mlsanity.com/paper/1708.05024/) (2017)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models](https://mlsanity.com/paper/1705.10513/) (2017)
- [On Sampling Strategies for Neural Network-based Collaborative Filtering](https://mlsanity.com/paper/1706.07881/) (2017)
- [DORO: Distributional and Outlier Robust Optimization](https://mlsanity.com/paper/2106.06142/) (2021)
- [Reinforced Negative Sampling over Knowledge Graph for Recommendation](https://mlsanity.com/paper/2003.05753/) (2020)
- [Adaptive Sampled Softmax with Kernel Based Sampling](https://mlsanity.com/paper/1712.00527/) (2017)
- [Boosting the Speed of Entity Alignment 10*: Dual Attention Matching Network with Normalized Hard Sample Mining](https://mlsanity.com/paper/2103.15452/) (2021)
- [Simplify and Robustify Negative Sampling for Implicit Collaborative Filtering](https://mlsanity.com/paper/2009.03376/) (2020)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Distributionally Robust Counterfactual Risk Minimization](https://mlsanity.com/paper/1906.06211/) (2019)
- [Adversarial Sampling and Training for Semi-Supervised Information Retrieval](https://mlsanity.com/paper/1811.04155/) (2018)
- [Word2Vec applied to Recommendation: Hyperparameters Matter](https://mlsanity.com/paper/1804.04212/) (2018)
- [A Generic Coordinate Descent Framework for Learning from Implicit Feedback](https://mlsanity.com/paper/1611.04666/) (2016)
- [Top Rank Optimization in Linear Time](https://mlsanity.com/paper/1410.1462/) (2014)
- [Cross Pairwise Ranking for Unbiased Item Recommendation](https://mlsanity.com/paper/2204.12176/) (2022)
- [A Modified AUC for Training Convolutional Neural Networks: Taking Confidence into Account](https://mlsanity.com/paper/2006.04836/) (2020)
- [CoSam: An Efficient Collaborative Adaptive Sampler for Recommendation](https://mlsanity.com/paper/2011.07739/) (2020)

## Built on by (most cited first, 18 of 18)

- [Plug-in Diffusion Model for Sequential Recommendation](https://mlsanity.com/paper/2401.02913/) (2024)
- [Double Correction Framework for Denoising Recommendation](https://mlsanity.com/paper/2405.11272/) (2024)
- [SPRec: Self-Play to Debias LLM-based Recommendation](https://mlsanity.com/paper/2412.09243/) (2024)
- [Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendation](https://mlsanity.com/paper/2403.00844/) (2024)
- [Improved Diversity-Promoting Collaborative Metric Learning for Recommendation](https://mlsanity.com/paper/2409.01012/) (2024)
- [Breaking the Top-K Barrier: Advancing Top-K Ranking Metrics Optimization in Recommender Systems](https://mlsanity.com/paper/2508.05673/) (2025)
- [Large Language Model Enhanced Hard Sample Identification for Denoising Recommendation](https://mlsanity.com/paper/2409.10343/) (2024)
- [Data and Context Matter: Towards Generalizing AI-based Software Vulnerability Detection](https://mlsanity.com/paper/2508.16625/) (2025)
- [Listwise Preference Alignment Optimization for Tail Item Recommendation](https://mlsanity.com/paper/2507.02255/) (2025)
- [Exploring Dataset-Scale Indicators of Data Quality](https://mlsanity.com/paper/2311.04016/) (2023)
- [Talos: Optimizing Top-K Accuracy in Recommender Systems](https://mlsanity.com/paper/2601.19276/) (2026)
- [Towards Reliable Negative Sampling for Recommendation with Implicit Feedback via In-Community Popularity](https://mlsanity.com/paper/2602.18759/) (2026)
- [Causal Negative Sampling via Diffusion Model for Out-of-Distribution Recommendation](https://mlsanity.com/paper/2508.07243/) (2025)
- [Hard vs. Noise: Resolving Hard-Noisy Sample Confusion in Recommender Systems via Large Language Models](https://mlsanity.com/paper/2511.07295/) (2025)
- [STARS: Semantic Tokens with Augmented Representations for Recommendation at Scale](https://mlsanity.com/paper/2512.10149/) (2025)
- [Correct and Weight: A Simple Yet Effective Loss for Implicit Feedback Recommendation](https://mlsanity.com/paper/2601.04291/) (2026)
- [TFPS: A Temporal Filtration-enhanced Positive Sample Set Construction Method for Implicit Collaborative Filtering](https://mlsanity.com/paper/2602.22521/) (2026)
- [Don't Contrast the Impossible: Region-Constrained Batching for Contrastive User Modeling on a Local Community Platform](https://mlsanity.com/paper/2607.28971/) (2026)

## Abstract (arXiv)

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.