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:
- Tightness Proofs: Comparing the "tightness" of bounds for full-batch losses.
- Equivalence Analysis: Proving that with exactly one negative sample ($K=1$), BPR and CCE are functionally identical.
- 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.
- 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