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

arXiv: https://arxiv.org/abs/1303.4434 · HTML: https://mlsanity.com/paper/1303.4434/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2013.

## Built on by (most cited first, 25 of 25)

- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [A Unified Framework for Soft Threshold Pruning](https://mlsanity.com/paper/2302.13019/) (2023)
- [Curriculum-based Asymmetric Multi-task Reinforcement Learning](https://mlsanity.com/paper/2211.03352/) (2022)
- [Reinforcement Learning with Heterogeneous Data: Estimation and Inference](https://mlsanity.com/paper/2202.00088/) (2022)
- [Tensor Recovery Based on A Novel Non-convex Function Minimax Logarithmic Concave Penalty Function](https://mlsanity.com/paper/2206.13506/) (2022)
- [Sparse-Input Neural Network using Group Concave Regularization](https://mlsanity.com/paper/2307.00344/) (2023)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [Hyperspectral Anomaly Detection Fused Unified Nonconvex Tensor Ring Factors Regularization](https://mlsanity.com/paper/2505.17881/) (2025)
- [Low-Rank Tensor Learning by Generalized Nonconvex Regularization](https://mlsanity.com/paper/2410.18402/) (2024)
- [Learning Multi-Attribute Differential Graphs with Non-Convex Penalties](https://mlsanity.com/paper/2505.09748/) (2025)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Learning to Accelerate by the Methods of Step-size Planning](https://mlsanity.com/paper/2204.01705/) (2022)
- [An inexact LPA for DC composite optimization and application to matrix completions with outliers](https://mlsanity.com/paper/2303.16822/) (2023)
- [Globally Convergent Accelerated Algorithms for Multilinear Sparse Logistic Regression with ℓ0-constraints](https://mlsanity.com/paper/2309.09239/) (2023)
- [Robust Low-Rank Matrix Completion via a New Sparsity-Inducing Regularizer](https://mlsanity.com/paper/2310.04762/) (2023)
- [Anderson acceleration for iteratively reweighted ℓ1 algorithm](https://mlsanity.com/paper/2403.07271/) (2024)
- [Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification](https://mlsanity.com/paper/2410.09420/) (2024)
- [Playing the Lottery With Concave Regularizers for Sparse Trainable Neural Networks](https://mlsanity.com/paper/2501.11135/) (2025)
- [A novel non-convex minimax p-th order concave penalty function approach to low-rank tensor completion](https://mlsanity.com/paper/2502.19979/) (2025)
- [Accelerating Large-Scale Regularized High-Order Tensor Recovery](https://mlsanity.com/paper/2506.09594/) (2025)
- [Beyond sparse denoising in frames: minimax estimation with a scattering transform](https://mlsanity.com/paper/2510.19612/) (2025)
- [Robust variable selection for spatial point processes observed with noise](https://mlsanity.com/paper/2510.25550/) (2025)
- [Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computation](https://mlsanity.com/paper/2602.12982/) (2026)
- [Fast and Effective Computation of Generalized Symmetric Matrix Factorization](https://mlsanity.com/paper/2603.19147/) (2026)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)

## Abstract (arXiv)

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.