Adaptive Third-Order Methods for Composite Convex Optimization

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

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

Abstract: In this paper we propose third-order methods for composite convex optimization problems in which the smooth part is a three-times continuously differentiable function with Lipschitz continuous third-order derivatives. The methods are adaptive in the sense that they do not require knowledge of the Lipschitz constant. Trial points are computed by the inexact minimization of models that consist in the nonsmooth part of the objective plus a quartic regularization of third-order Taylor polynomial of the smooth part. Specifically, approximate solutions of the auxiliary problems are obtained by using a Bregman gradient method as inner solver. Different from existing adaptive approaches for high-order methods, in our new schemes the regularization parameters are tuned by checking the progress of the inner solver. With this technique, we show that the basic method finds an \(\epsilon\) -approximate minimizer of the objective function performing at most \(\mathcal{O} (|\log (\epsilon )|\epsilon^{-\frac{1}{3}} )\) iterations of the inner solver. An accelerated adaptive third-order method is also presented with total inner iteration complexity of \(\mathcal{O} (|\log (\epsilon )|\epsilon^{-\frac{1}{4}})\).

Keywords: Composite minimization; third-order methods; worst-case complexity bounds (search for similar items in EconPapers)
Pages: 29
Date: 2024-01-01
Note: In: SIAM Journal on Optimization, 2023, vol. 33(3), p. 1855-1883
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:3313

DOI: 10.1137/22M1480872

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