Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Fast convergence to non-isolated minima: four equivalent conditions for C2 functions
 
research article

Fast convergence to non-isolated minima: four equivalent conditions for C2 functions

Rebjock, Quentin  
•
Boumal, Nicolas  
2024
Mathematical Programming

Optimization algorithms can see their local convergence rates deteriorate when the Hessian at the optimum is singular. These singularities are inescapable when the optima are non-isolated. Yet, under the right circumstances, several algorithms preserve their favorable rates even when optima form a continuum (e.g., due to over-parameterization). This has been explained under various structural assumptions, including the Polyak–Łojasiewicz condition, Quadratic Growth and the Error Bound. We show that, for cost functions which are twice continuously differentiable (C2), those three (local) properties are equivalent. Moreover, we show they are equivalent to the Morse–Bott property, that is, local minima form differentiable submanifolds, and the Hessian of the cost function is positive definite along its normal directions. We leverage this insight to improve local convergence guarantees for safe-guarded Newton-type methods under any (hence all) of the above assumptions. First, for adaptive cubic regularization, we secure quadratic convergence even with inexact subproblem solvers. Second, for trust-region methods, we argue capture can fail with an exact subproblem solver, then proceed to show linear convergence with an inexact one (Cauchy steps).

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s10107-024-02136-6
Scopus ID

2-s2.0-85204445671

Author(s)
Rebjock, Quentin  

École Polytechnique Fédérale de Lausanne

Boumal, Nicolas  

École Polytechnique Fédérale de Lausanne

Date Issued

2024

Published in
Mathematical Programming
Subjects

90C26

•

90C30

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
OPTIM  
FunderFunding(s)Grant NumberGrant URL

SERI

MB22.00027

Available on Infoscience
January 24, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/243760
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés