Reviews: Improved Algorithms for Collaborative PAC Learning

This paper continues the study of collaboration in the learning and obtains improved same complexity bounds. Background: The collaborative PAC model, introduced by Blum et al (NIPS'17), considers a setting where k players with different distributions D_is that are all consistent with some unknown function f * want to (\epsilon, \delta)-learn a classifier for their own distribution. The question Blum et al. asks is what is the total "overhead" over the sample complexity of accomplishing one task, if the players can collaborate. As an example when players do not collaborate, the k tasks have to be performed individually leading to an overhead of O(k). Blum et al showed that in the personalized setting, where different players can use different classifiers, the overhead is O(log(k)) with k O(d).