Implementable tensor methods in unconstrained convex optimization

Yurii Nesterov ()
Additional contact information
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

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

Abstract: In this paper we develop new tensor methods for unconstrained convex optimization, which solve at each iteration an auxiliary problem of minimizing convex multivariate polynomial. We analyze the simplest scheme, based on minimization of a regularized local model of the objective function, and its accelerated version obtained in the framework of estimating sequences. Their rates of convergence are compared with the worst-case lower complexity bounds for corresponding problem classes. Finally, for the third-order methods, we suggest an efficient technique for solving the auxiliary problem, which is based on the recently developed relative smoothness condition (Bauschke et al. in Math Oper Res 42:330–348, 2017; Lu et al. in SIOPT 28(1):333–354, 2018). With this elaboration, the third-order methods become implementable and very fast. The rate of convergence in terms of the function value for the accelerated third-order scheme reaches the level O(1k4) , where k is the number of iterations. This is very close to the lower bound of the order O(1k5) , which is also justified in this paper. At the same time, in many important cases the computational cost of one iteration of this method remains on the level typical for the second-order methods.

Keywords: High-order methods; Tensor methods; Convex optimization; Worst-case complexity bounds; Lower complexity bounds (search for similar items in EconPapers)
Pages: 27
Date: 2023-01-01
Note: In: Mathematical Programming, 2021, vol. 186, p. 157-183
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:3246

DOI: 10.1007/s10107-019-01449-1

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 ().