mlsanityData to 7 Oct 2026

Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problems

arXiv 2212.02724 ↗First posted 6 Dec 2022cs.LG math.OC stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

Minimax optimization problems have attracted significant attention in recent years due to their widespread application in numerous machine learning models. To solve the minimax problem, a wide variety of stochastic optimization methods have been proposed. However, most of them ignore the distributed setting where the training data is distributed on multiple workers. In this paper, we developed a novel decentralized stochastic gradient descent ascent method for the finite-sum minimax problem. In particular, by employing the variance-reduced gradient, our method can achieve O(frac√nkappa3(1-λ)2ε2) sample complexity and O(frackappa3(1-λ)2ε2) communication complexity for the nonconvex-strongly-concave minimax problem. As far as we know, our work is the first one to achieve such theoretical complexities for this kind of minimax problem. At last, we apply our method to AUC maximization, and the experimental results confirm the effectiveness of our method.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 27 of its 40 references that are in the map. First posted on arXiv 6 Dec 2022.

Builds on

27 of 40 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. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  6. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  7. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  8. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  9. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 109
  10. 2018Distributed Stochastic Gradient Tracking Methodscited by 106
  11. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  12. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
15 more
  1. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  2. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  3. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  4. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  5. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  6. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  7. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  8. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  9. 2020Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learningcited by 24
  10. 2019Communication-Efficient Local Decentralized SGD Methodscited by 21
  11. 2020Gradient Descent Ascent for Minimax Problems on Riemannian Manifoldscited by 16
  12. 2020Gradient Free Minimax Optimization: Variance Reduction and Faster Convergencecited by 11
  13. 2018Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Lojasiewicz Conditioncited by 7
  14. 2020Efficient Projection-Free Algorithms for Saddle Point Problemscited by 6
  15. 2020Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problemscited by 4

Built on by

Cited by year

Citing papers per year: 2023: 6; 2024: 4; 2025: 1.

11 papers.

  1. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  2. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
  3. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  4. 2023Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problemscited by 6
  5. 2023Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problemscited by 4
  6. 2023Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problemscited by 2
  7. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  8. 2024Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentumcited by 1
  9. 2023Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems?cited by 0
  10. 2023Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problemscited by 0
  11. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0