A NOISE-TOLERANT QUASI-NEWTON ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

Hao Jun M. Shi; Yuchen Xie; Richard Byrd; Jorge Nocedal

doi:10.1137/20M1373190

A NOISE-TOLERANT QUASI-NEWTON ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

Hao Jun M. Shi, Yuchen Xie, Richard Byrd, Jorge Nocedal

Industrial Engineering and Management Sciences

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

10 Scopus citations

Abstract

This paper describes an extension of the BFGS and L-BFGS methods for the minimization of a nonlinear function subject to errors. This work is motivated by applications that contain computational noise, employ low-precision arithmetic, or are subject to statistical noise. The classical BFGS and L-BFGS methods can fail in such circumstances because the updating procedure can be corrupted and the line search can behave erratically. The proposed method addresses these difficulties and ensures that the BFGS update is stable by employing a lengthening procedure that spaces out the points at which gradient differences are collected. A new line search, designed to tolerate errors, guarantees that the Armijo-Wolfe conditions are satisfied under most reasonable conditions, and works in conjunction with the lengthening procedure. The proposed methods are shown to enjoy convergence guarantees for strongly convex functions. Detailed implementations of the methods are presented, together with encouraging numerical results.

Original language	English (US)
Pages (from-to)	29-55
Number of pages	27
Journal	SIAM Journal on Optimization
Volume	32
Issue number	1
DOIs	https://doi.org/10.1137/20M1373190
State	Published - 2022

Funding

\ast Received by the editors October 13, 2020; accepted for publication (in revised form) September 7, 2021; published electronically January 5, 2022. https://doi.org/10.1137/20M1373190 Funding: The first author was supported by a grant from Facebook, and by National Science Foundation grant DMS-1620022. The second author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003. The third author was supported by National Science Foundation grant DMS-1620070. The fourth author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003, and by National Science Foundation grant DMS-1620022. \dagger Industrial Engineering and Management Sciences (IEMS), Northwestern University, Evanston, IL 60201 USA ([email protected], [email protected], [email protected]). \ddagger Department of Computer Science, University of Colorado, Boulder, CO 80309 USA (Richard. [email protected]).

Keywords

derivative-free optimization
noisy optimization
nonlinear optimization
quasi-Newton method
stochastic optimization
unconstrained optimization

ASJC Scopus subject areas

Software
Theoretical Computer Science
Applied Mathematics

Access to Document

10.1137/20M1373190

Cite this

@article{14a916043169477793a5f30690f39708,

title = "A NOISE-TOLERANT QUASI-NEWTON ALGORITHM FOR UNCONSTRAINED OPTIMIZATION",

abstract = "This paper describes an extension of the BFGS and L-BFGS methods for the minimization of a nonlinear function subject to errors. This work is motivated by applications that contain computational noise, employ low-precision arithmetic, or are subject to statistical noise. The classical BFGS and L-BFGS methods can fail in such circumstances because the updating procedure can be corrupted and the line search can behave erratically. The proposed method addresses these difficulties and ensures that the BFGS update is stable by employing a lengthening procedure that spaces out the points at which gradient differences are collected. A new line search, designed to tolerate errors, guarantees that the Armijo-Wolfe conditions are satisfied under most reasonable conditions, and works in conjunction with the lengthening procedure. The proposed methods are shown to enjoy convergence guarantees for strongly convex functions. Detailed implementations of the methods are presented, together with encouraging numerical results.",

keywords = "derivative-free optimization, noisy optimization, nonlinear optimization, quasi-Newton method, stochastic optimization, unconstrained optimization",

author = "Shi, {Hao Jun M.} and Yuchen Xie and Richard Byrd and Jorge Nocedal",

note = "Funding Information: \ast Received by the editors October 13, 2020; accepted for publication (in revised form) September 7, 2021; published electronically January 5, 2022. https://doi.org/10.1137/20M1373190 Funding: The first author was supported by a grant from Facebook, and by National Science Foundation grant DMS-1620022. The second author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003. The third author was supported by National Science Foundation grant DMS-1620070. The fourth author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003, and by National Science Foundation grant DMS-1620022. \dagger Industrial Engineering and Management Sciences (IEMS), Northwestern University, Evanston, IL 60201 USA ([email protected], [email protected], [email protected]). \ddagger Department of Computer Science, University of Colorado, Boulder, CO 80309 USA (Richard. [email protected]). Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics",

year = "2022",

doi = "10.1137/20M1373190",

language = "English (US)",

volume = "32",

pages = "29--55",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - A NOISE-TOLERANT QUASI-NEWTON ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

AU - Shi, Hao Jun M.

AU - Xie, Yuchen

AU - Byrd, Richard

AU - Nocedal, Jorge

N1 - Funding Information: \ast Received by the editors October 13, 2020; accepted for publication (in revised form) September 7, 2021; published electronically January 5, 2022. https://doi.org/10.1137/20M1373190 Funding: The first author was supported by a grant from Facebook, and by National Science Foundation grant DMS-1620022. The second author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003. The third author was supported by National Science Foundation grant DMS-1620070. The fourth author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003, and by National Science Foundation grant DMS-1620022. \dagger Industrial Engineering and Management Sciences (IEMS), Northwestern University, Evanston, IL 60201 USA ([email protected], [email protected], [email protected]). \ddagger Department of Computer Science, University of Colorado, Boulder, CO 80309 USA (Richard. [email protected]). Publisher Copyright: © 2022 Society for Industrial and Applied Mathematics

PY - 2022

Y1 - 2022

N2 - This paper describes an extension of the BFGS and L-BFGS methods for the minimization of a nonlinear function subject to errors. This work is motivated by applications that contain computational noise, employ low-precision arithmetic, or are subject to statistical noise. The classical BFGS and L-BFGS methods can fail in such circumstances because the updating procedure can be corrupted and the line search can behave erratically. The proposed method addresses these difficulties and ensures that the BFGS update is stable by employing a lengthening procedure that spaces out the points at which gradient differences are collected. A new line search, designed to tolerate errors, guarantees that the Armijo-Wolfe conditions are satisfied under most reasonable conditions, and works in conjunction with the lengthening procedure. The proposed methods are shown to enjoy convergence guarantees for strongly convex functions. Detailed implementations of the methods are presented, together with encouraging numerical results.

AB - This paper describes an extension of the BFGS and L-BFGS methods for the minimization of a nonlinear function subject to errors. This work is motivated by applications that contain computational noise, employ low-precision arithmetic, or are subject to statistical noise. The classical BFGS and L-BFGS methods can fail in such circumstances because the updating procedure can be corrupted and the line search can behave erratically. The proposed method addresses these difficulties and ensures that the BFGS update is stable by employing a lengthening procedure that spaces out the points at which gradient differences are collected. A new line search, designed to tolerate errors, guarantees that the Armijo-Wolfe conditions are satisfied under most reasonable conditions, and works in conjunction with the lengthening procedure. The proposed methods are shown to enjoy convergence guarantees for strongly convex functions. Detailed implementations of the methods are presented, together with encouraging numerical results.

KW - derivative-free optimization

KW - noisy optimization

KW - nonlinear optimization

KW - quasi-Newton method

KW - stochastic optimization

KW - unconstrained optimization

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

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

U2 - 10.1137/20M1373190

DO - 10.1137/20M1373190

M3 - Article

AN - SCOPUS:85131252287

SN - 1052-6234

VL - 32

SP - 29

EP - 55

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -

A NOISE-TOLERANT QUASI-NEWTON ALGORITHM FOR UNCONSTRAINED OPTIMIZATION

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this