TL;DR
Deep neural networks can generalize surprisingly well even when massively overparameterized. This paper proposes that the "effective capacity" of a network isn't just about its architecture or data, but crucially depends on its random initialization. They show that SGD implicitly regularizes the distance of the learned parameters from their initial values, which might be key to understanding generalization.
What Problem Does This Paper Address?
The deep learning community has been grappling with a puzzling observation: overparameterized neural networks, which theoretically should be prone to overfitting, can still achieve low test errors. This challenges traditional machine learning wisdom about the trade-off between model expressivity and generalization. While the training algorithm (like SGD) and data distribution are known to play a role, this paper focuses on a less explored factor: the random initialization of the network's weights. The authors aim to understand if and how the initial state of the network influences its ability to generalize, particularly in the context of SGD.
Methods
The core idea is to define and analyze an "effective model capacity" that is tied to a specific random initialization. Instead of looking at global norms of the weights (like the L2 norm from the origin), they focus on the L2 distance between the final learned weights and the initial weights.
- Empirical Analysis: They conduct experiments on MNIST and CIFAR-10 datasets, training networks of varying widths and sample sizes. They measure how the distance from initialization changes with these factors and with label noise.
- Theoretical Arguments: They develop theoretical arguments, particularly for linear networks, to show that the Rademacher complexity (a measure of model capacity) can be bounded by this distance from initialization. They also analyze why traditional norm-based bounds might fall short.
Datasets
- MNIST: Used for experiments with both real and noisy labels.
- CIFAR-10: Used for experiments with real data.
Key Insights and Ideas
- Initialization Matters: The paper strongly advocates for considering the random initialization as a fundamental component of a network's "effective capacity." This moves beyond solely focusing on architecture or data.
- Implicit Regularization of Distance: SGD appears to implicitly regularize the L2 distance between the learned weights and the initial weights. This distance tends to stabilize to a width-independent value.
- Distance vs. Norms: Traditional L2 or spectral norm regularization (from the origin) might not fully capture generalization because they don't account for the starting point. The distance from initialization seems to be a more relevant quantity.
- Noise and Distance: Increasing label noise requires the network to travel a larger distance from initialization to achieve memorization, suggesting a connection between noise robustness and this distance metric.
Key Results
- Width-Independent Distance: For real and corrupted data, the distance from initialization remains largely constant or even decreases with increasing network width (H).
- Sample Size Dependence: This distance does grow with the training set size (m), typically at rates between m^0.25 to m^0.4.
- Noise Impact: With noisy labels, the distance from initialization increases, and this effect is more pronounced with larger sample sizes.
- Linear Network Analysis: For linear networks, they prove an H-independent bound on the Rademacher complexity for hypotheses within a fixed distance 'r' from initialization.
Limitations and Future Work
- "How and Why": The paper leaves open the fundamental questions of how and why SGD implicitly regularizes the distance from initialization.
- Sufficiency for Generalization: It's still an open question whether this distance regularization is sufficient on its own to fully explain generalization in deep networks, especially for non-linear networks.
- Theoretical Extension: Extending the H-independent bounds from linear to non-linear networks remains a key future direction.
- Subspace Hypothesis: They pose the question of whether solutions found by SGD lie within a smaller subspace inside an H-independent radius around the initialization.
Summary updated