2016/03/20 by Paul Christiano, Paul F. Christiano, Christiano, Paul
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advice (programming) #Aggregate (composite) #Artificial intelligence #Collaborative filtering #Computer science #Computer security #Data Stream Mining Techniques #Data science #FOS: Computer and information sciences #Key (lock) #Machine Learning (cs.LG) #Machine learning #Mathematics #Point (geometry) #Pooling #Recommender system #Robustness (evolution) #Stochastic Gradient Optimization Techniques #cs.LG
paper · pdf · doi:10.48550/arxiv.1603.06265
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2016/03/20 · arxiv created 2016/04/08 · arxiv updated 2016/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many practical learning systems aggregate data across many users, while learning theory traditionally considers a single learner who trusts all of their observations. A case in point is the foundational learning problem of prediction with expert advice. To date, there has been no theoretical study of the general collaborative version of prediction with expert advice, in which many users face a similar problem and would like to share their experiences in order to learn faster. A key issue in this collaborative framework is robustness: generally algorithms that aggregate data are vulnerable to manipulation by even a small number of dishonest users. We exhibit the first robust collaborative algorithm for prediction with expert advice. When all users are honest and have similar tastes our algorithm matches the performance of pooling data and using a traditional algorithm. But our algorithm also guarantees that adding users never significantly degrades performance, even if the additional users behave adversarially. We achieve strong guarantees even when the overwhelming majority of users behave adversarially. As a special case, our algorithm is extremely robust to variation amongst the users.