Research map / Optimization / Optimizers
Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Accelerates iterative hard thresholding for sparse linear regression by safely pruning gradient computations via upper and lower bounds on parameter magnitudes, yielding identical outputs to plain IHT and up to 73x speedups.
Problem
Plain iterative hard thresholding (IHT) for k-sparse linear regression is bottlenecked by per-iteration gradient computations, which cost O(mn) or O(n^2) time.
Approach
Maintain a candidate set of k indices and use cheap O(n) upper and lower bounds on the gradient-descent pre-activations (computed from a previously computed anchor iterate) to prune gradient computations for indices that cannot enter the top-k set, while raising the pruning threshold with lower bounds; the outputs are exactly those of plain IHT.
Key results
- Up to 73 times faster than plain IHT across five feature selection datasets, outperforming RegIHT and AccIHT in all settings.
- Reduces the number of gradient computations by up to 98.87% on gisette.
- Objective values match plain IHT exactly for k = 1, 20, 160, 1280 across all datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Prune unnecessary gradient computations | IHT · Feature selection tasks (five datasets) | processing time: up to 73 times faster | Helped |
| Prune unnecessary gradient computations | IHT · gisette | number of gradient computations: up to 98.87% | Helped |
| Use safe pruning of gradient computations | IHT · gisette, robert, ledgar, real-sim, and epsilon | objective value: 56.01 × 10−2 -> 56.01 × 10−2; 31.99 × 10−2 -> 31.99 × 10−2; 14.01 × 10−2 -> 14.01 × 10−2; 80.73 × 10−3 -> 80.73 × 10−3; | No clear effect |
| Use FastIHT instead of RegIHT and AccIHT | IHT feature selection tasks · All settings across five datasets | processing time | Helped |
Limitations
- Processing time increases when k becomes large, reducing the speedup.
- Analysis restricted to linear regression with the squared loss and hard thresholding; extension to general convex losses left to future work.
- No error bars reported because baselines are computationally expensive.
Experimental setup
Datasets: gisette robert ledgar real-sim epsilon
Benchmarks: gisette robert ledgar real-sim epsilon
Metrics: wall clock time number of gradient computations objective value
Baselines: IHT RegIHT AccIHT
Builds on: iterative hard thresholding RegIHT AccIHT
Closest papers by meaning
- Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime (ICML 2022 · similarity 0.90)
- Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization (ICML 2017 · similarity 0.89)
- Learning Sparse Distributions using Iterative Hard Thresholding (NeurIPS 2019 · similarity 0.88)
- Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence (ICML 2024 · similarity 0.84)
- Exploring Learning Complexity for Efficient Downstream Dataset Pruning (ICLR 2025 · similarity 0.83)
- SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.