2024/02/16 by Yuyang Deng, Deng, Yuyang, Mingda Qiao +1 · 1 citation
Computer Science · Psychology · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Innovative Teaching and Learning Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Web Applications and Data Management
paper · pdf · doi:10.48550/arxiv.2402.10445
openalex publication_date 2024/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the n data distributions, while minimizing the number of samples drawn from them in total. Unlike in the usual collaborative learning setup, it is not assumed that there exists a single classifier that is simultaneously accurate for all distributions. We show that, when the data distributions satisfy a weaker realizability assumption, which appeared in [Crammer and Mansour, 2012] in the context of multi-task learning, sample-efficient learning is still feasible. We give a learning algorithm based on Empirical Risk Minimization (ERM) on a natural augmentation of the hypothesis class, and the analysis relies on an upper bound on the VC dimension of this augmented class. In terms of the computational efficiency, we show that ERM on the augmented hypothesis class is NP-hard, which gives evidence against the existence of computationally efficient learners in general. On the positive side, for two special cases, we give learners that are both sample- and computationally-efficient.