In this work we establish an algorithm and distribution independent non-asymptotic trade-off between the model size, excess test loss, and training loss of linear predictors. Specifically, we show that models that perform well on the test data (have low excess loss) are either "classical" -- have training loss close to the noise level, or are "modern" -- have a much larger number of parameters compared to the minimum needed to fit the training data exactly. We also provide a more precise asymptotic analysis when the limiting spectral distribution of the whitened features is Marchenko-Pastur. Remarkably, while the Marchenko-Pastur analysis is far more precise near the interpolation peak, where the number of parameters is just enough to fit the training data, in settings of most practical interest it differs from the distribution independent bound by only a modest multiplicative constant.
翻译:在这项工作中,我们在模型大小、过量测试损失以及线性预测器培训损失之间建立起了一种算法和独立的非无损分配的平衡。具体地说,我们表明,在测试数据上表现良好的模型(有低过重损失)要么是“古典”模型(具有接近噪音水平的培训损失,要么是“现代”模型),其参数数量比完全适应培训数据所需的最低值要多得多。当白化特征的有限光谱分布为Marchenko-Pastur时,我们还提供了更精确的无损分析。值得注意的是,马切科-Pastur模型的分析在内推峰附近非常精确,因为在这个顶峰里,参数的数量足以适应培训数据,在最符合实际利益的情况下,它与仅受适度的多倍数常数约束而独立的分布不同。