Inexact accelerated high-order proximal-point methods with auxiliary search procedure

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

No 2020010, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this paper, we complement the framework of Bi-Level Unconstrained Minimization (BLUM)[21] by a new pth-order proximal-point method convergent as O(k^{−(3p+1)/2}), where k is the iteration counter. As compared with [21], we replace the auxiliary line search by a convex segment search. This allows us to bound its complexity of by a logarithm of the desired accuracy. Each step in this search needs an approximate computation of the proximal-point operator. Under assumption on boundedness of (p+1)st derivative of the objective function, this can be done by one step of the pth-order augmented tensor method. In this way, for p = 2, we get a new second-order method with the rate of convergence O(^{k−7/2}) and logarithmic complexity of the auxiliary search at each iteration. Another possibility is to compute the proximal-point operator by lower-order minimization methods. As an example, for p = 3, we consider the upper-level process convergent as O^{(k−5)}. Assuming the boundedness of fourth derivative, an appropriate approximation of the proximal-point operator can be computed by a second-order method in logarithmic number of iterations. This combination gives a second-order scheme with much better complexity than the existing theoretical limits.

Keywords: convex optimization; tensor methods; proximal-point operator; lower complexity bounds; optimal methods (search for similar items in EconPapers)
Date: 2020-02-11
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2020.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:2020010

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