A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems.

Area of Science:

• Machine Learning
• Optimization
• Sparse Learning

Background:

• Non-convex sparsity-inducing penalties offer advantages over convex ones in sparse learning.
• Solving associated non-convex optimization problems is computationally challenging.
• Existing methods like Multi-Stage (MS) convex relaxation are often impractical for large-scale problems due to high computational cost.

Purpose of the Study:

• To propose an efficient algorithm for solving non-convex optimization problems in sparse learning.
• To address the computational challenges posed by non-convex penalties.
• To provide a practical solution for large-scale sparse learning applications.

Main Methods:

• Development of the General Iterative Shrinkage and Thresholding (GIST) algorithm.
• Iterative solving of proximal operator problems with closed-form solutions for common penalties.
• Incorporation of a line search with Barzilai-Borwein (BB) rule for rapid step size determination.
• Detailed convergence analysis of the GIST algorithm.

Main Results:

• The GIST algorithm effectively solves non-convex optimization problems for a wide range of penalties.
• The algorithm demonstrates efficiency and practicality on large-scale datasets through extensive experiments.
• The use of BB rule-initialized line search accelerates convergence.
• Closed-form solutions for proximal operators simplify computations for many penalties.

Conclusions:

• The proposed GIST algorithm offers an efficient and practical approach to non-convex sparse learning.
• GIST overcomes the computational limitations of previous methods for large-scale problems.
• The algorithm's convergence is theoretically analyzed and empirically validated.