Online Matrix Completion: A Collaborative Approach with Hott Items

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.