We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. In addition to providing general upper and lower bounds on the amount of communication needed for learning, we also present tight results for a number of common concept classes including conjunctions, parity functions, and decision lists. For linear separators, we show that for non-concentrated distributions, we can use a version of the Perceptron algorithm to learn with much less communication than the number of updates given by the usual margin bound. Our general results show that in addition to VC-dimension and covering number, quantities such as the teaching-dimension and mistake-bound of a class play an important role in determining communication requirements. We also show that boosting can be performed in a generic manner in the distributed setting to achieve communication with only logarithmic dependence on 1/epsilon for any concept class. We additionally present an analysis of privacy, considering both differential privacy and a notion of distributional privacy that is especially appealing in this context.

讨论分布式数据的PAC学习问题，分析了涉及的基本通信复杂性问题，包括教学维度和错误绑定。针对特定概念类别，如合取、奇偶函数和决策列表等，给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信，以及如何在不确定环境下实现低通信回归。同时，还考虑了隐私性，包括差分隐私和分布式隐私。

分布式学习，通信复杂度和隐私