Research map / Learning theory and algorithms / Kernels and regression theory
How many samples are needed to train a deep neural network?
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.
Derives a minimax lower bound of order sqrt(log d / n) on the squared L2 risk for sparse (l1-bounded) deep ReLU feed-forward networks via Fano's inequality and a packing-number lower bound, and empirically fits generalization error curves on MNIST, Fashion-MNIST, CIFAR-10 and California Housing, finding 1/sqrt(n) fits better than 1/n.
Problem
How many training samples are needed for deep ReLU networks; whether the generalization error can beat the parametric 1/n rate that classical statistics suggests.
Approach
Uses Fano's inequality with a local packing argument, and a new packing-number lower bound for l1-constrained deep ReLU network classes, to show a minimax lower bound scaling as 1/sqrt(n) (not 1/n) for non-linear deep ReLU networks, matching known upper bounds.
Key results
- Across MNIST, Fashion-MNIST, CIFAR-10 and California Housing, the fitted 1/sqrt(n) curve gives higher R-squared than the 1/n curve in most architectures (e.g., MNIST shallow ReLU net R-squared 0.93 for 1/sqrt(n) vs -1.4 for 1/n).
- Theorem gives minimax squared-risk lower bound (c^2/2) * (sparsity factor) * sqrt(log d / n), i.e., sample complexity scaling as 1/epsilon^4 rather than 1/epsilon^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Fit the 1/√n curve instead of the 1/n curve | ReLU networks · MNIST | MSE and R-squared: MSE: 1.7\cdot10^{-2} vs 5.2\cdot10^{-4}; 1.1\cdot10^{-2} vs 2.4\cdot10^{-4}. R-squared: -1.4\cdot10^{0} vs 9.3\cdot10^{- | Helped |
| Fit the 1/√n curve instead of the 1/n curve | ReLU networks and CNN · Fashion-MNIST | MSE and R-squared: MSE: 1.3\cdot10^{-2} vs 6.1\cdot10^{-4}; 1.4\cdot10^{-2} vs 8.4\cdot10^{-4}; 3.1\cdot10^{-2} vs 1.4\cdot10^{-3}. R-squar | Helped |
| Fit the 1/√n curve instead of the 1/n curve | ReLU networks and CNN · CIFAR | MSE and R-squared: MSE: 7.9\cdot10^{-2} vs 8.1\cdot10^{-3}; 2.9\cdot10^{-1} vs 3.1\cdot10^{-2}. R-squared: -3.5\cdot10^{0} vs 5.3\cdot10^{- | Helped |
| Fit the 1/√n curve instead of the 1/n curve | Five-hidden-layer ReLU network, width 300 · California Housing | MSE and R-squared: MSE: 9.9\cdot10^{-2} vs 2.1\cdot10^{-2}; R-squared: 2.1\cdot10^{-1} vs 8.4\cdot10^{-1}. | Helped |
Surprising findings
- Generalization error of deep ReLU networks appears to decay at 1/sqrt(n) rather than the parametric 1/n rate, in contrast to classical linear regression.
Limitations
- Lower bound holds for l1-constrained (sparse) ReLU networks with v0=1 and Gaussian inputs; constants are not exact.
- Empirical curve fitting uses fitted constants and only a few datasets and architectures; the rate decision is based on R-squared comparison, not formal testing.
- Authors state exact sample size cannot be determined in advance.
Experimental setup
Datasets: MNIST Fashion-MNIST CIFAR-10 California Housing Prices
Benchmarks: MNIST Fashion-MNIST CIFAR-10 California Housing Prices
Metrics: test prediction error (cross-entropy / MSE) R-squared of curve fit MSE of curve fit
Baselines: parametric 1/n rate least squares linear regression
Builds on: Fano's inequality local packing (Birgé) l1-norm generalization bounds for neural networks
Closest papers by meaning
- Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification (NeurIPS 2025 · similarity 0.85)
- Where Do Large Learning Rates Lead Us? (NeurIPS 2024 · similarity 0.84)
- Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning (ICLR 2024 · similarity 0.84)
- The Effect of Weight Precision on the Neuron Count in Deep ReLU Networks (ICML 2024 · similarity 0.84)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.84)
- Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training (ICML 2025 · similarity 0.84)
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.