Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization

Kenshi Abe, Mitsuki Sakamoto, Kaito Ariu, Atsushi Iwasaki
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:150-184, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-abe26a, title = {Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization}, author = {Abe, Kenshi and Sakamoto, Mitsuki and Ariu, Kaito and Iwasaki, Atsushi}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {150--184}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/abe26a/abe26a.pdf}, url = {https://proceedings.mlr.press/v306/abe26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization %A Kenshi Abe %A Mitsuki Sakamoto %A Kaito Ariu %A Atsushi Iwasaki %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-abe26a %I PMLR %P 150--184 %U https://proceedings.mlr.press/v306/abe26a.html %V 306 %X 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.
APA
Abe, K., Sakamoto, M., Ariu, K. & Iwasaki, A.. (2026). Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:150-184 Available from https://proceedings.mlr.press/v306/abe26a.html.

Related Material