Research map / Learning theory and algorithms / Kernels and regression theory
Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that empirical-risk minimizing two-layer networks generalize when both sample size and width are large relative to the width needed to express the data distribution, with matching sample-complexity lower bounds and explanations of robustness, over-parameterization and loss-function phenomena.
Problem
Classic VC/Rademacher bounds fail to explain generalization of over-parameterized networks, and algorithm-dependent (stability, NTK) bounds rely on strong assumptions; the paper asks when empirical-risk minimizers generalize.
Approach
Derives a population-accuracy lower bound for any empirical-risk minimizing two-layer ReLU/continuous-activation network in terms of the width needed to express the data distribution with a confidence margin, where the sample size N and network width W enter independently in the denominator, so over-parameterization helps; also gives a sample-complexity lower bound via VC dimension.
Key results
- Lower bound: for any empirical-risk minimizer of width W >= W_0+1, population accuracy >= 1 - O(W_0/(cW) + nL_p(W_0+c)sqrt(log(4n))/(c sqrt(N)) + sqrt(ln(2/delta)/N)), so N and W need only be large relative to the expressive cost W_0.
- Sample-complexity lower bound: for some distributions, fewer than Omega(VC(H_{W_0}(n))) ~ O(nW_0) samples lead to poor generalization for some empirical risk minimizer.
- For the distribution D_n, ReLU networks need width Omega(n) and Omega(n) samples, whereas sin(pi x) activation needs width 1 and only O(ln(delta)) samples to generalize.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase network width W and training sample count N independently, given a distribution expressible at width W₀ with confidence c | Empirical-risk-minimizing two-layer networks · D(n) | population accuracy: A_D(F)≥ 1-O(\frac{W_{0}}{cW}+ \frac{nL_p(W_{0}+c)\sqrt{\log(4n)}}{c\sqrt{N}}+\sqrt{\frac{\ln(2/\delta)}{N}}) | Helped |
| Use sin(πx) activation instead of ReLU | Two-layer networks on D_n · D_n | population accuracy: ReLU: A_\D(\F)\le 0.5+2\delta; sin activation: A_\D(\F)=1 | Helped |
| Use ReLU instead of sin(πx) activation | Two-layer networks on D_n · D_n | population accuracy: A_\D(\F)\le 0.5+2\delta vs. A_\D(\F)=1 | Hurt |
| Approximately minimize empirical risk within factor q | Two-layer networks · D(n) | population accuracy lower bound: A_\D(F)\ge 1-O(\frac{qW_0}{cW}+ \frac{nL_p(W_0+c)\sqrt{\log(4n)}}{c\sqrt{N}}+\sqrt{\frac{\ln(2/\delta)}{N}}) | Mixed |
| Use a bad loss function for empirical-risk minimization | Two-layer networks · Some distribution D | population accuracy: A_\D(\F)\le 0.5 | Hurt |
| Constrain ERM to width W₀, despite a width-W₀ network achieving high accuracy | Two-layer networks · Some distribution D | population accuracy: A_\D(\F)\ge 0.99; A_\D(\F)\le 0.6 | Hurt |
| Increase the required expressive width W₀ for a distribution | Empirical-risk-minimizing networks · Worst-case distributions expressible at width W₀ | training samples required for generalization: N \le O(nW_{0}(1-4\epsilon-\delta)) | Hurt |
Surprising findings
- Bad loss functions (e.g., MSE, linear loss) can yield poor generalization even when the empirical risk is minimized.
- For some distributions, adding width does not fix poor generalization of ERM with too small networks, implying over-parameterization is needed to find good networks.
Limitations
- Results are for two-layer networks; deep-network results are only preliminary in the appendix.
- Required expressive cost W_0 is not accurately computable for general distributions.
- Binary classification with positive-separation distributions only.
Experimental setup
Baselines: VC-dimension generalization bound Rademacher complexity bound NTK-based bound stability bound for SGD PAC-Bayes-KL bound
Builds on: Rademacher complexity bounds VC-dimension of ReLU networks NTK generalization analysis algorithmic stability bounds
Closest papers by meaning
- Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.92)
- In search of robust measures of generalization (NeurIPS 2020 · similarity 0.92)
- On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications (ICLR 2022 · similarity 0.91)
- Measuring Generalization with Optimal Transport (NeurIPS 2021 · similarity 0.90)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.89)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.