Pasteris, S; Vitale, F; Herbster, M; Gentile, C; Panisson, A; (2024) Adversarial Online Collaborative Filtering. In: Vernade, C and Hsu, D, (eds.) Proceedings of The 35th International Conference on Algorithmic Learning Theory. (pp. pp. 945-971). Proceedings of Machine Learning Research (PMLR): La Jolla, CA, USA.

Preview

Text pasteris24a.pdf - Published Version Download (556kB) | Preview

Abstract

We investigate the problem of online collaborative filtering under no-repetition constraints, whereby users need to be served content in an online fashion and a given user cannot be recommended the same content item more than once. We start by designing and analyzing an algorithm that works under biclustering assumptions on the user-item preference matrix, and show that this algorithm exhibits an optimal regret guarantee, while being fully adaptive, in that it is oblivious to any prior knowledge about the sequence of users, the universe of items, as well as the biclustering parameters of the preference matrix. We then propose a more robust version of this algorithm which operates with general matrices. Also this algorithm is parameter free, and we prove regret guarantees that scale with the amount by which the preference matrix deviates from a biclustered structure. To our knowledge, these are the first results on online collaborative filtering that hold at this level of generality and adaptivity under no-repetition constraints. Finally, we complement our theoretical findings with simple experiments on real-world datasets aimed at both validating the theory and empirically comparing to standard baselines. This comparison shows the competitive advantage of our approach over these baselines.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item