title: A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems.
abstract: 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.
authors.affiliation: State Key Laboratory on Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology (TNList), Department of Automation, Tsinghua University, Beijing 100084, China.
authors.forename: Pinghua
authors.initials: P
authors.lastname: Gong
authors.affiliation: State Key Laboratory on Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology (TNList), Department of Automation, Tsinghua University, Beijing 100084, China.
authors.forename: Changshui
authors.initials: C
authors.lastname: Zhang
authors.affiliation: Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada.
authors.forename: Zhaosong
authors.initials: Z
authors.lastname: Lu
authors.affiliation: Department of Statistics, Texas A&M University, TX 77843, USA.
authors.forename: Jianhua Z
authors.initials: JZ
authors.lastname: Huang
authors.affiliation: Computer Science and Engineering, Arizona State University, Tempe, AZ 85287, USA.
authors.forename: Jieping
authors.initials: J
authors.lastname: Ye