View in EDS

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is rather than.

Saved in:
Bibliographic Details
Title: Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is rather than.
Authors: Gratton, S.1 (AUTHOR) serge.gratton@enseeiht.fr, Sim, C.-K.2 (AUTHOR) chee-khian.sim@port.ac.uk, Toint, Ph. L.3 (AUTHOR) philippe.toint@unamur.be
Source: Computational Optimization & Applications. Nov2025, Vol. 92 Issue 2, p515-527. 13p.
Subjects: Asymptotic analysis, Computational complexity, Method of steepest descent (Numerical analysis), Mathematical bounds, Nonsmooth optimization, Algorithms, Nonconvex programming
Abstract: We revisit the standard "telescoping sum" argument ubiquitous in the final steps of analyzing evaluation complexity of algorithms for smooth nonconvex optimization, and obtain a refined formulation of the resulting bound as a function of the requested accuracy . While bounds obtained using the standard argument typically are of the form for some positive , the refined results are of the form . We then explore to which known algorithms our refined bounds are applicable and finally describe an example showing how close the standard and refined bounds can be. [ABSTRACT FROM AUTHOR]
Copyright of Computational Optimization & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 189054724
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is rather than.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Gratton%2C+S%2E%22">Gratton, S.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> serge.gratton@enseeiht.fr</i><br /><searchLink fieldCode="AR" term="%22Sim%2C+C%2E-K%2E%22">Sim, C.-K.</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> chee-khian.sim@port.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Toint%2C+Ph%2E+L%2E%22">Toint, Ph. L.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> philippe.toint@unamur.be</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Computational+Optimization+%26+Applications%22">Computational Optimization & Applications</searchLink>. Nov2025, Vol. 92 Issue 2, p515-527. 13p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Asymptotic+analysis%22">Asymptotic analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Method+of+steepest+descent+%28Numerical+analysis%29%22">Method of steepest descent (Numerical analysis)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+bounds%22">Mathematical bounds</searchLink><br /><searchLink fieldCode="DE" term="%22Nonsmooth+optimization%22">Nonsmooth optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Nonconvex+programming%22">Nonconvex programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We revisit the standard "telescoping sum" argument ubiquitous in the final steps of analyzing evaluation complexity of algorithms for smooth nonconvex optimization, and obtain a refined formulation of the resulting bound as a function of the requested accuracy . While bounds obtained using the standard argument typically are of the form for some positive , the refined results are of the form . We then explore to which known algorithms our refined bounds are applicable and finally describe an example showing how close the standard and refined bounds can be. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Computational Optimization & Applications is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189054724
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10589-025-00709-5
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 13
        StartPage: 515
    Subjects:
      – SubjectFull: Asymptotic analysis
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Method of steepest descent (Numerical analysis)
        Type: general
      – SubjectFull: Mathematical bounds
        Type: general
      – SubjectFull: Nonsmooth optimization
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Nonconvex programming
        Type: general
    Titles:
      – TitleFull: Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is rather than.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Gratton, S.
      – PersonEntity:
          Name:
            NameFull: Sim, C.-K.
      – PersonEntity:
          Name:
            NameFull: Toint, Ph. L.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 09266003
          Numbering:
            – Type: volume
              Value: 92
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Computational Optimization & Applications
              Type: main
ResultId 1