Timezone: »

 
Poster
Collaborative PAC Learning
Avrim Blum · Nika Haghtalab · Ariel Procaccia · Mingda Qiao

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #208
in Posters Wed »

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.

Keywords: Learning Theory
[ Paper] 

Author Information

Avrim Blum (Toyota Technological Institute at Chicago)
Nika Haghtalab (Carnegie Mellon University)
Ariel Procaccia (Carnegie Mellon University)
Mingda Qiao (Tsinghua University)

More from the Same Authors