IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2018032.html
   My bibliography  Save this paper

Global performance guarantees of second-order methods for unconstrained convex minimization

Author

Listed:
  • DVURECHENSKY Pavel,

    (Weierstrass Institute for Applied Analysis and Stochastics)

  • NESTEROV Yurii,

    (CORE, UCLouvain)

Abstract

In this paper we make an attempt to compare two distinct branches of research on second-order optimization methods. The first one studies self-concordant functions and barriers, the main assumption being that the third derivative of the objective is bounded by the second derivative. The second branch studies cubic regularized Newton methods with main assumption that the second derivative is Lipschitz continuous. We develop new theoretical analysis for a path-following scheme for general self-concordant function, as opposed to classical path-following scheme developed for self-concordant barriers. We show that the complexity bound for this scheme is better than for Damped Newton Method. Next, we analyze an important subclass of general self-concordant function, namely a class of strongly convex functions with Lipschitz continuous second derivative and show that for this subclass cubic regularized New Methods give even better complexity bound.

Suggested Citation

  • DVURECHENSKY Pavel, & NESTEROV Yurii,, 2018. "Global performance guarantees of second-order methods for unconstrained convex minimization," LIDAM Discussion Papers CORE 2018032, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2018032
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2018.html
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2018032. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.