# Structured Sparse Regression via Greedy Hard-Thresholding

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2016.

## Built on by (most cited first, 6 of 6)

- [Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm](https://mlsanity.com/paper/2106.06027/) (2021)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [A Splicing Approach to Best Subset of Groups Selection](https://mlsanity.com/paper/2104.12576/) (2021)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)

## Abstract (arXiv)

Several learning applications require solving high-dimensional regression problems where the relevant features belong to a small number of (overlapping) groups. For very large datasets and under standard sparsity constraints, hard thresholding methods have proven to be extremely efficient, but such methods require NP hard projections when dealing with overlapping groups. In this paper, we show that such NP-hard projections can not only be avoided by appealing to submodular optimization, but such methods come with strong theoretical guarantees even in the presence of poorly conditioned data (i.e. say when two features have correlation ≥ 0.99), which existing analyses cannot handle. These methods exhibit an interesting computation-accuracy trade-off and can be extended to significantly harder problems such as sparse overlapping groups. Experiments on both real and synthetic data validate our claims and demonstrate that the proposed methods are orders of magnitude faster than other greedy and convex relaxation techniques for learning with group-structured sparsity.