File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/18M1167498
- Scopus: eid_2-s2.0-85065392218
- WOS: WOS:000462593800035
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On the quadratic convergence of the cubic regularization method under a local error bound condition
Title | On the quadratic convergence of the cubic regularization method under a local error bound condition |
---|---|
Authors | |
Keywords | Cubic regularization Error bound Local quadratic convergence Low-rank matrix recovery Nonisolated solutions Phase retrieval Second-order critical points |
Issue Date | 2019 |
Citation | SIAM Journal on Optimization, 2019, v. 29, n. 1, p. 904-932 How to Cite? |
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. |
Persistent Identifier | http://hdl.handle.net/10722/313624 |
ISSN | 2023 Impact Factor: 2.6 2023 SCImago Journal Rankings: 2.138 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Yue, Man Chung | - |
dc.contributor.author | Zhou, Zirui | - |
dc.contributor.author | So, Anthony Man Cho | - |
dc.date.accessioned | 2022-06-23T01:18:47Z | - |
dc.date.available | 2022-06-23T01:18:47Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | SIAM Journal on Optimization, 2019, v. 29, n. 1, p. 904-932 | - |
dc.identifier.issn | 1052-6234 | - |
dc.identifier.uri | http://hdl.handle.net/10722/313624 | - |
dc.description.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. | - |
dc.language | eng | - |
dc.relation.ispartof | SIAM Journal on Optimization | - |
dc.subject | Cubic regularization | - |
dc.subject | Error bound | - |
dc.subject | Local quadratic convergence | - |
dc.subject | Low-rank matrix recovery | - |
dc.subject | Nonisolated solutions | - |
dc.subject | Phase retrieval | - |
dc.subject | Second-order critical points | - |
dc.title | On the quadratic convergence of the cubic regularization method under a local error bound condition | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1137/18M1167498 | - |
dc.identifier.scopus | eid_2-s2.0-85065392218 | - |
dc.identifier.volume | 29 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 904 | - |
dc.identifier.epage | 932 | - |
dc.identifier.isi | WOS:000462593800035 | - |