mlsanityData to 14 Oct 2026

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

arXiv 2010.13112 ↗First posted 25 Oct 2020cs.LG cs.DC math.OCcited by 14

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 5; 2024: 0; 2025: 3; 2026: 1.

14 papers.

Sort:

  1. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  2. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  3. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
  4. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  5. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  6. 2022Decentralized Stochastic Variance Reduced Extragradient Methodcited by 3
  7. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  8. 2021CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problemscited by 2
  9. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  10. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 2
  11. 2026γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functionscited by 1
  12. 2022SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalitiescited by 0
2 more
  1. 2023Federated Composite Saddle Point Optimizationcited by 0
  2. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0