Regret Guarantees for Item-Item Collaborative Filtering
This work addresses the need for efficient and effective recommendation algorithms in online settings, particularly for cold-start scenarios, but it appears incremental as it builds on existing collaborative filtering frameworks.
The paper tackles the problem of online binary matrix completion in recommendation systems by analyzing an item-item collaborative filtering algorithm, showing it achieves fundamentally better performance and good cold-start performance for new users compared to user-user collaborative filtering.
There is much empirical evidence that item-item collaborative filtering works well in practice. Motivated to understand this, we provide a framework to design and analyze various recommendation algorithms. The setup amounts to online binary matrix completion, where at each time a random user requests a recommendation and the algorithm chooses an entry to reveal in the user's row. The goal is to minimize regret, or equivalently to maximize the number of +1 entries revealed at any time. We analyze an item-item collaborative filtering algorithm that can achieve fundamentally better performance compared to user-user collaborative filtering. The algorithm achieves good "cold-start" performance (appropriately defined) by quickly making good recommendations to new users about whom there is little information.