Negative Sampling

Negative sampling is derived from Noise-Contrastive Estimation (NCE), which reframes the multi-class prediction problem as a binary logistic regression task. Instead of calculating scores for every possible output class, the model learns to distinguish a single positive target from a small set of noise samples drawn from a proposal distribution. This reduces the per-training-step complexity from O(|V|) to O(k+1), where k is the number of negative samples and |V| is the vocabulary size. The original word2vec implementation simplified NCE further by removing the normalization requirement, treating the objective as a pure binary classification between the observed context word and randomly sampled distractors.

Negative samples are drawn from a smoothed unigram distribution rather than uniformly. The probability of selecting a word as a negative is proportional to its frequency raised to the power of 3/4:

• Rare words get sampled more often than their raw frequency would suggest
• Frequent stop words get down-weighted to prevent them from dominating the negative set
• This power-law smoothing empirically produces better representations by balancing the signal across the vocabulary

The 3/4 exponent was discovered experimentally in word2vec and has become the de facto standard in embedding training pipelines, including GloVe and modern dense retrieval models.

Modern contrastive learning frameworks employ in-batch negatives to eliminate the need for a separate sampling step. Within a mini-batch of N pairs, each positive pair treats the other N-1 positive targets as negatives:

• Memory efficiency: No external negative bank or queue required
• Gradient coupling: All samples contribute to both positive and negative supervision simultaneously
• Batch size dependency: Larger batches provide more diverse negatives, improving the InfoNCE signal quality

This technique is foundational to SimCLR, CLIP, and dense retrieval models where batch sizes of 4096+ are common to ensure sufficient negative diversity.

Random negatives become insufficient as models converge. Hard negative mining selects distractors that are deceptively similar to the anchor but belong to different classes:

• Top-k ANN retrieval: Use the current model to find nearest neighbors and sample from high-similarity false positives
• Denoising heuristics: Filter out false negatives that share the same latent class as the anchor
• Adversarial generation: Synthesize negatives that maximize the current loss

In dense passage retrieval, hard negatives sourced from BM25 top results that don't contain the answer dramatically improve retrieval accuracy compared to random in-batch negatives alone.

The temperature parameter τ controls how sharply the model penalizes hard negatives in the contrastive loss. Lower temperatures (< 1.0) create a peakier distribution that heavily weights the hardest negatives, while higher temperatures smooth the penalty across all negatives:

• τ → 0: Model focuses almost exclusively on the single hardest negative
• τ → ∞: Uniform weighting, equivalent to treating all negatives equally
• Typical range: 0.07 to 0.5 for normalized embeddings

In NT-Xent loss (used by SimCLR), temperature tuning is critical—too low causes training instability, too high reduces discriminative power. The optimal value depends on batch size and embedding dimensionality.

Standard negative sampling introduces sampling bias when unlabeled negatives accidentally share the same semantic class as the anchor. This causes the model to incorrectly repel similar concepts. Debiased contrastive loss corrects for this by:

• Estimating the probability that a negative sample is actually a false negative
• Subtracting this bias term from the denominator of the softmax
• Preserving the repulsion only for true negatives while allowing semantically related concepts to remain proximal

This correction is essential for supervised contrastive learning where class labels are available, and for self-supervised settings where the data distribution contains many near-duplicate or highly similar instances.