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

Aleksandr Beznosikov; Alexander Rogozin; Dmitry Kovalev; Alexander Gasnikov

doi:10.1007/978-3-030-91059-4_18

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 proceeding › Conference contribution

7 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Optimization and Applications
Publisher	Springer International Publishing
Pages	246-257
Number of pages	12
ISBN (Print)	9783030910587
DOIs	https://doi.org/10.1007/978-3-030-91059-4_18
State	Published - Nov 5 2021

Bibliographical note

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).

Access to Document

10.1007/978-3-030-91059-4_18

https://repository.kaust.edu.sa/bitstream/10754/670330/1/Preprintfile1.pdf

Cite this

@inproceedings{9f5ae22ed1364474a30fa69dc1a5f447,

title = "Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks",

abstract = "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.",

author = "Aleksandr Beznosikov and Alexander Rogozin and Dmitry Kovalev and Alexander Gasnikov",

note = "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).",

year = "2021",

month = nov,

day = "5",

doi = "10.1007/978-3-030-91059-4_18",

language = "English (US)",

isbn = "9783030910587",

pages = "246--257",

booktitle = "Optimization and Applications",

publisher = "Springer International Publishing",

}

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 -

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

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this