Research map / Learning theory and algorithms / Sample complexity
A general approximation lower bound in $L^p$ norm, with applications to feed-forward 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 |
|---|---|---|---|
| Use packing numbers of the target class and fat-shattering dimension of the approximating class to lower-bound L^p approximation | General function classes F and G · L^p(μ), 1 ≤ p < +∞ | worst-case approximation error | Helped |
| Apply the general bound to Hölder balls and piecewise-affine networks | Feed-forward networks approximating Hölder balls · L^p(λ) | worst-case approximation error lower bound: c_1 {W^{-\gamma}} \log^{-\frac{3s}{d}}(W) | Helped |
| Use ReLU networks to approximate Hölder balls in L^p rather than sup norm | ReLU networks · Hölder balls | approximation rate | No clear effect |
| Apply the general bound to monotonic functions with Heaviside networks | Heaviside feed-forward networks · Multivariate monotonic functions, L^p(λ) | worst-case approximation error: c_3 W^{-\frac{1}{\alpha}} \log^{-\frac{3}{\alpha}}(W) | Helped |
| Approximate multivariate monotonic functions in L^p instead of sup norm | Heaviside feed-forward networks · Multivariate monotonic functions, d ≥ 2 | approximation feasibility: \frac{1}{2} | Helped |
| Vary p for monotonic-function approximation | Feed-forward networks · Multivariate monotonic functions, L^p(λ) | approximation rate dependence: \alpha = \max\{d, (d-1)p\} | Mixed |
Closest papers by meaning
- Generalization Bounds for Neural Networks via Approximate Description Length (NeurIPS 2019 · similarity 0.89)
- Generalization Bounds for Rank-sparse Neural Networks (NeurIPS 2025 · similarity 0.87)
- Minimum Norm Interpolation Meets The Local Theory of Banach Spaces (ICML 2024 · similarity 0.86)
- ReLU Network with Width $d+\mathcal{O}(1)$ Can Achieve Optimal Approximation Rate (ICML 2024 · similarity 0.85)
- Koopman-based generalization bound: New aspect for full-rank weights (ICLR 2024 · similarity 0.85)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.85)
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.