Research map / Learning theory and algorithms / Sample complexity
The Sample Complexity of One-Hidden-Layer Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Control only the hidden-layer spectral norm rather than requiring a width-independent guarantee | One-hidden-layer networks with non-smooth activation · High-dimensional inputs | fat-shattering dimension: c α^2 · ((bB b_x)^2 n)/ε^2 | Hurt |
| Replace spectral-norm control with Frobenius-norm control on W | One-hidden-layer networks with Lipschitz activation · Inputs with norm at most b_x | Rademacher complexity: m ≥ c·((bBb_xL)^2(1+log^3(m)))/ε^2 | Helped |
| Use a sufficiently smooth activation while retaining spectral-norm control | One-hidden-layer networks · Inputs with norm at most b_x | Rademacher complexity: m ≥ (b·\tilde{σ}(B b_x)/ε)^2 | Helped |
| Extend power activations to multiple layers with spectral-norm constraints | Deep networks with power activation · Inputs with norm at most b_x | Rademacher complexity: m ≥ (b·B^{k+k^2+... k^L}·b_x^{k^L}/ε)^2 | Helped |
| Impose convolutional weight-sharing on the hidden layer | Convolutional networks with linear output · Convolutional patches Φ | Rademacher complexity: m ≥ 2·O_Φ·(bBb_xL/ε)^2 | Helped |
| Replace the linear output layer with fixed Lipschitz pooling | Convolutional networks · Convolutional patches Φ | Rademacher complexity: m ≥ c·(LBb_x/ε)^2·log^2(m)log(mn); 1/4 · (B b_x/ε)^2 · log(n) | Mixed |
| Constrain W by its Frobenius norm in the fixed-dimension setting | One-hidden-layer networks · Inputs in R^d; ReLU with bias | fat-shattering dimension: \tilde{Ω}(min{nd, (bB b_x/ε)√d}) | Mixed |
Closest papers by meaning
- Fantastic Four: Differentiable and Efficient Bounds on Singular Values of Convolution Layers (ICLR 2021 · similarity 0.89)
- Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks (NeurIPS 2019 · similarity 0.88)
- On the Complexity of Learning Neural Networks (NeurIPS 2017 · similarity 0.88)
- Generalization Bounds for Neural Networks via Approximate Description Length (NeurIPS 2019 · similarity 0.88)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.87)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.86)
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.