Collaborative PAC Learning
Collaborative PAC Learning
复制标题
DOI：
--
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Avrim Blum;Nika Haghtalab;Ariel D. Procaccia;Mingda Qiao
中科院分区：
文献类型：
--
作者：
Avrim Blum;Nika Haghtalab;Ariel D. Procaccia;Mingda Qiao
我们引入了一个合作的PAC学习模型，其中k个玩家试图学习相同的基本概念。我们问需要多少信息才能同时为所有玩家学习一个准确的分类器。我们将协作PAC学习的样本复杂度与非协作（单人）学习的样本复杂度之比称为开销。我们设计了学习算法，在我们的模型中的个性化和集中式变体中具有O（ln（k））和O（ln^2（k））开销。这给出了一个指数级的改进，在天真的算法，不共享的球员之间的信息。我们补充我们的上限与欧米茄（ln（k））开销下限，表明我们的结果是紧密的对数因子。
We introduce a collaborative PAC learning model, in which k players attempt to learn the same underlying concept. We ask how much more information is required to learn an accurate classifier for all players simultaneously. We refer to the ratio between the sample complexity of collaborative PAC learning and its non-collaborative (single-player) counterpart as the overhead. We design learning algorithms with O(ln(k)) and O(ln^2(k)) overhead in the personalized and centralized variants our model. This gives an exponential improvement upon the naive algorithm that does not share information among players. We complement our upper bounds with an Omega(ln(k)) overhead lower bound, showing that our results are tight up to a logarithmic factor.