Source-linked AI summary
Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, Nathan Srebro
TL;DR
The paper addresses why existing complexity measures do not explain improved generalization with over-parametrization. It proposes unit-wise capacity bounds for two-layer ReLU networks, finding that the bound decreases with hidden-unit count and potentially tracks test-error behavior, while also providing an improved matching Rademacher lower bound.
Problem
Existing parameter-count, norm, margin, and sharpness measures do not explain why increasing hidden units can improve neural-network generalization.
Method
The paper introduces a unit-wise capacity measure and derives tighter generalization bounds for two-layer ReLU networks.
Results
The proposed capacity bound decreases with hidden-unit count and is the only compared bound that continues decreasing for networks with about 100 million parameters on CIFAR-10 and SVHN.
Takeaways & Limitations
Unit-level capacity measures could potentially explain why larger over-parametrized networks generalize better, and the paper supplies a stronger matching Rademacher-complexity lower bound.
Takeaways & Limitations
The results are limited to two-layer networks, and the absolute bounds remain much larger than the number of training samples.
Abstract
from arXiv · showhide
Despite existing work on ensuring generalization of neural networks in terms of scale sensitive complexity measures, such as norms, margin and sharpness, these complexity measures do not offer an explanation of why neural networks generalize better with over-parametrization. In this work we suggest a novel complexity measure based on unit-wise capacities resulting in a tighter generalization bound for two layer ReLU networks. Our capacity bound correlates with the behavior of test error with increasing network sizes, and could potentially explain the improvement in generalization with over-parametrization. We further present a matching lower bound for the Rademacher complexity that improves over previous capacity lower bounds for neural networks.
1 Introduction
The introduction asks why over-parametrized neural networks can generalize better despite fitting training data, and proposes unit-wise capacity measures to explain this behavior. The paper develops tighter bounds for two-layer ReLU networks and reports empirical evidence across datasets and architectures.
- Over-parametrized networks can fit random labels yet achieve lower generalization error on real labels, challenging traditional capacity-based expectations.
- Existing parameter-count, norm, margin, and sharpness measures do not explain why increasing hidden units can reduce test error.
- The paper studies two-layer ReLU networks because they preserve the observed over-parametrization behavior of more complex pre-activation ResNet18 models.
- The proposed capacity measure characterizes complexity at the hidden-unit level, with unit capacity and unit impact shrinking faster than 1/h as network size increases.
- The resulting generalization bound depends on the top-layer Frobenius norm and hidden-layer distance from initialization, both of which decrease with increasing network size.
- The authors empirically evaluate existing complexity measures on MNIST, CIFAR10, and SVHN, and provide tighter bounds plus a matching Rademacher-complexity lower bound.
2 Generalization of Two Layer ReLU Networks
The paper defines a unit-wise capacity framework for two-layer ReLU networks, derives tighter Rademacher and generalization bounds, and compares their width dependence with existing measures. Its bound decreases with network width in reported CIFAR-10 and SVHN regimes, while retaining a matching lower-bound result.
- Capacity framework: Rademacher complexity is used to bound generalization error, measuring how readily a function class fits random labels.The analysis selects a function class representing trained networks rather than all possible weights, because larger classes can yield weaker bounds.
- Capacity framework: Unit capacity is the per-hidden-unit distance from learned weights to initialization, while unit impact is the magnitude of its outgoing weights.The paper motivates a restricted class using these unit-wise quantities, which empirical observations suggest remain bounded in learned networks.
- Generalization bounds: Theorem 1 bounds Rademacher complexity through the sum over hidden units of the products of unit capacity and unit impact.The proof decomposes complexity across hidden units instead of layers, exploiting their individual linear structure rather than relying only on layer Lipschitzness.
- Generalization bounds: Theorem 2 extends the bound to any two-layer ReLU network through a union bound over possible unit-capacity and unit-impact values.The resulting bound contains an additional ˜O(√(h/m)) term; the supplied passage states that this term is small in the regimes shown in Figure 5.
- Comparison with existing results: Theorem 3 supplies an explicit lower bound showing that the first term of the upper bound cannot be avoided.The paper also states that even small spectral norms relative to initialization do not permit improving this upper bound, although the extra union-bound term may be a proof artifact.
- Comparison with existing results: The capacity bound is the only compared measure that decreases with network size for CIFAR-10 and SVHN networks reaching about 100 million parameters.Other norm-based bounds initially decrease but then increase, while the paper reports that its bound improves over VC-dimension for networks larger than 1024 units; numerical values remain loose.
3 Lower Bound
The paper establishes a Rademacher-complexity lower bound for a constrained two-layer ReLU class that matches the dominant upper-bound term and improves prior capacity lower bounds. The result also shows that small spectral-norm or Lipschitz bounds do not suffice to tighten the upper bound.
- Lower-bound construction: The lower-bound construction uses a smaller function class with an additional spectral-norm constraint, enabling comparison with existing results while extending to the larger class.The constrained class is contained in the original class, so the lower bound applies to the broader setting as well.
- Lower-bound construction: The lower bound matches the dominant first term in the upper bound of Theorem 1, showing that this term cannot be removed.The matching argument also establishes tightness when the relevant class reduces to a linear function class.
- Implications: Even with a small spectral norm relative to the reference matrix, which effectively bounds network Lipschitzness, the upper bound cannot be improved.This conclusion follows from the lower bound obtained under the additional spectral-norm restriction.
- Comparison with existing results: The lower bound strictly improves previous spectral-norm-based capacity lower bounds, which corresponded to the network’s Lipschitz constant.The paper emphasizes a gap between Lipschitz-based capacity and neural-network capacity, even for a class excluding all-rank-1 weight matrices.
- Implications: The lower-bound phenomenon depends on ReLU: the stated gap between neural networks with and without ReLU does not hold for linear networks.The construction can nevertheless be extended to deeper networks by setting intermediate weight matrices to the identity.
- Comparison with existing results: The paper reports an improvement over Bartlett et al.’s lower bound and over a bound for 1-Lipschitz loss compositions with spectrally bounded networks.The comparison includes a lower bound involving the number of network outputs c.
4 Generalization for Extremely Large Values of h
The paper introduces a tighter capacity bound designed to reduce the additive term for very large hidden-layer widths h. Using an entrywise-dominance cover of the ℓp ball, the resulting bound can decrease with h under suitable p.
- An entrywise-dominance cover for the ℓp ball is the main new ingredient for reducing the additive term.
- Theorem 5 applies to two-layer ReLU functions with h hidden units, p ≥ 2, γ > 0, δ ∈ (0, 1), and initialization U0.
- For p of order ln h, the revised bound decreases with h for larger network widths.
- The revised bound replaces the additive h-dependent term from Theorem 2, while changing the first-term norms to h-dependent quantities.
- At p = ln h, the resulting norm is a tight upper bound for ∥V∥F and has the same order when all rows of V have equal norm.
5 Discussion
The discussion presents the decreasing capacity bound and matching lower bound as potential explanations for improved generalization in larger networks, while identifying scope and magnitude limitations.
- The new capacity bound decreases as the number of hidden units increases and could potentially explain better generalization in larger networks.
- The theoretical results are currently limited to two-layer networks, leaving extension to deeper networks as future work.
- The bounds support relative comparisons between network sizes, but their absolute values remain much larger than the number of training samples.
- The paper does not determine whether optimization algorithms converge to low-complexity networks or how hyperparameter choices affect recovered complexity.
A.1 Experiments Settings
The experiments evaluate fully connected and ResNet18 architectures across image datasets using specified optimization settings and several capacity-bound comparisons.
- The supplementary experiments include a pre-activation ResNet18 trained on CIFAR-10, with channel widths controlled by k across eight residual blocks.
- Two-layer fully connected networks were trained on CIFAR-10, SVHN, and MNIST across 13 architectures whose hidden-unit counts doubled from 2^3 to 2^15.
- Training used SGD with mini-batch size 64, momentum 0.9, and fixed step sizes of 0.01 for MNIST and 0.001 for CIFAR-10 and SVHN.
- The networks were trained without weight decay, dropout, or batch normalization.
- Bounds were computed with exact log terms and constants, margins set to the 5th percentile, and random initialization used as the reference matrix where applicable.
A.2 Supplementary Figures
The supplementary figures compare learned-network measures and capacity bounds across datasets, including output-layer, first-layer, initialization-angle, singular-value, and error comparisons.
- Figures 6 and 7 show measures for single-hidden-layer fully connected networks trained on SVHN and MNIST, respectively.
- Figure 8 includes training and test errors alongside normalized and unnormalized comparisons of capacity bounds on MNIST.
- The supplementary discussion uses these figures to compare the proposed generalization bound with other bounds and to show the over-parametrization phenomenon on MNIST.
- In each figure, panels proceed from output-layer measures to first-layer measures, initialization-angle distributions, and first-layer singular values.
B.1 Proof of Theorem 1
The proof builds a Rademacher-complexity bound for the network class by decomposing it into hidden-unit contributions and applying contraction and vector inequalities. It then transfers this bound through the ramp loss to obtain a generalization result.
- Rademacher-complexity bound: A vector-contraction inequality relates vector norms to expected inner products with Rademacher variables and supplies the proof’s main technical tool.The argument invokes Maurer’s result for this step.
- Multi-class extension: For multi-class outputs, a Rademacher-like complexity bound is obtained for linear operators centered around a reference matrix.The lemma is stated for a matrix V0 and input vectors xi.
- Rademacher-complexity bound: The network class’s Rademacher complexity is decomposed into contributions from its hidden units.This decomposition is formalized in the Rademacher Decomposition lemma.
- Inductive proof: The induction establishes the bound across network depth, beginning with the base case t = 1 and concluding at t = m.The proof uses triangle inequalities and adds and subtracts initialization terms during the induction step.
- Loss composition: The ramp loss contributes a Lipschitz factor because it depends on the correct-label score and the maximum score among incorrect labels.Its effective Lipschitz constant is described as 2/γ in the supplied proof fragments.
B.2 Proof of Theorems 2 and 5
The proofs extend fixed-parameter complexity bounds to general two-layer ReLU networks by covering parameter spaces and applying union bounds. Specialized p = 2 results follow, while the general p ≥ 2 result is looser because of additional constants and logarithmic factors.
- Covering argument: A covering lemma enables a generalization bound without assuming prior knowledge of network-parameter norms.It covers an ℓp ball with entry-wise dominating elements and controls the cover size.
- Cover construction: The covering construction represents vectors through a finite set Q and bounds its size by counting integer solutions.This controls the number of elements required for the ℓp cover.
- Covering argument: The fixed-parameter result is extended to all networks by covering the possible values of α and β and taking a union bound.The resulting theorem applies to two-layer ReLU networks.
- Generalization bounds: The resulting probability-one-minus-δ generalization bounds apply to two-layer ReLU networks with parameters measured using ℓp,2 norms.The bounds are stated for arbitrary p ≥ 2 and include a reference initialization U0.
B.3 Proof of the Lower Bound
The lower-bound proof constructs a structured dataset and network using orthogonal Hadamard features, then selects subsets to extend the construction from powers of two to arbitrary dimensions and widths. The construction controls the hidden-layer norm through a diagonal scaling matrix and truncated orthogonal features.
- Construction: The proof begins with the special case h = d = 2^k and m = n2^k, using a structured dataset for the lower-bound construction.The general case is handled later by reducing dimensions and sample size to powers of two.
- Construction: The dataset is divided into 2^k groups, with each group containing n copies of a distinct standard-basis vector.This creates the structured sample used by the lower-bound example.
- Orthogonal features: A Hadamard matrix with orthogonal rows supplies the feature directions used in the construction.Its rows satisfy ⟨f_i, f_j⟩ = δ_ij.
- Network construction: The construction flips or truncates Hadamard features according to the signs of ξ and forms eF(ξ) from the resulting vectors.The feature matrix is then combined with Diag(β) to define U(ξ).
- Norm control: Because F is orthogonal, the constructed hidden-layer matrix satisfies ∥U(ξ)∥2 ≤ maxi βi.The proof also bounds each row norm of eF(ξ) by 1.
- Extension to general sizes: For arbitrary d = h ≤ m, the proof selects powers-of-two subsets of hidden units, input dimensions, and samples to obtain the lower bound.The selected subsets retain at least half of the corresponding original sizes.