OFFO minimization algorithms for second-order optimality and their complexity

Serge Gratton; Philippe TOINT

doi:10.1007/s10589-022-00435-2

OFFO minimization algorithms for second-order optimality and their complexity

Serge Gratton, Philippe TOINT

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

19 Téléchargements (Pure)

Résumé

An Adagrad-inspired class of algorithms for smooth unconstrained optimization
is presented in which the objective function is never evaluated and yet the
gradient norms decrease at least as fast as lO(1/\sqrt{k+1}) while
second-order optimality measures converge to zero at least as fast as
O(1/(k+1)^{1/3}). This latter rate of convergence is shown to be
essentially sharp and is identical to that known for more standard algorithms
(like trust-region or adaptive-regularization methods) using both function and
derivatives' evaluations. A related ``divergent stepsize'' method is also
described, whose essentially sharp rate of convergence is slighly inferior. It
is finally discussed how to obtain weaker second-order optimality guarantees
at a (much) reduced computional cost.

langue originale	Anglais
Pages (de - à)	573-607
Nombre de pages	35
journal	Computational Optimization and Applications
Volume	84
Numéro de publication	2
Les DOIs	https://doi.org/10.1007/s10589-022-00435-2
Etat de la publication	Publié - 15 févr. 2023

Accès au document

10.1007/s10589-022-00435-2

gt25manuscrit soumis, 445 KBLicense: Non spécifié

Autres fichiers et liens

Lien vers la publication sur Scopus

3 Article de travail
2 Article
1 Livre
1 Préprint

An optimally fast objective-function-free minimization algorithm using random subspaces
Bellavia, S., Gratton, S., Morini, B. & TOINT, P., 25 oct. 2023, Arxiv, 23 p.
Résultats de recherche: Papier de travail › Préprint

File
Complexity of a Class of First-Order Objective-Function-Free Optimization Algorithms
Gratton, S., Jerad, S. & TOINT, P., 6 juin 2023, Arxiv, 30 p.
Résultats de recherche: Papier de travail › Article de travail

File
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

2 Actif

Complexity in nonlinear optimization
Toint, P., Gould, N. I. M. & Cartis, C.
1/11/08 → …
Projet: Recherche
ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. & Toint, P.
1/01/87 → …
Projet: Axe de recherche

1 Discours invité

Some recent Proposals for nonconvex optimization
Philippe TOINT (Orateur)
4 mars 2024
Activité: Discours ou présentation › Discours invité

Contient cette citation

@article{f91ee175ca174f75a90fd9ab0bbb1d1e,

title = "OFFO minimization algorithms for second-order optimality and their complexity",

abstract = "An Adagrad-inspired class of algorithms for smooth unconstrained optimizationis presented in which the objective function is never evaluated and yet thegradient norms decrease at least as fast as lO(1/\sqrt{k+1}) whilesecond-order optimality measures converge to zero at least as fast asO(1/(k+1)^{1/3}). This latter rate of convergence is shown to beessentially sharp and is identical to that known for more standard algorithms(like trust-region or adaptive-regularization methods) using both function andderivatives' evaluations. A related ``divergent stepsize'' method is alsodescribed, whose essentially sharp rate of convergence is slighly inferior. Itis finally discussed how to obtain weaker second-order optimality guaranteesat a (much) reduced computional cost.",

keywords = "Adagrad, Evaluation complexity, Global rate of convergence, Objective-function-free optimization (OFFO), Second-order optimality",

author = "Serge Gratton and Philippe TOINT",

note = "Funding Information: S. Gratton.: Work partially supported by 3IA Artificial and Natural Intelligence Toulouse Institute (ANITI), French {"}Investing for the Future - PIA3{"} program under the Grant agreement ANR-19-PI3A-0004{"}. Ph. L. Toint.: Work partially supported by ANITI. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = feb,

day = "15",

doi = "10.1007/s10589-022-00435-2",

language = "English",

volume = "84",

pages = "573--607",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - OFFO minimization algorithms for second-order optimality and their complexity

AU - Gratton, Serge

AU - TOINT, Philippe

N1 - Funding Information: S. Gratton.: Work partially supported by 3IA Artificial and Natural Intelligence Toulouse Institute (ANITI), French "Investing for the Future - PIA3" program under the Grant agreement ANR-19-PI3A-0004". Ph. L. Toint.: Work partially supported by ANITI. Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/2/15

Y1 - 2023/2/15

N2 - An Adagrad-inspired class of algorithms for smooth unconstrained optimizationis presented in which the objective function is never evaluated and yet thegradient norms decrease at least as fast as lO(1/\sqrt{k+1}) whilesecond-order optimality measures converge to zero at least as fast asO(1/(k+1)^{1/3}). This latter rate of convergence is shown to beessentially sharp and is identical to that known for more standard algorithms(like trust-region or adaptive-regularization methods) using both function andderivatives' evaluations. A related ``divergent stepsize'' method is alsodescribed, whose essentially sharp rate of convergence is slighly inferior. Itis finally discussed how to obtain weaker second-order optimality guaranteesat a (much) reduced computional cost.

AB - An Adagrad-inspired class of algorithms for smooth unconstrained optimizationis presented in which the objective function is never evaluated and yet thegradient norms decrease at least as fast as lO(1/\sqrt{k+1}) whilesecond-order optimality measures converge to zero at least as fast asO(1/(k+1)^{1/3}). This latter rate of convergence is shown to beessentially sharp and is identical to that known for more standard algorithms(like trust-region or adaptive-regularization methods) using both function andderivatives' evaluations. A related ``divergent stepsize'' method is alsodescribed, whose essentially sharp rate of convergence is slighly inferior. Itis finally discussed how to obtain weaker second-order optimality guaranteesat a (much) reduced computional cost.

KW - Adagrad

KW - Evaluation complexity

KW - Global rate of convergence

KW - Objective-function-free optimization (OFFO)

KW - Second-order optimality

UR - http://www.scopus.com/inward/record.url?scp=85131881846&partnerID=8YFLogxK

U2 - 10.1007/s10589-022-00435-2

DO - 10.1007/s10589-022-00435-2

M3 - Article

AN - SCOPUS:85131881846

SN - 0926-6003

VL - 84

SP - 573

EP - 607

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 2

ER -

OFFO minimization algorithms for second-order optimality and their complexity

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

An optimally fast objective-function-free minimization algorithm using random subspaces

Complexity of a Class of First-Order Objective-Function-Free Optimization Algorithms

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

Projets

Complexity in nonlinear optimization

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

Activités

Some recent Proposals for nonconvex optimization

Contient cette citation