mlsanityData to 7 Oct 2026

Distributed Saddle-Point Problems Under Similarity

arXiv 2107.10706 ↗First posted 22 Jul 2021math.OC cs.DC cs.LGcited by 8

Not on the map. Why?

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.

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

Builds on

27 of 48 references.

References · 27

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2019Advances and Open Problems in Federated Learningcited by 3,021
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  7. 2015Distributionally Robust Logistic Regressioncited by 124
  8. 2017Network Topology and Communication-Computation Tradeoffs in Decentralized Optimizationcited by 119
  9. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  10. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  11. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  12. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
15 more
  1. 2017GIANT: Globally Improved Approximate Newton Method for Distributed Optimizationcited by 43
  2. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  3. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 42
  4. 2019Communication-Efficient Accurate Statistical Estimationcited by 32
  5. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 29
  6. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  7. 2020Multi-consensus Decentralized Accelerated Gradient Descentcited by 20
  8. 2019On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyondcited by 18
  9. 2019Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Lossescited by 17
  10. 2019A Decentralized Proximal Point-type Method for Saddle Point Problemscited by 17
  11. 2014Gradient Sliding for Composite Optimizationcited by 14
  12. 2021Decentralized Distributed Optimization for Saddle Point Problemscited by 10
  13. 2020Improved Complexity Bounds in Wasserstein Barycenter Problemcited by 9
  14. 2015Communication-Efficient Distributed Optimization of Self-Concordant Empirical Losscited by 7
  15. 2021Decentralized Personalized Federated Learning for Min-Max Problemscited by 4

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 3; 2023: 2; 2024: 2.

8 papers.

  1. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  2. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  3. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  4. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  5. 2024Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learningcited by 2
  6. 2022Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problemscited by 1
  7. 2024Local Methods with Adaptivity via Scalingcited by 1
  8. 2023Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problemscited by 0