There are two main paradigms in neighborhood-based collaborative filtering: the user-user paradigm and the item-item paradigm. In the user-user paradigm, to recommend items to a user, one first looks for similar users (a common measure of similarity is the so-called cosine similarity), and then recommends items liked by those similar users. In the item-item paradigm, to recommend items to a user, one first looks for items similar to items that the user has liked, and then recommends those similar items.

There is much empirical evidence that the item-item paradigm is more practical and works better in many cases (see Linden, Smith, and York [2003], Koren and Bell [2011]). We provide the theoretical justification to support this empirical observation by analyzing the item-item paradigm in a statistical decision theoretic framework. The performance loss or regret under the item-item collaborative filtering, along with appropriate exploration-exploitation, primarily depends on the 'item space dimensionality' rather than scaling with number of items or users.

This is based on joint work with Guy Bresler and Luis Voloch.