Timezone: »

 
Poster
Is Consensus Acceleration Possible in Decentralized Optimization over Slowly Time-Varying Networks?
Dmitry Metelev · Alexander Rogozin · Dmitry Kovalev · Alexander Gasnikov

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #743
in Poster Session 6 »

We consider decentralized optimization problems where one aims to minimize a sum of convex smooth objective functions distributed between nodes in the network. The links in the network can change from time to time. For the setting when the amount of changes is arbitrary, lower complexity bounds and corresponding optimal algorithms are known, and the consensus acceleration is not possible. However, in practice the magnitude of network changes may be limited. We derive lower complexity bounds for several regimes of velocity of networks changes. Moreover, we show how to obtain accelerated communication rates for a certain class of time-varying graphs using a specific consensus algorithm.

[ PDF]  [ Poster] 

Author Information

Dmitry Metelev (Moscow Institute of Physics and Technology)
Alexander Rogozin (Moscow Institute of Physics and Technology)
Dmitry Kovalev (KAUST)
Alexander Gasnikov (Moscow Institute of Physics and Technology)

More from the Same Authors