mlsanityData to 14 Oct 2026

Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems?

arXiv 2304.11788 ↗First posted 24 Apr 2023cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range of machine learning models. However, the current theoretical understanding of its convergence rate is far from satisfactory since existing works only focus on the nonconvex-strongly-concave problem. This motivates us to study decentralized minimax optimization algorithms for the nonconvex-nonconcave problem. To this end, we develop two novel decentralized stochastic variance-reduced gradient descent ascent algorithms for the finite-sum nonconvex-nonconcave problem that satisfies the Polyak-Lojasiewicz (PL) condition. In particular, our theoretical analyses demonstrate how to conduct local updates and perform communication to achieve the linear convergence rate. To the best of our knowledge, this is the first work achieving linear convergence rates for decentralized nonconvex-nonconcave problems. Finally, we verify the performance of our algorithms on both synthetic and real-world datasets. The experimental results confirm the efficacy of our algorithms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 19 of its 30 references that are in the map. First posted on arXiv 24 Apr 2023.

Builds on

19 of 30 references.

References · 19

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  4. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  7. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  8. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  9. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  10. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  11. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  12. 2016A Geometric Analysis of Phase Retrievalcited by 92
7 more
  1. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  2. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  3. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  4. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  5. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
  6. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 29
  7. 2022Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problemscited by 11

Built on by

Not cited yet.