# Distributed saddle point problems for strongly concave-convex functions arXiv: https://arxiv.org/abs/2202.05812 · HTML: https://mlsanity.com/paper/2202.05812/ ## Key facts - Cited by 3 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 79 references that are in the map. - First posted on arXiv 11 Feb 2022. ## Builds on (most cited first, 30 of 32) - [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017) - [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019) - [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014) - [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019) - [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018) - [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017) - [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020) - [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016) - [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017) - [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018) - [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014) - [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018) - [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017) - [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018) - [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021) - [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018) - [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018) - [A general framework for decentralized optimization with first-order methods](https://mlsanity.com/paper/2009.05837/) (2020) - [A linear algorithm for optimization over directed graphs with geometric convergence](https://mlsanity.com/paper/1803.02503/) (2018) - [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021) - [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021) - [ADD-OPT: Accelerated Distributed Directed Optimization](https://mlsanity.com/paper/1607.04757/) (2016) - [Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms](https://mlsanity.com/paper/2010.13112/) (2020) - [Optimal Algorithms for Decentralized Stochastic Variational Inequalities](https://mlsanity.com/paper/2202.02771/) (2022) - [A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency](https://mlsanity.com/paper/2110.01594/) (2021) - [Distributed support-vector-machine over dynamic balanced directed networks](https://mlsanity.com/paper/2104.00399/) (2021) - [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021) - [Push-SAGA: A decentralized stochastic algorithm with variance reduction over directed graphs](https://mlsanity.com/paper/2008.06082/) (2020) - [Distributed Nesterov gradient methods over arbitrary graphs](https://mlsanity.com/paper/1901.06995/) (2019) - [SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimization](https://mlsanity.com/paper/1803.08198/) (2018) ## Built on by (most cited first, 3 of 3) - [A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games](https://mlsanity.com/paper/2503.18224/) (2025) - [Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems](https://mlsanity.com/paper/2309.00997/) (2023) - [Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach](https://mlsanity.com/paper/2410.14592/) (2024) ## Abstract (arXiv) In this paper, we propose GT-GDA, a distributed optimization method to solve saddle point problems of the form: minx maxy F(x,y) :=G(x) + langle y, overlineP x rangle - H(y), where the functions G(·), H(·), and the the coupling matrix overlineP are distributed over a strongly connected network of nodes. GT-GDA is a first-order method that uses gradient tracking to eliminate the dissimilarity caused by heterogeneous data distribution among the nodes. In the most general form, GT-GDA includes a consensus over the local coupling matrices to achieve the optimal (unique) saddle point, however, at the expense of increased communication. To avoid this, we propose a more efficient variant GT-GDA-Lite that does not incur the additional communication and analyze its convergence in various scenarios. We show that GT-GDA converges linearly to the unique saddle point solution when G(·) is smooth and convex, H(·) is smooth and strongly convex, and the global coupling matrix overlineP has full column rank. We further characterize the regime under which GT-GDA exhibits a network topology-independent convergence behavior. We next show the linear convergence of GT-GDA to an error around the unique saddle point, which goes to zero when the coupling cost langle mathbf y, overlineP mathbf x rangle is common to all nodes, or when G(·) and H(·) are quadratic. Numerical experiments illustrate the convergence properties and importance of GT-GDA and GT-GDA-Lite for several applications.