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.

我们研究了稀疏线性回归的计算统计缺口，证明了这个问题需要至少大约 k^2 个样本才能有效解决，并且还应用于稀疏 PCA 问题的降低及低阶下界。

稀疏线性回归中的不当学习的计算统计差距

Computational-Statistical Gaps for Improper Learning in Sparse Linear  Regression

This work investigates the nuanced algorithm design choices for deep learning
in the presence of computational-statistical gaps. We begin by considering
offline sparse parity learning, a supervised classification problem which
admits a statistical query lower bound for gradient-based training of a
multilayer perceptron. This lower bound can be interpreted as a multi-resource
tradeoff frontier: successful learning can only occur if one is sufficiently
rich (large model), knowledgeable (large dataset), patient (many training
iterations), or lucky (many random guesses). We show, theoretically and
experimentally, that sparse initialization and increasing network width yield
significant improvements in sample efficiency in this setting. Here, width
plays the role of parallel search: it amplifies the probability of finding
"lottery ticket" neurons, which learn sparse features more sample-efficiently.
Finally, we show that the synthetic sparse parity task can be useful as a proxy
for real problems requiring axis-aligned feature learning. We demonstrate
improved sample efficiency on tabular classification benchmarks by using wide,
sparsely-initialized MLP models; these networks sometimes outperform tuned
random forests.

该研究调查了深度学习在计算统计差距存在的情况下的算法设计选择。通过考虑离线稀疏奇偶学习，一种多层感知器的梯度训练的统计查询下界，我们展示了稀疏初始化和增加网络宽度在样本效率方面的显著改进，以及合成稀疏奇偶任务对于需要轴对齐特征学习的真实问题的代理用途。