Improved Algorithms for Collaborative PAC Learning
We study a recent model of collaborative PAC learning where k players with k different tasks collaborate to learn a single classifier that works for all tasks. Previous work showed that when there is a classifier that has very small error on all tasks, there is a collaborative algorithm that finds a single classifier for all tasks and has O((ln(k))
2 ) times the worst-case sample complexity for learning a single task. In this work, we design new algorithms for both the realizable and the non-realizable setting, having sample complexity only O(ln(k)) times the worst-case sample complexity for learning a single task. The sample complexity upper bounds of our algorithms match previous lower bounds and in some range of parameters are even better than previous algorithms that are allowed to output different classifiers for different tasks.
This paper studies a PAC learning problem where there are k agents who each want to learn the same underlying concept. They are distinguished by the fact that they each have sample access to different distributions, and each requires the learned concept to have small expected error on their own distribution. This learning setting was introduced by Blum et al. [2017]. A bit more formally, suppose D_i is the distribution associated with agent i. The goal is to use a set of samples S (each of which is drawn from D_i for some i \in {1, ..., k}), labeled by an unknown function f*, to learn a concept f with low error. In particularly, with probability at least 1 – delta over the draw of S, across all D_i, the expected error of f should be at most epsilon.  Blum et al. show that if the VC dimension of the hypothesis class is d, then there is a learning algorithm for this problem which uses O(ln^2(k) / epsilon * ((d + k) * ln(1 / delta) samples. The goal of this paper is to change the dependence on ln(k) from ln^2(k) to ln(k). The authors give two algorithms. The first algorithm has a sample complexity of O(ln(k) / epsilon * (d * ln(1 / epsilon) + k * ln(k / delta))). This algorithm weights each distribution, starting off by placing equal weight on all distributions and drawing an equal number of samples from all distributions. It finds a hypothesis with zero error on the set of samples. It then draws some more samples from each distribution to estimate this hypothesis's error on each distribution. If the error associated with distribution D_i is high, it doubles that distribution's weight. In the next round, the number of samples it draws from each distribution is proportional to the distributions' weights. It repeats this procedure for log(k) rounds. It returns the majority function over all the classifiers it learned over all the algorithm’s rounds.  As the authors point out, the problem with this first algorithm is that when d = Theta(k), we again see a quadratic dependence on ln(k), as in the paper by Blum et al. [2017]. The authors get around this using another algorithm that runs for more rounds but uses fewer samples to test the error associated with each distribution. This second algorithm has a sample complexity of O(1 / epsilon * ln(k / delta) * (d * ln(1 / epsilon) + k + ln(1 / delta))). Finally, the authors also give algorithms for the non-realizable case, where there may not be a concept with zero test error, and the goal is to compete with the concept with the lowest test error.  I’d like to see more discussion about how the techniques from this paper compare to the techniques of the paper by Blum et al. [2017]. Both algorithms iteratively reweight each distribution, learn a classifier over the weighted sum of the distributions, estimate the error of this classifier on each distribution, and then use this error estimate to reweight the distributions and repeat. The differences in the two papers’ approaches seem to be in the reweighting scheme, and in the number of samples needed to estimate the classifier’s error at each round. It would be helpful if the authors could summarize where the ln^2(k) factor is coming from in Blum et al.’s paper. Why does using multiplicative weights help get around this?  As a smaller note, I understand the motivation of Blum et al.’s “personalized” variant of this problem, where each agent learns her own concept, but the goal is to avoid a sample complexity of O(dk). But in what scenario would the agents want to learn a single concept, which is the goal of this work? The authors give a little bit of motivation in the first paragraph, referring to AutoML, but it would be helpful to explain this connection more and provide more motivation.  Finally, the notation D_i is used in Section 2 before it is defined.  ===============After rebuttal================= Thanks, I like the bank loan example. I recommend adding more examples like this to motivate the paper.