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

arXiv: https://arxiv.org/abs/1410.5137 · HTML: https://mlsanity.com/paper/1410.5137/

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2014.

## Built on by (most cited first, 30 of 53)

- [AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks](https://mlsanity.com/paper/2106.12379/) (2021)
- [DAGs with No Curl: An Efficient DAG Structure Learning Approach](https://mlsanity.com/paper/2106.07197/) (2021)
- [Learnable Embedding Sizes for Recommender Systems](https://mlsanity.com/paper/2101.07577/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Backdoor Attack with Sparse and Invisible Trigger](https://mlsanity.com/paper/2306.06209/) (2023)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [Stability and Risk Bounds of Iterative Hard Thresholding](https://mlsanity.com/paper/2203.09413/) (2022)
- [Gradient Descent Converges Linearly for Logistic Regression on Separable Data](https://mlsanity.com/paper/2306.14381/) (2023)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [SoK: A Review of Differentially Private Linear Models For High-Dimensional Data](https://mlsanity.com/paper/2404.01141/) (2024)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Local Search Algorithms for Rank-Constrained Convex Optimization](https://mlsanity.com/paper/2101.06262/) (2021)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [AWP: Activation-Aware Weight Pruning and Quantization with Projected Gradient Descent](https://mlsanity.com/paper/2506.10205/) (2025)
- [Convergence of the mini-batch SIHT algorithm](https://mlsanity.com/paper/2209.14536/) (2022)
- [Slow Kill for Big Data Learning](https://mlsanity.com/paper/2305.01726/) (2023)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)
- [Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Model](https://mlsanity.com/paper/2106.14630/) (2021)
- [Robust High-Dimensional Regression with Coefficient Thresholding and its Application to Imaging Data Analysis](https://mlsanity.com/paper/2109.14856/) (2021)
- [The Stochastic Proximal Distance Algorithm](https://mlsanity.com/paper/2210.12277/) (2022)
- [Stochastic Mirror Descent for Large-Scale Sparse Recovery](https://mlsanity.com/paper/2210.12882/) (2022)
- [Distributed Semi-Supervised Sparse Statistical Inference](https://mlsanity.com/paper/2306.10395/) (2023)

## Abstract (arXiv)

The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard L0 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.