Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks

Aleksandr Beznosikov, Alexander Rogozin, Dmitry Kovalev, Alexander Gasnikov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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.
Original languageEnglish (US)
Title of host publicationOptimization and Applications
PublisherSpringer International Publishing
Number of pages12
ISBN (Print)9783030910587
StatePublished - Nov 5 2021


Dive into the research topics of 'Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks'. Together they form a unique fingerprint.

Cite this