Timezone: »

 
Poster
Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
Dmitry Kovalev · Elnur Gasanov · Alexander Gasnikov · Peter Richtarik

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @
in Poster Session 3 »
We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network whose links are allowed to change in time. We solve two fundamental problems for this task. First, we establish {\em the first lower bounds} on the number of decentralized communication rounds and the number of local computations required to find an $\epsilon$-accurate solution. Second, we design two {\em optimal algorithms} that attain these lower bounds: (i) a variant of the recently proposed algorithm ADOM (Kovalev et al, 2021) enhanced via a multi-consensus subroutine, which is optimal in the case when access to the dual gradients is assumed, and (ii) a novel algorithm, called ADOM+, which is optimal in the case when access to the primal gradients is assumed. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
Keywords: Optimization

Author Information

Dmitry Kovalev (KAUST)
Elnur Gasanov (KAUST)
Alexander Gasnikov (Moscow Institute of Physics and Technology)
Peter Richtarik (KAUST)

More from the Same Authors