Low-regret Recommendations

Tuesday, October 20, 2015 - 10:15am - 11:05am
Keller 3-180
Devavrat Shah (Massachusetts Institute of Technology)
Collaborative filtering is a popular solution for designing recommendation systems such as that suggesting you which movie to watch on Netflix or which product to buy on Amazon. There are two prominent versions of collaborative filtering algorithm. One, user-user where a user is recommended an item that is liked by other similar users. Two, item-item where a user a recommended an item that is similar to the other items s/he liked in past. There is much empirical evidence that item-item collaborative filtering works much better in practice compared to user-user.

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.

Based on a joint work with Guy Bresler and Luis Voloch.
MSC Code: 
93E 11