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

Coralia Cartis, Nicholas I.M. Gould, Philippe Toint

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférenceArticle dans les actes d'une conférence/un colloque

Résumé

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 our previous results. 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 ∊ 2 (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 α 2 [0; 1]), for which the method in question takes at least b∊-(2+α)/(1+α)c 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 b∊-2c 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 regularization method and other algorithms in a class of methods recently proposed by Curtis, Robinson and Samadi or by Royer and Wright, 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.

langue originaleAnglais
titreInvited Lectures
rédacteurs en chefBoyan Sirakov, Paulo Ney de Souza, Marcelo Viana
EditeurWorld Scientific Publishing Co Pte Ltd
Pages3729-3768
Nombre de pages40
ISBN (Electronique)9789813272934
Etat de la publicationPublié - 1 janv. 2018
Evénement2018 International Congress of Mathematicians, ICM 2018 - Rio de Janeiro, Brésil
Durée: 1 août 20189 août 2018

Série de publications

NomProceedings of the International Congress of Mathematicians, ICM 2018
Volume4

Une conférence

Une conférence2018 International Congress of Mathematicians, ICM 2018
PaysBrésil
La villeRio de Janeiro
période1/08/189/08/18

Empreinte digitale Examiner les sujets de recherche de « Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization ». Ensemble, ils forment une empreinte digitale unique.

  • Projets

    Complexity in nonlinear optimization

    TOINT, P., Gould, N. I. M. & Cartis, C.

    1/11/08 → …

    Projet: Recherche

    Contient cette citation

    Cartis, C., Gould, N. I. M., & Toint, P. (2018). Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization. Dans B. Sirakov, P. N. de Souza, & M. Viana (eds.), Invited Lectures (p. 3729-3768). (Proceedings of the International Congress of Mathematicians, ICM 2018; Vol 4). World Scientific Publishing Co Pte Ltd.