Extracting Dual Solutions via Primal Optimizers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912143516893184 |
|---|---|
| author | Carmon, Yair Jambulapati, Arun O'Carroll, Liam Sidford, Aaron |
| author_facet | Carmon, Yair Jambulapati, Arun O'Carroll, Liam Sidford, Aaron |
| contents | We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associated dual maximin optimization problem. Our method adds recursive regularization over a logarithmic number of rounds where each round consists of an approximate regularized primal optimization followed by the computation of a dual best response. We apply this result to obtain new state-of-the-art runtimes for solving matrix games in specific parameter regimes, obtain improved query complexity for solving the dual of the CVaR distributionally robust optimization (DRO) problem, and recover the optimal query complexity for finding a stationary point of a convex function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02949 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extracting Dual Solutions via Primal Optimizers Carmon, Yair Jambulapati, Arun O'Carroll, Liam Sidford, Aaron Optimization and Control Data Structures and Algorithms We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associated dual maximin optimization problem. Our method adds recursive regularization over a logarithmic number of rounds where each round consists of an approximate regularized primal optimization followed by the computation of a dual best response. We apply this result to obtain new state-of-the-art runtimes for solving matrix games in specific parameter regimes, obtain improved query complexity for solving the dual of the CVaR distributionally robust optimization (DRO) problem, and recover the optimal query complexity for finding a stationary point of a convex function. |
| title | Extracting Dual Solutions via Primal Optimizers |
| topic | Optimization and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.02949 |