A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914819295150080 |
|---|---|
| author | Kerger, Phillip Molinaro, Marco Jiang, Hongyi Basu, Amitabh |
| author_facet | Kerger, Phillip Molinaro, Marco Jiang, Hongyi Basu, Amitabh |
| contents | Given any algorithm for convex optimization that uses exact first-order information (i.e., function values and subgradients), we show how to use such an algorithm to solve the problem with access to inexact first-order information. This is done in a ``black-box'' manner without knowledge of the internal workings of the algorithm. This complements previous work that considers the performance of specific algorithms like (accelerated) gradient descent with inexact information. In particular, our results apply to a wider range of algorithms beyond variants of gradient descent, e.g., projection-free methods, cutting-plane methods, or any other first-order methods formulated in the future. Further, they also apply to algorithms that handle structured nonconvexities like mixed-integer decision variables. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00576 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles Kerger, Phillip Molinaro, Marco Jiang, Hongyi Basu, Amitabh Optimization and Control Given any algorithm for convex optimization that uses exact first-order information (i.e., function values and subgradients), we show how to use such an algorithm to solve the problem with access to inexact first-order information. This is done in a ``black-box'' manner without knowledge of the internal workings of the algorithm. This complements previous work that considers the performance of specific algorithms like (accelerated) gradient descent with inexact information. In particular, our results apply to a wider range of algorithms beyond variants of gradient descent, e.g., projection-free methods, cutting-plane methods, or any other first-order methods formulated in the future. Further, they also apply to algorithms that handle structured nonconvexities like mixed-integer decision variables. |
| title | A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.00576 |