# Sparse Linear Regression and Lattice Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 22 Feb 2024.

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

- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Classical Hardness of Learning with Errors](https://mlsanity.com/paper/1306.0281/) (2013)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection](https://mlsanity.com/paper/1910.10890/) (2019)
- [Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression](https://mlsanity.com/paper/2402.14103/) (2024)
- [An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices](https://mlsanity.com/paper/1506.02717/) (2015)

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

- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)

## Abstract (arXiv)

Sparse linear regression (SLR) is a well-studied problem in statistics where one is given a design matrix X∈ℝm× n and a response vector y=Xθ^*+w for a k-sparse vector θ^* (that is, |θ^*|0≤ k) and small, arbitrary noise w, and the goal is to find a k-sparse widehatθ ∈ ℝn that minimizes the mean squared prediction error frac1m|Xwidehatθ-Xθ^*|22. While ℓ1-relaxation methods such as basis pursuit, Lasso, and the Dantzig selector solve SLR when the design matrix is well-conditioned, no general algorithm is known, nor is there any formal evidence of hardness in an average-case setting with respect to all efficient algorithms. We give evidence of average-case hardness of SLR w.r.t. all efficient algorithms assuming the worst-case hardness of lattice problems. Specifically, we give an instance-by-instance reduction from a variant of the bounded distance decoding (BDD) problem on lattices to SLR, where the condition number of the lattice basis that defines the BDD instance is directly related to the restricted eigenvalue condition of the design matrix, which characterizes some of the classical statistical-computational gaps for sparse linear regression. Also, by appealing to worst-case to average-case reductions from the world of lattices, this shows hardness for a distribution of SLR instances; while the design matrices are ill-conditioned, the resulting SLR instances are in the identifiable regime. Furthermore, for well-conditioned (essentially) isotropic Gaussian design matrices, where Lasso is known to behave well in the identifiable regime, we show hardness of outputting any good solution in the unidentifiable regime where there are many solutions, assuming the worst-case hardness of standard and well-studied lattice problems.