Deep Learning Generalization and the Convex Hull of Training Sets

We study the generalization of deep learning models in relation to the convex hull of their training sets. Through an empirical analysis of machine learning benchmarks for image classification, we report that all testing samples are considerably outside the convex hull of their training sets, in the pixel space, in the wavelet space, and in the internal representations learned by deep networks. Therefore, the generalization of trained models depend on how they extrapolate outside the convex hull of their training data, i.e., how their decision boundaries extend outside the convex hull. From this perspective, which was not studied before, overparameterization of deep learning models is a necessary condition for shaping the extensions of decision boundaries outside their hull. At the same time, overparameterization should be accompanied by a specific training regime in order to yield a model that 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 overparameterization and the influence of training regime in shaping the decision boundaries outside the convex hull of training set. Our analysis suggests that deep learning models are largely extrapolation machines and over-parameterization is a necessary condition for their extrapolation capabilities, i.e., their generalization.