Collaborative PAC Learning
We consider 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 naïve algorithm that does not share information among players. We complement our upper bounds with an Ω(ln(k)) overhead lower bound, showing that our results are tight up to a logarithmic factor.
A natural but naïve algorithm that forgoes collaboration between players can achieve our objective by taking, from each player distribution, a number of samples that is sufficient for learning the individual task, and then training a classifier over all samples. Such an algorithm uses k times as many samples as needed for learning an individual task -we say that this algorithm incurs O(k) overhead in sample complexity. By contrast, we are interested in algorithms that take advantage of the collaborative environment, learn k tasks by sharing information, and incur o(k) overhead in sample complexity.
We study two variants of the aforementioned model: personalized and centralized. In the personalized setting (as in the department store example), we allow the learning algorithm to return different functions for different players. That is, our goal is to return classifiers f 1 , . . . , f k that have error of at most on player distributions D 1 , . . . , D k , respectively. In the centralized setting (as in the hospital example), the learning algorithm is required to return a single classifier f that has an error of at most on all player distributions D 1 , . . . , D k . Our results provide upper and lower bounds on the sample complexity overhead required for learning in both settings.
**Edit** I have read the other reviews and rebuttal. I thank the authors for their feedback and clarification and my positive evaluation of this paper remains unchanged.
The authors give theoretical guarantees for collaborative learning with shared information under the PAC regime. They show that the sample complexity for (\epsilon,\delta)-PAC learning k classifiers for a shared problem (or a size k majority-voting ensemble) only needs to grow by a factor of approximately 1+log(k) (or 1+log^2(k)) rather than a factor of k as naive theory might predict.
The authors provide pseudocode for two algorithms treated by the theory. These were correct as far as I could see, though I didn't implement either.
The paper is mostly clearly written, and strikes a sensible balance between what is included here and what is in the supplementary material, and I enjoyed reading it. I checked the paper and sections A and B of the supplementary material quite carefully, and skimmed C and D. There were no obvious major errors I could find.
It would, of course, have been ideal to see experimental results corroborating the theory, but space is limited and the theory is the main contribution. Hopefully those will appear in a later extended version.
I have mostly minor comments:
Somewhere it should be highlighted explicitly that t is a placeholder for log_{8/7}(k) thus although t is indeed logarithmic in k it is also not *very* small compared to k unless k is large (few hundred say) and in this setting a very large k strikes me as unlikely. On the other hand some central steps of the proof involve union bounding over 2t terms, which is usually disastrous, but here the individual sample complexities for each classifier still only grow like log(2t/\delta), i.e. loglog(k) and you may like to highlight that as well.
I think it is also worth mentioning that the guarantees for the second algorithm depend on a large enough quorum of individual voters being right at the same time (w.h.p) thus the guarantee I think is for the whole ensemble and not for parts of it i.e. since we don't know which individual classifiers are right and which are not. In particular, in practice could early stopping or communications errors potentially invalidate the theoretical guarantees here?
Line 202 and elsewhere use the notation of line 200, i.e. n_{r-1,c} + \frac{1}{8}n_{r-1,c-1}, since it is much clearer.
Line 251 can you please clarify the notation? \mathcal{D}_{\orth} is a distribution over - what? - with relation to the \mathcal{D}_i? It seems like \mathcal{F}_k and \mathcal{D}_k have some dependency on one another?
Line 393 in supplementary should be \forall r < r' \in [t].
A comment - the theory for the second algorithm looks like it could be adapted to, say, a bagged ensemble with only very minor modifications. There is little in the way of good theory for ensemble classification, in particular when is an ensemble of "weak" classifiers better than a single "strong" classifier is not well understood.