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.
Integrity signals
Registry
Cites
Statistics
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 worst case, one-shot averaging with IID data produces a global model no better than training a model on a single client.
“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]
Cites
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,863 · see citing works
Introductory Lectures on Convex Optimization: A Basic Course
Нестеров, Ю. Е. (2014) · Medical Entomology and Zoology · Cited by 3,576 · see citing works
Smooth minimization of non-smooth functions
Nesterov, Y. E. (2004) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,437 · see citing works
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 · see citing works
Parallelized Stochastic Gradient Descent
Zinkevich, M., Weimer, M., Li, L., & Smola, A. J. (2010) · Cited by 1,124 · see citing works
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Bekkerman, R., Bilenko, M., & Langford, J. C. (2011) · doi:10.1145/2107736.2107740 · Cited by 290 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
Communication-efficient algorithms for statistical optimization
(2013) · Journal of Machine Learning Research · doi:10.5555/2567709.2567769 · Cited by 195 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
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 72 · see citing works
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 · see citing works
Improved Distributed Principal Component Analysis
Liang, Y., Balcan, M.-F., Kanchanapally, V., & Woodruff, D. P. (2014) · neural information processing systems · Cited by 68 · see citing works
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 · see citing works
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 55 · see citing works
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 · see citing works
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 · see citing works
Distributed Stochastic Variance Reduced Gradient Methods.Preprint
Lee, J. D., Ma, T., & Lin, Q. (2015) · arXiv (Cornell University) · Cited by 9 · see citing works
Flagged first, then by citations
1 of the 26 references couldn’t be matched to a known paper.
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 · see citing works
“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 · see citing works
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 · see citing works
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 923 · see citing works
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 · see citing works
Communication-efficient edge ai: algorithms and systems
Shi, Y., Yang, K., Jiang, T., Zhang, J., & Letaief, K. B. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.3007787 · Cited by 488 · see citing works
A Unified Theory of Decentralized SGD with Changing Topology and Local UpdatesPreprint
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., & Stich, S. U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.10422 · Cited by 258 · see citing works
Distributed Mean Estimation with Limited CommunicationPreprint
Suresh, A. T., Yu, F. X., Kumar, S., & McMahan, H. B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.00429 · Cited by 227 · see citing works
Optimal algorithms for smooth and strongly convex distributed optimization in networksPreprint
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., & Massoulié, L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.08704 · Cited by 221 · see citing works
When Edge Meets Learning: Adaptive Control for Resource-Constrained Distributed Machine Learning
Wang, S., Tuor, T., Salonidis, T., Leung, K. K., Makaya, C., He, T., & Chan, K. (2018) · IEEE INFOCOM 2018 - IEEE Conference on Computer Communications · doi:10.1109/infocom.2018.8486403 · Cited by 209 · see citing works
Distributed optimization with arbitrary local solvers
Ma, C., Konečný, J., Jaggi, M., Smith, V., Jordan, M. I., Richtárik, P., & Takáč, M. (2017) · Optimization methods & software · doi:10.1080/10556788.2016.1278445 · Cited by 191 · see citing works
A Field Guide to Federated OptimizationPreprint
Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., y Arcas, B. A., Al-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.06917 · Cited by 181 · see citing works
Communication-Efficient Accurate Statistical Estimation
Fan, J., Guo, Y., & Wang, K. (2021) · Journal of the American Statistical Association · doi:10.1080/01621459.2021.1969238 · Cited by 145 · see citing works
A Survey on Large-Scale Machine Learning
Wang, M., Fu, W., He, X., Hao, S., & Wu, X. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3015777 · Cited by 148 · see citing works
Communication-efficient distributed learning: An overview
Cao, X., Başar, T., Diggavi, S., Eldar, Y. C., Letaief, K. B., Poor, H. V., & Zhang, J. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3242710 · Cited by 139 · see citing works
Decentralized Proximal Gradient Algorithms With Linear Convergence Rates
Alghunaim, S. A., Ryu, E. K., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3009363 · Cited by 122 · see citing works
An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
Li, S., Ngai, E. C. ‐., & Voigt, T. (2023) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2023.3237397 · Cited by 126 · see citing works
An Incentive Mechanism Design for Efficient Edge Learning by Deep Reinforcement Learning Approach
Zhan, Y., & Zhang, J. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155268 · Cited by 107 · see citing works
Lazily Aggregated Quantized Gradient Innovation for Communication-Efficient Federated Learning
Sun, J., Chen, T., Giannakis, G. B., Yang, Q., & Yang, Z. (2022) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3033286 · Cited by 102 · see citing works
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., & Suresh, A. T. (2020) · arXiv · doi:10.48550/arxiv.2008.03606 · Cited by 96 · see citing works
Stich, S. U., & Karimireddy, S. P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.05350 · Cited by 91 · see citing works
Sun, Y., Scutari, G., & Daneshmand, A. (2022) · SIAM Journal on Optimization · doi:10.1137/19m1259973 · Cited by 99 · see citing works
A distributed one-step estimator
Huang, C. Y., & Huo, X. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01369-0 · Cited by 81 · see citing works
Efficient Distributed Learning with SparsityPreprint
Wang, J., Kolar, M., Srebro, N., & Zhang, T. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.07991 · Cited by 80 · see citing works
Federated Region-Learning: An Edge Computing Based Framework for Urban Environment Sensing
Hu, B., Gao, Y., Liu, L., & Ma, H. (2018) · 2018 IEEE Global Communications Conference (GLOBECOM) · doi:10.1109/glocom.2018.8647649 · Cited by 67 · see citing works
Communication optimization strategies for distributed deep neural network training: A survey
Ouyang, S., Dong, D., Xu, Y., & Xiao, L. (2020) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2020.11.005 · Cited by 73 · see citing works
QSGD: Randomized Quantization for Communication-Optimal Stochastic Gradient DescentPreprint
Alistarh, D., Li, J. Z., Tomioka, R., & Vojnović, M. (2016) · arXiv (Cornell University) · Cited by 64 · see citing works
Minibatch vs Local SGD for Heterogeneous Distributed LearningPreprint
Woodworth, B., Patel, K. K., & Srebro, N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.04735 · Cited by 65 · see citing works
JointRec: A Deep-Learning-Based Joint Cloud Video Recommendation Framework for Mobile IoT
Duan, S., Zhang, D., Wang, Y., Li, L., & Zhang, Y. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2944889 · Cited by 63 · see citing works
Tight Complexity Bounds for Optimizing Composite ObjectivesPreprint
Woodworth, B., & Srebro, N. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.08003 · Cited by 58 · see citing works
Ahmad, I., Shahabuddin, S., Sauter, T., Harjula, E., Kumar, T., Meisel, M., Juntti, M. J., & Ylianttila, M. (2020) · IEEE Industrial Electronics Magazine · doi:10.1109/mie.2020.2979272 · Cited by 58 · see citing works
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 55 · see citing works
Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
Lee, J. D., Lin, Q., Ma, T., & Yang, T. (2017) · Journal of Machine Learning Research · Cited by 55 · see citing works
Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification
Wang, H., Gao, Y., Shi, Y., & Wang, R. (2016) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2016.2570808 · Cited by 46 · see citing works
Federated Region-Learning for Environment Sensing in Edge Computing System
Gao, Y., Liu, L., Hu, B., Lei, T., & Ma, H. (2020) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2020.3016035 · Cited by 45 · see citing works
Optimal Convergence Rates for Convex Distributed Optimization in Networks
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., & Massoulié, L. (2019) · HAL · Cited by 45 · see citing works
The Many Faces of Edge Intelligence
Peltonen, E., Ahmad, I., Aral, A., Capobianco, M., Ding, A. Y., Gil‐Castiñeira, F., Gilman, E., Harjula, E., Jurmu, M., Karvonen, T., et al. (2022) · IEEE Access · doi:10.1109/access.2022.3210584 · Cited by 45 · see citing works
Wu, B., Fang, F., Wang, X., Cai, D., Fu, S., & Ding, Z. (2024) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2024.3411479 · Cited by 43 · see citing works
Efficient distributed learning with sparsity
Wang, J., Kolar, M., Srebro, N., & Zhang, T. (2017) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 40 · see citing works
Lee, J. D., Lin, Q., Ma, T., & Yang, T. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.07595 · Cited by 38 · see citing works
Optimal Decentralized Distributed Algorithms for Stochastic Convex OptimizationPreprint
Gorbunov, E., Dvinskikh, D., & Gasnikov, A. V. (2019) · arXiv (Cornell University) · doi:10.20347/wias.preprint.2691 · Cited by 38 · see citing works
Faster Non-Convex Federated Learning via Global and Local MomentumPreprint
Das, R., Acharya, A., Hashemi, A., Sanghavi, S., Dhillon, I. S., & Topcu, U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.04061 · Cited by 35 · see citing works
Dvinskikh, D., & Gasnikov, A. V. (2021) · Journal of Inverse and Ill-Posed Problems · doi:10.1515/jiip-2020-0068 · Cited by 32 · see citing works
Proximal-Proximal-Gradient Method
Ryu, E. K., & Yin, W. (2019) · Journal of Computational Mathematics · doi:10.4208/jcm.1906-m2018-0282 · Cited by 30 · see citing works
Stochastic, Distributed and Federated Optimization for Machine LearningPreprint
Konečný, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.01155 · Cited by 36 · see citing works
Stability-Based Generalization Analysis of Distributed Learning Algorithms for Big Data
Wu, X., Zhang, J., & Wang, F. (2019) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2019.2910188 · Cited by 29 · see citing works
Imteaj, A., & Amini, M. H. (2021) · Frontiers in Communications and Networks · doi:10.3389/frcmn.2021.657653 · Cited by 28 · see citing works
Recent Theoretical Advances in Decentralized Distributed Convex Optimization
Gorbunov, E., Rogozin, A., Beznosikov, A. N., Dvinskikh, D., & Gasnikov, A. V. (2022) · Springer optimization and its applications · doi:10.1007/978-3-031-00832-0_8 · Cited by 30 · see citing works
Statistically Preconditioned Accelerated Gradient Method for Distributed OptimizationPreprint
Hendrikx, H., Xiao, L., Bubeck, S., Bach, F., & Massoulié, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.10726 · Cited by 26 · see citing works
Towards Accelerated Rates for Distributed Optimization over Time-Varying Networks
Rogozin, A., Lukoshkin, V., Gasnikov, A. V., Kovalev, D. A., & Shulgin, E. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-91059-4_19 · Cited by 23 · see citing works
A Fast Distributed Classification Algorithm for Large-Scale Imbalanced Data
Wang, H., Gao, Y., Shi, Y., & Wang, H. (2016) · Proceedings · doi:10.1109/icdm.2016.0168 · Cited by 21 · see citing works
DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence RatePreprint
Soori, S., Mischenko, K., Mokhtari, A., Dehnavi, M. M., & Gürbüzbalaban, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.00506 · Cited by 21 · see citing works
Krouka, M., Elgabli, A., Issaid, C. B., & Bennis, M. (2022) · IEEE Transactions on Green Communications and Networking · doi:10.1109/tgcn.2022.3173420 · Cited by 22 · see citing works
Gradual Federated Learning With Simulated Annealing
Nguyen, L. T., Kim, J., & Shim, B. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3125137 · Cited by 20 · see citing works
On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and BeyondPreprint
Yuan, X., & Li, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.02246 · Cited by 20 · see citing works
D2P-Fed: Differentially Private Federated Learning With Efficient CommunicationPreprint
Wang, L., Jia, R., & Song, D. X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.13039 · Cited by 20 · see citing works
Dvinskikh, D., & Gasnikov, A. V. (2019) · arXiv (Cornell University) · Cited by 19 · see citing works
The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent CommunicationPreprint
Woodworth, B., Bullins, B., Shamir, O., & Srebro, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.01583 · Cited by 19 · see citing works
Self-citationCommunication trade-offs for synchronized distributed SGD with large step sizePreprint
Patel, K. K., & Dieuleveut, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.11325 · Cited by 17 · see citing works
Less than a Single Pass: Stochastically Controlled Stochastic Gradient MethodPreprint
Lei, L., & Jordan, M. I. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.03261 · Cited by 16 · see citing works
Henna, S., & Davy, A. (2020) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2020.2978846 · Cited by 15 · see citing works
The Communication Complexity of Optimization
Vempala, S., Wang, R., & Woodruff, D. P. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.106 · Cited by 15 · see citing works
Projected Gradient Method for Decentralized Optimization over Time-Varying NetworksPreprint
Rogozin, A., & Gasnikov, A. V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08527 · Cited by 15 · see citing works
IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian MethodPreprint
Arjevani, Y., Bruna, J., Can, B., Gürbüzbalaban, M., Jegelka, S., & Lin, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.06733 · Cited by 15 · see citing works
Self-citationDecentralized Distributed Optimization for Saddle Point ProblemsPreprint
Rogozin, A., Beznosikov, A. N., Dvinskikh, D., Kovalev, D. A., Dvurechensky, P. E., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07758 · Cited by 15 · see citing works
Communication Optimization Algorithms for Distributed Deep Learning Systems: A Survey
Yu, E., Dong, D., & Liao, X. (2023) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2023.3323282 · Cited by 15 · see citing works
Blades: A Unified Benchmark Suite for Byzantine Attacks and Defenses in Federated Learning
Li, S., Ngai, E. C. ‐., Ye, F., Ju, L., Zhang, T., & Voigt, T. (2024) · IEEE/ACM International Conference on Internet-of-Things Design and Implementation (IoTDI) · doi:10.1109/iotdi61053.2024.00018 · Cited by 16 · see citing works
Distributed Saddle-Point Problems Under SimilarityPreprint
Beznosikov, A. N., Scutari, G., Rogozin, A., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.10706 · Cited by 14 · see citing works
Clients Eligibility-Based Lightweight Protocol in Federated Learning: An IDS Use Case
Asad, M., Otoum, S., & Shaukat, S. (2024) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2024.3398213 · Cited by 13 · see citing works
An Accelerated Second-Order Method for Distributed Stochastic Optimization
Agafonov, A., Dvurechensky, P. E., Scutari, G., Gasnikov, A. V., Kamzolov, D., Lukashevich, A., & Daneshmand, A. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683400 · Cited by 13 · see citing works
Local SGD With a Communication Overhead Depending Only on the Number of WorkersPreprint
Spiridonoff, A., Olshevsky, A., & Paschalidis, I. C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.02582 · Cited by 13 · see citing works
Deng, X., Sun, T., Liu, F., & Li, D. (2021) · Tsinghua Science & Technology · doi:10.26599/tst.2021.9010045 · Cited by 12 · see citing works
Gradient compression for communication-limited convex optimization
Khirirat, S., Johansson, M., & Alistarh, D. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619625 · Cited by 12 · see citing works
Dvurechensky, P. E., Kamzolov, D., Lukashevich, A., Lee, S., Ordentlich, E., Uribe, C. A., & Gasnikov, A. V. (2022) · EURO Journal on Computational Optimization · doi:10.1016/j.ejco.2022.100045 · Cited by 12 · see citing works
Acceleration in Distributed Optimization under SimilarityPreprint
Tian, Y., Scutari, G., Cao, T., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.12347 · Cited by 12 · see citing works
Distributed Computing and Inference for Big Data
Zhou, L., Gong, Z., & Xiang, P. (2023) · Annual Review of Statistics and Its Application · doi:10.1146/annurev-statistics-040522-021241 · Cited by 11 · see citing works
Communication-Efficient Distributed Optimization with Quantized PreconditionersPreprint
Alimisis, F., Davies, P., & Alistarh, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07214 · Cited by 11 · see citing works
Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable DevicesPreprint
Ryabinin, M., Gorbunov, E., Plokhotnyuk, V., & Pekhimenko, G. G. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.03239 · Cited by 12 · see citing works
Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract)
Karpov, N., Zhang, Q., & Zhou, Y. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00024 · Cited by 10 · see citing works
Challenges of AI in Wireless Networks for IoTPreprint
Ahmad, I., Shahabuddin, S., Kumar, T., Harjula, E., Meisel, M., Juntti, M. J., Sauter, T., & Ylianttila, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.04705 · Cited by 11 · see citing works
Distributed Saddle-Point Problems: Lower Bounds, Optimal and Robust AlgorithmsPreprint
Beznosikov, A. N., Samokhin, V., & Gasnikov, A. V. (2020) · arXiv (Cornell University) · Cited by 10 · see citing works
Topology Design and Graph Embedding for Decentralized Federated Learning
Duan, Y., Li, X., & Wu, J. (2024) · Intelligent and Converged Networks · doi:10.23919/icn.2024.0008 · Cited by 9 · see citing works
Inexact tensor methods and their application to stochastic convex optimization
Agafonov, A., Kamzolov, D., Dvurechensky, P. E., Gasnikov, A. V., & Takáč, M. (2023) · Optimization methods & software · doi:10.1080/10556788.2023.2261604 · Cited by 9 · see citing works
Accelerated Distributed Approximate Newton Method
Ye, H., He, C., & Chang, X. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3151736 · Cited by 8 · see citing works
Newton Method over Networks is Fast up to the Statistical PrecisionPreprint
Daneshmand, A., Scutari, G., Dvurechensky, P. E., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06780 · Cited by 8 · see citing works
Differentially Quantized Gradient Methods
Lin, C.-Y., Kostina, V., & Hassibi, B. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3171173 · Cited by 10 · see citing works
Woodworth, B., Bullins, B., Shamir, O., & Srebro, N. (2022) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2022/751 · Cited by 7 · see citing works
Self-citationOptimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-UpPreprint
Richards, D., & Rebeschini, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.03135 · Cited by 7 · see citing works
Joint Task and Resource Allocation for Mobile Edge Learning
Abutuleb, A., Sorour, S., & Hassanein, H. S. (2020) · Globecom · doi:10.1109/globecom42002.2020.9322399 · Cited by 6 · see citing works
Huo, X., & Cao, S. (2018) · Wiley Interdisciplinary Reviews Computational Statistics · doi:10.1002/wics.1451 · Cited by 6 · see citing works
Efficient Convex Optimization Requires Superlinear Memory
Marsden, A., Sharan, V., Sidford, A., & Valiant, G. J. (2024) · Journal of the ACM · doi:10.1145/3689208 · Cited by 6 · see citing works
Distributed Semi-Supervised Sparse Statistical Inference
Tu, J., Liu, W., Mao, X., & Xu, M. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3341704 · Cited by 5 · see citing works
Algani, Y. M. A., Kumar, A., Walid, M. A. A., Balu, S., Velayutham, P., & Kumar, A. (2023) · International Conference on Electronics and Renewable Systems (ICEARS) · doi:10.1109/icears56392.2023.10084935 · Cited by 5 · see citing works
Penalty-Based Method for Decentralized Optimization over Time-Varying Graphs
Rogozin, A., & Gasnikov, A. V. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-62867-3_18 · Cited by 5 · see citing works
Yu, A. W., Lin, Q., & Yang, T. (2015) · arXiv (Cornell University) · Cited by 5 · see citing works
DBS: Dynamic Batch Size For Distributed Deep Neural Network TrainingPreprint
Ye, Q., Zhou, Y., Shi, M., Sun, Y., & Lv, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.11831 · Cited by 5 · see citing works
Communication-Efficient distributed optimization for sparse learning via two-way truncation
Ren, J., Li, X., & Haupt, J. (2017) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap.2017.8313109 · Cited by 4 · see citing works
Quantized and Distributed Subgradient Optimization Method With Malicious Attack
Emiola, I., & Enyioha, C. (2022) · IEEE Control Systems Letters · doi:10.1109/lcsys.2022.3186900 · Cited by 4 · see citing works
STSyn: Speeding Up Local SGD With Straggler-Tolerant Synchronization
Zhu, F., Zhang, J., & Wang, X. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3452035 · Cited by 4 · see citing works
Graph reconstruction in the congested clique
Montealegre, P., Perez-Salazar, S., Rapaport, I., & Todinca, I. (2020) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2020.04.004 · Cited by 4 · see citing works
- 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 › Computer Science › Computer Networks and Communications › 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
