Source-linked AI summary
Exploring Generalization in Deep Learning
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, Nathan Srebro
TL;DR
The paper asks what drives generalization in deep networks, where overparameterization and training error alone provide limited explanations. It studies norms, robustness, and sharpness through theoretical guarantees and empirical tests, finding that scale-aware combinations—especially norms with expected sharpness—best capture the observed behavior, while important optimization questions remain unresolved.
Problem
The paper addresses why overparameterized deep networks can generalize well and what complexity measure explains generalization when parameter count and training error are insufficient.
Method
The paper evaluates norms, robustness, and sharpness through generalization analyses and experiments spanning scale normalization, margins, PAC-Bayes bounds, and observed training phenomena.
Results
Expected sharpness combined with norms appears to capture much of neural-network generalization, whereas sharpness alone is insufficient because it depends on parameter scale.
Takeaways & Limitations
Meaningful complexity comparisons require accounting for network output scale, and no single complexity measure clearly explains all observed generalization behavior.
Takeaways & Limitations
Sharpness alone does not control capacity, and the precise way optimization biases complexity toward low values remains unresolved.
Abstract
from arXiv · showhide
With a goal of understanding what drives generalization in deep networks, we consider several recently suggested explanations, including norm-based control, sharpness and robustness. We study how these measures can ensure generalization, highlighting the importance of scale normalization, and making a connection between sharpness and PAC-Bayes theory. We then investigate how well the measures explain different observed phenomena.
1 Introduction
Deep networks can generalize well despite overparameterization, but training error and parameter count alone do not explain why. The paper evaluates complexity measures by whether they guarantee generalization and account for observed behavior, emphasizing scale-aware norms, sharpness, and related mechanisms.
- Overparameterized networks can achieve low training error and still generalize well, despite having more parameters than training examples.
- Different global minima can have different generalization quality, so optimization choices may implicitly bias which solution is learned.
- A useful complexity measure should both ensure generalization theoretically and assign low complexity to networks learned in practice.
- Observed phenomena requiring explanation include random-label fitting, improved generalization with more hidden units, and differing generalization among zero-training-error solutions.
- The paper investigates norms, robustness, and sharpness, stressing that norm-based control must relate parameter scale to output scale, such as through margins.
- For ReLU networks, activation-pattern matrices depend on inputs and preceding parameters, providing the notation used to represent the network's piecewise-linear computation.
2 Generalization and Capacity Control in Deep Learning
The paper evaluates complexity measures for deep networks by asking whether they both guarantee generalization and track the low-complexity structure of models learned in practice. It argues that scale normalization is essential: norms should be related to margins, and sharpness should be combined with norm through PAC-Bayes analysis.
- Capacity control: A useful complexity measure must ensure generalization for restricted hypothesis classes while assigning low complexity to networks learned in practice.The paper evaluates candidate measures by analyzing the capacity of classes restricted by a complexity threshold.
- Network size: Parameter-count complexity is too weak in over-parameterized networks, which can fit random labels and may generalize better as hidden units increase.Thus, the number of parameters cannot explain several observed generalization phenomena.
- Norms and margins: Norm-based capacity control requires accounting for output scale because zero-one loss is invariant to output scaling; margins provide one such normalization.Without scale normalization, rescaling weights can make the norm arbitrarily small without changing classification loss.
- Norms and margins: The robust margin used in the empirical analysis permits a small fraction of training points to violate the margin, reducing sensitivity to outliers and dataset size.The qualitative results were reported as stable for reasonable ϵ values between 0.001 and 0.1.
- Lipschitz continuity and robustness: Bounding the network’s Lipschitz constant alone does not provide reasonable capacity control because the resulting bound can grow exponentially with input dimension and depth.This shows that the earlier norm-based bounds are not merely consequences of Lipschitz control.
- Sharpness: Sharpness by itself is scale-dependent and insufficient for capacity control, whereas PAC-Bayes combines expected sharpness with a norm or KL term.The balance between sharpness and norm depends on the perturbation scale σ; bi-criteria plots better capture the difference between true- and random-label networks.
3 Empirical Investigation
The experiments test whether complexity measures distinguish generalization across global minima and network sizes. The results show that some measures track observed behavior only over limited ranges, while others fail to explain it fully.
- Different global minima with zero training error are created by adding varying amounts of randomly labeled CIFAR10 data to a fixed 10,000-example set.Test error increases as the size of the random-label set increases.
- Increasing hidden units in the MNIST perceptron lowers test error even though 32 units already suffice to fit the training data.The experiment uses a fully connected feedforward network trained without explicit regularization.
- Figure 3 compares training and test errors, changes in complexity measures, and expected sharpness against PAC-Bayes KL across these global minima.
- Complexity measures generally decrease through 128 hidden units, but ℓ2-path norm and the joint PAC-Bayes measure do not explain improved generalization for larger networks.Accounting for hidden-unit dependence also prevents ℓ2-path norm from explaining the phenomenon, while the joint PAC-Bayes measure fails beyond size 128.
- The experiments therefore indicate that the examined measures can explain some generalization patterns but are not sufficient across all network-size regimes.
4 Bounding Sharpness
The paper derives sufficient conditions for bounding expected sharpness in ReLU networks and connects the resulting bound to generalization through PAC-Bayes. The conditions control layer interactions, activation-pattern sensitivity, and weight-norm balance, avoiding exponential depth dependence.
- Bounding sharpness: The sharpness-based generalization bound for ReLU networks does not suffer from exponential dependence on depth.The bound is established under sufficient conditions on the network and its perturbation response.
- Conditions on sharpness: Weak interactions between successive layers can produce high sharpness, while C1 prevents these cancellation effects.C1 controls the perturbation error when activations remain unchanged.
- Conditions on sharpness: C2 and C3 control activation-pattern sensitivity, preventing extreme changes in active-node counts and imbalances in incoming-weight norms.These conditions bound the perturbation error caused by changes in activations.
- PAC-Bayes bound: The PAC-Bayes bound balances expected sharpness against a weight-norm term through the perturbation scale σ.Larger σ increases expected sharpness but decreases the norm term, allowing optimization over σ.
- PAC-Bayes bound: For reasonable σ, the generalization error depends linearly on depth and worsens as μ decreases or C2 and C3 increase.The latter changes correspond to increasing network sharpness under the stated conditions.
- Empirical verification: The authors report that the conditions hold for networks trained in practice, with experiments suggesting μ ≥1/4, C2 ≤5, and C3 ≤3.Figure 5 verifies the conditions on a 10-layer perceptron with more than 10,000,000 parameters on MNIST.
5 Conclusion
The paper finds that no single complexity measure clearly explains generalization in deep networks. Expected sharpness combined with norms appears to capture much of the observed behavior, while the optimization bias behind low complexity remains unresolved.
- Conclusion: No clear single complexity measure explains generalization, but combinations of expected sharpness and norms capture much of the observed behavior.The conclusion summarizes the paper’s comparison of candidate measures across neural-network phenomena.
- Open questions: The precise relationship between optimization and implicit regularization, including how optimization biases complexity to be low, remains unresolved.This is identified as a major open issue.
A Experiments Settings
The experiments evaluate network size, norms, sharpness, and expected sharpness under specified architectures and optimization settings. Norms are scale-adjusted using margins, while sharpness measures are estimated through perturbation procedures.
- Architectures: Network-size experiments train two-layer ReLU perceptrons with varying hidden units, while other experiments use a modified VGG architecture with batch normalization, pooling, and dropout.The VGG configuration uses repeated convolutional stacks with 64, 128, 256, and 512 channels.
- Optimization: All experiments use SGD with mini-batches of 64, learning rate 0.01, momentum 0.9, and no weight decay.Training continues until cross-entropy loss is below 10^-4 when zero training error is achievable.
- Normalization: Batch-normalized networks are reparameterized to preserve the same function, and plotted norms are divided by the fifth-percentile training margin.This normalization is used to avoid scaling issues.
- Sharpness estimation: Sharpness is estimated by maximizing loss with 2000 stochastic gradient-ascent updates under perturbations bounded by α(|wi| + 1), with α = 5.10^-4.The ascent uses mini-batches of 64, step size 0.01, and momentum 0.9.
- Expected sharpness: Expected sharpness averages losses over 1000 Gaussian perturbations, with perturbation standard deviation α(10 |wi| + 1).Each perturbation is averaged over a mini-batch of size 64 and evaluated for different α values.
B.1 Proof of Lemma 1
The proof decomposes the effect of multi-layer perturbations into terms involving progressively larger sets of noisy layers. It establishes the base case for one noisy layer before applying an induction step.
- Proof setup: The proof defines gw,ν,s(x) as the network with weights replaced by perturbations νi in every layer i belonging to s.This notation isolates perturbations affecting selected layers.
- Inductive proof: The base case bounds terms with one noisy layer before the proof proceeds to terms with k + 1 noisy layers.The induction hypothesis applies to any set s ⊂[d] with |s| = k.
- Inductive proof: The proof substitutes the resulting inductive expression into equation (10) to obtain the final bound.The cited proof steps connect the single-layer base case and induction step to the decomposition.
B.2 Proof of Lemma 2
The proof proceeds inductively, bounding perturbation-induced activation changes and propagated errors layer by layer. It uses Gaussian perturbation bounds, decomposition into replacement terms, and scale relationships involving network outputs and layer norms.
- The proof controls perturbed activation-pattern differences through bounds on bDk − Dk and related indicator variables.
- Gaussian perturbations are bounded using norm constraints on inputs and high-probability concentration statements.
- The argument also evaluates the k = 2 case because the k = 1 case does not capture higher-layer dependencies.
- For perturbation scales σi = O(σ), the leading contribution scales as O(σ), while two remaining terms decay at least as O(σ^3/2).
- The propagated error is expanded into terms involving changes in activation patterns, weight matrices, and perturbation matrices, then each term is bounded separately.
- The lemma is proved by induction on the network depth, establishing the claim for k + 1 from the assumption for all i ≤ k.
C Supporting results
The supporting results establish auxiliary bounds for Gaussian matrix perturbations and visualize condition-number-related quantities across random and learned networks. These results support the analysis of the theorem’s structural conditions.
- Lemma 3 considers matrices A and B with an entrywise Gaussian perturbation matrix ν and provides a bound for the resulting expression.
- The supporting figure decomposes the parameter μ into cases based on the relation among a, c, and b − 1.
- Figure 6 reports Condition C1 through a condition number, with C1 defined as condition number 1.
- Jensen’s inequality is used in the supporting derivation.
D Conditions in Theorem 1
The experiments compare theorem conditions for a 10-layer, 1000-unit-per-layer network at random initialization and after MNIST training. Learned weights are reported as very similar to random initialization on these conditions.
- A 10-layer feedforward network with 1000 hidden units per layer is trained on MNIST for the comparison.
- Figures 6, 7, and 8 compare Conditions C1, C2, and C3 between learned weights and random initialization.
- The learned network is reported to be very similar to its random initialization in terms of these conditions.
- Figure 7 measures the ratio of activations that flip as perturbation magnitude changes, separately for random initialization and learned weights.
- Figure 8 presents Condition C3 and output values for random and learned networks.