Curse of "Low" Dimensionality in Recommender Systems

Naoto Ohsaka, Riku Togashi

TL;DR

While low-dimensional embeddings are often used in recommender systems to prevent overfitting and save memory, this paper argues they suffer from a "curse of low dimensionality." The authors prove that low-rank dot-product models are mathematically limited in their expressive power, leading to systemic popularity bias and a "self-biased feedback loop" that prevents the discovery of long-tail items.

What Problem Does This Paper Address?

In the world of collaborative filtering, dot-product models (like Matrix Factorization) are the workhorses of the industry. Engineers typically choose a relatively small embedding dimension ($d$)—often between 50 and 200—to keep the model "compact" and avoid overfitting sparse user data.

However, the authors point out a growing tension: while these low-rank models might achieve decent accuracy on standard benchmarks, they often fail at diversity, fairness, and robustness. They tend to recommend the same popular items to everyone (anti-personalization). This paper investigates whether this isn't just a tuning issue, but a fundamental mathematical limitation of low-dimensional geometry.

Methods

The authors combine empirical experiments with rigorous theoretical analysis:

  • Empirical Evaluation: They trained implicit Alternating Least Squares (iALS) models across a wide range of dimensions ($d$ from 8 up to 4,096) on three major datasets.
  • Metric Analysis: Beyond standard accuracy (Recall), they measured ARP (Average Recommendation Popularity), Catalog Coverage (how many unique items are actually recommended), and Gini Index (item fairness).
  • Simulation of Feedback Loops: They created a "training-observation loop" where a model’s own recommendations become the training data for the next iteration, simulating how a deployed system evolves over time.
  • Theoretical Proofs: They used the geometry of hyperplane arrangements and convex hulls to provide upper and lower bounds on the number of unique rankings a dot-product model can actually represent for a given dimension $d$.

Datasets

The study utilized three standard real-world datasets, binarized for implicit feedback:

  1. MovieLens 20M (ML-20M): A classic movie recommendation dataset.
  2. Million Song Dataset (MSD): A large-scale music discovery dataset.
  3. Epinions: A consumer review dataset with a focus on long-tail interactions.

Key Insights and Ideas

  • The Exponential Expressivity Gap: The authors prove that the number of possible rankings a model can produce is exponentially bounded by the dimension $d$. At low $d$, the model is "blind" to the vast majority of possible item permutations, forcing it to settle on a few "safe" (popular) rankings.
  • Popularity as a Geometric Shadow: Theoretically, popular items create a "convex cone" in the embedding space. In low dimensions, this cone is massive, effectively "shadowing" long-tail items. As $d$ increases, the space expands, allowing the model to "see" around the popular items and find niche matches for users.
  • The "Curse" is a Feedback Loop: Low-dimensional models don't just perform poorly; they actively degrade future data. Because they only recommend popular items, users only interact with popular items. This creates a biased dataset that makes the next version of the model even more obsessed with popularity—a death spiral for diversity.
  • Accuracy is a Deceptive Metric: The paper shows that two models can have nearly identical Recall scores, but the high-dimensional model will have significantly better catalog coverage and fairness. Choosing $d$ based on accuracy alone ignores these long-term "hidden" side effects.

Key Results

  • Popularity Bias: In ML-20M, models with low $d$ exhibited extremely high popularity bias (ARP). Increasing $d$ to 512 or 1024 significantly reduced this bias while maintaining or improving accuracy.
  • Pareto Frontiers: When plotting Accuracy vs. Diversity, high-dimensional models consistently formed a superior Pareto frontier. A model with $d=4096$ could achieve diversity levels that were mathematically impossible for a model with $d=64$, regardless of how other hyperparameters were tuned.
  • Data Collection Efficiency: In the feedback loop simulation, the $d=64$ model's ability to collect data on a variety of items (item recall) was abysmal compared to $d=256$. The low-rank model essentially "gave up" on the long-tail after just a few iterations.

Limitations and Future Work

  • Computational Cost: The primary drawback of high dimensionality is the cubic complexity ($O(d^3)$) of traditional ALS solvers. While the authors used a block coordinate descent solver to mitigate this, scaling to $d > 1000$ remains a challenge for massive production environments.
  • Serving Latency: Higher dimensions increase the cost of Maximum Inner Product Search (MIPS) during real-time serving.
  • Future Directions: The authors suggest exploring sparse representations to get the benefits of high dimensionality without the memory/compute overhead, and developing more efficient solvers specifically designed for high-rank recommendation tasks.

Summary updated

Abstract

Beyond accuracy, there are a variety of aspects to the quality of recommender systems, such as diversity, fairness, and robustness. We argue that many of the prevalent problems in recommender systems are partly due to low-dimensionality of user and item embeddings, particularly when dot-product models, such as matrix factorization, are used.In this study, we showcase empirical evidence suggesting the necessity of sufficient dimensionality for user/item embeddings to achieve diverse, fair, and robust recommendation. We then present theoretical analyses of the expressive power of dot-product models. Our theoretical results demonstrate that the number of possible rankings expressible under dot-product models is exponentially bounded by the dimension of item factors. We empirically found that the low-dimensionality contributes to a popularity bias, widening the gap between the rank positions of popular and long-tail items; we also give a theoretical justification for this phenomenon.
BibTeX
@inproceedings{ohsaka2023curse,
  author = {Naoto Ohsaka and Riku Togashi},
  title = {{Curse of "Low" Dimensionality in Recommender Systems}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2023},
  doi = {10.1145/3539618.3591659},
}

Loading related content...

Figure