Negative Sampling

Instead of computing gradients over the entire output vocabulary—which can reach millions of items—negative sampling updates only K+1 output vectors per training step (1 positive + K negatives). This reduces the per-step complexity from O(V) to O(K), where V is the vocabulary size and K is typically between 5 and 20.

• Training speedup: 100x to 10,000x for million-scale catalogs
• GPU memory savings: Only a fraction of the output embedding matrix is accessed
• Batch throughput: Enables larger batch sizes by eliminating the softmax bottleneck

The noise distribution from which negative samples are drawn critically impacts model quality. Common strategies include:

• Uniform distribution: Simple but ignores item popularity, often underperforming
• Unigram distribution: Samples proportional to item frequency in the training corpus
• Smoothed unigram: Raises frequencies to the 3/4 power to dampen the dominance of head items while still sampling popular negatives more often
• In-batch negatives: Reuses other positive items in the same batch as negatives, enabling zero-overhead sampling in two-tower architectures

The choice of distribution balances gradient signal quality against the risk of sampling too many easy negatives that provide no learning signal.

Negative sampling is a simplified variant of Noise-Contrastive Estimation, a statistical principle that reframes density estimation as a binary classification problem. The model learns to distinguish genuine data samples from those drawn from a known noise distribution.

• Original NCE: Preserves the proportionality between learned scores and true data probabilities
• Simplified negative sampling: Drops the theoretical normalization constraint for practical speed, treating the task as discriminating positive pairs from randomly corrupted ones
• InfoNCE loss: A modern formulation used in contrastive learning that treats the positive pair as the correct classification among a set of negative distractors

This binary classification framing makes the loss function numerically stable and avoids the expensive denominator computation of full softmax.

Random negatives are computationally cheap but often too easy—the model quickly learns to trivially separate them from positives, providing zero gradient signal. Hard negative mining selects negatives that the current model scores highly, forcing more discriminative learning:

• Online mining: Within each batch, select the highest-scoring negatives from a larger candidate pool
• Offline mining: Periodically run the current model over the full catalog to identify and cache confusing items
• Mixed strategy: Combine random negatives for coverage with hard negatives for decision boundary refinement
• Item frequency correction: Apply importance sampling weights to correct for the sampling bias introduced by non-uniform negative selection

Hard negatives are especially critical in dense embedding spaces where many items cluster near decision boundaries.

When negatives are drawn from a non-uniform distribution, the model's predicted scores become biased toward the sampling distribution. Without correction, popular items sampled as negatives more frequently receive artificially deflated scores.

• Importance weighting: Multiply each negative's loss contribution by the inverse of its sampling probability
• Log-Q correction: Subtract the log of the sampling probability from the model's output logit before computing the loss
• Batch-level correction: Apply a shared correction factor across all negatives in a batch when using frequency-based sampling

Proper bias correction ensures that the model's ranking order remains calibrated, which is essential for downstream retrieval tasks where items compete globally rather than within a single sampled set.

A highly efficient strategy for two-tower retrieval models where negatives are sourced from other positive examples within the same training batch. Each user-item pair in a batch of size B treats the other B-1 items as negatives.

• Zero sampling overhead: No separate negative generation step required
• Batch size dependency: Larger batches provide more and harder negatives, directly improving retrieval quality
• Popularity bias risk: Popular items appear more frequently as positives, causing them to be sampled as negatives more often—requires log-Q correction to debias
• Cross-batch memory: Advanced implementations maintain a memory bank of embeddings from recent batches to expand the effective negative pool beyond the current batch

This technique is foundational to modern YouTube-style candidate generation and large-scale product retrieval systems.

The statistical framework from which negative sampling is derived. NCE transforms a multi-class classification problem into a binary classification task by learning to distinguish the true data distribution from a noise distribution. Unlike the simplified negative sampling loss popularized by word2vec, full NCE preserves the theoretical property of converging to the true softmax probabilities as the number of noise samples increases. The key insight is that the partition function is treated as a learnable parameter rather than being explicitly computed.

A general training acceleration technique that sub-samples the output layer during gradient computation. Instead of updating all output classes, only the positive target and a small subset of sampled candidates receive weight updates. This umbrella term encompasses multiple strategies:

• Sampled Softmax: Re-weights logits to approximate full softmax
• Negative Sampling: Simplified loss without exact probability correction
• Importance Sampling: Biases sample selection toward high-loss candidates All methods reduce per-batch computation from O(|V|) to O(K) where K is the sample size.

A memory-efficient strategy that reuses positive items from other examples in the same mini-batch as negatives for the current query. This eliminates the need for a separate negative sampling step entirely. Common in two-tower retrieval models and contrastive learning, the technique scales negative count with batch size automatically. However, it introduces a popularity bias: frequently occurring items appear more often as negatives, potentially pushing their embeddings away from all queries. Mitigation requires corrective sampling probabilities or debiasing loss functions.

The deliberate selection of difficult negative examples that the model currently scores highly but are not relevant. Random negatives are often too easy, providing negligible gradient signal. Hard negatives—items semantically close to the positive but incorrect—force the model to learn fine-grained decision boundaries. Common mining strategies include:

• Online mining: Select highest-scoring non-positives from current batch
• Offline mining: Pre-compute nearest neighbors via ANN index
• Mix strategy: Blend hard negatives with random negatives to maintain embedding space uniformity

A training objective that corrects for the sampling bias introduced by candidate selection. Unlike vanilla negative sampling, sampled softmax applies a logit correction term that subtracts the log of the sampling probability Q from each candidate's score. This ensures the gradient approximates the true softmax gradient in expectation. The correction is critical when the sampling distribution is non-uniform. The full formula: logit_corrected = logit - log(Q(item)). Without this correction, the model learns a distorted probability distribution biased toward frequently sampled items.

A self-supervised paradigm where negative sampling is the defining mechanism. The model learns representations by pulling positive pairs (augmentations of the same data point) together in embedding space while pushing negative pairs (different data points) apart. Frameworks like SimCLR and MoCo differ primarily in how they manage negatives:

• SimCLR: Uses large batches for in-batch negatives
• MoCo: Maintains a momentum-encoded queue of negative representations
• BYOL: Eliminates explicit negatives entirely via asymmetric architectures The quality and quantity of negatives directly determine representation quality.