Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization

Abstract

Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this paper, we generalize HTP from compressive sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard thresholding step with or without debiasing. We prove that our method enjoys the strong guarantees analogous to HTP in terms of rate of convergence and parameter estimation accuracy. Numerical evidences show that our method is superior to the state-of-the-art greedy selection methods in sparse logistic regression and sparse precision matrix estimation tasks.

Cited by in corpus (30)

• Infinite Feature Selection: A Graph-based Feature Filtering Approach
• Discrimination-aware Channel Pruning for Deep Neural Networks
• Discrimination-aware Network Pruning for Deep Model Compression
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• A Tight Bound of Hard Thresholding
• High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• Compressive Sensing Using Iterative Hard Thresholding with Low Precision Data Representation: Theory and Applications
• An Extended Newton-type Algorithm for ${\ell }_2$-Regularized Sparse Logistic Regression and Its Efficiency for Classifying Large-scale Datasets
• AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks
• Structured Sparse Regression via Greedy Hard-Thresholding
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• Stochastic Greedy Algorithms For Multiple Measurement Vectors
• A Novel Framework for Online Supervised Learning with Feature Selection
• Iterative Hard Thresholding for Model Selection in Genome-Wide Association Studies
• Technical Report: Graph-Structured Sparse Optimization for Connected Subgraph Detection
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• Technical Report: A Generalized Matching Pursuit Approach for Graph-Structured Sparsity
• On The Projection Operator to A Three-view Cardinality Constrained Set
• Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint
• High Dimensional Multivariate Regression and Precision Matrix Estimation via Nonconvex Optimization
• Best-first Search Algorithm for Non-convex Sparse Minimization
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning
• Error bounds for rank constrained optimization problems and applications
• A Majorization Penalty Method for SVM with Sparse Constraint
• Unified Signal Compression Using a GAN with Iterative Latent Representation Optimization
• A Knowledge Transfer Framework for Differentially Private Sparse Learning