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

By Pinghua Gong, Changshui Zhang, Zhaosong Lu, Jianhua Z. Huang, Jieping Ye. International Conference on Machine Learning, 2013

431 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/3edae395b2a2e8a5a1796367cb7d1b0b206079d0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Numerical Analysis

Citations in the corpus

Convex Discriminative Multitask Clustering (2013, background): “How to find good local minima in the non-convex formulations seems not a well explored field in MTL, but is emerging in the study of the regularization frameworks, such as [52] and the references therein.”
What Objective Does Self-paced Learning Indeed Optimize? (2015, background): “, the hard and linear SPL regimes are equivalent to the optimizations on losses with the capped-norm penalty [11, 12, 13] and minimax concave plus penalty (MCP) [14], respectively.”
Neural Granger Causality (2021, background): “The scalar g ð m Þ is the step size, which is either set to a ﬁxed value or determined by line search [51].”
Multi-Task Feature Interaction Learning (2016, methodology): “Note that even when L is non-convex, a local optimal solution can be efficiently obtained using the GIST framework [17].”
Multi-Task Learning for Spatio-Temporal Event Forecasting (2015, methodology): “Motivated by the success of the iterative hard thresholding algo-rithm for solving l 0 -regularized problems [8] and the recent advances on nonconvex iterative shrinkage algorithm [14, 33], we propose to employ the Iterative Group Hard Thresh-olding framework to solve both problems.”
Accelerated Proximal Gradient Methods for Nonconvex Programming (2015, methodology): “(27) We compare monotone APG (mAPG) and nonmonotone APG (nmAPG) with monotone GIST 8 (mGIST), nonmonotone GIST (nmGIST) [19] and IFB [22].”
Ieee Transactions on Pattern Analysis and Machine Intelligence Classification with Noisy Labels by Importance Reweighting (positive): “In addition, our method inherits most batch learning optimization procedures designed for traditional classification problems with different regularizations; see, for examples, [13]–[17].”
Kronecker-Basis-Representation Based Tensor Sparsity and Its Applications to Tensor Recovery (2018, background): “where Q 1⁄4 O 1 U 1 N U N , which has been proved to have closed-form solution [25]”
Global Convergence of Splitting Methods for Nonconvex Composite Optimization (2014, neutral): “In particular, many sparse learning problems are in the form of (1) with h being a loss function, M being the identity map and P being a regularizer; see, for example, [6] for the use of the l0 norm as a regularizer, [14] for the use of the l1 norm, [13] for the use of the nuclear norm, and [21] and”
Feature Constrained Multi-Task Learning Models for Spatiotemporal Event Forecasting (2017, methodology): “Motivated by the success of the iterative hard thresholding algorithm for solving l0-regularized problems [7] and recent advances in nonconvex iterative shrinkage algorithms [15], [30], we propose to employ the Iterative Group Hard Thresholding framework to solve both problems.”
Learning Tree Structure in Multi-Task Learning (2015, methodology): “To solve the resulting objective function, we propose to use the general iterative shrinkage and thresholding (GIST) method [8], which needs to solve a proximal problem.”
MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels (2017, methodology): “Below is its formula presented in (Gong et al., 2013) (with the regularization hyperparameter setting to 1): B. Proof of Theorem 1 Theorem 1 Let the objective F ( w , v ) deﬁned in Eq.”