Sublinear Time Recommendation Algorithms

Abstract

We consider the problem of making personalized recommendations from lim- ited user data, modeled within the framework of assortment optimization under a random utility choice model. Motivated by settings such as online advertising where the space of items is massive and recommendation decisions need to be made almost instantaneously, we propose the first sublinear time algorithm for the problem, and show that it achieves a constant factor approximation under general choice models. Our algorithm relies on solving a generalization of the nearest neighbor problem, for which we develop a solution using an efficient sampling scheme built from locality-sensitive hash functions. We demonstrate the effectiveness of our approach on a large scale, real-world dataset.

Date
Event
INFORMS Annual Meeting, 2020 (virtual); INFORMS Annual Meeting, 2017, Houston (USA); INFORMS Revenue Management & Pricing Section Conference, 2017, Amsterdam (Netherlands); 5th ISB-POMS Workshop, 2017, Hyderabad (India)