Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization
This provides a theoretical foundation for efficient recommender systems using comparison data, which is incremental as it extends existing matrix completion techniques to a new feedback model.
The paper tackles the problem of learning personalized recommendations from sparse pairwise comparison data by analyzing a nonconvex matrix factorization model, showing that gradient-based methods converge exponentially fast near the true solution with provable guarantees.
This paper provides a theoretical analysis of a new learning problem for recommender systems where users provide feedback by comparing pairs of items instead of rating them individually. We assume that comparisons stem from latent user and item features, which reduces the task of predicting preferences to learning these features from comparison data. Similar to the classical matrix factorization problem, the main challenge in this learning task is that the resulting loss function is nonconvex. Our analysis shows that the loss function exhibits (restricted) strong convexity near the true solution, which ensures gradient-based methods converge exponentially, given an appropriate warm start. Importantly, this result holds in a sparse data regime, where each user compares only a few pairs of items. Our main technical contribution is to extend certain concentration inequalities commonly used in matrix completion to our model. Our work demonstrates that learning personalized recommendations from comparison data is computationally and statistically efficient.