Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.05747 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917549805928448 |
|---|---|
| author | Abe, Kenshi Sakamoto, Mitsuki Ariu, Kaito Iwasaki, Atsushi |
| author_facet | Abe, Kenshi Sakamoto, Mitsuki Ariu, Kaito Iwasaki, Atsushi |
| contents | This paper proposes asymmetric perturbation, where only one player's payoff function is perturbed, for solving bilinear saddle-point optimization problems, commonly arising in minimax problems, game theory, and constrained optimization. Symmetric perturbation is known to require decreasing its strength to ensure convergence to a solution, i.e., an equilibrium in the original game, resulting in a slower rate. First, with asymmetric perturbation, we show that, for a sufficiently small perturbation strength, the equilibrium strategy of the asymmetrically perturbed game coincides with an equilibrium strategy of the original unperturbed game. Second, building on this coincidence, we construct a learning algorithm with a linear last-iterate convergence rate. Third, motivated by the fact that the coincidence relies on the perturbation strength being sufficiently small, we also provide a parameter-free variant, retaining the linear rate. Finally, we empirically demonstrate fast convergence toward equilibria in both normal-form and extensive-form games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05747 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization Abe, Kenshi Sakamoto, Mitsuki Ariu, Kaito Iwasaki, Atsushi Optimization and Control This paper proposes asymmetric perturbation, where only one player's payoff function is perturbed, for solving bilinear saddle-point optimization problems, commonly arising in minimax problems, game theory, and constrained optimization. Symmetric perturbation is known to require decreasing its strength to ensure convergence to a solution, i.e., an equilibrium in the original game, resulting in a slower rate. First, with asymmetric perturbation, we show that, for a sufficiently small perturbation strength, the equilibrium strategy of the asymmetrically perturbed game coincides with an equilibrium strategy of the original unperturbed game. Second, building on this coincidence, we construct a learning algorithm with a linear last-iterate convergence rate. Third, motivated by the fact that the coincidence relies on the perturbation strength being sufficiently small, we also provide a parameter-free variant, retaining the linear rate. Finally, we empirically demonstrate fast convergence toward equilibria in both normal-form and extensive-form games. |
| title | Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2506.05747 |