On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging

Chris Junchi Li, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, Michael Jordan
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:9793-9826, 2022.

Abstract

We study the stochastic bilinear minimax optimization problem, presenting an analysis of the same-sample Stochastic ExtraGradient (SEG) method with constant step size, and presenting variations of the method that yield favorable convergence. In sharp contrasts with the basic SEG method whose last iterate only contracts to a fixed neighborhood of the Nash equilibrium, SEG augmented with iteration averaging provably converges to the Nash equilibrium under the same standard settings, and such a rate is further improved by incorporating a scheduled restarting procedure. In the interpolation setting where noise vanishes at the Nash equilibrium, we achieve an optimal convergence rate up to tight constants. We present numerical experiments that validate our theoretical findings and demonstrate the effectiveness of the SEG method when equipped with iteration averaging and restarting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-junchi-li22a, title = { On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging }, author = {Junchi Li, Chris and Yu, Yaodong and Loizou, Nicolas and Gidel, Gauthier and Ma, Yi and Le Roux, Nicolas and Jordan, Michael}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {9793--9826}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/junchi-li22a/junchi-li22a.pdf}, url = {https://proceedings.mlr.press/v151/junchi-li22a.html}, abstract = { We study the stochastic bilinear minimax optimization problem, presenting an analysis of the same-sample Stochastic ExtraGradient (SEG) method with constant step size, and presenting variations of the method that yield favorable convergence. In sharp contrasts with the basic SEG method whose last iterate only contracts to a fixed neighborhood of the Nash equilibrium, SEG augmented with iteration averaging provably converges to the Nash equilibrium under the same standard settings, and such a rate is further improved by incorporating a scheduled restarting procedure. In the interpolation setting where noise vanishes at the Nash equilibrium, we achieve an optimal convergence rate up to tight constants. We present numerical experiments that validate our theoretical findings and demonstrate the effectiveness of the SEG method when equipped with iteration averaging and restarting. } }
Endnote
%0 Conference Paper %T On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging %A Chris Junchi Li %A Yaodong Yu %A Nicolas Loizou %A Gauthier Gidel %A Yi Ma %A Nicolas Le Roux %A Michael Jordan %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-junchi-li22a %I PMLR %P 9793--9826 %U https://proceedings.mlr.press/v151/junchi-li22a.html %V 151 %X We study the stochastic bilinear minimax optimization problem, presenting an analysis of the same-sample Stochastic ExtraGradient (SEG) method with constant step size, and presenting variations of the method that yield favorable convergence. In sharp contrasts with the basic SEG method whose last iterate only contracts to a fixed neighborhood of the Nash equilibrium, SEG augmented with iteration averaging provably converges to the Nash equilibrium under the same standard settings, and such a rate is further improved by incorporating a scheduled restarting procedure. In the interpolation setting where noise vanishes at the Nash equilibrium, we achieve an optimal convergence rate up to tight constants. We present numerical experiments that validate our theoretical findings and demonstrate the effectiveness of the SEG method when equipped with iteration averaging and restarting.
APA
Junchi Li, C., Yu, Y., Loizou, N., Gidel, G., Ma, Y., Le Roux, N. & Jordan, M.. (2022). On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:9793-9826 Available from https://proceedings.mlr.press/v151/junchi-li22a.html.

Related Material