Distributed Learning, Communication Complexity, and Privacy
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Analyzes communication needed for distributed supervised learning and gives concrete protocols and bounds: a distributed AdaBoost yields D log(1/epsilon) examples total by using log(1/epsilon) rounds and O(d) examples per round, improving exponentially over the naive D/epsilon baselines; mistake‑bound methods use M examples but up to M rounds. Shows proper parity learning needs Ω(d^2) bits while an improper K=2 scheme uses O(d) bits; noisy-case protocols cut communication but are not yet computationally efficient.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:07Statistical / PAC learning model
- 3:52Two Main Aspects in Classic Machine Learning
- 4:33Sample Complexity Results
- 6:21Distributed Learning
- 10:12Interesting special case to think about
- 10:48Overview of Our Results
- 12:13Some simple communication baselines.
- 14:57Improving the Dependence on 1
- 15:42Recap of Adaboost
- 19:15Distributed Adaboost
- 21:53Dependence on 1/€, Agnostic learning
- 24:11Better results for special cases
- 27:25Interesting class: parity functions
- 31:05Distributed PAC learning: Summary
- 31:37Open questions
related talks
43mIs Interaction Necessary for Distributed Private Learning?
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
45mTesting and Learning Distributions Under Local Information Constraints
27mOn Distributed Differential Privacy and Counting Distinct Elements
53mDesigning Robust Learners
48mA New Paradigm for Learning with Distribution Shift
17mData privacy and reliable learning
53mOptimality in Locally Private Estimation and Learning