English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We establish or refute the optimality of inexact second-order methods forunconstrained nonconvex optimization from the point of view of worst-caseevaluation complexity, improving and generalizing the results of Cartis, Gouldand Toint (2010,2011). To this aim, we consider a new general class of inexactsecond-order algorithms for unconstrained optimization that includesregularization and trust-region variations of Newton's method as well as oftheir linesearch variants. For each method in this class and arbitrary accuracythreshold $\epsilon \in (0,1)$, we exhibit a smooth objective function withbounded range, whose gradient is globally Lipschitz continuous and whoseHessian is $\alpha-$H\"older continuous (for given $\alpha\in [0,1]$), forwhich the method in question takes at least$\lfloor\epsilon^{-(2+\alpha)/(1+\alpha)}\rfloor$ function evaluations togenerate 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 Lipschitzcontinuous on the path of iterates. These examples provide lower bounds on theworst-case evaluation complexity of methods in our class when applied to smoothproblems satisfying the relevant assumptions. Furthermore, for $\alpha=1$, thislower bound is of the same order in $\epsilon$ as the upper bound on theworst-case evaluation complexity of the cubic and other methods in a class ofmethods proposed in Curtis, Robinson and samadi (2017) or in Royer and Wright(2017), thus implying that these methods have optimal worst-case evaluationcomplexity within a wider class of second-order methods, and that Newton'smethod is suboptimal.

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