Sparse Linear Regression and Lattice Problems
Aparna Gupte Neekon Vafa Vinod Vaikuntanathan
Sparse linear regression (SLR) is a well-studied problem in statistics where
one is given a design matrix $X\in\mathbb{R}^{m\times n}$ and a response vector
$y=X\theta^*+w$ for a $k$-sparse vector $\theta^*$ (that is,
$\|\theta^*\|_0\leq k$) and small, arbitrary noise $w$, and the goal is to find
a $k$-sparse $\widehat{\theta} \in \mathbb{R}^n$ that minimizes the mean
squared prediction error $\frac{1}{m}\|X\widehat{\theta}-X\theta^*\|^2_2$.
While $\ell_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.