The DOI matches its DataCite record.
Distributed Learning, Communication Complexity and Privacy
Open accessAbstract
We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. We provide general upper and lower bounds on the amount of communication needed to learn well, showing 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. 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. We also show how 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, and demonstrate how recent work on agnostic learning from class-conditional queries can be used to achieve low communication in agnostic settings as well. We additionally present an analysis of privacy, considering both differential privacy and a notion of distributional privacy that is especially appealing in this context.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Existing convex distributed optimization work generally requires that the number of clients is much smaller than the number of examples per client, that data is distributed IID, and that each node has an identical number of data points; these assumptions are violated in federated optimization.
“In addition to assuming convexity, this existing work generally requires that the number of clients is much smaller than the number of examples per client, that the data is distributed across the clients in IID fashion, and that each node has an identical number of data points - all of these assumptions are violated in the federated optimization setting.”
From Communication-Efficient Learning of Deep Networks from Decentralized Data (2016) · cites this paper as [4]
Split into 2 atoms — 0 confirmed, 1 partially supported, 0 disputed, 0 misattributed, 1 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 25
- Maria-Florina Balcan and Steve Hanneke. Robust interactive learning. In Proc. 25th Annual Conference on Learning Theory (COLT), 2012.
- Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the SuLQ framework. In Proc. 24th ACM Symposium on Principles of Database Systems (PODS), pages 128–138, 2005.
- Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In Proc. 40th Annual ACM Symp. Theory of Computing, pages 609–618, 2008.
- Nader H. Bshouty. Exact learning of formulas in parallel. Machine Learning, 26(1):25–41, 1997.
- Michael Collins, Robert E. Schapire, and Yoram Singer. Logistic regression, adaboost and bregman dis- tances. Machine Learning, 48(1-3):253–285, 2002.
- Hal Daume III, Jeff Phillips, Avishek Saha, and Suresh Venkatasubramanian. Protocols for learning clas- sifiers on distributed data. In International Conference on Artificial Intelligence and Statistics (AIStats), 2012a.
- Hal Daume III, Jeff Phillips, Avishek Saha, and Suresh Venkatasubramanian. Efficient protocols for dis- tributed classification and optimization. CoRR, abs/1204.3523, 2012b. · arXiv
- Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction. In Proceedings of the 28th International Conference on Machine Learning, 2011.
- Cynthia Dwork. Differential privacy. In ICALP (2), pages 1–12, 2006.
- Cynthia Dwork. Differential privacy: A survey of results. In TAMC, pages 1–19, 2008.
- Cynthia Dwork. The differential privacy frontier (extended abstract). In TCC, pages 496–502, 2009.
- Cynthia Dwork and Kobbi Nissim. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of CRYPTO, Lecture Notes in Computer Science, pages 528–544. Springer, 2004.
- Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, pages 51–60, 2010.
- Yoav Freund. Boosting a weak learning algorithm by majority. In COLT, pages 202–216, 1990.
- Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an appli- cation to boosting. J. Comput. Syst. Sci., 55(1):119–139, 1997.
- Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. In Proceedings of COLT '91, pages 303–314. Morgan Kaufmann, 1991.
- Maurice Herlihy and Nir Shavit. The art of multiprocessor programming. Morgan Kaufmann, 2008.
- Joseph JáJá and Viktor K. Prasanna. Information transfer in distributed computing with applications to vlsi. J. ACM, 31(1):150–162, 1984.
- Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What Can We Learn Privately? In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 531–540, 2008.
- Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983– 1006, 1998.
- Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.
- Phil Long and Rocco Servedio. Algorithms and hardness results for parallel large margin learning. In NIPS, 2011.
- Ronald L. Rivest and Robert Sloan. Learning complicated concepts reliably and usefully. In Proceedings AAAI-88, pages 635–639, August 1988.
- Rocco Servedio. Perceptron, Winnow, and PAC learning. SIAM Journal on Computing, 31(5), 2002.
- Martin Zinkevich, Markus Weimer, Alexander J. Smola, and Lihong Li. Parallelized stochastic gradient descent. In NIPS, pages 2595–2603, 2010.
Cited by
Sorted by citations
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
Metadata
- Authors
- Balcan, M.-F., Blum, A., Fine, S., & Mansour, Y.
- Affiliations
- Georgia Institute of Technology (US)
- Carnegie Mellon University (US)
- IBM (United States) (US)
- Tel Aviv University (IL)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2012
- Volume
- 23
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1204.3514
- OpenAlex
- W2127180992
- Cited by
- 117
- References
- 0
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 3 · 2023: 6 · 2022: 5 · 2021: 7 · 2020: 11 · 2019: 12 · 2018: 14 · 2017: 11 · 2016: 18 · 2015: 9 · 2014: 8 · 2013: 8 · 2012: 3
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- KiltHub Repository (submittedVersion)
- Figshare (submittedVersion, cc-by)
- arXiv (Cornell University)
- KiltHub Repository
- Conference on Learning Theory
- Funders
- National Science Foundation (0953192, 1116892, 1065251)
- Carnegie Mellon University
- United States-Israel Binational Science Foundation
- Israeli Centers for Research Excellence
- Office of Naval Research (N00014{09-1-0751, N00014)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- distributed learning, communication complexity, PAC learning, pedagogical dimension, mistake bounds, VC dimension, covering number, conjunctions, parity function, decision lists, linear separators, perceptron, boosting, agnostic learning, differential privacy
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
