论文标题
过度拟合可能是无害的，但仅在一定程度上是无害的
Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree
论文作者
论文摘要
最近，研究了在过度参数化和过度拟合过度的统治下，在研究线性回归模型的概括误差的“双重研究”的兴趣中，希望这样的分析可以为理解为什么过度参数化的深层神经网络（DNN）仍然良好地概述。但是，迄今为止，大多数研究都集中在过度拟合数据的最低$ \ ell_2 $ -Norm解决方案上。相比之下，在本文中，我们研究了最小化$ \ ell_1 $ -norm的过度拟合解决方案，这在压缩感测文献中被称为基础追求（BP）。在稀疏的真实线性回归模型下，$ p $ i.i.d.高斯功能，我们表明，对于$ p $的范围范围很大，该限制呈指数增长，随着样本$ n $的数量，BP的模型误差的上限是$ p $降低的值。据我们所知，这是文献中第一个分析结果，确立了有限的$ n $和$ p $的双重拟合bp的两种结果。此外，我们的结果揭示了BP的双重发现与Min $ \ Ell_2 $ -Norm解决方案之间的显着差异。具体而言，BP的双重上限与信号强度无关，而对于高SNR和稀疏模型，BP的下降层可能比最低$ \ ell_2 $ norm solutions的BP的下降范围要低得多。
Recently, there have been significant interests in studying the so-called "double-descent" of the generalization error of linear regression models under the overparameterized and overfitting regime, with the hope that such analysis may provide the first step towards understanding why overparameterized deep neural networks (DNN) still generalize well. However, to date most of these studies focused on the min $\ell_2$-norm solution that overfits the data. In contrast, in this paper we study the overfitting solution that minimizes the $\ell_1$-norm, which is known as Basis Pursuit (BP) in the compressed sensing literature. Under a sparse true linear regression model with $p$ i.i.d. Gaussian features, we show that for a large range of $p$ up to a limit that grows exponentially with the number of samples $n$, with high probability the model error of BP is upper bounded by a value that decreases with $p$. To the best of our knowledge, this is the first analytical result in the literature establishing the double-descent of overfitting BP for finite $n$ and $p$. Further, our results reveal significant differences between the double-descent of BP and min $\ell_2$-norm solutions. Specifically, the double-descent upper-bound of BP is independent of the signal strength, and for high SNR and sparse models the descent-floor of BP can be much lower and wider than that of min $\ell_2$-norm solutions.
