Decentralized Distributed Optimization for Saddle Point Problems

Abstract

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.

References in corpus (6)

• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Robust clustering tools based on optimal transportation
• Optimal Algorithms for Decentralized Stochastic Variational Inequalities
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization
• Optimal Gradient Tracking for Decentralized Optimization