Examples of slow convergence for adaptive regularization optimization methods are not isolated

Philippe Toint

Examples of slow convergence for adaptive regularization optimization methods are not isolated

Philippe Toint

Namur Institute for Complex Systems

Résultats de recherche: Papier de travail

26 Téléchargements (Pure)

Résumé

The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most O(epsilon^{3/(3-q)}) evaluations of the objective function and its derivatives of degrees one and two to produce an epsilon-approximate critical point of order q in {1,2}. This bound was shown to be sharp by various authors. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure.

langue originale	Anglais
Éditeur	Arxiv
Volume	2409.16047
Etat de la publication	Publié - 25 sept. 2024

Accès au document

arXiv-2409.16047manuscrit soumis, 341 KB

4 Article
2 Papier de travail
1 Article dans les actes d'une conférence/un colloque

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is o(eps^{-2}) rather than O(eps^{-2})
Gratton, S., Sim, C. & Toint, P., 20 août 2024, Arxiv.
Résultats de recherche: Papier de travail

File
An adaptive regularization method in Banach spaces
Gratton, S., Jerad, S. & Toint, P. L., 24 nov. 2023, Dans: Optimization Methods and Software. 38, 6, p. 1163-1179 17 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

File
32 Téléchargements (Pure)
Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an 0(epsilon^{-3/2}) complexity bound
Gratton, S., Jerad, S. & TOINT, P., févr. 2023, Dans: SIAM Journal on Optimization. 33, 3, p. 1621-1646
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

File

1 Actif

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. (Co-investigateur) & Toint, P. (Co-investigateur)
1/01/87 → …
Projet: Axe de recherche

Contient cette citation

@techreport{abbf8fda551640c1a61e52e5be62b330,

title = "Examples of slow convergence for adaptive regularization optimization methods are not isolated",

abstract = "The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most O(epsilon^{3/(3-q)}) evaluations of the objective function and its derivatives of degrees one and two to produce an epsilon-approximate critical point of order q in {1,2}. This bound was shown to be sharp by various authors. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure.",

author = "Philippe Toint",

year = "2024",

month = sep,

day = "25",

language = "English",

volume = "2409.16047",

publisher = "Arxiv",

type = "WorkingPaper",

institution = "Arxiv",

}

TY - UNPB

T1 - Examples of slow convergence for adaptive regularization optimization methods are not isolated

AU - Toint, Philippe

PY - 2024/9/25

Y1 - 2024/9/25

N2 - The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most O(epsilon^{3/(3-q)}) evaluations of the objective function and its derivatives of degrees one and two to produce an epsilon-approximate critical point of order q in {1,2}. This bound was shown to be sharp by various authors. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure.

AB - The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most O(epsilon^{3/(3-q)}) evaluations of the objective function and its derivatives of degrees one and two to produce an epsilon-approximate critical point of order q in {1,2}. This bound was shown to be sharp by various authors. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure.

M3 - Working paper

VL - 2409.16047

BT - Examples of slow convergence for adaptive regularization optimization methods are not isolated

PB - Arxiv

ER -

Examples of slow convergence for adaptive regularization optimization methods are not isolated

Résumé

Accès au document

Empreinte digitale

Résultat de recherche

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is o(eps^{-2}) rather than O(eps^{-2})

An adaptive regularization method in Banach spaces

Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an 0(epsilon^{-3/2}) complexity bound

Projets

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Contient cette citation