Adversarial Online Collaborative Filtering

• URL: http://arxiv.org/abs/2302.05765v3
• Date: Tue, 22 Oct 2024 13:31:16 GMT
• Title: Adversarial Online Collaborative Filtering
• Authors: Stephen Pasteris, Fabio Vitale, Mark Herbster, Claudio Gentile, Andre' Panisson,
• Abstract summary: We investigate the problem of online collaborative filtering under no-repetition constraints. We design and analyze an algorithm that works under biclustering assumptions on the user-item preference matrix. We show that this algorithm exhibits an optimal regret guarantee, while being fully adaptive.
• Score: 20.931533714651376
• License:
• 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.

Related papers

• Adaptively Learning to Select-Rank in Online Platforms [34.258659206323664]
  This research addresses the challenge of adaptively ranking items from a candidate pool for heterogeneous users. We develop a user response model that considers diverse user preferences and the varying effects of item positions. Experiments conducted on both simulated and real-world datasets demonstrate our algorithm outperforms the baseline.
  arXiv  Detail & Related papers  (2024-06-07T15:33:48Z)
• Oracle Efficient Algorithms for Groupwise Regret [7.840453701379554]
  We show that a simple modification of the sleeping experts technique of [Blum & Lykouris] yields an efficient reduction to the well-understood problem of diminishing external regret absent group considerations. We find that uniformly across groups, our algorithm gives substantial error improvements compared to running a standard online linear regression algorithm with no groupwise regret guarantees.
  arXiv  Detail & Related papers  (2023-10-07T02:17:22Z)
• Overcoming Prior Misspecification in Online Learning to Rank [4.665041704405341]
  We propose and analyze adaptive algorithms that address the requirement for the prior to match the true prior. We also consider scalar relevance feedback on top of click feedback. We demonstrate the efficacy of our algorithms using both synthetic and real-world experiments.
  arXiv  Detail & Related papers  (2023-01-25T15:48:00Z)
• Fast online ranking with fairness of exposure [29.134493256287072]
  We show that our algorithm is computationally fast, generating rankings on-the-fly with computation cost dominated by the sort operation, memory efficient, and has strong theoretical guarantees. Compared to baseline policies that only maximize user-side performance, our algorithm allows to incorporate complex fairness of exposure criteria in the recommendations with negligible computational overhead.
  arXiv  Detail & Related papers  (2022-09-13T12:35:36Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise. First-order guarantees are relatively well understood in statistical and online learning. We show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees.
  arXiv  Detail & Related papers  (2021-07-05T19:20:34Z)
• The Stereotyping Problem in Collaboratively Filtered Recommender Systems [77.56225819389773]
  We show that matrix factorization-based collaborative filtering algorithms induce a kind of stereotyping. If preferences for a textitset of items are anti-correlated in the general user population, then those items may not be recommended together to a user. We propose an alternative modelling fix, which is designed to capture the diverse multiple interests of each user.
  arXiv  Detail & Related papers  (2021-06-23T18:37:47Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information [12.836994708337144]
  We develop an algorithm that matches the optimal sample complexity. Our algorithm is robust to model errors and outperforms the existing algorithms in terms of prediction performance.
  arXiv  Detail & Related papers  (2020-03-16T06:29:24Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.