  We study the generalization of over-parameterized deep networks (for image
classification) in relation to the convex hull of their training sets. Despite
their great success, generalization of deep networks is considered a mystery.
These models have orders of magnitude more parameters than their training
samples, and they can achieve perfect accuracy on their training sets, even
when training images are randomly labeled, or the contents of images are
replaced with random noise. The training loss function of these models has
infinite number of near zero minimizers, where only a small subset of those
minimizers generalize well. Overall, it is not clear why models need to be
over-parameterized, why we should use a very specific training regime to train
them, and why their classifications are so susceptible to imperceivable
adversarial perturbations (phenomenon known as adversarial vulnerability)
\cite{papernot2016limitations,shafahi2018adversarial,tsipras2018robustness}.
Some recent studies have made advances in answering these questions, however,
they only consider interpolation. We show that interpolation is not adequate to
understand generalization of deep networks and we should broaden our
perspective.
