A Decentralized Proximal Point-type Method for Saddle Point Problems

Abstract

In this paper, we focus on solving a class of constrained non-convex non-concave saddle point problems in a decentralized manner by a group of nodes in a network. Specifically, we assume that each node has access to a summand of a global objective function and nodes are allowed to exchange information only with their neighboring nodes. We propose a decentralized variant of the proximal point method for solving this problem. We show that when the objective function is $\rho$-weakly convex-weakly concave the iterates converge to approximate stationarity with a rate of $\mathcal{O}(1/\sqrt{T})$ where the approximation error depends linearly on $\sqrt{\rho }$. We further show that when the objective function satisfies the Minty VI condition (which generalizes the convex-concave case) we obtain convergence to stationarity with a rate of $\mathcal{O}(1/\sqrt{T})$. To the best of our knowledge, our proposed method is the first decentralized algorithm with theoretical guarantees for solving a non-convex non-concave decentralized saddle point problem. Our numerical results for training a general adversarial network (GAN) in a decentralized manner match our theoretical guarantees.

18 pages

References in corpus (15)

• Towards Deep Learning Models Resistant to Adversarial Attacks
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability
• A Variational Inequality Perspective on Generative Adversarial Networks
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• Local Saddle Point Optimization: A Curvature Exploitation Approach
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition

Cited by in corpus (7)

• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Recent theoretical advances in decentralized distributed convex optimization
• Distributed Saddle-Point Problems Under Similarity
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Alternating Direction Method of Multipliers for Decomposable Saddle-Point Problems