Abstract
Margin enlargement over training data has been an important strategy sinceperceptrons in machine learning for the purpose of boosting the robustness ofclassifiers toward a good generalization ability. Yet Breiman shows a dilemma(Breiman, 1999) that a uniform improvement on margin distribution \emph{doesnot} necessarily reduces generalization errors. In this paper, we revisitBreiman's dilemma in deep neural networks with recently proposed spectrallynormalized margins. A novel perspective is provided to explain Breiman'sdilemma based on phase transitions in dynamics of normalized margindistributions, that reflects the trade-off between expressive power of modelsand complexity of data. When data complexity is comparable to the modelexpressiveness in the sense that both training and test data share similarphase transitions in normalized margin dynamics, two efficient ways are derivedto predict the trend of generalization or test error via classic margin-basedgeneralization bounds with restricted Rademacher complexities. On the otherhand, over-expressive models that exhibit uniform improvements on trainingmargins, as a distinct phase transition to test margin dynamics, may lose sucha prediction power and fail to prevent the overfitting. Experiments areconducted to show the validity of the proposed method with some basicconvolutional networks, AlexNet, VGG-16, and ResNet-18, on several datasetsincluding Cifar10/100 and mini-ImageNet.