Distributed Learning, Communication Complexity and Privacy

Details Distributed Learning, Communication Complexity and Privacy Distributed Learning, Communication Complexity and Privacy

2012-04-16

arxiv.org/abs/1204.3514v2

Computer Science

Learning

18 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Distributed Learning, Communication Complexity and Privacy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Learning, Communication Complexity and Privacy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Learning, Communication Complexity and Privacy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6820