Computational-Statistical Gaps for Improper Learning in Sparse Linear
  Regression
Rares-Darius Buhai Jingqiu Ding Stefan Tiegel
We study computational-statistical gaps for improper learning in sparse
linear regression. More specifically, given $n$ samples from a $k$-sparse
linear model in dimension $d$, we ask what is the minimum sample complexity to
efficiently (in time polynomial in $d$, $k$, and $n$) find a potentially dense
estimate for the regression vector that achieves non-trivial prediction error
on the $n$ samples. Information-theoretically this can be achieved using
$\Theta(k \log (d/k))$ samples. Yet, despite its prominence in the literature,
there is no polynomial-time algorithm known to achieve the same guarantees
using less than $\Theta(d)$ samples without additional restrictions on the
model. Similarly, existing hardness results are either restricted to the proper
setting, in which the estimate must be sparse as well, or only apply to
specific algorithms.
  We give evidence that efficient algorithms for this task require at least
(roughly) $\Omega(k^2)$ samples. In particular, we show that an improper
learning algorithm for sparse linear regression can be used to solve sparse PCA
problems (with a negative spike) in their Wishart form, in regimes in which
efficient algorithms are widely believed to require at least $\Omega(k^2)$
samples. We complement our reduction with low-degree and statistical query
lower bounds for the sparse PCA problems from which we reduce.
  Our hardness results apply to the (correlated) random design setting in which
the covariates are drawn i.i.d. from a mean-zero Gaussian distribution with
unknown covariance.