Collaborative Filtering on a Budget

by Alexandros Karatzoglou, Alex Smola and Markus Weimer

This paper talks about dealing with large scale collaborative filtering. The collaborative filtering can be formulated as a matrix factorization problem and we may try several loss functions with different regularizer. One typical example is the M3F paper previously scanned here. A convenient solver is stochastic gradient descent.

The core idea proposed is we may use two hash functions (one for user and another for items recommended) to aggregate the user matrix and item matrix to eliminate the computational cost in large-scale problems. These matrices are approximated with the help of Rademacher functions. But I have no idea why this is possible. Maybe I will take a look some day later.