Distributed saddle point problems: lower bounds, near-optimal and robust algorithms.
Saved in:
| Title: | Distributed saddle point problems: lower bounds, near-optimal and robust algorithms. |
|---|---|
| Authors: | Beznosikov, Aleksandr1,2,3,4 (AUTHOR) anbeznosikov@gmail.com, Samokhin, Valentin5,6 (AUTHOR), Gasnikov, Alexander4,7,8 (AUTHOR) |
| Source: | Optimization Methods & Software. Oct2025, Vol. 40 Issue 5, p1249-1266. 18p. |
| Subjects: | Mathematical optimization, Distributed algorithms, Generative adversarial networks, Mathematical bounds, Convex domains, Nonlinear analysis |
| Abstract: | This paper focuses on the distributed optimization of stochastic saddle point problems. The first part of the paper is devoted to lower bounds for the centralized and decentralized distributed methods for smooth (strongly) convex-(strongly) concave saddle point problems, as well as the near-optimal algorithms by which these bounds are achieved. Next, we present a new federated algorithm for centralized distributed saddle-point problems – Extra Step Local SGD. The theoretical analysis of the new method is carried out for strongly convex-strongly concave and non-convex-non-concave problems. In the experimental part of the paper, we show the effectiveness of our method in practice. In particular, we train GANs in a distributed manner. [ABSTRACT FROM AUTHOR] |
| Copyright of Optimization Methods & Software is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | This paper focuses on the distributed optimization of stochastic saddle point problems. The first part of the paper is devoted to lower bounds for the centralized and decentralized distributed methods for smooth (strongly) convex-(strongly) concave saddle point problems, as well as the near-optimal algorithms by which these bounds are achieved. Next, we present a new federated algorithm for centralized distributed saddle-point problems – Extra Step Local SGD. The theoretical analysis of the new method is carried out for strongly convex-strongly concave and non-convex-non-concave problems. In the experimental part of the paper, we show the effectiveness of our method in practice. In particular, we train GANs in a distributed manner. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 10556788 |
| DOI: | 10.1080/10556788.2025.2463986 |
