On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum

Hongchang Gao, Junyi Li, Heng Huang
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:7017-7035, 2022.

Abstract

Federated Learning has been actively studied due to its efficiency in numerous real-world applications in the past few years. However, the federated stochastic compositional optimization problem is still underexplored, even though it has widespread applications in machine learning. In this paper, we developed a novel local stochastic compositional gradient descent with momentum method, which facilitates Federated Learning for the stochastic compositional problem. Importantly, we investigated the convergence rate of our proposed method and proved that it can achieve the $O(1/\epsilon^4)$ sample complexity, which is better than existing methods. Meanwhile, our communication complexity $O(1/\epsilon^3)$ can match existing methods. To the best of our knowledge, this is the first work achieving such favorable sample and communication complexities. Additionally, extensive experimental results demonstrate the superior empirical performance over existing methods, confirming the efficacy of our method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-gao22c, title = {On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum}, author = {Gao, Hongchang and Li, Junyi and Huang, Heng}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {7017--7035}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/gao22c/gao22c.pdf}, url = {https://proceedings.mlr.press/v162/gao22c.html}, abstract = {Federated Learning has been actively studied due to its efficiency in numerous real-world applications in the past few years. However, the federated stochastic compositional optimization problem is still underexplored, even though it has widespread applications in machine learning. In this paper, we developed a novel local stochastic compositional gradient descent with momentum method, which facilitates Federated Learning for the stochastic compositional problem. Importantly, we investigated the convergence rate of our proposed method and proved that it can achieve the $O(1/\epsilon^4)$ sample complexity, which is better than existing methods. Meanwhile, our communication complexity $O(1/\epsilon^3)$ can match existing methods. To the best of our knowledge, this is the first work achieving such favorable sample and communication complexities. Additionally, extensive experimental results demonstrate the superior empirical performance over existing methods, confirming the efficacy of our method.} }
Endnote
%0 Conference Paper %T On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum %A Hongchang Gao %A Junyi Li %A Heng Huang %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-gao22c %I PMLR %P 7017--7035 %U https://proceedings.mlr.press/v162/gao22c.html %V 162 %X Federated Learning has been actively studied due to its efficiency in numerous real-world applications in the past few years. However, the federated stochastic compositional optimization problem is still underexplored, even though it has widespread applications in machine learning. In this paper, we developed a novel local stochastic compositional gradient descent with momentum method, which facilitates Federated Learning for the stochastic compositional problem. Importantly, we investigated the convergence rate of our proposed method and proved that it can achieve the $O(1/\epsilon^4)$ sample complexity, which is better than existing methods. Meanwhile, our communication complexity $O(1/\epsilon^3)$ can match existing methods. To the best of our knowledge, this is the first work achieving such favorable sample and communication complexities. Additionally, extensive experimental results demonstrate the superior empirical performance over existing methods, confirming the efficacy of our method.
APA
Gao, H., Li, J. & Huang, H.. (2022). On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:7017-7035 Available from https://proceedings.mlr.press/v162/gao22c.html.

Related Material