  Non-convex sparsity-inducing penalties have recently received considerable
attentions in sparse learning. Recent theoretical investigations have
demonstrated their superiority over the convex counterparts in several sparse
learning settings. However, solving the non-convex optimization problems
associated with non-convex penalties remains a big challenge. A commonly used
approach is the Multi-Stage (MS) convex relaxation (or DC programming), which
relaxes the original non-convex problem to a sequence of convex problems. This
approach is usually not very practical for large-scale problems because its
computational cost is a multiple of solving a single convex problem. In this
paper, we propose a General Iterative Shrinkage and Thresholding (GIST)
algorithm to solve the nonconvex optimization problem for a large class of
non-convex penalties. The GIST algorithm iteratively solves a proximal operator
problem, which in turn has a closed-form solution for many commonly used
penalties. At each outer iteration of the algorithm, we use a line search
initialized by the Barzilai-Borwein (BB) rule that allows finding an
appropriate step size quickly. The paper also presents a detailed convergence
analysis of the GIST algorithm. The efficiency of the proposed algorithm is
demonstrated by extensive experiments on large-scale data sets.
