Curse of "Low" Dimensionality in Recommender Systems

Naoto Ohsaka, Riku Togashi

Abstract

Standard practices in collaborative filtering often favor low-dimensional embeddings to prevent overfitting and minimize memory usage. However, this study demonstrates that low-rank dot-product models suffer from a fundamental "curse of low dimensionality." We provide theoretical and empirical evidence that insufficient dimensionality restricts the expressive power of models, leading to systemic popularity bias and a failure to discover long-tail items. By analyzing the geometry of embedding spaces, we show that increasing dimensionality is essential for achieving diversity, fairness, and robustness in recommendations.

Introduction

In the world of collaborative filtering, dot-product models like Matrix Factorization are the industry workhorses. Engineers typically choose relatively small embedding dimensions ($d$)—often between 50 and 200—to keep models compact and avoid overfitting sparse user data. However, there is a growing tension: while these low-rank models achieve decent accuracy on standard benchmarks, they often fail at diversity, fairness, and robustness. They tend to recommend the same popular items to most users, leading to anti-personalization. This research investigates whether this is a tuning issue or a fundamental mathematical limitation of low-dimensional geometry.

Theoretical Framework: The Expressivity Gap

The authors utilize 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 represent for a given dimension $d$.

Their proofs demonstrate that the number of possible rankings is exponentially bounded by the dimension. At low $d$, the model is mathematically "blind" to the vast majority of possible item permutations. This forces the model to settle on a few "safe" rankings, which almost always favor popular items. 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 popular items and identify niche matches for users.

Empirical Methodology

To test these theoretical insights, the researchers trained implicit Alternating Least Squares (iALS) models across a wide range of dimensions ($d$ from 8 up to 4,096) using three real-world datasets: MovieLens 20M, Million Song Dataset, and Epinions.

Beyond standard accuracy (Recall), the study measured:

  • Average Recommendation Popularity (ARP): To quantify popularity bias.
  • Catalog Coverage: To determine how many unique items are actually recommended across the user base.
  • Gini Index: To measure item fairness.
  • Feedback Loop Simulation: 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.

Key Findings

1. The Feedback "Death Spiral"

Low-dimensional models don't just perform poorly; they actively degrade future data. Because they only recommend popular items, users only interact with those items. This creates a biased dataset that makes the next version of the model even more obsessed with popularity. In simulations, a $d=64$ model's ability to collect data on long-tail items was abysmal compared to $d=256$, essentially "giving up" on diversity after just a few iterations.

2. 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. When plotting Accuracy vs. Diversity, high-dimensional models consistently formed a superior Pareto frontier.

3. Reducing Popularity Bias

In the MovieLens 20M dataset, models with low $d$ exhibited extremely high popularity bias. Increasing $d$ to 512 or 1024 significantly reduced this bias while maintaining or even improving accuracy. 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.

Limitations and Future Directions

The primary drawback of high dimensionality is computational cost. Traditional ALS solvers have a cubic complexity ($O(d^3)$), making $d > 1000$ a challenge for massive production environments. Additionally, higher dimensions increase the cost of Maximum Inner Product Search (MIPS) during real-time serving.

To move beyond simple accuracy and build truly diverse recommender systems, future work must explore sparse representations and more efficient high-rank solvers. This would allow systems to harness the benefits of high dimensionality without the prohibitive memory and compute overhead.

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},
}
Figure