Regret Guarantees for Item-Item 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.
