# Online Matrix Completion: A Collaborative Approach with Hott Items

arXiv: https://arxiv.org/abs/2408.05843 · HTML: https://mlsanity.com/paper/2408.05843/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 11 Aug 2024.

## Builds on (most cited first, 26 of 26)

- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [Contextual Bandits with Latent Confounders: An NMF Approach](https://mlsanity.com/paper/1606.00119/) (2016)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Universal Matrix Completion](https://mlsanity.com/paper/1402.2324/) (2014)
- [Regret Guarantees for Item-Item Collaborative Filtering](https://mlsanity.com/paper/1507.05371/) (2015)
- [Bernoulli Rank-1 Bandits for Click Feedback](https://mlsanity.com/paper/1703.06513/) (2017)
- [A Latent Source Model for Online Collaborative Filtering](https://mlsanity.com/paper/1411.6591/) (2014)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [The Sample Complexity of Online One-Class Collaborative Filtering](https://mlsanity.com/paper/1706.00061/) (2017)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering](https://mlsanity.com/paper/1711.02198/) (2017)
- [Alternating Linear Bandits for Online Matrix-Factorization Recommendation](https://mlsanity.com/paper/1810.09401/) (2018)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information](https://mlsanity.com/paper/2003.07040/) (2020)
- [On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs](https://mlsanity.com/paper/2109.05408/) (2021)

## Abstract (arXiv)

We investigate the low rank matrix completion problem in an online setting with M users, N items, T rounds, and an unknown rank-r reward matrix R∈ ℝ^M× N. This problem has been well-studied in the literature and has several applications in practice. In each round, we recommend S carefully chosen distinct items to every user and observe noisy rewards. In the regime where M,N >> T, we propose two distinct computationally efficient algorithms for recommending items to users and analyze them under the benign hott items assumption.1) First, for S=1, under additional incoherence/smoothness assumptions on R, we propose the phased algorithm textscPhasedClusterElim. Our algorithm obtains a near-optimal per-user regret of tildeO(NM-1(Delta-1+Delta_hott-2)) where Delta_hott,Delta are problem-dependent gap parameters with Delta_hott >> Delta almost always. 2) Second, we consider a simplified setting with S=r where we make significantly milder assumptions on R. Here, we introduce another phased algorithm, textscDeterminantElim, to derive a regret guarantee of widetildeO(NM-1/rDeltadet-1)) where Delta_det is another problem-dependent gap. Both algorithms crucially use collaboration among users to jointly eliminate sub-optimal items for groups of users successively in phases, but with distinctive and novel approaches.