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

52 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

Funding

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.

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 optimization is presented in which the objective function is never evaluated and yet the gradient norms decrease at least as fast as lO(1/\textbackslash{}sqrt\{k+1\}) while second-order optimality measures converge to zero at least as fast as O(1/(k+1)\textasciicircum{}\{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.",

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

AB - 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.

KW - Adagrad

KW - Evaluation complexity

KW - Global rate of convergence

KW - Objective-function-free optimization (OFFO)

KW - Second-order optimality

UR - https://www.scopus.com/pages/publications/85131881846

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

Funding

Keywords

Access to Document

Other files and links

Fingerprint

A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muon

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

Complexity and performance for two classes of noise-tolerant first-order algorithms

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

ALGOPT2024 workshop on Algorithmic Optimization

Institut National Polytechnique de Toulouse

Objective-function-free optimization

Cite this

OFFO minimization algorithms for second-order optimality and their complexity

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Research output

Projects

Activities

Cite this