Timezone: »

Online Reciprocal Recommendation with Theoretical Performance Guarantees
Claudio Gentile · Nikos Parotsidis · Fabio Vitale

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #137

A reciprocal recommendation problem is one where the goal of learning is not just to predict a user's preference towards a passive item (e.g., a book), but to recommend the targeted user on one side another user from the other side such that a mutual interest between the two exists. The problem thus is sharply different from the more traditional items-to-users recommendation, since a good match requires meeting the preferences of both users. We initiate a rigorous theoretical investigation of the reciprocal recommendation task in a specific framework of sequential learning. We point out general limitations, formulate reasonable assumptions enabling effective learning and, under these assumptions, we design and analyze a computationally efficient algorithm that uncovers mutual likes at a pace comparable to those achieved by a clairvoyant algorithm knowing all user preferences in advance. Finally, we validate our algorithm against synthetic and real-world datasets, showing improved empirical performance over simple baselines.

Author Information

Claudio Gentile (INRIA)
Nikos Parotsidis (University of Rome Tor Vergata)
Fabio Vitale (Sapienza University of Rome)

More from the Same Authors