We show that the margin distribution --- normalized by a spectral complexity parameter --- is strongly predictive of neural network generalization performance. Namely, we 1) Use the margin distribution to correctly predict whether deep neural networks generalize under changes to label distribution such as randomization. That is, the margin distribution accurately predicts the difficulty of deep learning tasks. We further show that normalizing the margin by the network's spectral complexity is critical to obtaining this predictive power, and finally use the margin distribution to compare the generalization performance of multiple networks across different datasets on even terms. Our corresponding generalization bound places these results on rigorous theoretical footing.