CoChat
Sign Up
PreprintCited by 73Stochastic Gradient Optimization TechniquesDistributed Control Multi-Agent SystemsPrivacy-Preserving Technologies in Data

The DOI matches its DataCite record; its reference list is not available.

Robust and Communication-Efficient Collaborative Learning

Open access
Reisizadeh, Amirhossein, Taheri, Hossein, Mokhtari, Aryan, Hassani, Hamed, Pedarsani, Ramtin·2019·arXiv
DOI 10.48550/arxiv.1907.10595arXiv 1907.10595
Open this paper in CoChat — free accountOpen PDF

Abstract

We consider a decentralized learning problem, where a set of computing nodes aim at solving a non-convex optimization problem collaboratively. It is well-known that decentralized optimization schemes face two major system bottlenecks: stragglers' delay and communication overhead. In this paper, we tackle these bottlenecks by proposing a novel decentralized and gradient-based optimization algorithm named as QuanTimed-DSGD. Our algorithm stands on two main ideas: (i) we impose a deadline on the local gradient computations of each node at each iteration of the algorithm, and (ii) the nodes exchange quantized versions of their local models. The first idea robustifies to straggling nodes and the second alleviates communication efficiency. The key technical contribution of our work is to prove that with non-vanishing noises for quantization and stochastic gradients, the proposed method exactly converges to the global optimal for convex loss functions, and finds a first-order stationary point in non-convex scenarios. Our numerical evaluations of the QuanTimed-DSGD on training benchmark datasets, MNIST and CIFAR-10, demonstrate speedups of up to 3x in run-time, compared to state-of-the-art decentralized optimization methods.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1907.10595

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.

A few free checks a day · papers already verified open instantly · results are public

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?

  • Much of the existing literature applies to gradient compression.

    “Much of the existing literature applies to the objective (a) [282, 440, 281, 17, 235, 55].”

    From Advances and Open Problems in Federated Learning (2021) · cites this paper as [55]

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

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

References 66 · Cited by 73

Research works printed but not linked: 61

  1. Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. (2017). QSGD: Communication-efficient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems , pages 1707-1718.
  2. Ananthanarayanan, G., Ghodsi, A., Shenker, S., and Stoica, I. (2013). Effective straggler mitigation: Attack of the clones. In Presented as part of the 10th { USENIX } Symposium on Networked Systems Design and Implementation ( { NSDI } 13) , pages 185-198.
  3. Aysal, T. C., Coates, M., and Rabbat, M. (2007). Distributed average consensus using probabilistic quantization. In Statistical Signal Processing, 2007. SSP'07. IEEE/SP 14th Workshop on , pages 640-644. IEEE.
  4. Berahas, A. S., Iakovidou, C., and Wei, E. (2019). Nested distributed gradient methods with adaptive quantized communication. arXiv preprint arXiv:1903.08149 . · arXiv
  5. Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., and Anandkumar, A. (2018). signsgd: Compressed optimisation for non-convex problems. arXiv preprint arXiv:1802.04434 . · arXiv
  6. Bottou, L. and Bousquet, O. (2008). The tradeoffs of large scale learning. In Advances in neural information processing systems , pages 161-168.
  7. Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends R © in Machine Learning , 3(1):1-122.
  8. Chang, T.-H., Hong, M., and Wang, X. (2015). Multi-agent distributed optimization via inexact consensus admm. Signal Processing, IEEE Transactions on , 63(2):482-497.
  9. Choi, H.-L. and How, J. P. (2010). Continuous trajectory planning of mobile sensors for informative forecasting. Automatica , 46(8):1266-1275.
  10. Dean, J. and Barroso, L. A. (2013). The tail at scale. Communications of the ACM , 56(2):74-80.
  11. Dean, J., Corrado, G., Monga, R., Chen, K., Devin, M., Mao, M., Senior, A., Tucker, P., Yang, K., Le, Q. V., et al. (2012). Large scale distributed deep networks. In Advances in neural information processing systems , pages 1223-1231.
  12. Doan, T. T., Maguluri, S. T., and Romberg, J. (2018). Accelerating the convergence rates of distributed subgradient methods with adaptive quantization. arXiv preprint arXiv:1810.13245 . · arXiv
  13. Duchi, J. C., Agarwal, A., and Wainwright, M. J. (2012). Dual averaging for distributed optimization: convergence analysis and network scaling. Automatic Control, IEEE Trans. on , 57(3):592-606.
  14. Dutta, S., Joshi, G., Ghosh, S., Dube, P., and Nagpurkar, P. (2018). Slow and stale gradients can win the race: Error-runtime trade-offs in distributed sgd. arXiv preprint arXiv:1803.01113 . · arXiv
  15. El Chamie, M., Liu, J., and Ba¸ sar, T. (2016). Design and analysis of distributed averaging with quantized communication. IEEE Transactions on Automatic Control , 61(12):3870-3884.
  16. Ferdinand, N., Al-Lawati, H., Draper, S., and Nokleby, M. (2019). Anytime minibatch: Exploiting stragglers in online distributed optimization. International Conference on Learning Representations .
  17. Hong, M., Hajinezhad, D., and Zhao, M.-M. (2017). Prox-pda: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. In Proceedings of the 34th International Conference on Machine Learning - Volume 70 , ICML'17, pages 1529-1538. JMLR.org.
  18. Hong, M., Lee, J. D., and Razaviyayn, M. (2018). Gradient primal-dual algorithm converges to second-order stationary solutions for nonconvex distributed optimization. arXiv preprint arXiv:1802.08941 . · arXiv
  19. Jakovetic, D., Xavier, J., and Moura, J. M. (2014). Fast distributed gradient methods. Automatic Control, IEEE Transactions on , 59(5):1131-1146.
  20. Jha, D. K., Chattopadhyay, P., Sarkar, S., and Ray, A. (2016). Path planning in gps-denied environments via collective intelligence of distributed sensor networks. International Journal of Control , 89(5):984-999.
  21. Jiang, Z., Balu, A., Hegde, C., and Sarkar, S. (2017). Collaborative deep learning in fixed topology networks. In Advances in Neural Information Processing Systems , pages 5904-5914.
  22. Kashyap, A., Basar, T., and Srikant, R. (2006). Quantized consensus. 2006 IEEE International Symposium on Information Theory , pages 635-639.
  23. Koloskova, A., Stich, S. U., and Jaggi, M. (2019). Decentralized stochastic optimization and gossip algorithms with compressed communication. arXiv preprint arXiv:1902.00340 . · arXiv
  24. Lan, G. and Zhou, Y. (2018). Asynchronous decentralized accelerated stochastic gradient descent. arXiv preprint arXiv:1809.09258 . · arXiv
  25. Lee, C.-S., Michelusi, N., and Scutari, G. (2018a). Distributed quantized weight-balancing and average consensus over digraphs. In 2018 IEEE Conference on Decision and Control (CDC) , pages 5857-5862. IEEE.
  26. Lee, C.-S., Michelusi, N., and Scutari, G. (2018b). Finite rate quantized distributed optimization with geometric convergence. In 2018 52nd Asilomar Conference on Signals, Systems, and Computers , pages 1876-1880. IEEE.
  27. Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J. (2017a). Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems , pages 5330-5340.
  28. Lian, X., Zhang, W., Zhang, C., and Liu, J. (2017b). Asynchronous decentralized parallel stochastic gradient descent. arXiv preprint arXiv:1710.06952 . · arXiv
  29. Mei, S., Bai, Y., Montanari, A., et al. (2018). The landscape of empirical risk for nonconvex losses. The Annals of Statistics , 46(6A):2747-2774.
  30. Mokhtari, A. and Ribeiro, A. (2016). Dsa: Decentralized double stochastic averaging gradient algorithm. The Journal of Machine Learning Research , 17(1):2165-2199.
  31. Mokhtari, A., Shi, W., Ling, Q., and Ribeiro, A. (2016). Dqm: Decentralized quadratically approximated alternating direction method of multipliers. IEEE Transactions on Signal Processing , 64(19):5158-5173.
  32. Nedic, A., Olshevsky, A., Ozdaglar, A., and Tsitsiklis, J. N. (2008). Distributed subgradient methods and quantization effects. In Decision and Control, 2008. CDC 2008. 47th IEEE Conference on , pages 4177-4184. IEEE.
  33. Peng, Z., Xu, Y., Yan, M., and Yin, W. (2016). On the convergence of asynchronous parallel iteration with unbounded delays. Journal of the Operations Research Society of China , pages 1-38.
  34. Qu, G. and Li, N. (2017). Accelerated distributed nesterov gradient descent. arXiv preprint arXiv:1705.07176 . · arXiv
  35. Rabbat, M. G. and Nowak, R. D. (2005). Quantized incremental algorithms for distributed optimization. IEEE Journal on Selected Areas in Communications , 23(4):798-808.
  36. Recht, B., Re, C., Wright, S., and Niu, F. (2011). Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Proc. of the 25th Annual Conference on Neural Information Processing (NIPS) , pages 693-701.
  37. Reisizadeh, A., Mokhtari, A., Hassani, H., and Pedarsani, R. (2018). Quantized decentralized consensus optimization. In 2018 IEEE Conference on Decision and Control (CDC) , pages 5838-5843. IEEE.
  38. Reisizadeh, A., Mokhtari, A., Hassani, H., and Pedarsani, R. (2019a). An exact quantized decentralized gradient descent algorithm. IEEE Transactions on Signal Processing , 67(19):4934-4947.
  39. Reisizadeh, A., Prakash, S., Pedarsani, R., and Avestimehr, A. S. (2019b). Coded computation over heterogeneous clusters. IEEE Transactions on Information Theory .
  40. Reisizadeh, A., Prakash, S., Pedarsani, R., and Avestimehr, A. S. (2019c). Codedreduce: A fast and robust framework for gradient aggregation in distributed learning. arXiv preprint arXiv:1902.01981 . · arXiv
  41. Ribeiro, A. (2010). Ergodic stochastic optimization algorithms for wireless communication and networking. IEEE Transactions on Signal Processing , 58(12):6369-6386.
  42. Scaman, K., Bach, F., Bubeck, S., Massoulié, L., and Lee, Y. T. (2018). Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems , pages 27402749.
  43. Schizas, I. D., Ribeiro, A., and Giannakis, G. B. (2008). Consensus in ad hoc wsns with noisy links-part i: Distributed estimation of deterministic signals. Signal Processing, IEEE Transactions on , 56(1):350-364.
  44. Scutari, G., Facchinei, F., and Lampariello, L. (2017). Parallel and distributed methods for constrained nonconvex optimization?part i: Theory. IEEE Transactions on Signal Processing , 65(8):1929-1944.
  45. Scutari, G. and Sun, Y. (2018). Distributed nonconvex constrained optimization over time-varying digraphs. arXiv preprint arXiv:1809.01106 . · arXiv
  46. Seaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. (2017). Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 , pages 3027-3036. JMLR. org.
  47. Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. (2014). 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association .
  48. Shi, W., Ling, Q., Wu, G., and Yin, W. (2015b). A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing , 63(22):6013-6023.
  49. Shi, W., Ling, Q., Yuan, K., Wu, G., and Yin, W. (2014). On the linear convergence of the admm in decentralized consensus optimization. IEEE Trans. on Signal Processing , 62(7):1750-1761.
  50. Sun, H. and Hong, M. (2018). Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms. arXiv preprint arXiv:1804.02729 . · arXiv
  51. Tandon, R., Lei, Q., Dimakis, A. G., and Karampatziakis, N. (2016). Gradient coding. arXiv preprint arXiv:1612.03301 . · arXiv
  52. Tsianos, K. I., Lawlor, S., and Rabbat, M. G. (2012). Push-sum distributed dual averaging for convex optimization. CDC , pages 5453-5458.
  53. Tsitsiklis, J. N. and Luo, Z.-Q. (1987). Communication complexity of convex optimization. Journal of Complexity , 3(3):231-243.
  54. Uribe, C. A., Lee, S., Gasnikov, A., and Nedi´ c, A. (2018). A dual approach for optimal algorithms in distributed optimization over networks. arXiv preprint arXiv:1809.00710 . · arXiv
  55. Wang, D., Joshi, G., and Wornell, G. (2014). Efficient task replication for fast response times in parallel computation. In ACM SIGMETRICS Performance Evaluation Review , volume 42, pages 599-600. ACM.
  56. Wu, T., Yuan, K., Ling, Q., Yin, W., and Sayed, A. H. (2017). Decentralized consensus optimization with asynchrony and delays. IEEE Transactions on Signal and Information Processing over Networks , 4(2):293307.
  57. Yu, Q., Maddah-Ali, M. A., and Avestimehr, A. S. (2017). Polynomial codes: an optimal design for highdimensional coded matrix multiplication. arXiv preprint arXiv:1705.10464 . · arXiv
  58. Yuan, K., Ling, Q., and Yin, W. (2016). On the convergence of decentralized gradient descent. SIAM Journal on Optimization , 26(3):1835-1854.
  59. Yuksel, S. and Basar, T. (2003). Quantization and coding for decentralized lti systems. In 42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475) , volume 3, pages 2847-2852. IEEE.
  60. Zeng, J. and Yin, W. (2018). On nonconvex decentralized gradient descent. IEEE Transactions on signal processing , 66(11):2834-2848.
  61. Zhang, X., Liu, J., Zhu, Z., and Bentley, E. S. (2018). Compressed distributed gradient descent: Communicationefficient consensus over networks. arXiv preprint arXiv:1812.04048 . · arXiv

Metadata

Authors
Reisizadeh, A., Taheri, H., Mokhtari, A., Hassani, H., & Pedarsani, R.
Affiliations
  • University of California, Santa Barbara (US)
  • The University of Texas at Austin (US)
  • University of Pennsylvania (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
32
Pages
8386-8397
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1907.10595
arXiv
1907.10595
OpenAlex
W2963952839
Cited by
73
References
66
Citations by year
2025: 9 · 2024: 8 · 2023: 15 · 2022: 14 · 2021: 16 · 2020: 9 · 2019: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • eScholarship (California Digital Library) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (1837253, 1909320, 1755707)
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
decentralized learning, non-convex optimization, communication efficiency, gradient quantization, first-order stationary points, convergence analysis, distributed optimization

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