Safe Collaborative Filtering

Riku Togashi, Tatsushi Oka, Naoto Ohsaka, Tetsuro Morimura

Most recommender systems optimize for the "average" user, often leaving those with the most challenging tastes—the "tail users"—with poor results and a high risk of churning. This paper introduces SAFER₂ (Smoothing Approach For Efficient Risk-averse Recommender), a scalable collaborative filtering algorithm that optimizes for Conditional Value at Risk (CVaR) to prioritize these less-satisfied users without sacrificing the computational efficiency needed for web-scale applications.

The Problem: The "Rich Get Richer" Effect in Recommender Systems

Standard collaborative filtering (CF) techniques typically rely on Empirical Risk Minimization (ERM). In plain English, they try to minimize the average error across all users. While this sounds logical, it creates a "rich get richer" effect for data: the system gets very good at predicting for users with common tastes but fails the tail users who are harder to satisfy. From a business perspective, these dissatisfied users are the most likely to disengage, posing a serious risk to user retention and platform growth.

Illustration of Conditional Value at Risk (CVaR) focusing on the tail of the loss distribution.

The mathematical tool to fix this is Conditional Value at Risk (CVaR), which focuses on the average loss of the worst-off users (the "tail" of the loss distribution). However, CVaR is notoriously difficult to use in large-scale recommendation systems. It involves non-smooth, non-linear functions that break the "separability" of standard algorithms. In a system with millions of items, you need to be able to update item embeddings in parallel; CVaR usually forces you to look at all items at once, creating a massive computational bottleneck.

Methodology: Bridging Risk-Aversion and Scalability

The authors propose SAFER₂ to bridge the gap between risk-averse optimization and web-scale scalability. Their approach relies on three key technical pillars:

  1. Convolution-type Smoothing: To handle the non-smooth "kink" in the CVaR objective, they use integral convolution with smooth functions (mollifiers). This makes the objective twice differentiable, allowing them to use efficient Newton-Raphson solvers.
  2. Primal-Dual Splitting: This is the "secret sauce" for scalability. By reformulating the problem into a saddle-point optimization using dual variables, they decouple the users and items. This restores separability, making the algorithm "embarrassingly parallelizable"—just like the industry-standard Implicit Alternating Least Squares (iALS).
  3. Smart Regularization: They develop a Tikhonov regularization strategy based on "condition numbers." This ensures numerical stability during the optimization process, which is often a headache when dealing with the weighted linear systems found in CF.

For extremely large models, the authors also introduce SAFER₂++, which uses subspace-based block coordinate descent to handle very high-dimensional user/item embeddings efficiently.

Experiments and Key Results

The researchers evaluated their method on three standard real-world benchmarks: MovieLens 1M (ML-1M), MovieLens 20M (ML-20M), and the Million Song Dataset (MSD). They used a "strong generalization" protocol, meaning the models were tested on entirely new users not seen during training.

Relative performance of SAFER₂ and baselines over iALS across different quantile levels on ML-20M and MSD datasets.
  • Superior Tail Performance: On all three datasets, SAFER₂ consistently outperformed iALS and Variational Autoencoders (Mult-VAE) for tail users (measured at lower quantiles like $\alpha = 0.3$). For example, on ML-20M, SAFER₂ showed a clear improvement in Recall@50 for the least-satisfied users.
  • Competitive Efficiency: Despite the more complex objective, SAFER₂’s runtime per epoch is nearly identical to iALS. On the ML-20M dataset, iALS took 3.16 seconds per epoch, while SAFER₂ took 3.45 seconds—a negligible overhead for a significant gain in robustness.
  • Robustness to Limited Data: SAFER₂ showed remarkable "average-case" performance even when it wasn't specifically trying to optimize for it, suggesting that the risk-averse approach provides a form of regularization that helps the model generalize better from limited interactions.

Key Insights and Limitations

One of the most elegant findings of the paper is the ERM-QE Decomposition: the smoothed CVaR objective can be decomposed into a standard ERM term plus a "smoothed quantile estimation" term. This highlights that "safety" is essentially a targeted correction applied to the average performance. Furthermore, the paper challenges the "average is king" mindset. By shifting the focus to the $\alpha$-quantile (e.g., the bottom 30% of users), they show you can significantly help the users who need it most while still maintaining competitive average scores.

Limitations and Future Work: While the algorithm performs well empirically, the paper lacks a formal theoretical convergence guarantee for the specific combination of convolution smoothing and primal-dual splitting used here. Additionally, the "bandwidth" parameter ($h$) for the smoothing kernel is a new hyperparameter that requires careful tuning. Finally, the current work focuses on static datasets; exploring how "safe" CF behaves in a dynamic production environment with a constant stream of new interactions remains an open question.

Summary updated

Abstract

Excellent tail performance is crucial for modern machine learning tasks, such as algorithmic fairness, class imbalance, and risk-sensitive decision making, as it ensures the effective handling of challenging samples within a dataset. Tail performance is also a vital determinant of success for personalized recommender systems to reduce the risk of losing users with low satisfaction. This study introduces a "safe" collaborative filtering method that prioritizes recommendation quality for less-satisfied users rather than focusing on the average performance. Our approach minimizes the conditional value at risk (CVaR), which represents the average risk over the tails of users' loss. To overcome computational challenges for web-scale recommender systems, we develop a robust yet practical algorithm that extends the most scalable method, implicit alternating least squares (iALS). Empirical evaluation on real-world datasets demonstrates the excellent tail performance of our approach while maintaining competitive computational efficiency.
BibTeX
@inproceedings{togashi2024safe,
  author = {Riku Togashi and Tatsushi Oka and Naoto Ohsaka and Tetsuro Morimura},
  title = {{Safe Collaborative Filtering}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=yarUvgEXq3},
}
Figure