Nonparametric Preference Completion

In the preference completion problem, there is a pool of items and a pool of users. Each user rates a subset of the items and the goal is to recover the personalized ranking of each user over all of the items. This problem is fundamental to recommender systems, arising in tasks such as movie recommendation and news personalization. A common approach is to first estimate the ratings through either a matrix completion estimator or a neighborhood-based method and to output personalized rankings from the estimated ratings [13, 26, 17, 2]. Recent research has observed a number of shortcomings of this approach [25, 15]; for example, many ratings-oriented algorithms minimize the RMSE, which does not necessarily produce a good ranking [5]. This observation has sparked a number of proposals of algorithms that aim to directly recover the rankings [25, 15, 16, 19, 18, 8]. Although these ranking-oriented algorithms have strong empirical performance, there are few theoretical guarantees to date and they all make specific distributional assumptions (discussed in more detail below). In this paper, we consider a statistical framework for nonparametric preference completion.