Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives

Geovani Nunes Grapiglia () and Yurii Nesterov ()
Additional contact information
Geovani Nunes Grapiglia: Université catholique de Louvain, ICTEAM
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3237, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: Unconstrained minimization; high-order methods; tensor methods; Hölder condition; worst-case global complexity bounds (search for similar items in EconPapers)
Pages: 30
Date: 2023-01-01
Note: In: SIAM Journal on Optimization, 2020, vol. 30(4), p. 2750-2779
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3237

DOI: 10.1137/19M1259432

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().