# Distributed Saddle-Point Problems Under Similarity

arXiv: https://arxiv.org/abs/2107.10706 · HTML: https://mlsanity.com/paper/2107.10706/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 22 Jul 2021.

## Builds on (most cited first, 27 of 27)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [A Decentralized Parallel Algorithm for Training Generative Adversarial Nets](https://mlsanity.com/paper/1910.12999/) (2019)
- [Communication-Efficient Accurate Statistical Estimation](https://mlsanity.com/paper/1906.04870/) (2019)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond](https://mlsanity.com/paper/1908.02246/) (2019)
- [Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses](https://mlsanity.com/paper/1907.01771/) (2019)
- [A Decentralized Proximal Point-type Method for Saddle Point Problems](https://mlsanity.com/paper/1910.14380/) (2019)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Decentralized Distributed Optimization for Saddle Point Problems](https://mlsanity.com/paper/2102.07758/) (2021)
- [Improved Complexity Bounds in Wasserstein Barycenter Problem](https://mlsanity.com/paper/2010.04677/) (2020)
- [Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss](https://mlsanity.com/paper/1501.00263/) (2015)
- [Decentralized Personalized Federated Learning for Min-Max Problems](https://mlsanity.com/paper/2106.07289/) (2021)

## Built on by (most cited first, 8 of 8)

- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees](https://mlsanity.com/paper/2110.03313/) (2021)
- [Federated Minimax Optimization with Client Heterogeneity](https://mlsanity.com/paper/2302.04249/) (2023)
- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning](https://mlsanity.com/paper/2409.14280/) (2024)
- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [Local Methods with Adaptivity via Scaling](https://mlsanity.com/paper/2406.00846/) (2024)
- [Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems](https://mlsanity.com/paper/2309.00997/) (2023)

## Abstract (arXiv)

We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type - master/workers (thus centralized) architectures and meshed (thus decentralized) networks. The local functions at each node are assumed to be similar, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general class of algorithms solving the SPP. We show that a given suboptimality ε>0 is achieved over master/workers networks in Omegabig(Delta· δ/μ· log (1/varepsilon)big) rounds of communications, where δ>0 measures the degree of similarity of the local functions, μ is their strong convexity constant, and Delta is the diameter of the network. The lower communication complexity bound over meshed networks reads Omegabig(1/√ρ · δ/μ·log (1/varepsilon)big), where ρ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust logistic regression problem.