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

Area of Science:

• Optimization Theory
• Machine Learning
• Numerical Analysis

Background:

• Constrained minimization problems are central to many scientific and engineering disciplines.
• Sparse solutions are highly desirable in high-dimensional data analysis for interpretability and efficiency.
• Existing methods for -constrained minimization may lack efficiency or scalability.

Purpose of the Study:

• To introduce a novel family of Newton-type greedy selection algorithms for -constrained minimization.
• To extend constrained Newton methods to non-convex settings with cardinality constraints.
• To analyze the convergence properties and practical performance of the proposed methods.

Main Methods:

• Approximating the objective function with a quadratic model around the current iterate.
• Solving a quadratic program subject to a cardinality constraint.
• Employing a line search to determine the next iterate.
• Extending constrained Newton methods for non-convex sparse optimization.

Main Results:

• The proposed algorithms exhibit asymptotic convergence.
• Superlinear local convergence rates are achieved, contingent on estimation error.
• The methods demonstrate superior performance compared to state-of-the-art techniques.
• Effective application demonstrated on sparse logistic regression and support vector machines.

Conclusions:

• The developed Newton-type greedy selection methods offer an effective approach for -constrained minimization.
• These algorithms provide a robust extension of constrained Newton methods to non-convex sparse problems.
• The favorable comparison with existing methods highlights their practical utility in machine learning.