Negative Sampling Strategies

The Catalog Scale Bottleneck

In recommendation systems and retrieval models, catalog size $N$ is massive ($10\text{ Million items}$ on Amazon, YouTube, or Spotify).

If we train a Two-Tower model using standard Softmax:

$$P(i \mid u) = \frac{\exp(u^T v_i)}{\sum_{j=1}^N \exp(u^T v_j)}$$

Calculating the Softmax denominator requires computing 10 Million dot products for every single training sample!

  Full Softmax:    Compute 10,000,000 dot products per sample!  ──► IMPOSSIBLE FOR PRODUCTION!
  Negative Sample: Compute 1 Positive + 100 Negative items!     ──► FAST & SCALABLE!

Negative Sampling replaces full catalog Softmax with an approximate loss function (Sampled Softmax, BPR, InfoNCE) evaluated over a small subset of Negative Items.

Negative Sampling Strategies

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ 1. UNIFORM RANDOM        │ 2. IN-BATCH NEGATIVES    │ 3. HARD NEGATIVE MINING  │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Draw negative items      │ Reuse positive items of  │ Sample items that score  │
│ uniformly at random from │ OTHER users in the same  │ high dot products but    │
│ the full catalog.        │ mini-batch.              │ were NOT clicked (DNS).  │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

1. Uniform Random Sampling

Draw $K$ negative items uniformly at random from the catalog.

• Pros: Computationally simple.
• Cons (Easy Negatives Problem): Most random items are completely obvious non-matches (e.g. recommending a tractor to a user looking for iPhone cases). The model receives zero gradient signal and fails to learn subtle decision boundaries.

2. In-Batch Negatives (Two-Tower Standard)

Given a mini-batch of $B$ user-item pairs ${(u_1, v_1), (u_2, v_2), \dots, (u_B, v_B)}$:

For User 1 ($u_1$), treat Item 1 ($v_1$) as the Positive Item, and treat Items $v_2, v_3, \dots, v_B$ from other users as Negative Items!

  Batch Matrix Multiplication (B x B):
                   Item 1 (Pos)   Item 2 (Neg)   Item 3 (Neg)
  User 1 (u1)  ┌     +3.2           -1.1           -0.4     ┐
  User 2 (u2)  │     -0.8           +4.1           -1.5     │
  User 3 (u3)  └     -1.2           -0.9           +2.8     ┘

• Pros: Highly efficient $B \times B$ GPU matrix multiplication.
• Popularity Bias Fix: Naturally samples popular items as negatives more frequently (proportional to item frequency in training batches). Apply log correction $\log P(i)$ to correct for sampling bias.

3. Hard Negative Mining (Dynamic Negative Sampling / DNS)

Select negative items that the current model incorrectly ranks with high similarity scores:

$$\text{Hard Negative } i^* = \arg\max_{i \in \text{Unclicked}} \left( u^T v_i \right)$$

• Pros: Provides strong non-zero gradient signals, forcing the model to learn fine-grained feature boundaries.
• Cons (False Negative Risk): Sampling hard un-clicked items risks accidentally sampling a True Positive item that the user simply hasn't discovered yet.

Say this out loud

Negative Sampling replaces full catalog Softmax by evaluating loss over a small subset of negative items. Uniform random sampling produces easy negatives with zero gradients. In-batch negatives reuse positive items from other users in the mini batch for fast GPU matrix multiplication. Hard negative mining selects high scoring un clicked items to force fine grained decision boundary learning.

Followups to expect

1. What is Bayesian Personalized Ranking (BPR Loss)? A pairwise ranking loss function $\mathcal{L}_{\text{BPR}} = -\log \sigma(u^T v_i - u^T v_j)$ that forces positive item score $u^T v_i$ to be higher than un-observed negative item score $u^T v_j$.
2. How do you prevent False Negatives in Hard Negative Mining? Filter candidate hard negatives using margin bounds or ensemble consensus, ensuring selected hard negatives do not belong to the same fine category as the positive item.