Exploiting higher-order derivatives in convex optimization methods
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929272382291968 |
|---|---|
| author | Kamzolov, Dmitry Gasnikov, Alexander Dvurechensky, Pavel Agafonov, Artem Takáč, Martin |
| author_facet | Kamzolov, Dmitry Gasnikov, Alexander Dvurechensky, Pavel Agafonov, Artem Takáč, Martin |
| contents | Exploiting higher-order derivatives in convex optimization is known at least since 1970's. In each iteration higher-order (also called tensor) methods minimize a regularized Taylor expansion of the objective function, which leads to faster convergence rates if the corresponding higher-order derivative is Lipschitz-continuous. Recently a series of lower iteration complexity bounds for such methods were proved, and a gap between upper an lower complexity bounds was revealed. Moreover, it was shown that such methods can be implementable since the appropriately regularized Taylor expansion of a convex function is also convex and, thus, can be minimized in polynomial time. Only very recently an algorithm with optimal convergence rate $1/k^{(3p+1)/2}$ was proposed for minimizing convex functions with Lipschitz $p$-th derivative. For convex functions with Lipschitz third derivative, these developments allowed to propose a second-order method with convergence rate $1/k^5$, which is faster than the rate $1/k^{3.5}$ of existing second-order methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_13190 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Exploiting higher-order derivatives in convex optimization methods Kamzolov, Dmitry Gasnikov, Alexander Dvurechensky, Pavel Agafonov, Artem Takáč, Martin Optimization and Control Exploiting higher-order derivatives in convex optimization is known at least since 1970's. In each iteration higher-order (also called tensor) methods minimize a regularized Taylor expansion of the objective function, which leads to faster convergence rates if the corresponding higher-order derivative is Lipschitz-continuous. Recently a series of lower iteration complexity bounds for such methods were proved, and a gap between upper an lower complexity bounds was revealed. Moreover, it was shown that such methods can be implementable since the appropriately regularized Taylor expansion of a convex function is also convex and, thus, can be minimized in polynomial time. Only very recently an algorithm with optimal convergence rate $1/k^{(3p+1)/2}$ was proposed for minimizing convex functions with Lipschitz $p$-th derivative. For convex functions with Lipschitz third derivative, these developments allowed to propose a second-order method with convergence rate $1/k^5$, which is faster than the rate $1/k^{3.5}$ of existing second-order methods. |
| title | Exploiting higher-order derivatives in convex optimization methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2208.13190 |