Decentralized Distributed Optimization for Saddle Point Problems
Alexander Rogozin, Aleksandr Nikolaevich Beznosikov, Darina Dvinskikh, Dmitry A. Kovalev, Pavel Dvurechensky, Alexander Vladimirovich Gasnikov · arXiv (Cornell University) · 2021
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.