Last-iterate convergence: Zero-sum games and constrained min-max optimization
© Constantinos Daskalakis and Ioannis Panageas. Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al [Daskalakis et al., ICLR, 2018] and follow-up work of Liang and Stokes [Liang and Stokes, 2018] have established that a variant...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143460 |
| _version_ | 1826203898342277120 |
|---|---|
| author | Daskalakis, C Panageas, I |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Daskalakis, C Panageas, I |
| author_sort | Daskalakis, C |
| collection | MIT |
| description | © Constantinos Daskalakis and Ioannis Panageas. Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al [Daskalakis et al., ICLR, 2018] and follow-up work of Liang and Stokes [Liang and Stokes, 2018] have established that a variant of the widely used Gradient Descent/Ascent procedure, called “Optimistic Gradient Descent/Ascent (OGDA)”, exhibits last-iterate convergence to saddle points in unconstrained convex-concave min-max optimization problems. We show that the same holds true in the more general problem of constrained min-max optimization under a variant of the no-regret Multiplicative-Weights-Update method called “Optimistic Multiplicative-Weights Update (OMWU)”. This answers an open question of Syrgkanis et al [Syrgkanis et al., NIPS, 2015]. The proof of our result requires fundamentally different techniques from those that exist in no-regret learning literature and the aforementioned papers. We show that OMWU monotonically improves the Kullback-Leibler divergence of the current iterate to the (appropriately normalized) min-max solution until it enters a neighborhood of the solution. Inside that neighborhood we show that OMWU becomes a contracting map converging to the exact solution. We believe that our techniques will be useful in the analysis of the last iterate of other learning algorithms. |
| first_indexed | 2024-09-23T12:45:06Z |
| format | Article |
| id | mit-1721.1/143460 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:45:06Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | mit-1721.1/1434602023-02-13T21:35:00Z Last-iterate convergence: Zero-sum games and constrained min-max optimization Daskalakis, C Panageas, I Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Constantinos Daskalakis and Ioannis Panageas. Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al [Daskalakis et al., ICLR, 2018] and follow-up work of Liang and Stokes [Liang and Stokes, 2018] have established that a variant of the widely used Gradient Descent/Ascent procedure, called “Optimistic Gradient Descent/Ascent (OGDA)”, exhibits last-iterate convergence to saddle points in unconstrained convex-concave min-max optimization problems. We show that the same holds true in the more general problem of constrained min-max optimization under a variant of the no-regret Multiplicative-Weights-Update method called “Optimistic Multiplicative-Weights Update (OMWU)”. This answers an open question of Syrgkanis et al [Syrgkanis et al., NIPS, 2015]. The proof of our result requires fundamentally different techniques from those that exist in no-regret learning literature and the aforementioned papers. We show that OMWU monotonically improves the Kullback-Leibler divergence of the current iterate to the (appropriately normalized) min-max solution until it enters a neighborhood of the solution. Inside that neighborhood we show that OMWU becomes a contracting map converging to the exact solution. We believe that our techniques will be useful in the analysis of the last iterate of other learning algorithms. 2022-06-17T14:24:41Z 2022-06-17T14:24:41Z 2019-01-01 2022-06-17T14:20:15Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143460 Daskalakis, C and Panageas, I. 2019. "Last-iterate convergence: Zero-sum games and constrained min-max optimization." Leibniz International Proceedings in Informatics, LIPIcs, 124. en 10.4230/LIPIcs.ITCS.2019.27 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 3.0 unported license https://creativecommons.org/licenses/by/3.0/ application/pdf DROPS |
| spellingShingle | Daskalakis, C Panageas, I Last-iterate convergence: Zero-sum games and constrained min-max optimization |
| title | Last-iterate convergence: Zero-sum games and constrained min-max optimization |
| title_full | Last-iterate convergence: Zero-sum games and constrained min-max optimization |
| title_fullStr | Last-iterate convergence: Zero-sum games and constrained min-max optimization |
| title_full_unstemmed | Last-iterate convergence: Zero-sum games and constrained min-max optimization |
| title_short | Last-iterate convergence: Zero-sum games and constrained min-max optimization |
| title_sort | last iterate convergence zero sum games and constrained min max optimization |
| url | https://hdl.handle.net/1721.1/143460 |
| work_keys_str_mv | AT daskalakisc lastiterateconvergencezerosumgamesandconstrainedminmaxoptimization AT panageasi lastiterateconvergencezerosumgamesandconstrainedminmaxoptimization |