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

arXiv: https://arxiv.org/abs/2303.00970 · HTML: https://mlsanity.com/paper/2303.00970/

## Key facts

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

## Builds on (most cited first, 30 of 35)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [Which Training Methods for GANs do actually Converge?](https://mlsanity.com/paper/1801.04406/) (2018)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Feature Learning in Infinite-Width Neural Networks](https://mlsanity.com/paper/2011.14522/) (2020)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks](https://mlsanity.com/paper/2001.11443/) (2020)
- [Mean-Field Langevin Dynamics: Exponential Convergence and Annealing](https://mlsanity.com/paper/2202.01009/) (2022)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Mean-Field Langevin Dynamics and Energy Landscape of Neural Networks](https://mlsanity.com/paper/1905.07769/) (2019)
- [Finding Mixed Nash Equilibria of Generative Adversarial Networks](https://mlsanity.com/paper/1811.02002/) (2018)
- [On Gradient-Based Learning in Continuous Games](https://mlsanity.com/paper/1804.05464/) (2018)
- [Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/2007.01452/) (2020)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [Convergence of Learning Dynamics in Stackelberg Games](https://mlsanity.com/paper/1906.01217/) (2019)
- [A mean-field analysis of two-player zero-sum games](https://mlsanity.com/paper/2002.06277/) (2020)
- [Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis](https://mlsanity.com/paper/2012.15477/) (2020)
- [Convex Formulation of Overparameterized Deep Neural Networks](https://mlsanity.com/paper/1911.07626/) (2019)

## Built on by (most cited first, 2 of 2)

- [Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games](https://mlsanity.com/paper/2505.07642/) (2025)
- [A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization](https://mlsanity.com/paper/2404.12312/) (2024)

## 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.