PaperlayerView exact revision on arXiv

Source-linked AI summary

Fantastic Generalization Measures and Where to Find Them

Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, Samy Bengio

arXiv:1912.02178v1cs.LGstat.ML

TL;DR

The paper addresses whether complexity measures reliably predict deep-network generalization beyond the small model sets used in much prior work. It evaluates more than 40 measures across over 10,000 convolutional networks with systematically varied training conditions and controlled analyses. Sharpness- and optimization-related measures emerge as promising, while several norm-based measures show surprising failures.

  • Problem

    Prior evaluations of complexity measures often used only a few models, leaving their reliability across broader settings uncertain.

  • Method

    The study trains over 10,000 networks while varying hyperparameters and uses controlled analyses to distinguish potentially causal relationships from spurious correlations.

  • Results

    Sharpness-based and optimization-related measures perform promisingly, whereas many norm-based measures perform poorly and can negatively correlate with generalization under stochastic optimization.

  • Takeaways & Limitations

    Sharpness-based and optimization-based complexity measures warrant further investigation as predictors of the generalization gap.

  • Takeaways & Limitations

    Directly optimizing a complexity measure can confound evaluation because it may alter the loss landscape or interact with implicit optimization regularization.

Abstract

from arXiv · show

Generalization of deep networks has been of great interest in recent years, resulting in a number of theoretically and empirically motivated complexity measures. However, most papers proposing such measures study only a small set of models, leaving open the question of whether the conclusion drawn from those experiments would remain valid in other settings. We present the first large scale study of generalization in deep networks. We investigate more then 40 complexity measures taken from both theoretical bounds and empirical studies. We train over 10,000 convolutional networks by systematically varying commonly used hyperparameters. Hoping to uncover potentially causal relationships between each measure and generalization, we analyze carefully controlled experiments and show surprising failures of some measures as well as promising measures for further research.

1 Introduction

This study evaluates more than 40 complexity measures across over 10,000 convolutional networks to assess how reliably they predict generalization. It finds promising performance from sharpness- and optimization-related measures, alongside failures of several norm-based measures and risks of spurious correlations.

  • Complexity measures quantify properties of the model, optimizer, or training data and are intended to relate monotonically to the generalization gap without using validation data.The study considers both theoretically and empirically motivated measures.
  • Over 10,000 models were trained across CIFAR-10 and SVHN while varying hyperparameters, optimization algorithms, and stopping criteria.The controlled design aimed to produce a wide range of generalization behaviors.
  • Some measures can exhibit high correlation with generalization through spurious relationships rather than causal insights, motivating more controlled evaluation procedures.The authors specifically propose a rigorous approach to mitigate this problem.
  • Many norm-based measures perform poorly and can negatively correlate with generalization when stochasticity enters the optimization procedure.The product-of-spectral-norms bound has a particularly strong negative correlation with generalization.
  • Sharpness-based measures, including PAC-Bayesian bounds and the sharpness measure of Keskar et al., perform best overall and appear promising for further research.The study also reports that optimization-related measures such as gradient noise and optimization speed can predict generalization.
  • The study compares a broader range of measures and models than prior large-scale work while using controlled experiments to reduce undesired artificial correlations.Its findings are intended to motivate further study of sharpness-based and optimization-based measures.

2 Generalization: What is the goal and how to evaluate?

The paper evaluates complexity measures as predictors of generalization while recognizing that correlation, regularization, and existing bounds may not establish causality. It uses controlled hyperparameter variation and a granulated ranking measure to reduce spurious correlations.

  • Existing generalization bounds are often vacuous on current deep-learning tasks, limiting their evidential value for causal relationships.
  • Regularizing a complexity measure can confound evaluation because it may alter optimization difficulty or duplicate implicit regularization from the optimizer.
  • Correlation-based evaluation can mislead when architectures, optimization algorithms, datasets, or only a few hyperparameters generate artificial associations.
  • The study uses controlled experiments over sufficiently trained models with broad hyperparameter variation to capture causal effects as much as possible.
  • Kendall’s τ measures ranking consistency between complexity and generalization, but a high value can arise without the measure capturing the cause of generalization.
  • The granulated Ψ averages within-hyperparameter ranking consistency across the remaining hyperparameter combinations, rewarding measures that perform reliably across hyperparameter changes.
  • A thought experiment gives a depth-sensitive measure overall τ = 0.362 but Ψ = 0.11, illustrating why Ψ can reject narrow ranking success.
  • The proposed measure is only a small step toward capturing causal relationships between complexity measures and generalization empirically.

3 Generating a Family of Trained Models

The study constructs a large, varied family of trained convolutional models by combining hyperparameter choices and optimization settings. Most models fit the training data while retaining a wide range of generalization gaps for evaluating complexity measures.

  • 7 hyperparameter types with 3 choices each produce 2187 CIFAR-10 models, while repeated and SVHN experiments bring the total above 10,000.
  • Models are trained to cross-entropy 0.01, and models failing to reach this threshold are discarded.
  • The tested hyperparameters span weight decay, layer width, batch size, learning rate, dropout, and architectural depth.
  • Figure 2 summarizes training accuracy, training cross-entropy, and the generalization-gap distribution across the model pool.
  • All models exceed 0.99 training accuracy while exhibiting a wide range of generalization gaps, creating a suitable testbed for complexity measures.

4 Performance of Complexity Measures

The study evaluates complexity measures across controlled hyperparameter changes, finding that predictive performance varies substantially across measure families. Sharpness-based measures are promising, while several norm-based measures fail or correlate in the opposite direction from expected.

  • Baselines and complexity measures: The study compares baseline, VC-, norm-, margin-, sharpness-, and optimization-based measures using ranking correlation and mutual information across hyperparameter changes.The baselines include an oracle ranking based on noisy generalization gaps and canonical hyperparameter orderings.
  • Norm- and margin-based measures: Spectral complexity is strongly negatively correlated with generalization across every hyperparameter type.Changing the reference from initialization to the origin improves both τ and Ψ, but the correlations remain negative.
  • Norm- and margin-based measures: Path norm is positively correlated with generalization across all hyperparameter types, achieving τ = 0.373 and Ψ = 0.311.The path norm is a norm in function space rather than parameter space.
  • Norm- and margin-based measures: The Fisher-Rao metric performs worse than path norm, with τ = −0.553 for depth and overall τ = 0.078 despite Ψ = 0.154.Its positive mutual-information score but near-chance ranking correlation suggests sensitivity to individual hyperparameter changes without capturing their interactions.
  • Norm- and margin-based measures: Increasing dropout probability makes proper norms negatively correlated with generalization changes, despite dropout usually reducing the generalization gap.This suggests dropout may contribute to growth in these norms, contrary to the usual capacity-based interpretation of larger norms.
  • Sharpness-based measures: Worst-case sharpness bounds outperform PAC-Bayes bounds in both τ and Ψ, and 1/α′ has the highest mutual information with generalization among all hyperparameters and overall.The bounds use parameter perturbations selected to keep perturbed training error at most 0.1; the worst-case version searches for the most loss-changing direction.
  • Optimization-based measures: The initial optimization phase and final gradient-variance measures provide promising optimization-based predictors of generalization.Initial optimization difficulty is negatively correlated with optimization speed, while final gradient variance is positively correlated across every hyperparameter type.

5 Conclusion

The study conducts large-scale correlation experiments and proposes a framework to distinguish causal from spurious relationships in generalization measures. It finds PAC-Bayesian bounds effective and identifies them as a promising direction, while acknowledging important scope limitations.

  • The experiments test correlations between diverse complexity measures and deep-model generalization at large scale.The study also proposes a framework intended to better disentangle causal from spurious correlation.
  • PAC-Bayesian bounds are confirmed as effective and presented as a promising direction for understanding generalization.
  • The study is limited to seven common hyperparameter types, relatively small architectures, two image-classification datasets, convolutional networks, and classification models.The authors state that these settings do not reflect production models.
  • The authors suggest that future studies should examine more hyperparameters and broader model and dataset settings.

A.1 More training details

The training procedure uses batch normalization throughout and removes it before computing complexity measures. Stopping criteria are treated as essential because they can change both evaluations and conclusions about measure predictiveness.

  • Batch normalization is used in every model because it is crucial for reliably reaching low cross-entropy values.Before measuring complexity, the authors fuse normalization parameters and statistics into the preceding convolution.
  • Batch normalization is removed before measure computation to avoid re-parameterization effects on measures such as sharpness.
  • Stopping criteria can completely change evaluation and resulting conclusions about generalization measures.
  • Iteration- or epoch-based stopping can make cross-entropy highly predictive because models optimize at different speeds and fit training data differently.

A.3 All Model Specification

The models are Network-in-Network-like convolutional architectures assembled by stacking NiN-blocks. Width, depth, dropout, batch size, and optimizer-specific training hyperparameters are systematically varied.

  • The architecture uses NiN-blocks, each containing one stride-2 3 × 3 convolution followed by two stride-1 1 × 1 convolutions.
  • Model size is varied by stacking different numbers of NiN-blocks, while width uses 2 × 96, 4 × 96, or 8 × 96 output channels.
  • Dropout is selected from 0.0, 0.25, and 0.5, and batch size from 32, 64, and 128.
  • Learning rates and regularization coefficients are tuned separately for each optimizer while retaining three choices for each hyperparameter.Adaptive methods can also benefit from tuning initial learning rate and learning-rate decay.
  • Momentum SGD uses momentum 0.9, Adam uses ϵ = 1e-3, and all listed optimizers apply ×0.1 learning-rate decay at iterations 60000 and 90000.

A.4 Canonical Measures

The canonical ordering encodes community expectations about how seven hyperparameter categories relate to generalization gap. These expectations cover batch size, architecture, regularization, learning rate, and optimizer choice.

  • Batchsize: Smaller batch sizes are expected to produce smaller generalization gaps.
  • Depth: Deeper networks are expected to produce smaller generalization gaps.
  • Width: Wider networks are expected to produce smaller generalization gaps.
  • Dropout: Higher dropout rates up to 0.5 are expected to produce smaller generalization gaps.
  • Weight decay and learning rate: Higher allowed weight decay and learning rates are expected to produce smaller generalization gaps.
  • Optimizer: The expected optimizer ordering is Momentum SGD < Adam < RMSProp for generalization gap.

A.5 Definition of Random Variables

The study defines conditional joint and marginal probabilities for comparing generalization gaps and complexity measures across model pairs under fixed hyperparameter conditions.

  • Definition of Random Variables: For a subset S of hyperparameters, S_ab denotes the collective condition formed by the corresponding components of θ for models a and b.Examples include conditioning on no hyperparameters, learning rate, or learning rate together with dropout.
  • Definition of Random Variables: Each S_ab condition yields a 2 by 2 joint distribution over whether model a exceeds model b in generalization gap and complexity measure.The compared events are Pr(g(a) > g(b) | S_ab) and Pr(μ(a) > μ(b) | S_ab).
  • Definition of Random Variables: The notation Pr(μ, g | S_ab), Pr(g | S_ab), and Pr(μ | S_ab) denotes the joint and marginal conditional probabilities.
  • Definition of Random Variables: With N = 3 choices for each hyperparameter in S, the procedure produces N^|S| tables for each hyperparameter combination.Because configurations occur with equal probability, the aggregate quantities can be computed over model pairs.

A.6 All Results

The experiments evaluate complexity measures across extensive model configurations, datasets, training criteria, and hyperparameter settings, with results organized through rank correlations, mutual information, and variability analyses.

  • Reported analyses: Table 5 reports rank-correlation coefficients between complexity measures and hyperparameters for models trained on CIFAR-10.
  • Reported analyses: Table 6 reports mutual information between complexity measures and hyperparameters for models trained on CIFAR-10.
  • Reported analyses: Table 7 reports rank-correlation coefficients for models trained on SVHN, while Table 8 reports CIFAR-10 correlations at convergence to loss 0.1.
  • Reported analyses: The standard deviations in Table 10 are small across five CIFAR-10 runs, suggesting the Table 5 results are statistically significant.

C Complexity Measures

The paper evaluates theoretical and empirical complexity measures, including VC-dimension-based quantities, against generalization using high-probability bounds and correlation analyses.

  • Complexity measures: Complexity measures are evaluated either as generalization-bound quantities with probability 0.99 or as measures without provable error bounds.
  • Results: Canonical hyperparameter orderings are generally positively correlated with generalization under both τ and Ψ, but optimizer correlation τ is close to zero.The authors interpret this ordering as validating several techniques used by practitioners within the studied model range.
  • VC-dimension-based measures: The VC-dimension analysis restates a theorem for piecewise-linear networks and extends it to convolutional networks with pooling and ReLU activations.The extension bounds the equivalent depth by d′ ≤ 9d log_2(n) and accounts for activations and parameters.
  • VC-dimension-based measures: The resulting VC-based measure is motivated by a generalization bound, while a parameter-count measure is also introduced to avoid dependencies viewed as possible proof artifacts.

C.1.1 Measures on the output of the network

The paper defines output-based, margin, entropy, norm, path, Fisher-Rao, and PAC-Bayesian measures to assess how model properties and perturbation behavior relate to generalization.

  • Measures on the output of the network: Output-based measures use only network outputs, including final cross-entropy, training margins, and negative output entropy.The margin is set to the 10th percentile of training margins, ensuring training margin loss is at most 0.1.
  • Measures on the output of the network: With fixed cross-entropy, increasing output entropy distributes prediction uncertainty more equally among incorrect labels and connects to label smoothing and larger margins.
  • Norm-based measures: The paper evaluates norm-based measures built from products or rebalanced sums of spectral and Frobenius norms, including convolutional-network spectral bounds.
  • Other complexity measures: Additional measures quantify distance from initialization or the origin, path norm, and Fisher-Rao norm.Path norm is computed by squaring parameters, forwarding an all-ones input, and taking the square root of the summed outputs.
  • PAC-Bayesian measures: PAC-Bayesian measures assess expected or worst-case flatness through Gaussian perturbations, KL divergence, and perturbation scales selected to keep perturbed loss at most 0.1.
Loading 1912.02178v1…