When is memorization of irrelevant training data necessary for high-accuracy learning?
Files
Accepted manuscript
Date
DOI
Authors
Brown, Gavin
Bun, Mark
Feldman, Vitaly
Smith, Adam
Talwar, Kunal
Version
OA Version
Citation
G. Brown, M. Bun, V. Feldman, A. Smith, K. Talwar. "When is memorization of irrelevant training data necessary for high-accuracy learning?." Symposium on Theory of Computing (STOC) https://arxiv.org/abs/2012.06421
Abstract
Modern machine learning models are complex and frequently encode surprising amounts
of information about individual inputs. In extreme cases, complex models appear to
memorize entire input examples, including seemingly irrelevant information (social security
numbers from text, for example). In this paper, we aim to understand whether this
sort of memorization is necessary for accurate learning. We describe natural prediction
problems in which every sufficiently accurate training algorithm must encode, in the prediction
model, essentially all the information about a large subset of its training examples.
This remains true even when the examples are high-dimensional and have entropy much
higher than the sample size, and even when most of that information is ultimately irrelevant
to the task at hand. Further, our results do not depend on the training algorithm
or the class of models used for learning.
Our problems are simple and fairly natural variants of the next-symbol prediction
and the cluster labeling tasks. These tasks can be seen as abstractions of image- and
text-related prediction problems. To establish our results, we reduce from a family of
one-way communication problems for which we prove new information complexity lower
bounds.