2019

Communication-Efficient Local Decentralized SGD Methods

Li, Xiang, Yang, Wenhao, Wang, Shusen et al.

Understand

Recently, the technique of local updates is a powerful tool in centralized settings to improve communication efficiency via periodical communication.

For decentralized settings, it is still unclear how to efficiently combine local updates and decentralized communication.
In this work, we propose an algorithm named as LD-SGD, which incorporates arbitrary update schemes that alternate between multiple Local updates and multiple Decentralized SGDs, and provide an analytical framework for LD-SGD.
Under the framework, we present a sufficient condition to guarantee the convergence.

Built on

S. S. Ram, A. Nedić, and V. V. Veeravalli, “Asynchronous gossip algorithm for stochastic optimization: Constant stepsize analysis,” in Recent Advances in Optimization and its Applications in Engineering . Springer, 2010, pp. 51–60
2010
Earlier work this paper cites.
M. Zinkevich, M. Weimer, L. Li, and A. J. Smola, “Parallelized stochastic gradient descent,” in Advances in neural information processing systems , 2010, pp. 2595–2603
2010
Earlier work this paper cites.
Y. Zhang, J. C. Duchi, and M. J. Wainwright, “Communication-efficient algorithms for statistical optimization,” Journal of Machine Learning Research , vol. 14, pp. 3321–3363, 2013
2013
Earlier work this paper cites.
P. Bianchi, G. Fort, and W. Hachem, “Performance of a distributed stochastic approximation algorithm,” IEEE Transactions on Information Theory , vol. 59, no. 11, pp. 7405–7418, 2013
2013
Earlier work this paper cites.
M. Li, T. Zhang, Y. Chen, and A. J. Smola, “Efficient mini-batch training for stochastic optimization,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining , 2014, pp. 661–670
2014
Earlier work this paper cites.
M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V. Josifovski, J. Long, E. J. Shekita, and B.-Y. Su, “Scaling distributed machine learning with the parameter server,” in USENIX Symposium on Operating Systems Design and Implementation (OSDI) , 2014
2014
Earlier work this paper cites.
F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu, “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 , 2014
2014
Earlier work this paper cites.
O. Shamir, N. Srebro, and T. Zhang, “Communication-efficient distributed optimization using an approximate Newton-type method,” in International conference on machine learning (ICML) , 2014
2014
Earlier work this paper cites.
J. Kone v
Original
2015
Earlier work this paper cites.
Y. Zhang, J. Duchi, and M. Wainwright, “Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates,” Journal of Machine Learning Research , vol. 16, pp. 3299–3340, 2015
2015
Earlier work this paper cites.
Y. Zhang and X. Lin, “DiSCO: distributed optimization for self-concordant empirical loss,” in International Conference on Machine Learning (ICML) , 2015
2015
Earlier work this paper cites.
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , 2016
2016
Earlier work this paper cites.
K. Yuan, Q. Ling, and W. Yin, “On the convergence of decentralized gradient descent,” SIAM Journal on Optimization , vol. 26, no. 3, pp. 1835–1854, 2016
2016
Earlier work this paper cites.
B. Sirb and X. Ye, “Consensus optimization with delayed and stochastic gradients on decentralized networks,” in 2016 IEEE International Conference on Big Data (Big Data) . IEEE, 2016, pp. 76–85
2016
Earlier work this paper cites.
V. Smith, S. Forte, C. Ma, M. Takac, M. I. Jordan, and M. Jaggi, “CoCoA: A general framework for communication-efficient distributed optimization,” arXiv preprint arXiv:1611.02189 , 2016
Original
2016
Earlier work this paper cites.
S. J. Reddi, J. Konecnỳ, P. Richtárik, B. Póczós, and A. Smola, “AIDE: fast and communication efficient distributed optimization,” arXiv preprint arXiv:1608.06879 , 2016
Original
2016
Earlier work this paper cites.
J. Konecnỳ, H. B. McMahan, D. Ramage, and P. Richtárik, “Federated optimization: distributed machine learning for on-device intelligence,” arXiv preprint arXiv:1610.02527 , 2016
Original
2016
Earlier work this paper cites.
O. Press and L. Wolf, “Using the output embedding to improve language models,” arXiv preprint arXiv:1608.05859 , 2016
Original
2016
Earlier work this paper cites.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial Intelligence and Statistics (AISTATS) , 2017
2017
Earlier work this paper cites.

Similar

J. Kone v
Original
2017
Cited alongside, same era.
X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,” in Advances in Neural Information Processing Systems (NIPS) , 2017
2017
Cited alongside, same era.
G. Lan, S. Lee, and Y. Zhou, “Communication-efficient algorithms for decentralized and stochastic optimization,” Mathematical Programming , pp. 1–48, 2017
2017
Cited alongside, same era.
Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally, “Deep gradient compression: Reducing the communication bandwidth for distributed training,” arXiv preprint arXiv:1712.01887 , 2017
Original
2017
Cited alongside, same era.
H. Zhang, J. Li, K. Kara, D. Alistarh, J. Liu, and C. Zhang, “Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning,” in Proceedings of the 34th International Conference on Machine Learning-Volume 70 . JMLR. org, 2017, pp. 4035–4043
2017
Cited alongside, same era.
J. D. Lee, Q. Liu, Y. Sun, and J. E. Taylor, “Communication-efficient sparse regression,” The Journal of Machine Learning Research , vol. 18, no. 1, pp. 115–144, 2017
2017
Cited alongside, same era.
S.-B. Lin, X. Guo, and D.-X. Zhou, “Distributed learning with regularized least squares,” Journal of Machine Learning Research , vol. 18, no. 1, pp. 3202–3232, 2017
2017
Cited alongside, same era.
V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar, “Federated multi-task learning,” in Advances in Neural Information Processing Systems (NIPS) , 2017
2017
Cited alongside, same era.
F. Zhou and G. Cong, “On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization,” arXiv preprint arXiv:1708.01012 , 2017
Original
2017
Cited alongside, same era.
Z. Jiang, A. Balu, C. Hegde, and S. Sarkar, “Collaborative deep learning in fixed topology networks,” in Advances in Neural Information Processing Systems , 2017, pp. 5904–5914
2017
Cited alongside, same era.
T. Lin, S. U. Stich, and M. Jaggi, “Don’t use large mini-batches, use local sgd,” arXiv preprint arXiv:1808.07217 , 2018
Original
2018
Cited alongside, same era.
S. U. Stich, “Local SGD converges fast and communicates little,” arXiv preprint arXiv:1805.09767 , 2018
Original
2018
Cited alongside, same era.

Then

Shusen Wang, Farbod Roosta Khorasani, Peng Xu, and Michael W. Mahoney, “GIANT: Globally improved approximate newton method for distributed optimization,” in Conference on Neural Information Processing Systems (NeurIPS) , 2018
2018
Later among the works it cites.
D. Mahajan, N. Agrawal, S. S. Keerthi, S. Sellamanickam, and L. Bottou, “An efficient distributed learning algorithm based on effective local functional approximations,” Journal of Machine Learning Research , vol. 19, no. 1, pp. 2942–2978, 2018
2018
Later among the works it cites.
Y. You, Z. Zhang, C.-J. Hsieh, J. Demmel, and K. Keutzer, “Imagenet training in minutes,” in Proceedings of the 47th International Conference on Parallel Processing . ACM, 2018, p. 1
2018
Later among the works it cites.
L. Bottou, F. E. Curtis, and J. Nocedal, “Optimization methods for large-scale machine learning,” Siam Review , vol. 60, no. 2, pp. 223–311, 2018
2018
Later among the works it cites.
T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” arXiv preprint arXiv:1908.07873 , 2019
Original
2019
Closest in time.
A. K. Sahu, T. Li, M. Sanjabi, M. Zaheer, A. Talwalkar, and V. Smith, “Federated optimization for heterogeneous networks,” arXiv preprint arXiv:1812.06127 , 2019
Original
2019
Closest in time.
J. Wang, A. K. Sahu, Z. Yang, G. Joshi, and S. Kar, “Matcha: Speeding up decentralized sgd via matching decomposition sampling,” arXiv preprint arXiv:1905.09435 , 2019
Original
2019
Closest in time.
A. Koloskova, S. U. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” arXiv preprint arXiv:1902.00340 , 2019
Original
2019
Closest in time.
Q. Luo, J. He, Y. Zhuo, and X. Qian, “Heterogeneity-aware asynchronous decentralized training,” arXiv preprint arXiv:1909.08029 , 2019
Original
2019
Closest in time.
S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and P. Richtárik, “Stochastic distributed learning with gradient quantization and variance reduction,” arXiv preprint arXiv:1904.05115 , 2019
Original
2019
Closest in time.
S. Wang, “A sharper generalization bound for divide-and-conquer ridge regression,” in The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI) , 2019
2019
Closest in time.
M. Assran, N. Loizou, N. Ballas, and M. Rabbat, “Stochastic gradient push for distributed deep learning,” in International Conference on Machine Learning , 2019, pp. 344–353
2019
Closest in time.
J. Wang, V. Tantia, N. Ballas, and M. Rabbat, “Slowmo: Improving communication-efficient distributed sgd with slow momentum,” arXiv preprint arXiv:1910.00643 , 2019
Original
2019
Closest in time.
X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of FedAvg on Non-IID data,” arXiv:1907.02189 , 2019
Original
2019
Closest in time.
F. Haddadpour and M. Mahdavi, “On the convergence of local descent methods in federated learning,” arXiv preprint arXiv:1910.14425 , 2019
Original
2019
Closest in time.
H. Yu, S. Yang, and S. Zhu, “Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning,” in AAAI Conference on Artificial Intelligence , 2019
2019
Closest in time.
F. Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe, “Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization,” in International Conference on Machine Learning (ICML) , 2019
2019
Closest in time.
H. Yu, R. Jin, and S. Yang, “On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization,” in International Conference on Machine Learning (ICML) , 2019
2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…