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

Research output: Contribution to journal › Article › peer-review

23 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	573-607
Number of pages	35
Journal	Computational Optimization and Applications
Volume	84
Issue number	2
DOIs	https://doi.org/10.1007/s10589-022-00435-2
Publication status	Published - 15 Feb 2023

Keywords

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

Access to Document

10.1007/s10589-022-00435-2

gt25Submitted manuscript, 445 KBLicence: Unspecified

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds and convex constraints

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

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

ALGOPT2024 workshop on Algorithmic Optimization

Objective-function-free optimization

Institut National Polytechnique de Toulouse

Cite this

OFFO minimization algorithms for second-order optimality and their complexity

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Research output

Projects

Activities

Cite this