2020

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

Feldman, Vitaly, Zhang, Chiyuan

Understand

Deep learning algorithms are well-known to have a propensity for fitting the training data very well and often fit even outliers and mislabeled data points.

Such fitting requires memorization of training data labels, a phenomenon that has attracted significant research interest but has not been given a compelling explanation so far.
A recent work of Feldman (2019) proposes a theoretical explanation for this phenomenon based on a combination of two insights.
First, natural image and data distributions are (informally) known to be long-tailed, that is have a significant fraction of rare and atypical examples.

Built on

“Does Learning Require Memorization? A Short Tale about a Long Tail” Extended abstract in STOC 2020
Original
Vitaly Feldman · 1906
Earlier work this paper cites.
“Residuals and influence in regression”
R Cook and Sanford Weisberg · 1982
Earlier work this paper cites.
“Characterizing Structural Regularities of Labeled Data in Overparameterized Models”
Original
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar and Michael. Mozer · 2002
Earlier work this paper cites.
“Estimating Training Data Influence by Tracking Gradient Descent”, 2020
Original
Garima Pruthi, Frederick Liu, Mukund Sundararajan and Satyen Kale · 2002
Earlier work this paper cites.
“Capturing long-tail distributions of object subcategories”
Xiangxin Zhu, Dragomir Anguelov and Deva Ramanan · 2014
Earlier work this paper cites.
“TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems” Software available from tensorflow.org, 2015
Mart“’n Abadi et al · 2015
Earlier work this paper cites.
“Going deeper with convolutions”
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke and Andrew Rabinovich · 2015
Earlier work this paper cites.
“Deep Residual Learning for Image Recognition”
K. He, X. Zhang, S. Ren and J. Sun · 2016
Earlier work this paper cites.
“A closer look at memorization in deep networks”
Devansh Arpit, Stanislaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville and Yoshua Bengio · 2017
Earlier work this paper cites.
“Densely connected convolutional networks”
Gao Huang, Zhuang Liu, Laurens Van Der and Kilian Weinberger · 2017
Earlier work this paper cites.
“Understanding black-box predictions via influence functions”
Pang Koh and Percy Liang · 2017
Earlier work this paper cites.
“Exploring generalization in deep learning”
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester and Nati Srebro · 2017
Earlier work this paper cites.

Similar

“Membership Inference Attacks Against Machine Learning Models”
Reza Shokri, Marco Stronati, Congzheng Song and Vitaly Shmatikov · 2017
Cited alongside, same era.
“The devil is in the tails: Fine-grained classification in the wild”
Original
Grant Van and Pietro Perona · 2017
Cited alongside, same era.
“Explaining the success of adaboost and random forests as interpolating classifiers”
Abraham Wyner, Matthew Olson, Justin Bleich and David Mease · 2017
Cited alongside, same era.
“Understanding deep learning requires rethinking generalization”
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals · 2017
Cited alongside, same era.
“Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate”
Mikhail Belkin, Daniel Hsu and Partha Mitra · 2018
Cited alongside, same era.
“To Understand Deep Learning We Need to Understand Kernel Learning”
Mikhail Belkin, Siyuan Ma and Soumik Mandal · 2018
Cited alongside, same era.
“Does data interpolation contradict statistical optimality?”
Original
Mikhail Belkin, Alexander Rakhlin and Alexandre Tsybakov · 2018
Cited alongside, same era.
“Just interpolate: Kernel” ridgeless” regression can generalize”
Original
Tengyuan Liang and Alexander Rakhlin · 2018
Cited alongside, same era.
“Representer point selection for explaining deep neural networks”
Chih-Kuan Yeh, Joon Kim, Ian En-Hsu Yen and Pradeep Ravikumar · 2018
Cited alongside, same era.
“Two models of double descent for weak features”
Original
Mikhail Belkin, Daniel Hsu and Ji Xu · 2019
Cited alongside, same era.
“Benign Overfitting in Linear Regression”
Original
Peter Bartlett, Philip Long, G“’abor Lugosi and Alexander Tsigler · 2019
Cited alongside, same era.

Then

“Differential privacy has disparate impact on model accuracy”
Eugene Bagdasaryan, Omid Poursaeed and Vitaly Shmatikov · 2019
Later among the works it cites.
“Data scarcity, robustness and extreme multi-label classification”
Rohit Babbar and Bernhard Sch“”olkopf · 2019
Later among the works it cites.
“Distribution Density, Tails, and Outliers in Machine Learning: Metrics and Applications”
Original
Nicholas Carlini, “’Ulfar Erlingsson and Nicolas Papernot · 2019
Later among the works it cites.
“Surprises in High-Dimensional Ridgeless Least Squares Interpolation”
Original
Trevor Hastie, Andrea Montanari, Saharon Rosset and Ryan Tibshirani · 2019
Later among the works it cites.
“Harmless interpolation of noisy data in regression”
Original
Vidya Muthukumar, Kailas Vodrahalli and Anant Sahai · 2019
Later among the works it cites.
“Uniform convergence may be unable to explain generalization in deep learning”
Vaishnavh Nagarajan and J Kolter · 2019
Later among the works it cites.
“Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon”
Alexander Rakhlin and Xiyu Zhai · 2019
Later among the works it cites.
“An Empirical Study of Example Forgetting during Deep Neural Network Learning”
Mariya Toneva, Alessandro Sordoni, Remi des Combes, Adam Trischler, Yoshua Bengio and Geoffrey. Gordon · 2019
Later among the works it cites.
“Do We Train on Test Data? Purging CIFAR of Near-Duplicates”
Björn Barz and Joachim Denzler · 2020
Closest in time.
“Additional Material” https://pluskid.github.io/influence-memorization/ , 2020
Vitaly Feldman and Chiyuan Zhang · 2020
Closest in time.
“Fantastic Generalization Measures and Where to Find Them”
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan and Samy Bengio · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…