Online Low Rank Matrix Completion

Prateek Jain, Soumyabrata Pal

Abstract

We investigate the problem of online low-rank matrix completion involving $M$ users and $N$ items over $T$ interaction rounds. In each round, the algorithm recommends one item per user and receives a noisy reward based on a low-rank preference matrix. Traditional multi-armed bandit (MAB) approaches fail to exploit the correlations between users and items, leading to poor regret performance. We demonstrate that the underlying low-rank structure can be leveraged to achieve sub-linear regret with nearly optimal dependence on $M$ and $N$. We introduce a simple Explore-Then-Commit (ETC) strategy achieving $O(T^{2/3})$ regret and a more sophisticated algorithm, OCTAL (Online Collaborative filTering using iterAtive user cLustering), which achieves a nearly optimal regret of $O(T^{1/2})$ in the rank-1 setting. Our results show that collaborative filtering can significantly reduce the exploration required for effective recommendations.

Introduction

Modern recommendation systems face the daunting task of matching millions of users with millions of items. In an online setting, where preferences must be learned through sequential interactions, the efficiency of the learning process is paramount. Standard "multi-armed bandit" (MAB) algorithms treat every item as an independent arm. However, if a system has 100,000 items but only 100 rounds to make recommendations, a standard MAB approach learns almost nothing useful, resulting in "vacuous" regret.

The key to overcoming this bottleneck lies in the observation that user preferences are not independent; they are highly correlated. These correlations allow us to model the reward structure as a low-rank matrix. For instance, if two users share a preference for a specific genre, their reactions to other items in that genre are likely to be similar. Exploiting this low-rank structure in an online environment is challenging due to the non-convex nature of the low-rank manifold, which complicates real-time updates as new data arrives.

Algorithmic Frameworks

Explore-Then-Commit (ETC)

As a baseline for exploiting low-rank structure, we first consider the Explore-Then-Commit (ETC) approach. This strategy operates in two distinct phases:

  1. Exploration: The algorithm recommends items at random to all users for a fixed number of rounds. This data is used to construct an initial estimate of the reward matrix using standard offline matrix completion techniques.
  2. Commitment: For all remaining rounds, the algorithm recommends the item estimated to have the highest reward for each user.

While ETC is straightforward and achieves a regret of $O(T^{2/3})$—outperforming independent bandit models—it is inherently sub-optimal because it does not refine its estimates during the commitment phase.

OCTAL: Iterative User Clustering

To achieve better performance, we propose OCTAL (Online Collaborative filTering using iterAtive user cLustering). Specifically optimized for the rank-1 setting, OCTAL uses a phased approach where the length of each phase increases exponentially. In each phase, the algorithm performs three critical tasks:

  • Matrix Refinement: It updates the estimate of the latent preference matrix using all accumulated data.
  • User Clustering: Users are grouped into clusters based on their latent representations. In a rank-1 scenario, this often involves identifying users with similar polarities of preference.
  • Item Elimination: Based on cluster-level feedback, the algorithm identifies and discards items that are statistically unlikely to be optimal for a given cluster.

This phased, "anytime" structure allows OCTAL to transition from exploration to exploitation more fluidly than ETC, leading to a nearly optimal minimax regret rate of $O(T^{1/2})$.

Empirical Evaluation

We evaluated our algorithms using synthetic data and three prominent real-world datasets: MovieLens 1M, Jester (joke ratings), and Book-Crossing. These datasets represent varying scales of users and items, providing a robust testbed for collaborative filtering.

Our experiments revealed several key insights:

  • Regret Efficiency: OCTAL consistently outperformed both the ETC approach and the standard Upper Confidence Bound (UCB) algorithm. UCB, which ignores the low-rank structure, suffered from high regret as it attempted to explore the item space for each user individually.
  • Scalability: A crucial theoretical and practical advantage of our methods is that regret depends only logarithmically on the number of items ($N$). This ensures that the algorithms remain performant even as the item catalog grows to massive scales.
  • Cold Start Mitigation: By sharing information across users, OCTAL mitigates the "cold start" problem. It requires significantly fewer recommendations per user to begin providing high-quality suggestions compared to non-collaborative methods.

Conclusion and Future Work

This work demonstrates that online low-rank matrix completion is not only theoretically viable but also practically superior to independent bandit models. By utilizing iterative clustering and item elimination, the OCTAL algorithm achieves the theoretical lower bound for regret in the rank-1 setting.

Future research will focus on generalizing the phased clustering approach of OCTAL to general rank-$r$ settings. While the current version performs well on real-world data (which often features a dominant top singular value), a formal extension to higher ranks remains an open challenge. Additionally, exploring more complex noise models beyond simple additive or stochastic noise will further improve the robustness of these algorithms in non-stationary real-world environments.

Summary updated

Abstract

We study the problem of {\em online} low-rank matrix completion with $\mathsf{M}$ users, $\mathsf{N}$ items and $\mathsf{T}$ rounds. In each round, the algorithm recommends one item per user, for which it gets a (noisy) reward sampled from a low-rank user-item preference matrix. The goal is to design a method with sub-linear regret (in $\mathsf{T}$) and nearly optimal dependence on $\mathsf{M}$ and $\mathsf{N}$. The problem can be easily mapped to the standard multi-armed bandit problem where each item is an {\em independent} arm, but that leads to poor regret as the correlation between arms and users is not exploited. On the other hand, exploiting the low-rank structure of reward matrix is challenging due to non-convexity of the low-rank manifold. We first demonstrate that the low-rank structure can be exploited using a simple explore-then-commit (ETC) approach that ensures a regret of $O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{2/3})$. That is, roughly only $\mathsf{polylog} (\mathsf{M}+\mathsf{N})$ item recommendations are required per user to get a non-trivial solution. We then improve our result for the rank-$1$ setting which in itself is quite challenging and encapsulates some of the key issues. Here, we propose \textsc{OCTAL} (Online Collaborative filTering using iterAtive user cLustering) that guarantees nearly optimal regret of $O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{1/2})$. OCTAL is based on a novel technique of clustering users that allows iterative elimination of items and leads to a nearly optimal minimax rate.
BibTeX
@inproceedings{jain2023online,
  author = {Prateek Jain and Soumyabrata Pal},
  title = {{Online Low Rank Matrix Completion}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=47KG_AvNqeZ},
}
Figure