Elamur Research⌕
☰
home / papers / 2020 / What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation

What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation

Paper · 2020 · Vitaly Feldman and Chiyuan Zhang

Summary

Deep networks routinely fit outliers and mislabeled training points. Classical generalization theory treats this as harmful overfitting, so it cannot explain why it happens. Feldman's earlier "long tail theory" argued that memorization is needed for near-optimal accuracy when data contain many rare subpopulations, but it lacked empirical support. This paper tests that theory on MNIST, CIFAR-100 and ImageNet.

Exact leave-one-out memorization and influence scores would need millions of training runs. The authors instead define subsampled versions: models are trained on random subsets of the data, and each example's effect is estimated by comparing models that did or did not see it. This yields estimates for all examples at once from a few thousand runs, and the method works with any model.

On the two larger datasets, many training examples turn out to be strongly memorized. Removing them hurts test accuracy more than removing a random set of equal size. Many test images depend on a single, visually similar training image. These results suggest that limiting memorization, for example through compression or differential privacy, may disproportionately harm under-represented groups.

Key points

  • Estimator cost: Exact estimation needs a number of runs that grows with dataset size n (Ω(n/σ²)). The subsampled estimator needs only O(1/σ²) runs to cover every example together.
  • ImageNet memorization: About 32% of training examples have memorization estimates ≥ 0.3. Removing them lowers test accuracy by roughly 3.4%, compared with about 2.6% for a random subset of the same size.
  • High-influence pairs: Pairs were selected with thresholds of 0.25 (memorization) and 0.15 (influence). ImageNet yielded 1641 such pairs covering 1462 test images (2.92% of the test set), and 1298 of those images rely on just one training example.
  • Architecture and retraining checks (CIFAR-100):
    • ResNet50, ResNet18, Inception and DenseNet100 produce strongly correlated sets of memorized examples and high-influence pairs.
    • Retraining only the last layer on fixed representations finds just 38 memorized examples, versus 18,099 with full ResNet50 training. This indicates that memorization mostly lives in the learned representations.
  • Released resource: The computed memorization and influence values for CIFAR-100 and ImageNet are publicly available [FZ20].

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢GoogleMountain View · United States492 works · 440,462 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 works

Cite

Cite as Vitaly Feldman and Chiyuan Zhang. 2020. What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation. arXiv:2008.03703.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2008.03703 · arXiv 2008.03703

@misc{feldman2020what,
  title = {{What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation}},
  author = {Vitaly Feldman and Chiyuan Zhang},
  year = {2020},
  doi = {10.48550/arxiv.2008.03703},
  eprint = {2008.03703},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2008.03703}
}

References

34 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. M. Abadi et al. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. Software available from tensorflow.org. 2015. URL : https://www.tensorflow.org/. ↗
  2. D. Arpit, S. Jastrzkebski, N. Ballas, D. Krueger, E. Bengio, M. S. Kanwal, T. Maharaj, A. Fischer, A. Courville, Y. Bengio, et al. “A closer look at memorization in deep networks”. In: Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org. 2017, pp. 233–242. find
  3. B. Barz and J. Denzler. “Do We Train on Test Data? Purging CIFAR of Near-Duplicates”. In: Journal of Imaging 6.6 (2020), p. 41. find
  4. M. Belkin, D. J. Hsu, and P. Mitra. “Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate”. In: Advances in Neural Information Processing Systems. 2018, pp. 2300–2311. find
  5. M. Belkin, D. Hsu, and J. Xu. “Two models of double descent for weak features”. In: arXiv preprint arXiv:1903.07571 (2019). — [arXiv:1903.07571](https://arxiv.org/abs/1903.07571) find
  6. P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. “Benign Overfitting in Linear Regression”. In: arXiv preprint arXiv:1906.11300 (2019). — [arXiv:1906.11300](https://arxiv.org/abs/1906.11300) find
  7. M. Belkin, S. Ma, and S. Mandal. “To Understand Deep Learning We Need to Understand Kernel Learning”. In: ICML. Vol. 80. Proceedings of Machine Learning Research. PMLR, 2018, pp. 541–549. URL : http://proceedings.mlr.press/v80/belkin18a.html. ↗
  8. E. Bagdasaryan, O. Poursaeed, and V. Shmatikov. “Differential privacy has disparate impact on model accuracy”. In: Advances in Neural Information Processing Systems. 2019, pp. 15453–15462. find
  9. M. Belkin, A. Rakhlin, and A. B. Tsybakov. “Does data interpolation contradict statistical optimality?” In: arXiv preprint arXiv:1806.09471 (2018). — [arXiv:1806.09471](https://arxiv.org/abs/1806.09471) find
  10. R. Babbar and B. Schölkopf. “Data scarcity, robustness and extreme multi-label classification”. In: Machine Learning (2019). find
  11. N. Carlini, Ú. Erlingsson, and N. Papernot. “Distribution Density, Tails, and Outliers in Machine Learning: Metrics and Applications”. In: arXiv preprint arXiv:1910.13427 (2019). — [arXiv:1910.13427](https://arxiv.org/abs/1910.13427) find
  12. R. D. Cook and S. Weisberg. Residuals and influence in regression. New York: Chapman and Hall, 1982. find
  13. V. Feldman. “Does Learning Require Memorization? A Short Tale about a Long Tail”. In: CoRR abs/1906.05271 (2019). Extended abstract in STOC 2020. arXiv: 1906.05271. URL : http://arxiv.org/abs/1906.05271. — [arXiv:1906.05271](https://arxiv.org/abs/1906.05271) ↗
  14. V. Feldman and C. Zhang. Additional Material. https://pluskid.github . io / influence - memorization/. 2020. ↗
  15. G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. “Densely connected convolutional networks”. In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2017, pp. 4700–4708. find
  16. T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. “Surprises in High-Dimensional Ridgeless Least Squares Interpolation”. In: arXiv preprint arXiv:1903.08560 (2019). — [arXiv:1903.08560](https://arxiv.org/abs/1903.08560) find
  17. K. He, X. Zhang, S. Ren, and J. Sun. “Deep Residual Learning for Image Recognition”. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2016, pp. 770–778.
  18. Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. “Fantastic Generalization Measures and Where to Find Them”. In: ICLR. 2020. URL : https://openreview.net/forum?id=SJgIPJBFvH. ↗
  19. Z. Jiang, C. Zhang, K. Talwar, and M. C. Mozer. “Characterizing Structural Regularities of Labeled Data in Overparameterized Models”. In: CoRR abs/2002.03206 (2020). arXiv: 2002.03206. URL : https://arxiv.org/abs/2002.03206. — [arXiv:2002.03206](https://arxiv.org/abs/2002.03206) ↗
  20. P. W. Koh and P. Liang. “Understanding black-box predictions via influence functions”. In: Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org. 2017, pp. 1885–1894.
  21. T. Liang and A. Rakhlin. “Just interpolate: Kernel” ridgeless” regression can generalize”. In: arXiv preprint arXiv:1808.00387 (2018). — [arXiv:1808.00387](https://arxiv.org/abs/1808.00387) find
  22. V. Muthukumar, K. Vodrahalli, and A. Sahai. “Harmless interpolation of noisy data in regression”. In: arXiv preprint arXiv:1903.09139 (2019). — [arXiv:1903.09139](https://arxiv.org/abs/1903.09139) find
  23. B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. “Exploring generalization in deep learning”. In: Advances in Neural Information Processing Systems. 2017, pp. 5947–5956. find
  24. V. Nagarajan and J. Z. Kolter. “Uniform convergence may be unable to explain generalization in deep learning”. In: Advances in Neural Information Processing Systems. 2019, pp. 11611–11622. find
  25. G. Pruthi, F. Liu, M. Sundararajan, and S. Kale. Estimating Training Data Influence by Tracking Gradient Descent. 2020. arXiv: 2002.08484 [cs.LG].
  26. A. Rakhlin and X. Zhai. “Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon”. In: COLT. Vol. 99. PMLR, 2019, pp. 2595–2623. URL : http://proceedings.mlr.press/v99/rakhlin19a.html. ↗
  27. R. Shokri, M. Stronati, C. Song, and V. Shmatikov. “Membership Inference Attacks Against Machine Learning Models”. In: 2017 IEEE Symposium on Security and Privacy, SP 2017. 2017, pp. 3–18.
  28. C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. “Going deeper with convolutions”. In: Proceedings of the IEEE conference on computer vision and pattern recognition. 2015, pp. 1–9. find
  29. M. Toneva, A. Sordoni, R. T. des Combes, A. Trischler, Y. Bengio, and G. J. Gordon. “An Empirical Study of Example Forgetting during Deep Neural Network Learning”. In: ICLR. OpenReview.net, 2019. URL : https://openreview.net/forum?id=BJlxm30cKm. ↗
  30. G. Van Horn and P. Perona. “The devil is in the tails: Fine-grained classification in the wild”. In: arXiv preprint arXiv:1709.01450 (2017). — [arXiv:1709.01450](https://arxiv.org/abs/1709.01450) find
  31. A. J. Wyner, M. Olson, J. Bleich, and D. Mease. “Explaining the success of adaboost and random forests as interpolating classifiers”. In: The Journal of Machine Learning Research 18.1 (2017), pp. 1558–1590. find
  32. C.-K. Yeh, J. Kim, I. E.-H. Yen, and P. K. Ravikumar. “Representer point selection for explaining deep neural networks”. In: Advances in Neural Information Processing Systems. 2018, pp. 9291–9301. find
  33. X. Zhu, D. Anguelov, and D. Ramanan. “Capturing long-tail distributions of object subcategories”. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014, pp. 915– 922. find
  34. C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. “Understanding deep learning requires rethinking generalization”. In: ICLR. 2017. URL : https://openreview.net/forum?id=Sy8gdB9xx. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/feldman-2020-neural-networks-memorize-why-discovering/