Collaborative Filtering (CF) is a common approach for recommender systems, which utilize information from many users' prior preferences. In particular, a matrix-based approach, which attempts to predict by fitting a low-rank or low-norm matrix to the observed data, has proven highly effective in modern CF tasks, such as the Netflix challenge. In this talk, I will outline two recent contributions in this direction. The first is a simple and principled algorithm to find a low-rank solution to large-scale convex optimization problems, such as those encountered in CF. The second is the development of online learning algorithms for CF, which can potentially provide very strong guarantees under minimal assumptions on the users' behavior. Moreover, the unique nature of CF hinders the application of standard online learning techniques, and requires some fundamentally new approaches which might be of independent interest.
Based on joint works with Nicolò Cesa-Bianchi, Alon Gonen, Sasha Rakhlin, Shai Shalev-Shwartz and Karthik Sridharan.