Superfast Second-Order Methods for Unconstrained Convex Optimization

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

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

Abstract: In this paper, we present new second-order methods with convergence rate O(k−4) , where k is the iteration counter. This is faster than the existing lower bound for this type of schemes (Agarwal and Hazan in Proceedings of the 31st conference on learning theory, PMLR, pp. 774–792, 2018; Arjevani and Shiff in Math Program 178(1–2):327–360, 2019), which is O(k−7/2). Our progress can be explained by a finer specification of the problem class. The main idea of this approach consists in implementation of the third-order scheme from Nesterov (Math Program 186:157–183, 2021) using the second-order oracle. At each iteration of our method, we solve a nontrivial auxiliary problem by a linearly convergent scheme based on the relative non-degeneracy condition (Bauschke et al. in Math Oper Res 42:330–348, 2016; Lu et al. in SIOPT 28(1):333–354, 2018). During this process, the Hessian of the objective function is computed once, and the gradient is computed O(ln1ϵ) times, where ϵ is the desired accuracy of the solution for our problem.

Keywords: Convex optimization; Tensor methods; Lower complexity bounds; Second-order methods (search for similar items in EconPapers)
Pages: 30
Date: 2023-01-01
Note: In: Journal of Optimization Theory and Applications, 2021, vol. 191(1), p. 1-30
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:3248

DOI: 10.1007/s10957-021-01930-y

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