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.

References in corpus (5)

• Nearly unbiased variable selection under minimax concave penalty
• A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
• Multi-Stage Multi-Task Feature Learning
• Sequential Convex Programming Methods for A Class of Structured Nonlinear Programming
• Iterative Reweighted Minimization Methods for $l_p$ Regularized Unconstrained Nonlinear Programming

Cited by in corpus (51)

• Classification with Noisy Labels by Importance Reweighting
• MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels
• A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
• Neural Granger Causality
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Multi-Stage Multi-Task Feature Learning
• Non-local Low-rank Cube-based Tensor Factorization for Spectral CT Reconstruction
• What Objective Does Self-paced Learning Indeed Optimize?
• Sparse-Input Neural Networks for High-dimensional Nonparametric Regression and Classification
• Generalized Singular Value Thresholding
• Successive Convex Approximation Algorithms for Sparse Signal Estimation with Nonconvex Regularizations
• Where did the tumor start? An inverse solver with sparse localization for tumor growth models
• Sparse and Functional Principal Components Analysis
• Efficient DC Algorithm for Constrained Sparse Optimization
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• Image-Driven Biophysical Tumor Growth Model Calibration
• Fast Low-Rank Matrix Learning with Nonconvex Regularization
• An Extended Newton-type Algorithm for ${\ell }_2$-Regularized Sparse Logistic Regression and Its Efficiency for Classifying Large-scale Datasets
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Schatten-$p$ Quasi-Norm Regularized Matrix Optimization via Iterative Reweighted Singular Value Minimization
• Proximal Iteratively Reweighted Algorithm with Multiple Splitting for Nonconvex Sparsity Optimization
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• Large-Scale Low-Rank Matrix Learning with Nonconvex Regularizers
• Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction
• A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
• Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• Convergence rate analysis of a sequential convex programming method with line search for a class of constrained difference-of-convex optimization problems
• On ${\ell }_p$-hyperparameter Learning via Bilevel Nonsmooth Optimization
• Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
• Fast Learning with Nonconvex L1-2 Regularization
• Efficient Inexact Proximal Gradient Algorithm for Nonconvex Problems
• Nonconvex Approach for Sparse and Low-Rank Constrained Models with Dual Momentum
• A refined convergence analysis of pDCA${}_e$ with applications to simultaneous sparse recovery and outlier detection
• Importance sampling strategy for non-convex randomized block-coordinate descent
• Penalty methods for a class of non-Lipschitz optimization problems
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
• Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statistics
• Relaxed Sparse Eigenvalue Conditions for Sparse Estimation via Non-convex Regularized Regression
• On the superiority of PGMs to PDCAs in nonsmooth nonconvex sparse regression
• Inexact proximal DC Newton-type method for nonconvex composite functions
• An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs
• Asynchronous Delay-Aware Accelerated Proximal Coordinate Descent for Nonconvex Nonsmooth Problems
• Binary matrix completion with nonconvex regularizers
• A Non-Convex Relaxation for Fixed-Rank Approximation
• On the Conditions of Sparse Parameter Estimation via Log-Sum Penalty Regularization
• Nonconvex Penalization in Sparse Estimation: An Approach Based on the Bernstein Function
• Greedy methods, randomization approaches and multi-arm bandit algorithms for efficient sparsity-constrained optimization
• Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence