Low Regret Recommendations and Item-Item Collaborative Filtering
summary
Shows that a simple item-item collaborative filtering algorithm (nearest-neighbor style with explicit explore/exploit and a never-repeat constraint) gets provable performance when items are iid from a distribution of binary like vectors with finite doubling dimension D. Cold-start time scales with the inverse liked-item fraction (≈1/μ) and does not grow with number of users; cumulative per-user regret becomes sublinear with exponent roughly (D+1)/(D+2) and then transitions to a lower linear slope depending on user count. Empirical MovieLens plots show blocky item types consistent with the model.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:27Recommendation system
- 5:12Which algorithm to use?
- 6:47Model and objective
- 11:22Collaborative gain
- 12:03Structure in data
- 12:47Structure: item space dimension
- 20:59Performance of item-item CF
- 23:05Summary
related talks
58mRecommender Systems – A Walkthrough
37mA primer on recommendation systems.
33mPicking What to Watch Next: Build a Recommendation System
48mCollective Intelligence
41mRecommender Systems: Crafting Effective Personalised Experiences
32mLet's talk about Recommendation Systems!
23mML-Powered Search & Recommendation 101
20mBuilding Recommender system