Between hard and soft thresholding: optimal iterative thresholding algorithms
From MaRDI portal
Abstract: Iterative thresholding algorithms seek to optimize a differentiable objective function over a sparsity or rank constraint by alternating between gradient steps that reduce the objective, and thresholding steps that enforce the constraint. This work examines the choice of the thresholding operator, and asks whether it is possible to achieve stronger guarantees than what is possible with hard thresholding. We develop the notion of relative concavity of a thresholding operator, a quantity that characterizes the worst-case convergence performance of any thresholding operator on the target optimization problem. Surprisingly, we find that commonly used thresholding operators, such as hard thresholding and soft thresholding, are suboptimal in terms of worst-case convergence guarantees. Instead, a general class of thresholding operators, lying between hard thresholding and soft thresholding, is shown to be optimal with the strongest possible convergence guarantee among all thresholding operators. Examples of this general class includes thresholding with appropriate choices of , and a newly defined {em reciprocal thresholding} operator. We also investigate the implications of the improved optimization guarantee in the statistical setting of sparse linear regression, and show that this new class of thresholding operators attain the optimal rate for computationally efficient estimators, matching the Lasso.
Recommendations
Cited in
(19)- Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
- The convergence guarantee of the iterative hard thresholding algorithm with suboptimal feedbacks for large systems
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- A convergent iterative hard thresholding for nonnegative sparsity optimization
- A tight bound of hard thresholding
- Dual iterative hard thresholding
- Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
- A tight bound of modified iterative hard thresholding algorithm for compressed sensing.
- Software for limited memory restarted \(\ell^p\)-\(\ell^q\) minimization methods using generalized Krylov subspaces
- Exact recovery in the double sparse model: sufficient and necessary signal conditions
- An _0-constrained and _1-regularized estimator for graphical models
- Robust and computationally efficient gradient-based estimation
- Accelerated stochastic approximation with state-dependent noise
- Understanding best subset selection: a tale of two c(omplex)ities
- High-dimensional variable selection with heterogeneous signals: a precise asymptotic perspective
- Sparse approximation of complex networks
- Mean squared error bounds for the Rangan-Goyal soft thresholding algorithm
- Sparse projection onto semi-symmetric sets with applications to sparse optimization
- Iterative thresholding algorithms
This page was built for publication: Between hard and soft thresholding: optimal iterative thresholding algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5006544)
