# The Fine-Grained Hardness of Sparse Linear Regression

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 6 Jun 2021.

## Builds on (most cited first, 9 of 9)

- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Approximate Sparse Linear Regression](https://mlsanity.com/paper/1609.08739/) (2016)
- [Tight Hardness Results for Maximum Weight Rectangles](https://mlsanity.com/paper/1602.05837/) (2016)
- [More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture](https://mlsanity.com/paper/1805.08554/) (2018)
- [Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms](https://mlsanity.com/paper/1607.04229/) (2016)
- [On the Quantitative Hardness of CVP](https://mlsanity.com/paper/1704.03928/) (2017)
- [Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)](https://mlsanity.com/paper/1911.02440/) (2019)
- [Solving the Closest Vector Problem in 2n Time--- The Discrete Gaussian Strikes Again!](https://mlsanity.com/paper/1504.01995/) (2015)

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

- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [Sparse Linear Regression and Lattice Problems](https://mlsanity.com/paper/2402.14645/) (2024)
- [Towards Learning Stochastic Population Models by Gradient Descent](https://mlsanity.com/paper/2404.07049/) (2024)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization](https://mlsanity.com/paper/2402.17902/) (2024)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)
- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)

## Abstract (arXiv)

Sparse linear regression is the well-studied inference problem where one is given a design matrix A ∈ ℝM× N and a response vector b ∈ ℝM, and the goal is to find a solution x ∈ ℝN which is k-sparse (that is, it has at most k non-zero coordinates) and minimizes the prediction error |A x - b|2. On the one hand, the problem is known to be NP-hard which tells us that no polynomial-time algorithm exists unless P = NP. On the other hand, the best known algorithms for the problem do a brute-force search among Nk possibilities. In this work, we show that there are no better-than-brute-force algorithms, assuming any one of a variety of popular conjectures including the weighted k-clique conjecture from the area of fine-grained complexity, or the hardness of the closest vector problem from the geometry of numbers. We also show the impossibility of better-than-brute-force algorithms when the prediction error is measured in other ℓp norms, assuming the strong exponential-time hypothesis.