Online Matrix Completion: A Collaborative Approach with Hott Items

Dheeraj Baby, Soumyabrata Pal
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:2248-2276, 2024.

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∈RM×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+Δ−2hott)) 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Δ−1det)) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-baby24a, title = {Online Matrix Completion: A Collaborative Approach with Hott Items}, author = {Baby, Dheeraj and Pal, Soumyabrata}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {2248--2276}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/baby24a/baby24a.pdf}, url = {https://proceedings.mlr.press/v235/baby24a.html}, 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}\in \mathbb{R}^{{M}\times {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 $\tilde{O}({N}{M}^{-1}(\Delta^{-1}+\Delta_{\text{hott}}^{-2}))$ where $\Delta_{\text{hott}},\Delta$ are problem-dependent gap parameters with $\Delta_{\text{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, DeterminantElim, to derive a regret guarantee of $\tilde{O}({N}{M}^{-1/r}\Delta_\text{det}^{-1}))$ where $\Delta_{\text{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.} }
Endnote
%0 Conference Paper %T Online Matrix Completion: A Collaborative Approach with Hott Items %A Dheeraj Baby %A Soumyabrata Pal %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-baby24a %I PMLR %P 2248--2276 %U https://proceedings.mlr.press/v235/baby24a.html %V 235 %X 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}\in \mathbb{R}^{{M}\times {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 $\tilde{O}({N}{M}^{-1}(\Delta^{-1}+\Delta_{\text{hott}}^{-2}))$ where $\Delta_{\text{hott}},\Delta$ are problem-dependent gap parameters with $\Delta_{\text{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, DeterminantElim, to derive a regret guarantee of $\tilde{O}({N}{M}^{-1/r}\Delta_\text{det}^{-1}))$ where $\Delta_{\text{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.
APA
Baby, D. & Pal, S.. (2024). Online Matrix Completion: A Collaborative Approach with Hott Items. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:2248-2276 Available from https://proceedings.mlr.press/v235/baby24a.html.

Related Material