Answers are grounded in this paper and cite their sources.
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 ε∈ (0,1), we exhibit a smooth objective function with bounded range, whose gradient is globally Lipschitz continuous and whose Hessian is $α-$Hölder continuous (for given α∈ [0,1]), for which the method in question takes at least ε-(2+α)/(1+α) function evaluations to generate a first iterate whose gradient is smaller than $ε$ in norm. Moreover, we also construct another function on which Newton's takes ε⁻² 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 $α=1$, this lower bound is of the same order in $ε$ as the upper bound on the worst-case evaluation complexity of the cubic 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.
No takes yet. Share an insight, caveat, or question.
Cartis et al. (2019) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: