Online Matrix Completion: A Collaborative Approach with Hott Items

Abstract

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 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 PhasedClusterElim. Our algorithm obtains a near-optimal per-user regret of O(NM^-1(^-1+_hott^-2)) where _hott, are problem-dependent gap parameters with _hott >> 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, DeterminantElim, to derive a regret guarantee of O(NM^-1/r_det^-1)) where _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.

Tasks

Reproductions