Does Learning Require Memorization? A Short Tale about a Long Tail
This addresses a foundational issue in machine learning theory, explaining memorization in over-parameterized models and its implications for privacy and fairness, with broad relevance to AI research.
The paper tackles the problem of understanding why over-parameterized models memorize training data, showing that for natural long-tailed distributions, memorization of labels, including outliers and noisy ones, is necessary to achieve near-optimal generalization error. It provides a theoretical model linking this to empirical phenomena in image and text data.
State-of-the-art results on image recognition tasks are achieved using over-parameterized learning algorithms that (nearly) perfectly fit the training set and are known to fit well even random labels. This tendency to memorize the labels of the training data is not explained by existing theoretical analyses. Memorization of the training data also presents significant privacy risks when the training data contains sensitive personal information and thus it is important to understand whether such memorization is necessary for accurate learning. We provide the first conceptual explanation and a theoretical model for this phenomenon. Specifically, we demonstrate that for natural data distributions memorization of labels is necessary for achieving close-to-optimal generalization error. Crucially, even labels of outliers and noisy labels need to be memorized. 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 our results show that memorization is necessary whenever the distribution of subpopulation frequencies is long-tailed. Image and text data is known to be long-tailed and therefore our results establish a formal link between these empirical phenomena. Our results allow to quantify the cost of limiting memorization in learning and explain the disparate effects that privacy and model compression have on different subgroups.