  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.
