mlsanityData to 7 Oct 2026

An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization

arXiv 2212.02387 ↗First posted 5 Dec 2022cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

This paper studies the stochastic nonconvex-strongly-concave minimax optimization over a multi-agent network. We propose an efficient algorithm, called Decentralized Recursive gradient descEnt Ascent Method (DREAM), which achieves the best-known theoretical guarantee for finding the ε-stationary points. Concretely, it requires O(min (kappa3ε-3,kappa2 √N ε-2 )) stochastic first-order oracle (SFO) calls and tildeO(kappa2 ε-2) communication rounds, where kappa is the condition number and N is the total number of individual functions. Our numerical experiments also validate the superiority of DREAM over previous methods.

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

Builds on

50 of 83 references.

References · 50

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  9. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 218
  10. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  11. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  12. 2013On the Convergence of Decentralized Gradient Descentcited by 158
38 more
  1. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  2. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  3. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  4. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  5. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  6. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  7. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  8. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  9. 2017Gradient descent GAN optimization is locally stablecited by 65
  10. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  11. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  12. 2020Optimal Complexity in Decentralized Trainingcited by 59
  13. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  14. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  15. 2017Learning with Average Top-k Losscited by 52
  16. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  17. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  18. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  19. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  20. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  21. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
  22. 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
  23. 2017Accelerated Distributed Nesterov Gradient Descentcited by 24
  24. 2020Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learningcited by 24
  25. 2022SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problemscited by 23
  26. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  27. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  28. 2020An Optimal Algorithm for Decentralized Finite Sum Optimizationcited by 19
  29. 2020Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Conditioncited by 19
  30. 2021Optimal Gradient Tracking for Decentralized Optimizationcited by 18
  31. 2020Fast decentralized non-convex finite-sum optimization with recursive variance reductioncited by 17
  32. 2021DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimizationcited by 16
  33. 2019Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structurecited by 15
  34. 2020Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimizationcited by 13
  35. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  36. 2020Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problemscited by 7
  37. 2021A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimizationcited by 5
  38. 2022On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimizationcited by 3

Built on by

Cited by year

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

6 papers.

  1. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
  2. 2023Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problemscited by 2
  3. 2025DICE: Data Influence Cascade in Decentralized Learningcited by 2
  4. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  5. 2024Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updatescited by 0
  6. 2025Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approachcited by 0