Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916127609716736 |
|---|---|
| author | Kim, Juno Yamamoto, Kakei Oko, Kazusato Yang, Zhuoran Suzuki, Taiji |
| author_facet | Kim, Juno Yamamoto, Kakei Oko, Kazusato Yang, Zhuoran Suzuki, Taiji |
| contents | In this paper, we extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We propose mean-field Langevin averaged gradient (MFL-AG), a single-loop algorithm that implements gradient descent ascent in the distribution spaces with a novel weighted averaging, and establish average-iterate convergence to the mixed Nash equilibrium. We also study both time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result which accounts for the dependency of the particle interactions on all previous distributions. Furthermore, we propose mean-field Langevin anchored best response (MFL-ABR), a symmetric double-loop algorithm based on best response dynamics with linear last-iterate convergence. Finally, we study applications to zero-sum Markov games and conduct simulations demonstrating long-term optimality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01127 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems Kim, Juno Yamamoto, Kakei Oko, Kazusato Yang, Zhuoran Suzuki, Taiji Optimization and Control Machine Learning In this paper, we extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We propose mean-field Langevin averaged gradient (MFL-AG), a single-loop algorithm that implements gradient descent ascent in the distribution spaces with a novel weighted averaging, and establish average-iterate convergence to the mixed Nash equilibrium. We also study both time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result which accounts for the dependency of the particle interactions on all previous distributions. Furthermore, we propose mean-field Langevin anchored best response (MFL-ABR), a symmetric double-loop algorithm based on best response dynamics with linear last-iterate convergence. Finally, we study applications to zero-sum Markov games and conduct simulations demonstrating long-term optimality. |
| title | Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2312.01127 |