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.
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.
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