Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Research output: Working paper

17 Downloads (Pure)

Abstract

We establish or refute the optimality of inexact second-order methods for
unconstrained nonconvex optimization from the point of view of worst-case evaluation complexity, improving and generalizing the results of Cartis, Gould
and Toint (2010,2011). To this aim, we consider a new general class of inexact second-order algorithms for unconstrained optimization that includes regularization and trust-region variations of Newton's method as well as of
their linesearch variants. For each method in this class and arbitrary
accuracy threshold $\epsilon \in (0,1)$, we exhibit a smooth objective
function with bounded range, whose gradient is globally Lipschitz continuous
and whose Hessian is $\alpha-$H\"older continuous (for given $\alpha\in
[0,1]$), for which the method in question takes at least $\lfloor\epsilon^{-(2+\alpha)/(1+\alpha)}\rfloor$ function evaluations to generate a first iterate whose gradient is smaller than $\epsilon$ in norm. Moreover, we also construct another function on which Newton's takes $\lfloor\epsilon^{-2}\rfloor$ evaluations, but whose Hessian is Lipschitz continuous on the path of iterates. These examples provide lower bounds on the worst-case evaluation complexity of methods in our class when applied to smooth problems satisfying the relevant assumptions. Furthermore, for $\alpha=1$, this lower bound is of the same order in $\epsilon$ as the upper bound on the worst-case evaluation complexity of the cubic %(and more generally $(2+\alpha)$) regularization method and other methods in a class of methods proposed in Curtis, Robinson and Samadi (2017) or in Royer and Wright (2017), thus implying that these methods have optimal worst-case evaluation complexity within a wider class of second-order methods, and that Newton's method is suboptimal.
Original languageEnglish
PublisherArxiv
Number of pages35
Volume1709.07180
Publication statusPublished - 22 Sep 2017

Fingerprint

Newton-Raphson method
Optimality
Optimization
Function evaluation
Evaluation
Iterate
Newton Methods
Lipschitz
Lower bound
Gradient
Trust Region
Nonconvex Optimization
Line Search
Unconstrained Optimization
Regularization Method
Evaluation Function
Regularization
Class
Upper bound
Norm

Keywords

  • evaluation complexity
  • nonlinear optimization
  • second-order methods

Cite this

@techreport{335f6ad032d646f88f9b1644f10982c5,
title = "Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization",
abstract = "We establish or refute the optimality of inexact second-order methods forunconstrained nonconvex optimization from the point of view of worst-case evaluation complexity, improving and generalizing the results of Cartis, Gouldand Toint (2010,2011). To this aim, we consider a new general class of inexact second-order algorithms for unconstrained optimization that includes regularization and trust-region variations of Newton's method as well as oftheir linesearch variants. For each method in this class and arbitraryaccuracy threshold $\epsilon \in (0,1)$, we exhibit a smooth objectivefunction with bounded range, whose gradient is globally Lipschitz continuousand whose Hessian is $\alpha-$H\{"}older continuous (for given $\alpha\in[0,1]$), for which the method in question takes at least $\lfloor\epsilon^{-(2+\alpha)/(1+\alpha)}\rfloor$ function evaluations to generate a first iterate whose gradient is smaller than $\epsilon$ in norm. Moreover, we also construct another function on which Newton's takes $\lfloor\epsilon^{-2}\rfloor$ evaluations, but whose Hessian is Lipschitz continuous on the path of iterates. These examples provide lower bounds on the worst-case evaluation complexity of methods in our class when applied to smooth problems satisfying the relevant assumptions. Furthermore, for $\alpha=1$, this lower bound is of the same order in $\epsilon$ as the upper bound on the worst-case evaluation complexity of the cubic {\%}(and more generally $(2+\alpha)$) regularization method and other methods in a class of methods proposed in Curtis, Robinson and Samadi (2017) or in Royer and Wright (2017), thus implying that these methods have optimal worst-case evaluation complexity within a wider class of second-order methods, and that Newton's method is suboptimal.",
keywords = "evaluation complexity, nonlinear optimization, second-order methods",
author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
year = "2017",
month = "9",
day = "22",
language = "English",
volume = "1709.07180",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

Arxiv, 2017.

Research output: Working paper

TY - UNPB

T1 - Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe

PY - 2017/9/22

Y1 - 2017/9/22

N2 - We establish or refute the optimality of inexact second-order methods forunconstrained nonconvex optimization from the point of view of worst-case evaluation complexity, improving and generalizing the results of Cartis, Gouldand Toint (2010,2011). To this aim, we consider a new general class of inexact second-order algorithms for unconstrained optimization that includes regularization and trust-region variations of Newton's method as well as oftheir linesearch variants. For each method in this class and arbitraryaccuracy threshold $\epsilon \in (0,1)$, we exhibit a smooth objectivefunction with bounded range, whose gradient is globally Lipschitz continuousand whose Hessian is $\alpha-$H\"older continuous (for given $\alpha\in[0,1]$), for which the method in question takes at least $\lfloor\epsilon^{-(2+\alpha)/(1+\alpha)}\rfloor$ function evaluations to generate a first iterate whose gradient is smaller than $\epsilon$ in norm. Moreover, we also construct another function on which Newton's takes $\lfloor\epsilon^{-2}\rfloor$ evaluations, but whose Hessian is Lipschitz continuous on the path of iterates. These examples provide lower bounds on the worst-case evaluation complexity of methods in our class when applied to smooth problems satisfying the relevant assumptions. Furthermore, for $\alpha=1$, this lower bound is of the same order in $\epsilon$ as the upper bound on the worst-case evaluation complexity of the cubic %(and more generally $(2+\alpha)$) regularization method and other methods in a class of methods proposed in Curtis, Robinson and Samadi (2017) or in Royer and Wright (2017), thus implying that these methods have optimal worst-case evaluation complexity within a wider class of second-order methods, and that Newton's method is suboptimal.

AB - We establish or refute the optimality of inexact second-order methods forunconstrained nonconvex optimization from the point of view of worst-case evaluation complexity, improving and generalizing the results of Cartis, Gouldand Toint (2010,2011). To this aim, we consider a new general class of inexact second-order algorithms for unconstrained optimization that includes regularization and trust-region variations of Newton's method as well as oftheir linesearch variants. For each method in this class and arbitraryaccuracy threshold $\epsilon \in (0,1)$, we exhibit a smooth objectivefunction with bounded range, whose gradient is globally Lipschitz continuousand whose Hessian is $\alpha-$H\"older continuous (for given $\alpha\in[0,1]$), for which the method in question takes at least $\lfloor\epsilon^{-(2+\alpha)/(1+\alpha)}\rfloor$ function evaluations to generate a first iterate whose gradient is smaller than $\epsilon$ in norm. Moreover, we also construct another function on which Newton's takes $\lfloor\epsilon^{-2}\rfloor$ evaluations, but whose Hessian is Lipschitz continuous on the path of iterates. These examples provide lower bounds on the worst-case evaluation complexity of methods in our class when applied to smooth problems satisfying the relevant assumptions. Furthermore, for $\alpha=1$, this lower bound is of the same order in $\epsilon$ as the upper bound on the worst-case evaluation complexity of the cubic %(and more generally $(2+\alpha)$) regularization method and other methods in a class of methods proposed in Curtis, Robinson and Samadi (2017) or in Royer and Wright (2017), thus implying that these methods have optimal worst-case evaluation complexity within a wider class of second-order methods, and that Newton's method is suboptimal.

KW - evaluation complexity

KW - nonlinear optimization

KW - second-order methods

M3 - Working paper

VL - 1709.07180

BT - Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

PB - Arxiv

ER -