Interpolation, extrapolation and memorisation in neural networks

January 25, 2022 — June 14, 2024

algebra
graphical models
how do science
machine learning
meta learning
networks
probability
statistics
Figure 1: Learn this convex hull.

Interpreting models in terms of their ability to interpolate and memorise and when that becomes extrapolation. Connection to neural scaling, overparameterization.

The notion of interpolation and extrapolation is fundamental in various fields from deep learning to function approximation. Interpolation occurs for a sample x whenever this sample falls inside or on the boundary of the given dataset’s convex hull. Extrapolation occurs when x falls outside of that convex hull. One fundamental (mis)conception is that state-of-the-art algorithms work so well because of their ability to correctly interpolate training data. A second (mis)conception is that interpolation happens throughout tasks and datasets, in fact, many intuitions and theories rely on that assumption. We empirically and theoretically argue against those two points and demonstrate that on any high-dimensional (>100) dataset, interpolation almost surely never happens. Those results challenge the validity of our current interpolation/extrapolation definition as an indicator of generalization performances.

Classic works in this domain include Balestriero, Pesenti, and LeCun (2021); Le (2018); Ma, Bassily, and Belkin (2018); Zhang et al. (2017); Zhang et al. (2021)

1 References

Alabdulmohsin, Neyshabur, and Zhai. 2022. “Revisiting Neural Scaling Laws in Language and Vision.” Advances in Neural Information Processing Systems.
Balestriero, Pesenti, and LeCun. 2021. “Learning in High Dimension Always Amounts to Extrapolation.”
Bartlett, Montanari, and Rakhlin. 2021. “Deep Learning: A Statistical Viewpoint.” Acta Numerica.
Belkin. 2021. “Fit Without Fear: Remarkable Mathematical Phenomena of Deep Learning Through the Prism of Interpolation.” Acta Numerica.
Belkin, Hsu, Ma, et al. 2019. “Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off.” Proceedings of the National Academy of Sciences.
Domingos. 2020. “Every Model Learned by Gradient Descent Is Approximately a Kernel Machine.” arXiv:2012.00152 [Cs, Stat].
Feldman. 2020. “Does Learning Require Memorization? A Short Tale about a Long Tail.” In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020.
Grosse, Bae, Anil, et al. 2023. “Studying Large Language Model Generalization with Influence Functions.”
Hastie, Montanari, Rosset, et al. 2020. “Surprises in High-Dimensional Ridgeless Least Squares Interpolation.”
Hoel. 2021. “The Overfitted Brain: Dreams Evolved to Assist Generalization.” Patterns.
Le. 2018. “A Bayesian Perspective on Generalization and Stochastic Gradient Descent.” In.
Loog, Viering, Mey, et al. 2020. “A Brief Prehistory of Double Descent.” Proceedings of the National Academy of Sciences.
Ma, Bassily, and Belkin. 2018. “The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-Parametrized Learning.” In Proceedings of the 35th International Conference on Machine Learning.
Nakkiran, Kaplun, Bansal, et al. 2019. “Deep Double Descent: Where Bigger Models and More Data Hurt.” arXiv:1912.02292 [Cs, Stat].
Papyan, Han, and Donoho. 2020. “Prevalence of Neural Collapse During the Terminal Phase of Deep Learning Training.” Proceedings of the National Academy of Sciences.
Power, Burda, Edwards, et al. 2022. “Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets.”
Refinetti, d’Ascoli, Ohana, et al. 2021. “Align, Then Memorise: The Dynamics of Learning with Feedback Alignment.” arXiv:2011.12428 [Cond-Mat, Stat].
Webb, Dulberg, Frankland, et al. 2020. “Learning Representations That Support Extrapolation.” In Proceedings of the 37th International Conference on Machine Learning.
Wilson, and Izmailov. 2020. “Bayesian Deep Learning and a Probabilistic Perspective of Generalization.”
Xu, Zhang, Li, et al. 2021. “How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks.”
Zhang, Bengio, Hardt, et al. 2017. “Understanding Deep Learning Requires Rethinking Generalization.” In Proceedings of ICLR.
———, et al. 2021. “Understanding Deep Learning (Still) Requires Rethinking Generalization.” Communications of the ACM.
Zhan, Xie, Mao, et al. 2022. “Evaluating Interpolation and Extrapolation Performance of Neural Retrieval Models.” In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. CIKM ’22.