Negative Sampling

In a catalog of millions of items, a user typically clicks on fewer than 0.01% of available options. Training on all unclicked items as negatives would require computing and updating gradients for millions of examples per positive instance. Negative sampling reduces this to a fixed small set—typically 4 to 256 negatives per positive—slashing the computational complexity from O(N) to O(K) where K is a constant. This transforms an intractable full-softmax problem into a practical binary classification task, enabling real-time model updates on consumer-scale datasets.

The choice of sampling distribution critically impacts model quality. Common strategies include:

• Uniform Sampling: Randomly selects negatives, but over-samples irrelevant items that are easy to classify, providing little learning signal.
• Popularity-Based Sampling: Selects negatives proportional to their empirical frequency in the data, correcting for the natural exposure bias where popular items appear more often.
• Unigram Distribution: Raises item frequencies to the power of 3/4, striking a balance between uniform and popularity-based sampling, as popularized by word2vec.
• In-Batch Negatives: Reuses positive items from other examples in the same mini-batch as negatives, maximizing hardware utilization with zero additional sampling cost.

Because negative sampling deliberately distorts the true data distribution, models must apply mathematical corrections to produce calibrated probability estimates. The standard approach applies a correction term to the logits: subtract log(Q) where Q is the probability of sampling that item. Without this correction, the model systematically overestimates click probabilities. In production systems like YouTube's recommendation engine, this correction is applied during inference to recover unbiased ranking scores from the sampled training objective, ensuring that the final CTR predictions remain well-calibrated.

Random negatives are often too easy for the model to classify, providing minimal gradient signal. Hard negative mining deliberately selects items that the model currently ranks highly but which the user did not engage with—items that are plausible but incorrect. Techniques include:

• Online Hard Negative Mining: During training, score all in-batch items and select the highest-scoring non-clicked items as negatives.
• Offline Pre-selection: Use a separate retrieval model to generate a candidate pool of near-miss items. This strategy forces the model to learn fine-grained distinctions between genuinely relevant and superficially similar items, significantly improving ranking precision.

Negative sampling is closely related to Noise Contrastive Estimation (NCE), a statistical technique that transforms a multi-class classification problem into a binary classification task by learning to distinguish true data samples from artificially generated noise. The key distinction: NCE is an asymptotically consistent estimator that converges to the true softmax distribution with enough noise samples, while negative sampling is a heuristic approximation that prioritizes learning high-quality item embeddings over strict probabilistic correctness. In practice, negative sampling often outperforms NCE for representation learning tasks where the goal is ranking quality rather than likelihood estimation.

Modern CTR systems like Deep Retrieval and YouTube DNN combine negative sampling with two-tower architectures, where separate neural networks encode users and items into a shared embedding space. During training, the user tower processes the query, the item tower encodes positive and sampled negative items, and a dot-product or cosine similarity computes relevance scores. The loss function—typically sampled softmax loss—only updates the embeddings of the positive item and the sampled negatives, leaving the vast majority of item embeddings untouched per batch. This decoupling enables training on billion-scale catalogs where full-softmax computation would be impossible.

The statistical framework from which negative sampling is derived. NCE reframes the classification problem into a binary logistic regression task: distinguishing true data samples from noise samples drawn from a known distribution.

• Core Idea: Instead of computing a full softmax over millions of items, the model learns by contrasting positive examples against a small set of artificially generated negative examples.
• Mathematical Basis: Approximates the log-probability of the true data distribution by learning a density ratio between the data and noise distributions.
• Key Distinction: Standard NCE requires the noise distribution to be normalized, while Negative Sampling simplifies this by dropping the normalization constant, making it a computationally cheaper approximation.

The primary computational bottleneck that negative sampling solves. In a full softmax, the gradient must update the embedding vector for every single item in the catalog on every training step.

• Weight Matrix: An embedding table of size V x D where V is vocabulary size (often millions) and D is embedding dimension.
• Sparse Gradient Update: Negative sampling converts a dense O(V*D) matrix multiplication into a sparse update touching only K+1 rows, where K is the number of negative samples.
• GPU Memory: This sparse access pattern allows the massive embedding tables to be stored in CPU RAM or SSD, with only the active rows fetched to GPU memory during training.

Information Noise Contrastive Estimation loss, the dominant objective function in self-supervised contrastive learning. It treats the positive pair as the single true class and all other instances in the batch as negatives.

• Formula: -log( exp(sim(q, k+)/τ) / Σ exp(sim(q, ki)/τ) ) where τ is a temperature parameter controlling concentration.
• Temperature: A low τ creates a sharper distribution, heavily penalizing hard negatives, while a high τ smooths the distribution.
• Relevance: Directly connects the negative sampling concept from supervised CTR prediction to modern representation learning frameworks like SimCLR and MoCo.