A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property

Man Chung Yue, Zirui ZHOU*, Anthony Man Cho So

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)327-358
Number of pages32
JournalMathematical Programming
Volume174
Issue number1-2
DOIs
Publication statusPublished - 1 Mar 2019

Scopus Subject Areas

  • Software
  • Mathematics(all)

User-Defined Keywords

  • Convex composite minimization
  • Error bound
  • Proximal Newton method
  • Sequential quadratic approximation
  • Superlinear convergence

Fingerprint

Dive into the research topics of 'A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property'. Together they form a unique fingerprint.

Cite this