File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10107-018-1280-6
- Scopus: eid_2-s2.0-85063953410
- WOS: WOS:000463715600014
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property
Title | A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property |
---|---|
Authors | |
Keywords | Convex composite minimization Error bound Proximal Newton method Sequential quadratic approximation Superlinear convergence |
Issue Date | 2019 |
Citation | Mathematical Programming, 2019, v. 174, n. 1-2, p. 327-358 How to Cite? |
Abstract | We propose a new family of inexact sequential quadratic approximation (SQA) methods, which we call the inexact regularized proximal Newton (IRPN) method, for minimizing the sum of two closed proper convex functions, one of which is smooth and the other is possibly non-smooth. Our proposed method features strong convergence guarantees even when applied to problems with degenerate solutions while allowing the inner minimization to be solved inexactly. Specifically, we prove that when the problem possesses the so-called Luo–Tseng error bound (EB) property, IRPN converges globally to an optimal solution, and the local convergence rate of the sequence of iterates generated by IRPN is linear, superlinear, or even quadratic, depending on the choice of parameters of the algorithm. Prior to this work, such EB property has been extensively used to establish the linear convergence of various first-order methods. However, to the best of our knowledge, this work is the first to use the Luo–Tseng EB property to establish the superlinear convergence of SQA-type methods for non-smooth convex minimization. As a consequence of our result, IRPN is capable of solving regularized regression or classification problems under the high-dimensional setting with provable convergence guarantees. We compare our proposed IRPN with several empirically efficient algorithms by applying them to the ℓ1-regularized logistic regression problem. Experiment results show the competitiveness of our proposed method. |
Persistent Identifier | http://hdl.handle.net/10722/313623 |
ISSN | 2023 Impact Factor: 2.2 2023 SCImago Journal Rankings: 1.982 |
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 | Mathematical Programming, 2019, v. 174, n. 1-2, p. 327-358 | - |
dc.identifier.issn | 0025-5610 | - |
dc.identifier.uri | http://hdl.handle.net/10722/313623 | - |
dc.description.abstract | We propose a new family of inexact sequential quadratic approximation (SQA) methods, which we call the inexact regularized proximal Newton (IRPN) method, for minimizing the sum of two closed proper convex functions, one of which is smooth and the other is possibly non-smooth. Our proposed method features strong convergence guarantees even when applied to problems with degenerate solutions while allowing the inner minimization to be solved inexactly. Specifically, we prove that when the problem possesses the so-called Luo–Tseng error bound (EB) property, IRPN converges globally to an optimal solution, and the local convergence rate of the sequence of iterates generated by IRPN is linear, superlinear, or even quadratic, depending on the choice of parameters of the algorithm. Prior to this work, such EB property has been extensively used to establish the linear convergence of various first-order methods. However, to the best of our knowledge, this work is the first to use the Luo–Tseng EB property to establish the superlinear convergence of SQA-type methods for non-smooth convex minimization. As a consequence of our result, IRPN is capable of solving regularized regression or classification problems under the high-dimensional setting with provable convergence guarantees. We compare our proposed IRPN with several empirically efficient algorithms by applying them to the ℓ1-regularized logistic regression problem. Experiment results show the competitiveness of our proposed method. | - |
dc.language | eng | - |
dc.relation.ispartof | Mathematical Programming | - |
dc.subject | Convex composite minimization | - |
dc.subject | Error bound | - |
dc.subject | Proximal Newton method | - |
dc.subject | Sequential quadratic approximation | - |
dc.subject | Superlinear convergence | - |
dc.title | A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s10107-018-1280-6 | - |
dc.identifier.scopus | eid_2-s2.0-85063953410 | - |
dc.identifier.volume | 174 | - |
dc.identifier.issue | 1-2 | - |
dc.identifier.spage | 327 | - |
dc.identifier.epage | 358 | - |
dc.identifier.eissn | 1436-4646 | - |
dc.identifier.isi | WOS:000463715600014 | - |