When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916120041095168 |
|---|---|
| author | Kim, Junhyung Lyle Gidel, Gauthier Kyrillidis, Anastasios Pedregosa, Fabian |
| author_facet | Kim, Junhyung Lyle Gidel, Gauthier Kyrillidis, Anastasios Pedregosa, Fabian |
| contents | The extragradient method has gained popularity due to its robust convergence properties for differentiable games. Unlike single-objective optimization, game dynamics involve complex interactions reflected by the eigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method to diverge, even for bilinear games, while the extragradient method achieves convergence. Building on the recently proven accelerated convergence of the momentum extragradient method for bilinear games \citep{azizian2020accelerating}, we use a polynomial-based analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios encompass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_04659 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | When is Momentum Extragradient Optimal? A Polynomial-Based Analysis Kim, Junhyung Lyle Gidel, Gauthier Kyrillidis, Anastasios Pedregosa, Fabian Machine Learning Optimization and Control The extragradient method has gained popularity due to its robust convergence properties for differentiable games. Unlike single-objective optimization, game dynamics involve complex interactions reflected by the eigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method to diverge, even for bilinear games, while the extragradient method achieves convergence. Building on the recently proven accelerated convergence of the momentum extragradient method for bilinear games \citep{azizian2020accelerating}, we use a polynomial-based analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios encompass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate. |
| title | When is Momentum Extragradient Optimal? A Polynomial-Based Analysis |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2211.04659 |