Adaptive matrix completion for the users and the items in tail

Mohit Sharma, George KarypisWWW 2019 · DOI · arXiv

Introduction: The Challenge of the Long Tail

Most modern recommender systems rely on Matrix Completion, specifically Low-Rank Matrix Factorization (MF). These models assume that the underlying user-item rating matrix can be approximated by a small number of latent factors representing preferences and item characteristics. However, a significant limitation of standard MF is the assumption of uniform rating distribution. In practice, real-world data is highly skewed: a small number of "blockbuster" items receive the majority of ratings, while the vast "tail" of items and users remains sparsely represented.

The authors identify a critical failure mode: as model complexity (rank) increases to capture nuances in popular items, the model begins to "hallucinate" patterns in the tail where data is insufficient. This localized overfitting leads to poor recommendations for the very users and items that most need accurate discovery.

Proposed Adaptive Methods

To address this, the paper introduces four "frequency-aware" techniques designed to dynamically adjust model complexity:

  1. Frequency Adaptive Rating Prediction (FARP): Trains multiple models with varying ranks and selects the appropriate model based on the frequency quartile of the target user or item.
  2. Truncated Matrix Factorization (TMF): A single-model approach where the number of active latent dimensions is a dynamic function (sigmoid) of frequency. Tail items use fewer dimensions, while popular items utilize the full latent space.
  3. TMF + Dropout: Regularizes TMF by probabilistically selecting the number of active ranks from a Poisson distribution during training, acting as a form of structural regularization.
  4. Inverse Frequency Weighted Matrix Factorization (IFWMF): Modifies the loss function to penalize errors on infrequent entities more heavily, forcing the model to prioritize tail accuracy during the optimization process.

Datasets and Experimental Setup

The methods were evaluated across four major benchmarks. Subsampling was applied to the Yahoo Music and Netflix sets to simulate the extreme power-law distributions found in real-world e-commerce settings.

Table 1: Statistics of the datasets used in the evaluation.

Key Insights: The Rank-Frequency Trade-off

The central discovery of this work is that for infrequent items, less is more. While a high-rank model (e.g., rank-50) might be optimal for a popular movie, a low-rank model (e.g., rank-1 or rank-5) is often more accurate for obscure titles because it prevents the model from fitting to noise.

Figure 1: Impact of model rank on RMSE for frequent vs. infrequent items and users on MovieLens.

As shown in Figure 1, for infrequent items (red line), RMSE increases sharply as the rank increases beyond a very small value. In contrast, frequent items (blue line) maintain stable or improving performance with higher ranks. This confirms that overfitting in matrix completion is localized to low-density regions of the matrix, rather than being a global phenomenon.

Results and Performance

The proposed adaptive methods consistently outperformed standard MF and state-of-the-art local methods like LLORMA:

  • Tail Accuracy: On the Flixster dataset, the proposed methods improved RMSE for tail items by up to 53% and for tail users by up to 8%.
  • Global Performance: Even when looking at the entire dataset, the TMF and FARP models achieved lower overall error than standard approaches, proving that frequency-awareness does not come at the cost of popular item accuracy.
  • Efficiency: TMF + Dropout and FARP were particularly effective at achieving high accuracy with fewer total parameters, suggesting that "frequency-awareness" is a highly efficient regularizer.

Conclusion and Future Directions

This research highlights the necessity of dynamic model complexity in recommendation. By treating the latent factor vector as a hierarchy—where general features are captured first and niche features are added only when data permits—we can significantly improve discovery in the long tail. Future work could explore integrating these adaptive techniques with content-based filtering to address the "cold-start" problem (items with zero ratings) and optimizing the computational overhead for massive-scale production environments.

Summary updated

BibTeX
@inproceedings{sharma2019adaptive,
  author = {Mohit Sharma and George Karypis},
  title = {{Adaptive matrix completion for the users and the items in tail}},
  booktitle = {The Web Conference},
  year = {2019},
  doi = {10.1145/3308558.3313736},
}
Figure