The DOI matches its DataCite record; 25 of the 26 references it cites were found in a registry or an index.
Communication Complexity of Distributed Convex Learning and Optimization
Open accessAbstract
We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to individual machines, and the types of functions considered. We identify cases where existing algorithms are already worst-case optimal, as well as cases where room for further improvement is still possible. Among other things, our results indicate that without similarity between the local objective functions (due to statistical data similarity or otherwise) many communication rounds may be required, even if the machines have unbounded computational power.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“This approach has been studied extensively in the convex case with IID data, and it is known that in the worst-case, the global model produced is no better than training a model on a single client [44, 3, 46].”
From Communication-Efficient Learning of Deep Networks from Decentralized Data (2016) · cites this paper as [3]
Citations
Cites
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,917
Introductory Lectures on Convex Optimization: A Basic Course
Нестеров, Ю. Е. (2014) · Medical Entomology and Zoology · Cited by 3,576
Smooth minimization of non-smooth functions
Nesterov, Y. E. (2004) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,437
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Niu, F., Recht, B., Re, C., & Wright, S. J. (2011) · arXiv · doi:10.48550/arxiv.1106.5730 · Cited by 1,211
Parallelized Stochastic Gradient Descent
Zinkevich, M., Weimer, M., Li, L., & Smola, A. J. (2010) · Cited by 1,124
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
Optimal Distributed Online Prediction using Mini-BatchesPreprint
DekelOfer, Gilad-BachrachRan, ShamirOhad, & Xiaolin (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.1367 · Cited by 564
Self-citationCommunication-Efficient Distributed Optimization using an Approximate Newton-type Method
Shamir, O., Srebro, N., & Zhang, T. (2013) · arXiv · doi:10.48550/arxiv.1312.7853 · Cited by 424
Self-citationNumerical linear algebra in the streaming model
Clarkson, K. L., & Woodruff, D. P. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536445 · Cited by 304
Bekkerman, R., Bilenko, M., & Langford, J. C. (2011) · doi:10.1145/2107736.2107740 · Cited by 290
A Reliable Effective Terascale Linear Learning SystemPreprint
Agarwal, A., Chapelle, O., Dudı́k, M., & Langford, J. C. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.4198 · Cited by 280
Distributed Coordinate Descent Method for Learning with Big Data
Richtárik, P., & Takác, M. (2013) · Journal of machine learning research · doi:10.48550/arxiv.1310.2059 · Cited by 266
Communication-Efficient Distributed Dual Coordinate AscentPreprint
Jaggi, M., Smith, V., Takáč, M., Terhorst, J., Krishnan, S., Hofmann, T., & Jordan, M. I. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.1458 · Cited by 203
Communication-efficient algorithms for statistical optimization
(2013) · Journal of Machine Learning Research · doi:10.5555/2567709.2567769 · Cited by 195
Better Mini-Batch Algorithms via Accelerated Gradient Methods
Cotter, A., Shamir, O., Srebro, N., & Sridharan, K. (2011) · arXiv · doi:10.48550/arxiv.1106.4574 · Cited by 173
Self-citationDistributed stochastic optimization and learning
Shamir, O., & Srebro, N. (2014) · 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2014.7028543 · Cited by 120
Self-citationDistributed Learning, Communication Complexity and PrivacyPreprint
Balcan, M.-F., Blum, A. L., Fine, S., & Mansour, Y. (2012) · arXiv (Cornell University) · doi:10.1184/r1/6475568 · Cited by 112
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and EstimationPreprint
Shamir, O. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.3494 · Cited by 76
Self-citationCompeting with the Empirical Risk Minimizer in a Single PassPreprint
Frostig, R., Ge, R., Kakade, S. M., & Sidford, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.6606 · Cited by 71
Improved Distributed Principal Component Analysis
Liang, Y., Balcan, M.-F., Kanchanapally, V., & Woodruff, D. P. (2014) · neural information processing systems · Cited by 68
Communication-Efficient Distributed Optimization of Self-concordant Empirical Loss
Zhang, Y., & Xiao, L. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97478-1_11 · Cited by 62
Improved Distributed Principal Component AnalysisPreprint
Balcan, M.-F., Kanchanapally, V., Liang, Y., & Woodruff, D. P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.5823 · Cited by 58
Communication complexity of convex optimization
Tsitsiklis, J. N., & Luo, Z.-Q. T. (1987) · Journal of Complexity · doi:10.1016/0885-064x(87)90013-6 · Cited by 52
A Parallel SGD method with Strong ConvergencePreprint
Mahajan, D. K., Keerthi, S. S., Sundararajan, S., & Bottou, L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.0636 · Cited by 10
Distributed Stochastic Variance Reduced Gradient Methods.Preprint
Lee, J. D., Ma, T., & Lin, Q. (2015) · arXiv (Cornell University) · Cited by 9
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
“no better than training a model on a single client [44, 3, 46].”
BackgroundAdaptive Federated Learning in Resource Constrained Edge Computing Systems
Wang, S., Tuor, T., Salonidis, T., Leung, K. K., Makaya, C., He, T., & Chan, K. (2019) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2019.2904348 · Cited by 2,232
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., & Suresh, A. T. (2019) · arXiv · doi:10.48550/arxiv.1910.06378 · Cited by 1,734
Federated Learning of Deep Networks using Model AveragingPreprint
McMahan, H. B., Moore, E., Ramage, D., & y Arcas, B. A. (2016) · arXiv (Cornell University) · Cited by 1,005
Federated Optimization:Distributed Optimization Beyond the DatacenterPreprint
Konečný, J., McMahan, B., & Ramage, D. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.03575 · Cited by 547
Metadata
- Authors
- Arjevani, Y., & Shamir, O.
- Affiliations
- Weizmann Institute of Science (IL)
- ORCID
- Arjevani, Yossi
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2015
- Volume
- 28
- Pages
- 1756-1764
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1506.01900
- OpenAlex
- W2962897077
- Cited by
- 133
- References
- 26
- Citations by year
- 2026: 1 · 2024: 14 · 2023: 11 · 2022: 12 · 2021: 19 · 2020: 31 · 2019: 18 · 2018: 7 · 2017: 9 · 2016: 8 · 2015: 3
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- neural information processing systems
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Keywords
- communication complexity, distributed optimization, communication-efficient algorithms, communication rounds, fundamental limits
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
