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

GRAPIGLIA Geovani, Nunes () and Yurii, Nesterov ()
Additional contact information
GRAPIGLIA Geovani, Nunes: Université catholique de Louvain, Belgium
Yurii, Nesterov: Université catholique de Louvain, CORE, Belgium

No 2019028, LIDAM Discussion Papers 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 n-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 O(e-1/(p+n-1))$ for reducing the functional residual below a given e Î\in (0,1). Assuming that n is known, we obtain an improved complexity bound of O(e-1/(p+n))$ for the corresponding accelerated scheme. For the case in which n is unknown, we present a universal accelerated tensor scheme with iteration complexity of O(e-p/[(p+1)(p+n-1)]). A lower complexity bound of O(e-2/[3(p+n)-2]) is also obtained for this problem class.

Keywords: unconstrained minimization; higher-order methods; tensor methods; Hölder condition; worst-case global complexity; bounds (search for similar items in EconPapers)
Date: 2019-12-17
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2019.html (application/pdf)

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:louvco:2019028

Access Statistics for this paper

More papers in LIDAM Discussion Papers 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 ().