Affordable Access

deepdyve-link
Publisher Website

Newton-Type Greedy Selection Methods for $\ell _0$ -Constrained Minimization.

Authors
  • Yuan, Xiao-Tong
  • Liu, Qingshan
Type
Published Article
Journal
IEEE transactions on pattern analysis and machine intelligence
Publication Date
Dec 01, 2017
Volume
39
Issue
12
Pages
2437–2450
Identifiers
DOI: 10.1109/TPAMI.2017.2651813
PMID: 28092519
Source
Medline
License
Unknown

Abstract

We introduce a family of Newton-type greedy selection methods for -constrained minimization problems. The basic idea is to construct a quadratic function to approximate the original objective function around the current iterate and solve the constructed quadratic program over the cardinality constraint. The next iterate is then estimated via a line search operation between the current iterate and the solution of the sparse quadratic program. This iterative procedure can be interpreted as an extension of the constrained Newton methods from convex minimization to non-convex -constrained minimization. We show that the proposed algorithms converge asymptotically and the rate of local convergence is superlinear up to certain estimation error. Our methods compare favorably against several state-of-the-art greedy selection methods when applied to sparse logistic regression and sparse support vector machines.

Report this publication

Statistics

Seen <100 times