A Tight Bound of Hard Thresholding

Abstract

This paper is concerned with the hard thresholding operator which sets all but the $k$ largest absolute elements of a vector to zero. We establish a {\em tight} bound to quantitatively characterize the deviation of the thresholded solution from a given signal. Our theoretical result is universal in the sense that it holds for all choices of parameters, and the underlying analysis depends only on fundamental arguments in mathematical optimization. We discuss the implications for two domains: Compressed Sensing. On account of the crucial estimate, we bridge the connection between the restricted isometry property (RIP) and the sparsity parameter for a vast volume of hard thresholding based algorithms, which renders an improvement on the RIP condition especially when the true sparsity is unknown. This suggests that in essence, many more kinds of sensing matrices or fewer measurements are admissible for the data acquisition procedure. Machine Learning. In terms of large-scale machine learning, a significant yet challenging problem is learning accurate sparse models in an efficient manner. In stark contrast to prior work that attempted the ${\ell }_1$-relaxation for promoting sparsity, we present a novel stochastic algorithm which performs hard thresholding in each iteration, hence ensuring such parsimonious solutions. Equipped with the developed bound, we prove the {\em global linear convergence} for a number of prevalent statistical models under mild assumptions, even though the problem turns out to be non-convex.

V1 was submitted to COLT 2016. V2 fixes minor flaws, adds extra experiments and discusses time complexity, V3 has been accepted to JMLR

References in corpus (5)

• Nearly unbiased variable selection under minimax concave penalty
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Orthogonal Matching Pursuit with Replacement
• A Sharp Restricted Isometry Constant Bound of Orthogonal Matching Pursuit

Cited by in corpus (10)

• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• High Dimensional Robust Sparse Regression
• Finite Sample Prediction and Recovery Bounds for Ordinal Embedding
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Fast Low-Rank Matrix Estimation without the Condition Number
• Analysis of Optimal Thresholding Algorithms for Compressed Sensing
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• An equivalence between critical points for rank constraints versus low-rank factorizations
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise