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

4 Papier de travail
2 Article
1 Livre
1 Préprint

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
Gratton, S., Jerad, S. & Toint, P., 10 juil. 2024, (Soumis) Arxiv, 32 p.
Résultats de recherche: Papier de travail

File
Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds constraints
Toint, P., 10 juil. 2024, Arxiv.
Résultats de recherche: Papier de travail

File
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

2 Actif

Complexity in nonlinear optimization
Toint, P. (Co-investigateur), Gould, N. I. M. (Co-investigateur) & Cartis, C. (Co-investigateur)
1/11/08 → …
Projet: Recherche
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

5 Recherche/Enseignement dans une institution externe
4 Discours invité
1 Participation à un atelier/workshop, un séminaire, un cours

ALGOPT2024 workshop on Algorithmic Optimization
Toint, P. (Orateur)
27 août 2024 → 30 août 2024
Activité: Participation ou organisation d'un événement › Participation à un atelier/workshop, un séminaire, un cours
Objective-function-free optimization
Toint, P. (Orateur)
18 juin 2024
Activité: Discours ou présentation › Discours invité
Institut National Polytechnique de Toulouse
Toint, P. (Chercheur visiteur)
24 juin 2024 → 29 juin 2024
Activité: Visite d'une organisation externe › Recherche/Enseignement dans une institution externe

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

Projets

Activités

Contient cette citation