# A Tale of Two Efficient and Informative Negative Sampling Distributions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2020.

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

- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Hard Negative Sampling via Regularized Optimal Transport for Contrastive Representation Learning](https://mlsanity.com/paper/2111.03169/) (2021)
- [iACOS: Advancing Implicit Sentiment Extraction with Informative and Adaptive Negative Examples](https://mlsanity.com/paper/2311.03896/) (2023)
- [Variational Information Pursuit with Large Language and Multimodal Models for Interpretable Predictions](https://mlsanity.com/paper/2308.12562/) (2023)
- [Fast Gauss-Newton for Multiclass Cross-Entropy](https://mlsanity.com/paper/2605.06081/) (2026)

## Abstract (arXiv)

Softmax classifiers with a very large number of classes naturally occur in many applications such as natural language processing and information retrieval. The calculation of full softmax is costly from the computational and energy perspective. There have been various sampling approaches to overcome this challenge, popularly known as negative sampling (NS). Ideally, NS should sample negative classes from a distribution that is dependent on the input data, the current parameters, and the correct positive class. Unfortunately, due to the dynamically updated parameters and data samples, there is no sampling scheme that is provably adaptive and samples the negative classes efficiently. Therefore, alternative heuristics like random sampling, static frequency-based sampling, or learning-based biased sampling, which primarily trade either the sampling cost or the adaptivity of samples per iteration are adopted. In this paper, we show two classes of distributions where the sampling scheme is truly adaptive and provably generates negative samples in near-constant time. Our implementation in C++ on CPU is significantly superior, both in terms of wall-clock time and accuracy, compared to the most optimized TensorFlow implementations of other popular negative sampling approaches on powerful NVIDIA V100 GPU.