On Iterative Hard Thresholding Methods for High-dimensional M-Estimation

Abstract

The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard $L_0$ constraints. Of the known methods, the class of projected gradient descent (also known as iterative hard thresholding (IHT)) methods is known to offer the fastest and most scalable solutions. However, the current state-of-the-art is only able to analyze these methods in extremely restrictive settings which do not hold in high dimensional statistical models. In this work we bridge this gap by providing the first analysis for IHT-style methods in the high dimensional statistical setting. Our bounds are tight and match known minimax lower bounds. Our results rely on a general analysis framework that enables us to analyze several popular hard thresholding style algorithms (such as HTP, CoSaMP, SP) in the high dimensional regression setting. We also extend our analysis to a large family of "fully corrective methods" that includes two-stage and partial hard-thresholding algorithms. We show that our results hold for the problem of sparse regression, as well as low-rank matrix recovery.

20 pages, 3 figures, To appear in the proceedings of the 28th Annual Conference on Neural Information Processing Systems, NIPS 2014

References in corpus (6)

• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Estimation of high-dimensional low-rank matrices
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Orthogonal Matching Pursuit with Replacement
• Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint

Cited by in corpus (24)

• Soft Threshold Weight Reparameterization for Learnable Sparsity
• Robust Regression via Hard Thresholding
• A Tight Bound of Hard Thresholding
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks
• Stochastic gradient descent methods for estimation with large data sets
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Alternating minimization and alternating descent over nonconvex sets
• Iterative Hard Thresholding for Model Selection in Genome-Wide Association Studies
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Federated Nonconvex Sparse Learning
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Convergence for nonconvex ADMM, with applications to CT imaging
• 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
• Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Model
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• Stochastic Hard Thresholding Algorithms for AUC Maximization
• Best-first Search Algorithm for Non-convex Sparse Minimization
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
• Depth Descent Synchronization in $\mathrm{SO}(D)$