The limit points of (optimistic) gradient descent in min-max optimization
© 2018 Curran Associates Inc.All rights reserved. Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cyc...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143126 |
| _version_ | 1826204590274510848 |
|---|---|
| author | Daskalakis, C Panageas, I |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daskalakis, C Panageas, I |
| author_sort | Daskalakis, C |
| collection | MIT |
| description | © 2018 Curran Associates Inc.All rights reserved. Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cycle, and there is no good understanding of their limit points when they do not. When they converge, do they converge to local min-max solutions? We characterize the limit points of two basic first order methods, namely Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA). We show that both dynamics avoid unstable critical points for almost all initializations. Moreover, for small step sizes and under mild assumptions, the set of OGDA-stable critical points is a superset of GDA-stable critical points, which is a superset of local min-max solutions (strict in some cases). The connecting thread is that the behavior of these dynamics can be studied from a dynamical systems perspective. |
| first_indexed | 2024-09-23T12:57:52Z |
| format | Article |
| id | mit-1721.1/143126 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:57:52Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | mit-1721.1/1431262023-01-23T20:19:00Z The limit points of (optimistic) gradient descent in min-max optimization Daskalakis, C Panageas, I Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 Curran Associates Inc.All rights reserved. Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cycle, and there is no good understanding of their limit points when they do not. When they converge, do they converge to local min-max solutions? We characterize the limit points of two basic first order methods, namely Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA). We show that both dynamics avoid unstable critical points for almost all initializations. Moreover, for small step sizes and under mild assumptions, the set of OGDA-stable critical points is a superset of GDA-stable critical points, which is a superset of local min-max solutions (strict in some cases). The connecting thread is that the behavior of these dynamics can be studied from a dynamical systems perspective. 2022-06-14T19:17:17Z 2022-06-14T19:17:17Z 2018-01-01 2022-06-14T19:09:01Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143126 Daskalakis, C and Panageas, I. 2018. "The limit points of (optimistic) gradient descent in min-max optimization." Advances in Neural Information Processing Systems, 2018-December. en https://papers.nips.cc/paper/2018/hash/139c3c1b7ca46a9d4fd6d163d98af635-Abstract.html Advances in Neural Information Processing Systems Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Neural Information Processing Systems (NIPS) |
| spellingShingle | Daskalakis, C Panageas, I The limit points of (optimistic) gradient descent in min-max optimization |
| title | The limit points of (optimistic) gradient descent in min-max optimization |
| title_full | The limit points of (optimistic) gradient descent in min-max optimization |
| title_fullStr | The limit points of (optimistic) gradient descent in min-max optimization |
| title_full_unstemmed | The limit points of (optimistic) gradient descent in min-max optimization |
| title_short | The limit points of (optimistic) gradient descent in min-max optimization |
| title_sort | limit points of optimistic gradient descent in min max optimization |
| url | https://hdl.handle.net/1721.1/143126 |
| work_keys_str_mv | AT daskalakisc thelimitpointsofoptimisticgradientdescentinminmaxoptimization AT panageasi thelimitpointsofoptimisticgradientdescentinminmaxoptimization AT daskalakisc limitpointsofoptimisticgradientdescentinminmaxoptimization AT panageasi limitpointsofoptimisticgradientdescentinminmaxoptimization |