On the quadratic convergence of the cubic regularization method under a local error bound condition

Man Chung Yue, Zirui ZHOU, Anthony Man Cho So

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

In this paper we consider the cubic regularization (CR) method, a regularized version of the classical Newton method, for minimizing a twice continuously differentiable function. While it is well known that the CR method is globally convergent and enjoys a superior global iteration complexity, existing results on its local quadratic convergence require a stringent nondegeneracy condition. We prove that under a local error bound (EB) condition, which is a much weaker requirement than the existing nondegeneracy condition, the sequence of iterates generated by the CR method converges at least Q-quadratically to a second-order critical point. This indicates that adding cubic regularization not only equips Newton's method with remarkable global convergence properties but also enables it to converge quadratically even in the presence of degenerate solutions. As a by-product, we show that without assuming convexity the proposed EB condition is equivalent to a quadratic growth condition, which could be of independent interest. To demonstrate the usefulness and relevance of our convergence analysis, we focus on two concrete nonconvex optimization problems that arise in phase retrieval and low-rank matrix recovery and prove that with overwhelming probability the sequence of iterates generated by the CR method for solving these two problems converges at least Q-quadratically to a global minimizer. To support and complement our theoretical development, we also present numerical results of the CR method when applied to solve these two problems.

Original languageEnglish
Pages (from-to)904-932
Number of pages29
JournalSIAM Journal on Optimization
Volume29
Issue number1
DOIs
Publication statusPublished - 2019

Scopus Subject Areas

  • Software
  • Theoretical Computer Science

User-Defined Keywords

  • Cubic regularization
  • Error bound
  • Local quadratic convergence
  • Low-rank matrix recovery
  • Nonisolated solutions
  • Phase retrieval
  • Second-order critical points

Fingerprint

Dive into the research topics of 'On the quadratic convergence of the cubic regularization method under a local error bound condition'. Together they form a unique fingerprint.

Cite this