# Deep Learning Generalization and the Convex Hull of Training Sets

arXiv: https://arxiv.org/abs/2101.09849 · HTML: https://mlsanity.com/paper/2101.09849/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 58 references that are in the map.
- First posted on arXiv 25 Jan 2021.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networks](https://mlsanity.com/paper/1706.02690/) (2017)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Noise or Signal: The Role of Image Backgrounds in Object Recognition](https://mlsanity.com/paper/2006.09994/) (2020)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Predicting the Generalization Gap in Deep Networks with Margin Distributions](https://mlsanity.com/paper/1810.00113/) (2018)
- [Large Margin Deep Networks for Classification](https://mlsanity.com/paper/1803.05598/) (2018)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [Geometric robustness of deep networks: analysis and improvement](https://mlsanity.com/paper/1711.09115/) (2017)
- [Geometry of Optimization and Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1705.03071/) (2017)
- [The loss landscape of overparameterized neural networks](https://mlsanity.com/paper/1804.10200/) (2018)
- [Hold me tight! Influence of discriminative features on deep network boundaries](https://mlsanity.com/paper/2002.06349/) (2020)

## Built on by (most cited first, 10 of 10)

- [Asymmetric Certified Robustness via Feature-Convex Neural Networks](https://mlsanity.com/paper/2302.01961/) (2023)
- [Generating Adversarial Attacks in the Latent Space](https://mlsanity.com/paper/2304.04386/) (2023)
- [MANO: Exploiting Matrix Norm for Unsupervised Accuracy Estimation Under Distribution Shifts](https://mlsanity.com/paper/2405.18979/) (2024)
- [Decision boundaries and convex hulls in the feature space that deep learning functions learn from images](https://mlsanity.com/paper/2202.04052/) (2022)
- [Quantile-constrained Wasserstein projections for robust interpretability of numerical and machine learning models](https://mlsanity.com/paper/2209.11539/) (2022)
- [A Sketching Method for Finding the Closest Point on a Convex Hull](https://mlsanity.com/paper/2102.10502/) (2021)
- [Possibility for Proactive Anomaly Detection](https://mlsanity.com/paper/2504.11623/) (2025)
- [Over-parameterization: A Necessary Condition for Models that Extrapolate](https://mlsanity.com/paper/2203.10447/) (2022)
- [An Ambiguity Measure for Recognizing the Unknowns in Deep Learning](https://mlsanity.com/paper/2312.06077/) (2023)
- [Dual feature-based and example-based explanation methods](https://mlsanity.com/paper/2401.16294/) (2024)

## Abstract (arXiv)

We study the generalization of deep learning models in relation to the convex hull of their training sets. A trained image classifier basically partitions its domain via decision boundaries and assigns a class to each of those partitions. The location of decision boundaries inside the convex hull of training set can be investigated in relation to the training samples. However, our analysis shows that in standard image classification datasets, all testing images are considerably outside that convex hull, in the pixel space, in the wavelet space, and in the internal representations learned by deep networks. Therefore, the performance of a trained model partially depends on how its decision boundaries are extended outside the convex hull of its training data. From this perspective which is not studied before, over-parameterization of deep learning models may be considered a necessity for shaping the extension of decision boundaries. At the same time, over-parameterization should be accompanied by a specific training regime, in order to yield a model that not only fits the training set, but also its decision boundaries extend desirably outside the convex hull. To illustrate this, we investigate the decision boundaries of a neural network, with various degrees of parameters, inside and outside the convex hull of its training set. Moreover, we use a polynomial decision boundary to study the necessity of over-parameterization and the influence of training regime in shaping its extensions outside the convex hull of training set.