Tight Bounds for Collaborative PAC Learning via Multiplicative Weights *
We study the collaborative PAC learning problem recently proposed in Blum et al. [3], in which we have k players and they want to learn a target function collaboratively, such that the learned function approximates the target function well on all players' distributions simultaneously. The quality of the collaborative learning algorithm is measured by the ratio between the sample complexity of the algorithm and that of the learning algorithm for a single distribution (called the overhead). We obtain a collaborative learning algorithm with overhead O(ln k), improving the one with overhead O(ln 2 k) in [3]. We also show that an Ω(ln k) overhead is inevitable when k is polynomial bounded by the VC dimension of the hypothesis class. Finally, our experimental study has demonstrated the superiority of our algorithm compared with the one in Blum et al.
[3] on real-world datasets.
Update after rebuttal:  As mentioned in my review, the authors should clarify that using the multiplicative weight scheme was suggested by Blum et al. and its overhead was discussed (without proof) to be the same as one shown in Theorem 3 of this paper---overhead log^2(k). For a reference, see the last paragraph of section 3 in http://papers.nips.cc/paper/6833-collaborative-pac-learning.pdf. The technical insight of this paper is, in addition to using multiplicative weight update, to change the "Accuracy Test" to the "Weak Test" to further reduce the samples complexity down to the overhead of log(k). The authors in their rebuttal have ignored this fact. So it's best if the camera-ready version reflects this fact accurately.  Before rebuttal:  This paper continues the study of collaboration in the context of machine 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_i's 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. shows that in the personalized setting, where different players can use different classifiers, the overhead is O(log(k)) with k = O(d) . They also considered a centralized setting where all players should use the same functions. In this case, they showed that overhead is O(log(k)^2) when k = O(d). They also showed a matching lower bound of Omega(log(k)) overhead for the case of k=d.  Summary: This paper obtains an improved overhead for the centralized setting. Their main result, appearing in section 3, is that one can get an overhead of O(log(k)) in the centralized setting. More precisely, the sample complexity they obtain is: O(\epsilon^-1 (d+k)(ln(k) + ln(1/delta)). There second contribution is to extend the lower bound of Blum et al. to the more general case of k = d^O(1). Lastly, they do a set of experiments comparing their algorithm to a naive algorithm and the Blum et al. algorithm on a number of datasets and show that their algorithms have better empirical performance.  Overall, I think this is a nice paper. The problem and the setting it studies is very natural. I think the subject matter can be of interest to the broader community and can be related to other areas including, federated and distributed learning, multi-task learning, and transfer learning. I appreciate that the authors have complemented their theoretical results with the experimental findings.   There are a few weaker points in the paper that I explain below.  1. The Basic algorithm: The authors spend quite a bit of space on the basic algorithm that has a log^2(k) overhead in the Centralized setting. My first concern about this is that Blum et al. discussed this algorithm briefly in their paper (see last paragraph section 3 of the Blum et al.) and the fact that it has log^2(k) overhead without going into the details. The reason is that the proof of this algorithm is too similar to the original approach of Blum et al. So, I don’t think the authors should focus so much of their efforts and presentation the paper on this basic algorithm. Secondly, their proof approach appears to be incremental over Blum et al approach. In my opinion the authors should simply state these results without proof (defer the proof to the appendix) and also mention that it was discussed by Blum et al.  2. I think the novel and interesting part of this paper is indeed the algorithm in Section 3. Unfortunately, very little information is given about this proof. I would suggest that the authors expand this part and include the proofs.  3. I'm not sure if the sample complexity in Theorem 4 is accurate. Let k =1, then this is showing a sample complexity of d/\epsilon ln(1/\delta) for one task. But, the best upper bound we know in the PAC setting is 1/\epsilon (d ln(1/\epsilon) + \ln(1/\delta)) with an additional  ln(1/\epsilon). I ask the authors to explain in the rebuttal what the correct sample complexity is in this case.