Negative Sampling

In standard recommendation training, computing the cross-entropy loss requires normalizing over the entire item catalog—potentially millions of items. This requires a dot product between the user embedding and every item embedding, followed by a softmax. The gradient must then update every item vector, making training on billion-scale catalogs computationally prohibitive. Negative sampling transforms this into a binary classification task between the true positive pair and a small set of randomly sampled negatives.

Popularized by the Word2Vec framework, SGNS treats the problem as learning to distinguish observed user-item pairs from randomly generated ones. The objective maximizes the probability of the positive pair while minimizing it for k negative samples drawn from a noise distribution. Key properties:

• k is typically 5–20 for large datasets
• The noise distribution is often a unigram distribution raised to the 3/4th power to balance frequent and rare items
• Each training step updates only 1 + k item embeddings instead of the full vocabulary

A highly efficient variant that reuses other positive items within the same mini-batch as negatives for a given query. For a batch of size B, each query gets B-1 negatives for free, requiring no additional sampling or embedding lookups. This technique is foundational to modern two-tower retrieval models. The trade-off is a selection bias toward popular items that appear more frequently in batches, which can be corrected with log-Q correction or mixed negative strategies.

Random negatives are easy to classify and provide weak gradients. Hard negatives—items that are similar to the positive but not actually interacted with—push the model to learn finer-grained distinctions. Strategies include:

• Offline mining: Pre-computing high-scoring but unclicked items using a previous model checkpoint
• Online mining: Dynamically selecting negatives with the highest current model scores within a batch
• Mixed strategies: Combining random negatives for coverage with hard negatives for decision boundary refinement

The theoretical foundation of negative sampling. NCE frames density estimation as a discriminative proxy task: distinguishing data samples from samples drawn from a known noise distribution. Unlike standard negative sampling, NCE provides a consistent estimator of the true softmax distribution when the number of noise samples approaches infinity. In practice, the simplified negative sampling loss used in most implementations drops the theoretical guarantees but works remarkably well for representation learning.

The distribution from which negatives are drawn introduces bias into the learned embeddings. Without correction, popular items are pushed down more frequently, distorting the embedding space. Correction techniques include:

• Log-Q correction: Subtracting the log-probability of the negative under the sampling distribution from the model score
• Importance sampling: Weighting negatives inversely by their sampling probability
• Uniform sampling: Using a uniform distribution over items, which is unbiased but computationally expensive for retrieval

The theoretical framework from which negative sampling is derived. NCE transforms the multinomial classification problem into a binary classification task: distinguishing true data samples from noise samples drawn from a known distribution.

• Key insight: Instead of computing the full softmax over all classes, the model learns by contrasting positive pairs against a small set of noise samples
• Difference from negative sampling: NCE preserves the mathematical properties of maximum likelihood estimation, while negative sampling simplifies the objective to a logistic regression-style loss
• Origin: Proposed by Gutmann and Hyvärinen (2010) for estimating unnormalized statistical models

The original word2vec architecture that popularized negative sampling for learning distributed word representations. The model predicts surrounding context words given a target word, using negative sampling to avoid computing probabilities over the entire vocabulary.

• Training objective: Maximize the probability of true context words while minimizing the probability of randomly sampled negative words
• Efficiency gain: With 5–20 negative samples per positive example, training scales linearly with corpus size rather than vocabulary size
• Adopted by Item2Vec: The same principle applies to recommendation systems where user sessions are treated as sentences and items as words

A training efficiency technique that reuses other positive items within the same mini-batch as negatives for a given query, eliminating the need for a separate negative sampling step.

• How it works: For a batch of N user-item pairs, each item serves as a positive for its paired user and a negative for all other N-1 users in the batch
• Advantage: Zero additional computation for negative selection, as the item embeddings are already computed for the forward pass
• Bias trade-off: Popular items appear more frequently as in-batch negatives, introducing a sampling bias that can be corrected with log-Q correction or mixed sampling strategies
• Common in: Two-tower retrieval models and contrastive learning frameworks like SimCLR

A broader class of training approximations that evaluate the loss function on only a subset of all possible output classes rather than the full output space.

• Includes: Negative sampling, sampled softmax, and noise contrastive estimation
• Critical for: Training classifiers with millions of output classes where full softmax computation is intractable
• TensorFlow implementation: tf.nn.sampled_softmax_loss and tf.nn.nce_loss provide built-in candidate sampling for large-scale recommendation models
• Trade-off: Faster training at the cost of noisier gradient estimates, mitigated by increasing the number of sampled candidates

The probability distribution used to draw negative samples, which significantly impacts model quality. The standard approach raises item frequencies to the power of 0.75 to smooth the distribution.

• Uniform sampling: Simple but produces weak negatives that don't help the model learn fine-grained distinctions
• Unigram distribution: Samples proportional to item frequency, but over-samples popular items as negatives, causing the model to overly penalize them
• Smoothed distribution (P^0.75): Empirically found to balance the representation of rare and frequent items, giving rare items a higher chance of being sampled as negatives
• Hard negative mining: Intentionally sampling items that the current model scores highly but are not true positives, forcing the model to learn sharper decision boundaries

The retrieval infrastructure that makes negative sampling practical at inference time. After training embeddings with negative sampling, ANN indices enable sub-linear search over billion-scale embedding corpora.

• HNSW: Builds a multi-layered navigable graph achieving logarithmic search complexity
• Product Quantization (PQ): Compresses embeddings by decomposing the vector space into subspaces, reducing memory by 10–30x
• Connection to training: The same cosine similarity used in ANN retrieval is learned during training via negative sampling objectives
• Production stack: FAISS, ScaNN, and Annoy are widely deployed libraries that serve embeddings trained with negative sampling