Decentralized saddle point problems via non-Euclidean mirror prox.
Saved in:
| Title: | Decentralized saddle point problems via non-Euclidean mirror prox. |
|---|---|
| Authors: | Rogozin, Alexander1,2 (AUTHOR) aleksandr.rogozin@phystech.edu, Beznosikov, Aleksandr1,2 (AUTHOR), Dvinskikh, Darina2 (AUTHOR), Kovalev, Dmitry3 (AUTHOR), Dvurechensky, Pavel4 (AUTHOR), Gasnikov, Alexander1,2,5 (AUTHOR) |
| Source: | Optimization Methods & Software. Oct2025, Vol. 40 Issue 5, p1127-1152. 26p. |
| Subjects: | Mathematical optimization, Distributed algorithms, Nonlinear theories, Non-Euclidean geometry, Communication complexity (Information theory) |
| Abstract: | We consider smooth convex-concave saddle point problems in the decentralized distributed setting, where a finite-sum objective is distributed among the nodes of a computational network. At each node, the local objective depends on the groups of local and global variables. For such problems, we propose a decentralized distributed algorithm with $ O(\varepsilon ^{-1}) $ O (ϵ − 1) communication and oracle calls complexities to achieve accuracy ε in terms of the duality gap and in terms of consensus between nodes. Further, we prove lower bounds for the communication and oracle calls complexities and show that our algorithm matches these bounds, i.e. it is optimal. In contrast to existing decentralized algorithms, our algorithm admits non-euclidean proximal setup, including, e.g. entropic. We illustrate the work of the proposed algorithm on the prominent problem of computing Wasserstein barycenters (WB), where a non-euclidean proximal setup arises naturally in a bilinear saddle point reformulation of the WB problem. [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: | We consider smooth convex-concave saddle point problems in the decentralized distributed setting, where a finite-sum objective is distributed among the nodes of a computational network. At each node, the local objective depends on the groups of local and global variables. For such problems, we propose a decentralized distributed algorithm with $ O(\varepsilon ^{-1}) $ O (ϵ − 1) communication and oracle calls complexities to achieve accuracy ε in terms of the duality gap and in terms of consensus between nodes. Further, we prove lower bounds for the communication and oracle calls complexities and show that our algorithm matches these bounds, i.e. it is optimal. In contrast to existing decentralized algorithms, our algorithm admits non-euclidean proximal setup, including, e.g. entropic. We illustrate the work of the proposed algorithm on the prominent problem of computing Wasserstein barycenters (WB), where a non-euclidean proximal setup arises naturally in a bilinear saddle point reformulation of the WB problem. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 10556788 |
| DOI: | 10.1080/10556788.2023.2280062 |
