For Valid Generalization the Size of the Weights is More Important than the Size of the Network

Peter L. BartlettNeurIPS 1996 · OpenReview

Introduction: The Parameter Paradox

In the mid-90s, statistical learning theory relied heavily on the Vapnik-Chervonenkis (VC) dimension to predict model generalization. The prevailing rule of thumb was straightforward: to avoid catastrophic overfitting, the number of training examples needed to vastly exceed the number of parameters in a model.

However, researchers observed a persistent paradox in neural networks. Models with massive numbers of weights often generalized remarkably well, even when trained on relatively small datasets. Traditional VC-bounds were too "loose" for these models, predicting severe overfitting that simply did not materialize in practice. Peter Bartlett's seminal paper bridges this gap between theory and reality, proving that the magnitude of the weights—rather than the sheer number of weights—is the critical predictor of generalization performance.

Theoretical Framework: Beyond VC-Dimension

To explain why large networks generalize well, Bartlett moves away from binary "correct/incorrect" classification metrics and introduces the fat-shattering dimension. Unlike VC-dimension, which asks if a model can represent any possible labeling of a set of points, the fat-shattering dimension is "scale-sensitive." It evaluates whether a model can represent those labelings with a specific margin (a gap of at least $\gamma$).

The paper's mathematical foundation relies on several key concepts:

  1. Covering Numbers: Utilizing $l_\infty$ and $l_2$ pseudometrics to bound how many "representative" functions are required to approximate the entire hypothesis class.
  2. $L_1$ Norm Constraints: Analyzing networks where the sum of the absolute values of the weights (the $L_1$ norm) at each node is bounded by a constant $A$.
  3. Maurey’s Lemma: A tool from functional analysis used to demonstrate that an element in the convex hull of a set of functions can be approximated by a sparse linear combination of those functions.

(Note: As a purely theoretical work focused on mathematical bounds, the paper does not rely on empirical datasets like MNIST or CIFAR, but rather provides sample complexity formulas applicable to any distribution on an input space.)

Key Results: Weight Size Over Network Size

The most profound insight of Bartlett's work is that the number of hidden units in a layer can theoretically be infinite without necessarily hurting generalization, provided the weights remain small.

  • Generalization Bounds: The paper establishes that misclassification probability is bounded by the proportion of training errors (with a margin) plus a complexity term that scales with the fat-shattering dimension.
  • Fat-Shattering Dimension of Deep Nets: For a depth-$l$ network with $L_1$ weight bounds $A$, the fat-shattering dimension is roughly $O(n \cdot A^{l(l+1)})$, where $n$ is the input dimension. Crucially, the number of hidden units per layer does not appear in this bound.
  • Rate of Convergence: The error estimate converges at a rate of approximately $O(1/\sqrt{m})$, where $m$ is the number of training patterns (ignoring logarithmic factors).

Practical Implications

Bartlett's theoretical framework provides rigorous justification for several common heuristics used by deep learning practitioners:

  • The "Linear Part" Intuition: The paper formalizes the idea that when weights are small, sigmoid activation units operate primarily in their "linear" region. In this state, a multi-layer network behaves more like a simple linear model, possessing much lower complexity than its raw parameter count suggests.
  • Theoretical Support for Regularization: The findings validate techniques like weight decay (which explicitly penalizes large weights) and early stopping (which halts training before weights can grow excessively large).
  • Margin Matters: Generalization is closely tied to how "distinctly correct" the training examples are. If a network classifies points with a large margin—meaning the output is far from the decision threshold—it is significantly more likely to generalize well to unseen data.

Limitations and Future Directions

While a massive leap forward from VC-dimension, the paper has a few limitations:

  • Pre-specified Margin: In the primary theorem, the margin parameter $\gamma$ must be specified in advance. While a data-dependent "uniform" version is possible, it is only briefly addressed.
  • Tightness of Bounds: Although these bounds are much tighter than VC-bounds, they can still be conservative compared to the actual empirical performance of modern deep learning models.
  • Specific Architectures: The analysis focuses strictly on feed-forward sigmoid networks. Extending these results to architectures that dominate modern machine learning, such as those using ReLU activations or Convolutional layers, is left as an avenue for future research.

Summary updated

Abstract

This paper shows that if a large neural network is used for a pattern classification problem, and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. More specifi(cid:173) cally, consider an i-layer feed-forward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A. The misclassification probability con(cid:173) verges to an error estimate (that is closely related to squared error on the training set) at rate O((cA)l(l+1)/2J(log n)jm) ignoring log factors, where m is the number of training patterns, n is the input dimension, and c is a constant. This may explain the gen(cid:173) eralization performance of neural networks, particularly when the number of training examples is considerably smaller than the num(cid:173) ber of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training.
BibTeX
@inproceedings{bartlett1996valid,
  author = {Peter L. Bartlett},
  title = {{For Valid Generalization the Size of the Weights is More Important than the Size of the Network}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
  url = {https://openreview.net/forum?id=BJZyX_WdWS},
}
Figure