RSRG/DOLCIT Seminar

Similarity based collaborative filtering for matrix estimation is a popular heuristic that has been used widely across industry in the previous decades to build recommendation systems, due to its simplicity and scalability. However, despite its popularity, there has been little theoretical foundation explaining its widespread success. In this talk, I will present theoretical guarantees for collaborative filtering under a nonparametric latent variable model, which arises from the natural property of exchangeability'', i.e. invariance under relabeling of the dataset. The analysis suggests that similarity based collaborative filtering can be viewed as kernel regression for latent variable models, where the features are not directly observed, and the kernel must be estimated from the data. In addition, while classical collaborative filtering typically requires a dense dataset, I will introduce an iterative collaborative filtering algorithm which compares larger radius neighborhoods of data to compute similarities. Our results show that this estimate converges even for very sparse datasets, which has implications towards sparse graphon estimation. The algorithms can be applied in a variety of settings, such as recommendations for online markets, analysis of social networks, or denoising crowdsourced labels.