CryptoDB
Sparse Linear Regression and Lattice Problems
Authors: 


Download:  
Conference:  TCC 2024 
Abstract:  Sparse linear regression (SLR) is a wellstudied problem in statistics where one is given a design matrix $\mathbf{X} \in \mathbb{R}^{m \times n}$ and a response vector $\mathbf{y} = \mathbf{X} \boldsymbol{\theta}^* + \mathbf{w}$ for a $k$sparse vector $\boldsymbol{\theta}^*$ (that is, $\\boldsymbol{\theta}^*\_0 \leq k$) and small, arbitrary noise $\mathbf{w}$, and the goal is to find a $k$sparse $\widehat{\boldsymbol{\theta}} \in \mathbb{R}^{n}$ that minimizes the mean squared prediction error $\frac{1}{m} \\mathbf{X} \widehat{\boldsymbol{\theta}}  \mathbf{X} \boldsymbol{\theta}^*\^2_2$. While $\ell_1$relaxation methods such as basis pursuit, Lasso, and the Dantzig selector solve SLR when the design matrix is wellconditioned, no general algorithm is known, nor is there any formal evidence of hardness in an averagecase setting with respect to all efficient algorithms. We give evidence of averagecase hardness of SLR w.r.t. all efficient algorithms assuming the worstcase hardness of lattice problems. Specifically, we give an instancebyinstance 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 statisticalcomputational gaps for sparse linear regression. Also, by appealing to worstcase to averagecase reductions from the world of lattices, this shows hardness for a distribution of SLR instances; while the design matrices are illconditioned, the resulting SLR instances are in the identifiable regime. Furthermore, for wellconditioned (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 worstcase hardness of standard and wellstudied lattice problems. 
BibTeX
@inproceedings{tcc202434796, title={Sparse Linear Regression and Lattice Problems}, publisher={SpringerVerlag}, author={Aparna Gupte and Neekon Vafa and Vinod Vaikuntanathan}, year=2024 }