ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks

Kovalev D.; Shulgin E.; Richtarik P.; A. Rogozin; A. Gasnikov

?

ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks

P. 5784–5793.

Kovalev D., Shulgin E., Richtarik P., Rogozin A., Gasnikov A.

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 (Nesterov, 2003). 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.

Language: English

Text on another site

Keywords: Decentralized optimization accelerated method

In book

Proceedings of the 38th International Conference on Machine Learning (ICML 2021)

Vol. 139. , PMLR, 2021.

Decentralized personalized federated learning: Lower bounds and optimal algorithm for all personalization modes

Sadiev A., Borodich E., Beznosikov A. et al., EURO Journal on Computational Optimization 2022 Vol. 10 Article 100041

This paper considers the problem of decentralized, personalized federated learning. For centralized personalized federated learning, a penalty that measures the deviation from the local model and its average, is often added to the objective function. However, in a decentralized setting this penalty is expensive in terms of communication costs, so here, a different penalty — ...

Added: October 28, 2022

Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems

Dvinskikh D., Gasnikov A., Journal of Inverse and Ill-posed problems 2021 Vol. 29 No. 3 P. 385–405

We introduce primal and dual stochastic gradient oracle methods for decentralized convex optimization problems. Both for primal and dual oracles, the proposed methods are optimal in terms of the number of communication steps. However, for all classes of the objective, the optimality in terms of the number of oracle calls per node takes place only ...

Added: October 29, 2021

Accelerated Methods for Saddle-Point Problem

Alkousa M., Gasnikov A., Dvinskikh D. et al., Computational Mathematics and Mathematical Physics 2020 Vol. 60 No. 11 P. 1787–1809

Recently, it has been shown how, on the basis of the usual accelerated gradient method for solving problems of smooth convex optimization, accelerated methods for more complex problems (with a structure) and problems that are solved using various local information about the behavior of a function (stochastic gradient, Hessian, etc.) can be obtained. The term ...

Added: February 5, 2021