TY - GEN
T1 - Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
AU - Beznosikov, Aleksandr
AU - Rogozin, Alexander
AU - Kovalev, Dmitry
AU - Gasnikov, Alexander
N1 - KAUST Repository Item: Exported on 2022-10-01
Acknowledgements: The research of A. Beznosikov, A. Rogozin and A. Gasnikov was supported by Russian Science Foundation (project No. 21-71-30005).
PY - 2021/11/5
Y1 - 2021/11/5
N2 - Decentralized optimization methods have been in the focus of optimization community due to their scalability, increasing popularity of parallel algorithms and many applications. In this work, we study saddle point problems of sum type, where the summands are held by separate computational entities connected by a network. The network topology may change from time to time, which models real-world network malfunctions. We obtain lower complexity bounds for algorithms in this setup and develop near-optimal methods which meet the lower bounds.
AB - Decentralized optimization methods have been in the focus of optimization community due to their scalability, increasing popularity of parallel algorithms and many applications. In this work, we study saddle point problems of sum type, where the summands are held by separate computational entities connected by a network. The network topology may change from time to time, which models real-world network malfunctions. We obtain lower complexity bounds for algorithms in this setup and develop near-optimal methods which meet the lower bounds.
UR - http://hdl.handle.net/10754/670330
UR - https://link.springer.com/10.1007/978-3-030-91059-4_18
UR - http://www.scopus.com/inward/record.url?scp=85120046430&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-91059-4_18
DO - 10.1007/978-3-030-91059-4_18
M3 - Conference contribution
SN - 9783030910587
SP - 246
EP - 257
BT - Optimization and Applications
PB - Springer International Publishing
ER -