Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2311.17296 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916246452174848 |
|---|---|
| author | Kim, Jaeyeon Park, Chanwoo Ozdaglar, Asuman Diakonikolas, Jelena Ryu, Ernest K. |
| author_facet | Kim, Jaeyeon Park, Chanwoo Ozdaglar, Asuman Diakonikolas, Jelena Ryu, Ernest K. |
| contents | While first-order optimization methods are usually designed to efficiently reduce the function value $f(x)$, there has been recent interest in methods efficiently reducing the magnitude of $\nabla f(x)$, and the findings show that the two types of methods exhibit a certain symmetry. In this work, we present mirror duality, a one-to-one correspondence between mirror-descent-type methods reducing function value and reducing gradient magnitude. Using mirror duality, we obtain the dual accelerated mirror descent (dual-AMD) method that efficiently reduces $ψ^*(\nabla f(x))$, where $ψ$ is a distance-generating function and $ψ^*$ quantifies the magnitude of $\nabla f(x)$. We then apply dual-AMD to efficiently reduce $\|\nabla f(\cdot) \|_q$ for $q\in [2,\infty)$ and to efficiently compute $\varepsilon$-approximate solutions of the optimal transport problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_17296 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Mirror Duality in Convex Optimization Kim, Jaeyeon Park, Chanwoo Ozdaglar, Asuman Diakonikolas, Jelena Ryu, Ernest K. Optimization and Control While first-order optimization methods are usually designed to efficiently reduce the function value $f(x)$, there has been recent interest in methods efficiently reducing the magnitude of $\nabla f(x)$, and the findings show that the two types of methods exhibit a certain symmetry. In this work, we present mirror duality, a one-to-one correspondence between mirror-descent-type methods reducing function value and reducing gradient magnitude. Using mirror duality, we obtain the dual accelerated mirror descent (dual-AMD) method that efficiently reduces $ψ^*(\nabla f(x))$, where $ψ$ is a distance-generating function and $ψ^*$ quantifies the magnitude of $\nabla f(x)$. We then apply dual-AMD to efficiently reduce $\|\nabla f(\cdot) \|_q$ for $q\in [2,\infty)$ and to efficiently compute $\varepsilon$-approximate solutions of the optimal transport problem. |
| title | Mirror Duality in Convex Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2311.17296 |