A Theoretical Analysis of Recommendation Loss Functions under Negative Sampling

Giulia Di Teodoro, Federico Siciliano, Nicola Tonellotto, Fabrizio Silvestri

TL;DR

This paper provides the first formal theoretical proof that Categorical Cross Entropy (CCE) is the tightest surrogate for ranking metrics like NDCG when using all negative items. However, the authors reveal a twist: when using negative sampling, these bounds become probabilistic, and Binary Cross Entropy (BCE) surprisingly offers the strongest worst-case bound, explaining why it often performs well in the later stages of training.

What Problem Does This Paper Address?

In Recommender Systems (RS), we want to maximize ranking metrics like Normalized Discounted Cumulative Gain (NDCG) or Mean Reciprocal Rank (MRR). The problem? These metrics are discrete and non-differentiable—you can't run gradient descent on them directly.

To get around this, researchers use "surrogate" loss functions:

  • BCE (Binary Cross Entropy): Treats every item interaction as an independent "yes/no" classification.
  • BPR (Bayesian Personalized Ranking): A pairwise approach that tries to score a positive item higher than a negative one.
  • CCE (Categorical Cross Entropy): A multi-class approach that looks at the probability distribution across all items.

While empirical evidence often suggests CCE is superior, we’ve lacked a rigorous theoretical framework explaining why—especially when we use negative sampling (training on a tiny subset of items to save computation). This paper bridges that gap, connecting these common losses to the ranking metrics they are meant to optimize.

Methods

The authors employ formal mathematical analysis to establish lower bounds. They prove that these losses act as surrogates for NDCG and MRR by showing that minimizing the loss is equivalent to maximizing a lower bound of the ranking metric.

Key methodological contributions include:

  1. Tightness Proofs: Comparing the "tightness" of bounds for full-batch losses.
  2. Equivalence Analysis: Proving that with exactly one negative sample ($K=1$), BPR and CCE are functionally identical.
  3. Probabilistic Bounding: Since negative sampling introduces randomness, the authors use hypergeometric distributions to calculate the probability that a sampled loss remains a valid bound for the true rank.
  4. Worst-Case Analysis: They examine the "edge cases" to see which loss remains the most reliable when sampling is involved.

Datasets

The theoretical findings were validated using four different model architectures (SASRec, GRU4Rec, NCF, and LightGCN) across five diverse real-world datasets:

  • MovieLens-1M: The classic movie rating benchmark.
  • Amazon Beauty & Amazon Books: Product reviews from the e-commerce giant.
  • Foursquare NYC: Location-based check-in data.
  • Yelp: Business reviews and user interactions.

Key Insights and Ideas

  • CCE is the "Full-Batch" King: When you can afford to calculate scores for every single item in the catalog, CCE is theoretically the best surrogate because it provides the tightest bound on NDCG. It "aligns" most closely with the metric.
  • The $K=1$ Paradox: If you only sample one negative item per positive interaction, BPR and CCE are mathematically the same. This simplifies the choice for engineers working with very sparse sampling.
  • The Sampling "Catch": Once you start sampling, you lose the guarantee that minimizing loss improves your rank. Instead, you get a probabilistic guarantee. The paper shows that as you increase the number of negative samples ($K$), the probability of the loss being a "good" bound increases.
  • BCE’s Late-Game Strength: In worst-case sampled scenarios, BCE actually provides a stronger bound than CCE or BPR. This explains the "BCE plateau": BCE often starts training slowly (especially with many negative samples) but can eventually surpass other losses as the model matures.

Key Results

  • Empirical Validation: Experiments confirmed that CCE generally leads to faster convergence and more stable training across different datasets.
  • Negative Sample Impact: For BCE, using more negative samples ($K=100$ vs $K=1$) significantly slows down early training (creating a performance plateau) but eventually leads to a higher final NDCG.
  • Model Consistency: The theoretical hierarchy (CCE > BPR > BCE for full loss) held up well in practice, though the "probabilistic" nature of sampling meant that BCE could occasionally "win" in the final epochs of training on specific datasets like MovieLens-1M.

Limitations and Future Work

The authors acknowledge a few key boundaries to their study:

  • Uniform Sampling Only: The current proofs assume negative items are sampled uniformly. In practice, many systems use "hard negative mining" or popularity-biased sampling, which would require a different probabilistic analysis.
  • Target Score Assumption: The analysis assumes the score for the "positive" item is non-negative ($s_+ \geq 0$). While usually true late in training, it might not hold during the very first few iterations.
  • Single-User Focus: The proofs focus on a single user's ranking. Extending this to a multi-user scenario—where an item might be positive for User A but negative for User B—remains an open (and complex) mathematical challenge.

For those interested in the proofs or the implementation, the authors have released their code and supplementary material on GitHub.

Summary updated

Abstract

Loss functions like Categorical Cross Entropy (CCE), Binary Cross Entropy (BCE), and Bayesian Personalized Ranking (BPR) are commonly used in training Recommender Systems (RSs) to differentiate positive items - those interacted with by users - and negative items. While prior works empirically showed that CCE outperforms BCE and BPR when using the full set of negative items, we provide a theoretical explanation for this by proving that CCE offers the tightest lower bound on ranking metrics like Normalized Discounted Cumulative Gain (NDCG) and Mean Reciprocal Rank (MRR), followed by BPR and BCE. However, using the full set of negative items is computationally infeasible for large-scale RSs, prompting the use of negative sampling techniques. Under negative sampling, we reveal that BPR and CCE are equivalent when a single negative sample is drawn, and all three losses converge to the same global minimum. We further demonstrate that the sampled losses remain lower bounds for NDCG (MRR), albeit in a probabilistic sense. Our worst-case analysis shows that BCE offers the strongest bound on NDCG (MRR). Experiments on five datasets and four models empirically support these theoretical findings. Our code and supplementary material are available at https://github.com/federicosiciliano/recsys_losses.git.
BibTeX
@inproceedings{teodoro2025theoretical,
  author = {Giulia Di Teodoro and Federico Siciliano and Nicola Tonellotto and Fabrizio Silvestri},
  title = {{A Theoretical Analysis of Recommendation Loss Functions under Negative Sampling}},
  booktitle = {IJCNN},
  year = {2025},
  doi = {10.1109/ijcnn64981.2025.11228603},
}
Figure