Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Online Matrix Completion: A Collaborative Approach with Hott Items
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies online low-rank matrix completion with many users and items under a hott-items (separability) assumption, proposing PhasedClusterElim (S=1) and DeterminantElim (S=r) with sublinear per-user regret guarantees.
Problem
Online collaborative filtering / matrix completion with bandit feedback where M, N >> T; the goal is to minimize per-user regret while learning a rank-r reward matrix, improving on greedy algorithms whose gap dependence is Δ^-2.
Approach
Relies on a hott-items (separability) assumption so users cluster by best item; uses opinionated users as labels to assign overlapping user groups, then jointly eliminates items per group in phases with matrix completion sub-routines. For S=r, eliminates r-column subsets by estimating determinant-based averages.
Key results
- PhasedClusterElim (S=1) achieves per-user regret Õ(NM^-1(Δ^-1+Δ_hott^-2)) under hott items and incoherence assumptions, improving on the greedy Δ^-2 dependence.
- DeterminantElim (S=r) achieves regret Õ(σ²N/(c_avg c_max M^{1/r} Δ_det)) under only non-negative embeddings and hott-item assumptions.
- On a synthetic instance (M=N=200, r=4, T=300), the simplified PhasedElimSimplified incurs lower cumulative regret than AM and ETC with exploration 25, 50, 75.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PhasedElimSimplified instead of Alternating Minimization or Explore-Then-Commit | Online matrix completion · Synthetic, M=200, N=200, rank 4, T=300 | cumulative regret | Helped |
| Use PhasedElimSimplified instead of Explore-Then-Commit with 25 exploration rounds | Online matrix completion · Synthetic, M=200, N=200, rank 4, T=300 | regret per round | Helped |
| Increase Explore-Then-Commit exploration period from 25 to 50 or 75 rounds | Explore-Then-Commit · Synthetic, M=200, N=200, rank 4, T=300 | exploitation regret per round | Helped |
| Increase Explore-Then-Commit exploration period from 25 to 50 or 75 rounds | Explore-Then-Commit · Synthetic, M=200, N=200, rank 4, T=300 | exploration cost | Hurt |
Surprising findings
- The natural item-elimination strategy (intersecting candidate sets within clusters) can fail for non-opinionated users, motivating the expansion step.
Limitations
- Regret bounds depend quadratically on Δ_hott^-1 and exponentially in rank for run-time.
- Relies on matrix completion oracle with incoherence and condition-number assumptions that may not hold for sub-matrices.
- Experiments are small, synthetic, and only compare against AM and ETC.
Experimental setup
Datasets: synthetic low-rank reward matrices (M=200, N=200, r=4, T=300)
Benchmarks: synthetic low-rank reward matrix
Metrics: cumulative regret per-round regret
Baselines: Alternating Minimization (AM) Explore-Then-Commit (ETC)
Builds on: explore-then-commit alternating minimization for online matrix completion nuclear norm matrix completion
Closest papers by meaning
- Online Low Rank Matrix Completion (ICLR 2023 · similarity 0.93)
- Mixture Matrix Completion (NeurIPS 2018 · similarity 0.88)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.86)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.85)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.85)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.