Comparing Recommendation Losses under Negative Sampling

Giulia Di Teodoro, Federico Siciliano, Nicola Tonellotto, Fabrizio SilvestriIIR 2025

Introduction

In recommender systems (RS), a persistent "objective mismatch" exists between the proxy loss functions used during training and the ranking metrics used for evaluation. While models are typically optimized using Categorical Cross-Entropy (CCE), Binary Cross-Entropy (BCE), or Bayesian Personalized Ranking (BPR), they are evaluated using metrics such as Normalized Discounted Cumulative Gain (NDCG) or Mean Reciprocal Rank (MRR).

Furthermore, the massive scale of modern item catalogs necessitates the use of negative sampling—training on a small subset of non-interacted items. This paper provides a unified theoretical framework to bridge the gap between these sampled losses and downstream ranking performance, establishing formal connections and identifying the most effective surrogate objectives.

Theoretical Framework

The authors derive equivalences and bounds for major loss functions under negative sampling, specifically examining how they upper-bound the negative log of NDCG.

The $K=1$ Equivalence

A significant theoretical finding is that when exactly one negative item is sampled ($K=1$), BPR and CCE become mathematically identical. In this specific case, optimizing either loss function results in the same parameter updates, suggesting that the choice between them is irrelevant at the lowest sampling limit.

BCE as the Tightest Surrogate

The study proves that BCE offers the tightest theoretical bound on NDCG among the three losses. Mathematically, the hierarchy of bounds is established as follows: the probability that the negative log of NDCG is bounded by the BCE loss is greater than or equal to the same probability for BPR, which is in turn greater than or equal to that for CCE. This confirms BCE as the most theoretically sound proxy for ranking, as it "tracks" the ranking objective more closely than BPR or CCE, particularly as the number of negative samples increases.

Experimental Results

The theoretical findings were validated across five benchmark datasets (MovieLens-1M, Amazon-Beauty, Amazon-Books, Yelp, and Foursquare NYC) using various architectures, including Matrix Factorization, SASRec, and LightGCN.

The Negative Sampling Trade-off

The experiments quantify a clear trade-off regarding the number of negative samples ($K$). Using fewer negatives (e.g., $K=1$ or $5$) facilitates faster improvements in the early stages of training. Conversely, a larger number of negatives (e.g., $K=100$) results in a slower initial learning phase but ultimately leads to a significantly higher performance ceiling.

Impact of negative sample size (K) on NDCG@10 for BCE-GRU4Rec.

Empirical Performance of Loss Functions

In alignment with the theoretical hierarchy, BCE consistently demonstrated superior final performance, especially when paired with a high number of negative samples. On datasets like Foursquare, while CCE often showed greater stability during the early-to-mid phases of training, the theoretical tightness of BCE suggests it as the superior long-term objective for maximizing ranking accuracy.

Comparison of BCE, BPR, and CCE loss functions on the Foursquare dataset.

Conclusion

This research clarifies the relationship between training objectives and ranking metrics in recommender systems. By proving that BCE provides the tightest bound on NDCG and identifying the trade-offs inherent in negative sampling, the authors provide a rigorous foundation for selecting loss functions. Future work remains to extend this framework to non-uniform "hard" negative sampling and to further explore the optimization dynamics of gradient descent across these different loss landscapes.

Summary updated

BibTeX
@inproceedings{teodoro2025comparing,
  author = {Giulia Di Teodoro and Federico Siciliano and Nicola Tonellotto and Fabrizio Silvestri},
  title = {{Comparing Recommendation Losses under Negative Sampling}},
  booktitle = {IIR},
  year = {2025},
}
Figure