ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks

Dmitry Kovalev, Egor Shulgin, Peter Richtarik, Alexander V Rogozin, Alexander Gasnikov
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5784-5793, 2021.

Abstract

We propose ADOM – an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. ADOM uses a dual oracle, i.e., we assume access to the gradient of the Fenchel conjugate of the individual loss functions. Up to a constant factor, which depends on the network structure only, its communication complexity is the same as that of accelerated Nesterov gradient method. To the best of our knowledge, only the algorithm of Rogozin et al. (2019) has a convergence rate with similar properties. However, their algorithm converges under the very restrictive assumption that the number of network changes can not be greater than a tiny percentage of the number of iterations. This assumption is hard to satisfy in practice, as the network topology changes usually can not be controlled. In contrast, ADOM merely requires the network to stay connected throughout time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-kovalev21a, title = {ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks}, author = {Kovalev, Dmitry and Shulgin, Egor and Richtarik, Peter and Rogozin, Alexander V and Gasnikov, Alexander}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5784--5793}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/kovalev21a/kovalev21a.pdf}, url = {https://proceedings.mlr.press/v139/kovalev21a.html}, abstract = {We propose ADOM – an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. ADOM uses a dual oracle, i.e., we assume access to the gradient of the Fenchel conjugate of the individual loss functions. Up to a constant factor, which depends on the network structure only, its communication complexity is the same as that of accelerated Nesterov gradient method. To the best of our knowledge, only the algorithm of Rogozin et al. (2019) has a convergence rate with similar properties. However, their algorithm converges under the very restrictive assumption that the number of network changes can not be greater than a tiny percentage of the number of iterations. This assumption is hard to satisfy in practice, as the network topology changes usually can not be controlled. In contrast, ADOM merely requires the network to stay connected throughout time.} }
Endnote
%0 Conference Paper %T ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks %A Dmitry Kovalev %A Egor Shulgin %A Peter Richtarik %A Alexander V Rogozin %A Alexander Gasnikov %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-kovalev21a %I PMLR %P 5784--5793 %U https://proceedings.mlr.press/v139/kovalev21a.html %V 139 %X We propose ADOM – an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. ADOM uses a dual oracle, i.e., we assume access to the gradient of the Fenchel conjugate of the individual loss functions. Up to a constant factor, which depends on the network structure only, its communication complexity is the same as that of accelerated Nesterov gradient method. To the best of our knowledge, only the algorithm of Rogozin et al. (2019) has a convergence rate with similar properties. However, their algorithm converges under the very restrictive assumption that the number of network changes can not be greater than a tiny percentage of the number of iterations. This assumption is hard to satisfy in practice, as the network topology changes usually can not be controlled. In contrast, ADOM merely requires the network to stay connected throughout time.
APA
Kovalev, D., Shulgin, E., Richtarik, P., Rogozin, A.V. & Gasnikov, A.. (2021). ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5784-5793 Available from https://proceedings.mlr.press/v139/kovalev21a.html.

Related Material