Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We consider an online model for recommendation systems, with each user being recommended an item at each time-step and providing 'like' or 'dislike' feedback. A latent variable model specifies the user preferences: both users and items are clustered into types. The model captures structure in both the item and user spaces, as used by item-item and user-user collaborative filtering algorithms. We study the situation in which the type preference matrix has i.i.d. entries.

An important aspect of real-world recommendation systems is that each recommendation impacts what is learned about the users and items, which in turn determines the possible accuracy of future recommendations. This introduces a tension between exploring to obtain information and exploiting existing knowledge to make good recommendations.

Our main contribution is an algorithm that simultaneously uses both item and user structures in exploration phase, proved to be near-optimal via corresponding information-theoretic lower bounds. In particular, our analysis highlights the sub-optimality of using only one of item or user structure (as is done in most collaborative filtering algorithms).

(Joint work with Guy Bresler)