TY - JOUR
T1 - Tight bounds for collaborative PAC learning via multiplicative weights
AU - Chen, Jiecao
AU - Zhang, Qin
AU - Zhou, Yuan
N1 - Jiecao Chen and Qin Zhang are supported in part by NSF CCF-1525024, CCF-1844234 and IIS-1633215. Part of the work was done when Yuan Zhou was visiting the Shanghai University of Finance and Economics.
PY - 2018
Y1 - 2018
N2 - 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(ln2 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.
AB - 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(ln2 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.
UR - http://www.scopus.com/inward/record.url?scp=85064839438&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064839438&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85064839438
SN - 1049-5258
VL - 2018-December
SP - 3598
EP - 3607
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018
Y2 - 2 December 2018 through 8 December 2018
ER -