Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives
(2020) SIAM Journal on Optimization — Vol. 30, n° 4, p. 2750-2779 (2020)
Files
CORE_RP_3237.pdf
Open Access - Adobe PDF
- 902.47 KB
Details
- Authors
- Abstract
- In this paper we study $p$-order methods for unconstrained minimization of convex functions that are $p$-times differentiable $(p ≥ 2)$ with $\nu$-Hölder continuous $p$th derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of ${\Os}(\epsilon^{-1/(p+\nu-1)})$ for reducing the functional residual below a given $\epsilon \in (0,1)$. Assuming that $\nu$ is known, we obtain an improved complexity bound of ${\Os}(\epsilon^{-1/(p+\nu)})$ for the corresponding accelerated scheme. For the case in which $\nu$ is unknown, we present a universal accelerated tensor scheme with iteration complexity of ${\Os}(\epsilon^{-p/[(p+1)(p+\nu-1)]})$. A lower complexity bound of ${\Os}(\epsilon^{-2/[3(p+\nu)-2])$ is also obtained for this problem class.
- Affiliations
Citations
Nunes Grapiglia, G., & Nesterov, Y. (2020). Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives. SIAM Journal on Optimization, 30(4), 2750-2779. https://doi.org/10.1137/19M1259432 (Original work published 2020)