CoChat
Sign Up
PreprintCited by 244Stochastic Gradient Optimization TechniquesDistributed Control Multi-Agent SystemsAdvanced Optimization Algorithms Research

The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.

On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization

Open access
Yu, Hao, Jin, Rong, Yang, Sen·2019·arXiv
DOI 10.48550/arxiv.1905.03817arXiv 1905.03817
Open this paper in CoChat — free accountOpen PDF

Abstract

Recent developments on large-scale distributed machine learning applications, e.g., deep neural networks, benefit enormously from the advances in distributed non-convex optimization techniques, e.g., distributed Stochastic Gradient Descent (SGD). A series of recent works study the linear speedup property of distributed SGD variants with reduced communication. The linear speedup property enable us to scale out the computing capability by adding more computing nodes into our system. The reduced communication complexity is desirable since communication overhead is often the performance bottleneck in distributed systems. Recently, momentum methods are more and more widely adopted in training machine learning models and can often converge faster and generalize better. For example, many practitioners use distributed SGD with momentum to train deep neural networks with big data. However, it remains unclear whether any distributed momentum SGD possesses the same linear speedup property as distributed SGD and has reduced communication complexity. This paper fills the gap by considering a distributed communication efficient momentum SGD method and proving its linear speedup property.

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.1905.03817

Cites

0 citation errors · 0 not checkable

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?

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

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 36

  1. Aji, A. F. and Heafield, K. Sparse communication for distributed gradient descent. In Conference on Empirical Methods in Natural Language Processing (EMNLP) , 2017.
  2. Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication-efficient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS) , 2017.
  3. Assran, M., Loizou, N., Ballas, N., and Rabbat, M. Stochastic gradient push for distributed deep learning. arXiv:1811.10792 , 2018. · arXiv
  4. Chen, K. and Huo, Q. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering. In Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2016.
  5. Dean, J., Corrado, G., Monga, R., Chen, K., Devin, M., Mao, M., Senior, A., Tucker, P., Yang, K., Le, Q. V., et al. Large scale distributed deep networks. In Advances in Neural Information Processing Systems (NIPS) , 2012.
  6. Dekel, O., Gilad-Bachrach, R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research , 13(165-202), 2012.
  7. Ghadimi, E., Feyzmahdavian, H. R., and Johansson, M. Global convergence of the heavy-ball method for convex optimization. arXiv:1412.7457 , 2014. · arXiv
  8. Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization , 23(4):2341-2368, 2013.
  9. Goyal, P., Doll´ ar, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K. Accurate, large minibatch SGD: training imagenet in 1 hour. arXiv:1706.02677 , 2017. · arXiv
  10. He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In IEEE conference on computer vision and pattern recognition (CVPR) , 2016.
  11. Horn, R. A. and Johnson, C. R. Matrix Analysis . Cambridge University Press, 1985.
  12. Jiang, P. and Agrawal, G. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems (NeurIPS) , 2018.
  13. Jiang, Z., Balu, A., Hegde, C., and Sarkar, S. Collaborative deep learning in fixed topology networks. In Advances in Neural Information Processing Systems (NIPS) , 2017.
  14. Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems (NIPS) , 2012.
  15. Li, M., Andersen, D. G., Smola, A. J., and Yu, K. Communication efficient distributed machine learning with the parameter server. In Advances in Neural Information Processing Systems (NIPS) , 2014.
  16. Lian, X., Huang, Y., Li, Y., and Liu, J. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems (NIPS) , 2015.
  17. Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems (NIPS) , 2017.
  18. Lin, T., Stich, S. U., and Jaggi, M. Don't use large minibatches, use local SGD. arXiv:1808.07217 , 2018. · arXiv
  19. Mania, H., Pan, X., Papailiopoulos, D., Recht, B., Ramchandran, K., and Jordan, M. I. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization , 27(4):2202-2229, 2017.
  20. McMahan, H. B., Moore, E., Ramage, D., Hampson, S., et al. Communication-efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS) , 2017.
  21. Nesterov, Y. Introductory Lectures on Convex Optimization: A Basic Course . Springer Science & Business Media, 2004.
  22. Polyak, B. T. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics , 4(5):1-17, 1964.
  23. Seide, F. and Agarwal, A. CNTK: Microsoft's open-source deep-learning toolkit. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . ACM, 2016.
  24. Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochastic gradient descent and its application to dataparallel distributed training of speech DNNs. In Annual Conference of the International Speech Communication Association (INTERSPEECH) , 2014.
  25. Stich, S. U. Local SGD converges fast and communicates little. arXiv:1805.09767 , 2018. · arXiv
  26. Strom, N. Scalable distributed DNN training using commodity GPU cloud computing. In Annual Conference of the International Speech Communication Association (INTERSPEECH) , 2015.
  27. Su, H., Chen, H., and Xu, H. Experiments on parallel training of deep neural network using model averaging. arXiv:1507.01239v3 , 2018. · arXiv
  28. Sutskever, I., Martens, J., Dahl, G., and Hinton, G. On the importance of initialization and momentum in deep learning. In International conference on machine learning (ICML) , 2013.
  29. Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J. D 2 : Decentralized training over decentralized data. arXiv:1803.07068 , 2018. · arXiv
  30. Wang, J. and Joshi, G. Cooperative SGD: A unified framework for the design and analysis of communicationefficient SGD algorithms. arXiv:1808.07576 , 2018a. · arXiv
  31. Wang, J. and Joshi, G. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD. arXiv:1810.08313 , 2018b. · arXiv
  32. Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NIPS) , 2017.
  33. Yan, Y., Yang, T., Li, Z., Lin, Q., and Yang, Y. A unified analysis of stochastic momentum methods for deep learning. In International Joint Conference on Artificial Intelligence (IJCAI) , 2018.
  34. Yu, H., Yang, S., and Zhu, S. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. arXiv:1807.06629 , 2018. · arXiv
  35. Zavriev, S. and Kostyuk, F. Heavy-ball method in nonconvex optimization problems. Computational Mathematics and Modeling , 4(4):336-341, 1993.
  36. Zhou, F. and Cong, G. On the convergence properties of a K -step averaging stochastic gradient descent algorithm for nonconvex optimization. In International Joint Conference on Artificial Intelligence (IJCAI) , 2018.

Cited by

Sorted by citations

Items 201–244 of 244

Related

See all

Metadata

Authors
Yu, H., Jin, R., & Yang, S.
Affiliations
Alibaba Group (China) (CN)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Pages
7184-7193
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1905.03817
arXiv
1905.03817
OpenAlex
W2944542720
Cited by
244
References
0
Citations by year
2026: 1 · 2025: 14 · 2024: 33 · 2023: 42 · 2022: 41 · 2021: 52 · 2020: 42 · 2019: 18
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • International Conference on Machine Learning
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 › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
Keywords
linear speedup, momentum SGD, communication efficiency, distributed stochastic gradient descent, convergence analysis, deep neural network training

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