State-of-the-art results on image recognition tasks are achieved using over-parameterized learning algorithms that (nearly) perfectly fit the training set. This phenomenon is referred to as data interpolation or, informally, as memorization of the training data. The question of why such algorithms generalize well to unseen data is not adequately addressed by the standard theoretical frameworks and, as a result, significant theoretical and experimental effort has been devoted to understanding the properties of such algorithms. We provide a simple and generic model for prediction problems in which interpolating the dataset is necessary for achieving close-to-optimal generalization error. The model is motivated and supported by the results of several recent empirical works. In our model, data is sampled from a mixture of subpopulations and the frequencies of these subpopulations are chosen from some prior. The model allows to quantify the effect of not fitting the training data on the generalization performance of the learned classifier and demonstrates that memorization is necessary whenever frequencies are long-tailed. Image and text data are known to follow such distributions and therefore our results establish a formal link between these empirical phenomena. To the best of our knowledge, this is the first general framework that demonstrates statistical benefits of plain memorization for learning. Our results also have concrete implications for the cost of ensuring differential privacy in learning.

本文提出了对于自然数据分布来说，必须要对标签进行记忆才能达到接近最优的泛化误差的第一概念解释和理论模型。该模型支持最近几项实证研究的结果，发现对于长尾子群分布的数据采样，标签的记忆是必要的，而图像和文本数据也被证明是长尾的。我们的研究不仅可能量化在学习过程中限制记忆的代价，而且还能解释隐私和模型压缩对不同子组的影响不同的不同效应。

学习需要记忆吗？一个长尾故事的简短描绘