Between hard and soft thresholding: optimal iterative thresholding algorithms

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 ${\ell }_q$ thresholding with appropriate choices of $q$, 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.

References in corpus (10)

• Nearly unbiased variable selection under minimax concave penalty
• Simultaneous analysis of Lasso and Dantzig selector
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Robust Regression via Hard Thresholding
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• IHT dies hard: Provable accelerated Iterative Hard Thresholding
• Gradient descent with nonconvex constraints: local concavity determines convergence

Cited by in corpus (5)

• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery
• High Dimensional Robust Sparse Regression
• Analysis of Optimal Thresholding Algorithms for Compressed Sensing
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle