# Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2020.

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

- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems](https://mlsanity.com/paper/2105.14216/) (2021)
- [Distributed Extra-gradient with Optimal Complexity and Communication Guarantees](https://mlsanity.com/paper/2308.09187/) (2023)
- [Federated Stochastic Minimax Optimization under Heavy-Tailed Noises](https://mlsanity.com/paper/2511.04456/) (2025)
- [γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](https://mlsanity.com/paper/2602.13506/) (2026)
- [SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities](https://mlsanity.com/paper/2210.05994/) (2022)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)
- [Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees](https://mlsanity.com/paper/2509.04133/) (2025)

## Abstract (arXiv)

This paper focuses on the distributed optimization of stochastic saddle point problems. The first part of the paper is devoted to lower bounds for the centralized and decentralized distributed methods for smooth (strongly) convex-(strongly) concave saddle point problems, as well as the near-optimal algorithms by which these bounds are achieved. Next, we present a new federated algorithm for centralized distributed saddle-point problems - Extra Step Local SGD. The theoretical analysis of the new method is carried out for strongly convex-strongly concave and non-convex-non-concave problems. In the experimental part of the paper, we show the effectiveness of our method in practice. In particular, we train GANs in a distributed manner.