Decentralized Distributed Optimization for Saddle Point Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911831239426048 |
|---|---|
| author | Rogozin, Alexander Beznosikov, Aleksandr Dvinskikh, Darina Kovalev, Dmitry Dvurechensky, Pavel Gasnikov, Alexander |
| author_facet | Rogozin, Alexander Beznosikov, Aleksandr Dvinskikh, Darina Kovalev, Dmitry Dvurechensky, Pavel Gasnikov, Alexander |
| contents | We consider distributed convex-concave saddle point problems over arbitrary connected undirected networks and propose a decentralized distributed algorithm for their solution. The local functions distributed across the nodes are assumed to have global and local groups of variables. For the proposed algorithm we prove non-asymptotic convergence rate estimates with explicit dependence on the network characteristics. To supplement the convergence rate analysis, we propose lower bounds for strongly-convex-strongly-concave and convex-concave saddle-point problems over arbitrary connected undirected networks. We illustrate the considered problem setting by a particular application to distributed calculation of non-regularized Wasserstein barycenters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_07758 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Decentralized Distributed Optimization for Saddle Point Problems Rogozin, Alexander Beznosikov, Aleksandr Dvinskikh, Darina Kovalev, Dmitry Dvurechensky, Pavel Gasnikov, Alexander Optimization and Control Distributed, Parallel, and Cluster Computing We consider distributed convex-concave saddle point problems over arbitrary connected undirected networks and propose a decentralized distributed algorithm for their solution. The local functions distributed across the nodes are assumed to have global and local groups of variables. For the proposed algorithm we prove non-asymptotic convergence rate estimates with explicit dependence on the network characteristics. To supplement the convergence rate analysis, we propose lower bounds for strongly-convex-strongly-concave and convex-concave saddle-point problems over arbitrary connected undirected networks. We illustrate the considered problem setting by a particular application to distributed calculation of non-regularized Wasserstein barycenters. |
| title | Decentralized Distributed Optimization for Saddle Point Problems |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2102.07758 |