Rethinking Breiman's Dilemma in Neural Networks: Phase Transitions of Margin Dynamics

Weizhi Zhu, Yifei Huang, Yuan YaoFrontiers in Applied Mathematics and Statistics 2020 · DOI

TL;DR

This paper revisits Breiman's dilemma in deep neural networks, proposing that "phase transitions" in margin distributions during training can predict generalization error. When model complexity matches data complexity, training and test margins behave similarly, allowing for early stopping. However, when models are over-expressive, this predictability breaks down, leading to overfitting.

What Problem Does This Paper Address?

For decades, increasing the "margin" of a classifier (how confidently it classifies data points) has been a key strategy to improve generalization. However, Leo Breiman's 1999 work highlighted a "dilemma": simply making margins larger doesn't always lead to better generalization and can even cause overfitting. This is particularly relevant in deep learning, where models are often over-parameterized. The authors aim to understand why this dilemma occurs in deep neural networks and propose a way to predict generalization error by analyzing the dynamics of margin distributions during training.

Methods

The core of the paper's approach is to analyze the dynamics of normalized margin distributions throughout the training process. They divide the margin distribution into "low/small margins" (associated with misclassified samples) and "high/large margins" (associated with confidently classified samples).

Key techniques include:

  • Spectrally Normalized Margins: Using a recent technique to normalize network margins, which helps in bounding generalization error.
  • Phase Transitions: Identifying specific points in training where the behavior of margin distributions changes dramatically. They observe that when model expressiveness is balanced with data complexity, both training and test margins exhibit similar "decrease-increase" phase transitions.
  • Margin-Based Generalization Bounds: Developing theoretical bounds that relate training margin error to test error. They propose two such bounds: one based on normalized margin error and another using "quantile margins" (which adaptively select thresholds).
  • Rademacher Complexity: A theoretical tool used to bound generalization error, which they adapt to the context of normalized margins.

Datasets

The authors use standard benchmark datasets for their experiments:

  • CIFAR-10
  • CIFAR-100
  • Mini-ImageNet

They also introduce noise by randomly permuting a percentage of labels in these datasets to simulate challenging scenarios.

Key Insights and Ideas

  • Margin Dynamics, Not Just Magnitude: The key insight is that how the margin distribution changes during training (its dynamics) is more informative than just its final magnitude.
  • Phase Transitions as Predictors: The "decrease-increase" phase transition in high margin distributions for both training and test data is a strong indicator that the model's expressiveness is well-matched to the data complexity. This synchronization allows for predicting generalization error.
  • Breiman's Dilemma Explained: When a model is over-expressive, training margins (both low and high) improve uniformly, but test margins exhibit a different, often distinct, phase transition. This disconnect is the root of Breiman's dilemma, where training progress doesn't translate to better generalization.
  • Quantile Margins for Adaptability: The proposed "quantile margin" approach offers a more adaptive way to predict generalization error, as it can dynamically select thresholds based on the training progress, outperforming fixed thresholds.
  • Model vs. Data Complexity: The paper emphasizes that the relationship between model expressive power and data complexity is crucial, and this relationship can be observed through margin dynamics, not just by counting parameters.

Key Results

  • Predicting Overfitting: The proposed margin dynamics analysis, particularly using quantile margins, successfully predicts the onset of overfitting and allows for effective early stopping in scenarios where model and data complexity are balanced.
  • Failure Cases: In cases of over-expressive models (e.g., larger CNNs on simpler datasets), the training and test margin dynamics diverge, and the proposed methods fail to predict generalization error, demonstrating Breiman's dilemma.
  • Experimental Validation: The theoretical findings are supported by experiments on various CNN architectures (basic CNNs, AlexNet, VGG-16, ResNet-18) across different datasets.
  • Rank Correlation Analysis: Heatmaps showing Spearman's rank correlation coefficients between training and test margin errors confirm that synchronized phase transitions lead to high correlations, while divergent transitions lead to low correlations.

Limitations and Future Work

  • Normalization Factor Estimation: The paper discusses the impact of different methods for estimating normalization factors (e.g., l1-based vs. power iteration) on the range of predictability, suggesting that more accurate estimates might extend predictability but don't fundamentally resolve Breiman's dilemma when model complexity becomes too high.
  • Data-Driven Early Stopping: The authors suggest future work on designing more sophisticated data-driven early stopping rules by monitoring margin dynamics.
  • Degree-of-Freedom Measurement: Further research is proposed to study the "degree-of-freedom" of models by monitoring margin dynamics, which could offer a more nuanced understanding of model complexity relative to data.

Summary updated

Abstract

Margin enlargement over training data has been an important strategy since perceptrons in machine learning for the purpose of boosting the confidence of training toward a good generalization ability. Yet Breiman (1999) shows a dilemma that a uniform improvement on margin distribution does not necessarily reduces generalization errors. In this paper, we revisit Breiman's dilemma in deep neural networks with recently proposed spectrally normalized margins, from a novel perspective based on phase transitions of normalized margin distributions in training dynamics. Normalized margin distribution of a classifier over the data, can be divided into two parts: low/small margins such as some negative margins for misclassified samples vs. high/large margins for high confident correctly classified samples, that often behave differently during the training process. Low margins for training and test datasets are often effectively reduced in training, along with reductions of training and test errors; while high margins may exhibit different dynamics, reflecting the trade-off between expressive power of models and complexity of data. When data complexity is comparable to the model expressiveness, high margin distributions for both training and test data undergo similar decrease-increase phase transitions during training. In such cases, one can predict the trend of generalization or test error by margin-based generalization bounds with restricted Rademacher complexities, shown in two ways in this paper with early stopping time exploiting such phase transitions. On the other hand, over-expressive models may have both low and high training margins undergoing uniform improvements, with a distinct phase transition in test margin dynamics. This reconfirms the Breiman's dilemma associated with overparameterized neural networks where margins fail to predict overfitting. Experiments are conducted with some basic convolutional networks, AlexNet, VGG-16, and ResNet-18, on several datasets including Cifar10/100 and mini-ImageNet.
BibTeX
@inproceedings{zhu2020rethinking,
  author = {Weizhi Zhu and Yifei Huang and Yuan Yao},
  title = {{Rethinking Breiman's Dilemma in Neural Networks: Phase Transitions of Margin Dynamics}},
  booktitle = {Frontiers in Applied Mathematics and Statistics},
  year = {2020},
  doi = {10.3389/fams.2020.575073},
}
Figure