mlsanityData to 7 Oct 2026

PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium

arXiv 2303.00970 ↗First posted 2 Mar 2023math.OC cs.GT cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We consider the non-convex non-concave objective function in two-player zero-sum continuous games. The existence of pure Nash equilibrium requires stringent conditions, posing a major challenge for this problem. To circumvent this difficulty, we examine the problem of identifying a mixed Nash equilibrium, where strategies are randomized and characterized by probability distributions over continuous domains. To this end, we propose PArticle-based Primal-dual ALgorithm (PAPAL) tailored for a weakly entropy-regularized min-max optimization over probability distributions. This algorithm employs the stochastic movements of particles to represent the updates of random strategies for the ε-mixed Nash equilibrium. We offer a comprehensive convergence analysis of the proposed algorithm, demonstrating its effectiveness. In contrast to prior research that attempted to update particle importance without movements, PAPAL is the first implementable particle-based algorithm accompanied by non-asymptotic quantitative convergence results, running time, and sample complexity guarantees. Our framework contributes novel insights into the particle-based algorithms for continuous min-max optimization in the general non-convex non-concave setting.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 35 of its 80 references that are in the map. First posted on arXiv 2 Mar 2023.

Builds on

35 of 80 references.

References · 35

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2015Domain-Adversarial Training of Neural Networkscited by 3,023
  3. 2016Improved Techniques for Training GANscited by 2,938
  4. 2018Which Training Methods for GANs do actually Converge?cited by 672
  5. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  6. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  7. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  8. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  9. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  10. 2017Training GANs with Optimismcited by 217
  11. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  12. 2020Feature Learning in Infinite-Width Neural Networkscited by 182
23 more
  1. 2017Generalization and Equilibrium in Generative Adversarial Nets (GANs)cited by 165
  2. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  3. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  4. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  5. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  6. 2020A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networkscited by 68
  7. 2022Mean-Field Langevin Dynamics: Exponential Convergence and Annealingcited by 60
  8. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  9. 2019Mean-Field Langevin Dynamics and Energy Landscape of Neural Networkscited by 49
  10. 2018Finding Mixed Nash Equilibria of Generative Adversarial Networkscited by 48
  11. 2018On Gradient-Based Learning in Continuous Gamescited by 46
  12. 2020Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networkscited by 44
  13. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  14. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  15. 2019Convergence of Learning Dynamics in Stackelberg Gamescited by 28
  16. 2020A mean-field analysis of two-player zero-sum gamescited by 28
  17. 2020Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysiscited by 21
  18. 2019Convex Formulation of Overparameterized Deep Neural Networkscited by 16
  19. 2022An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Gamescited by 14
  20. 2017An Online Learning Approach to Generative Adversarial Networkscited by 13
  21. 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
  22. 2022Provably convergent quasistatic dynamics for mean-field two-player zero-sum gamescited by 9
  23. 2017A Globally Linearly Convergent Method for Pointwise Quadratically Supportable Convex-Concave Saddle Point Problemscited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2025Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Gamescited by 2
  2. 2024A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimizationcited by 1