Computer Research and Modeling
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Computer Research and Modeling:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Computer Research and Modeling, 2018, Volume 10, Issue 3, Pages 305–314 (Mi crm253)  

This article is cited in 1 scientific paper (total in 1 paper)

SPECIAL ISSUE

A hypothesis about the rate of global convergence for optimal methods (Newton's type) in smooth convex optimization

A. V. Gasnikova, D. A. Kovalevb

a Moscow Institute of Physics and Technology, 9 Institutskij per., Dolgoprudny, Moscow Region, 141707, Russia
b Institute for Information Transmission Problems of the Russian Academy of Sciences, 19 Bolshoy Karetny per., Moscow, 127051, Russia

Abstract: In this paper we discuss lower bounds for convergence of convex optimization methods of high order and attainability of this bounds. We formulate a hypothesis that covers all the cases. It is noticeable that we provide this statement without a proof. Newton method is the most famous method that uses gradient and Hessianof optimized function. However, it converges locally even for strongly convex functions. Global convergence can be achieved with cubic regularization of Newton method [Nesterov, Polyak, 2006], whose iteration cost is comparable with iteration cost of Newton method and is equivalent to inversion of Hessian of optimized function.Yu. Nesterov proposed accelerated variant of Newton method with cubic regularization in 2008 [Nesterov,2008]. R. Monteiro and B. Svaiter managed to improve global convergence of cubic regularized method in 2013 [Monteiro, Svaiter, 2013]. Y. Arjevani, O. Shamir and R. Shiff showed that convergence bound of Monteiro and Svaiter is optimal (cannot be improved by more than logarithmic factor with any second order method) in 2017 [Arjevani et al., 2017]. They also managed to find bounds for convex optimization methods of p-th order for $p\geq2$. However, they got bounds only for first and second order methods for strongly convex functions. In 2018 Yu. Nesterov proposed third order convex optimization methods with rate of convergence that is close to this lower bounds and with similar to Newton method cost of iteration [Nesterov, 2018]. Consequently, it was showed that high order methods can be practical. In this paper we formulate lower bounds for p-th order methods for $p\geq3$ for strongly convex unconstrained optimization problems. This paper can be viewed as a little survey of state of the art of high order optimization methods.

Keywords: Newton method, Hesse matrix, lower bounds, Chebyshev's type methods, superliner rate of convergence.

Funding Agency Grant Number
Russian Science Foundation 17-11-01027
This work was supported by RSCF grant No. 17-11-01027


DOI: https://doi.org/10.20537/2076-7633-2018-10-3-305-314

Full text: PDF file (135 kB)
Full text: http://crm.ics.org.ru/.../2685
References: PDF file   HTML file

UDC: 519.86
Received: 28.02.2018
Revised: 12.05.2018
Accepted:24.05.2018

Citation: A. V. Gasnikov, D. A. Kovalev, “A hypothesis about the rate of global convergence for optimal methods (Newton's type) in smooth convex optimization”, Computer Research and Modeling, 10:3 (2018), 305–314

Citation in format AMSBIB
\Bibitem{GasKov18}
\by A.~V.~Gasnikov, D.~A.~Kovalev
\paper A hypothesis about the rate of global convergence for optimal methods (Newton's type) in smooth convex optimization
\jour Computer Research and Modeling
\yr 2018
\vol 10
\issue 3
\pages 305--314
\mathnet{http://mi.mathnet.ru/crm253}
\crossref{https://doi.org/10.20537/2076-7633-2018-10-3-305-314}


Linking options:
  • http://mi.mathnet.ru/eng/crm253
  • http://mi.mathnet.ru/eng/crm/v10/i3/p305

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Gasnikov, E. A. Gorbunov, D. A. Kovalev, A. A. M. Mokhammed, E. O. Chernousova, “Obosnovanie gipotezy ob optimalnykh otsenkakh skorosti skhodimosti chislennykh metodov vypukloi optimizatsii vysokikh poryadkov”, Kompyuternye issledovaniya i modelirovanie, 10:6 (2018), 737–753  mathnet  crossref
  • Computer Research and Modeling
    Number of views:
    This page:400
    Full text:152
    References:31

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021