Research map / Architectures and efficiency / RNNs and normalization
ReLU Network with Width $d+\mathcal{O}(1)$ Can Achieve Optimal Approximation Rate
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 ReLU networks of minimal width d+1 (or d+O(1) for uniform norm) achieve the optimal O(L^{-2/d}) approximation rate for continuous functions, extended to vector-valued mappings and other activations.
Problem
Narrow ReLU networks of near-minimal width d+O(1) are known to be universal approximators, but their optimal approximation rate (relation between parameter count/depth and error) was unknown.
Approach
Constructs ReLU networks of width max{d+1,5} that encode the input cube index into a scalar via a narrow depth-O(L^{1/d}) network and fit O(L^2) points with a width-5 point-fitting network, achieving O(omega_f(L^{-2/d})) in Lp; for uniform norm, it adapts Yarotsky's bit-extraction construction to width d+11 with a slightly weaker rate O(L^{-2/(d+1)}) for vector-valued maps. Also transfers rates to
Key results
- ReLU networks of width max{d+1,5} and depth 25L+7d+4 achieve Lp error bounded by 7 sqrt(d) omega_f(L^{-2/d}) for continuous f on [0,1]^d, matching the VC-dimension lower bound rate.
- For the uniform norm, width d+11 networks achieve error O(omega_f(L^{-2/(d+1)})), which is nearly optimal.
- Vector-valued extension: width max{d+1, v+6} achieves optimal Lp rate for mappings into R^v.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a ReLU network with width max{d + 1, 5} for Lp approximation | ReLU feed-forward networks · [0, 1]^d, Lp norm (p ∈ [1, ∞)) | approximation rate: O(ωf(L−2/d)) | Helped |
| Use a ReLU network with width d + 11 for uniform approximation | ReLU feed-forward networks · [0, 1]^d, uniform norm | approximation rate: O(ωf(L−2/(d+1))) | Helped |
| Use a ReLU network with width max{d + 1, v + 6} for vector-valued Lp approximation | ReLU feed-forward networks · T ⊂ Rd to Rv, Lp norm (p ∈ [1, ∞)) | approximation rate: O(ωf(diam (T ) L−2/d)) | Helped |
| Use a ReLU network with width d + v + 10 for vector-valued uniform approximation | ReLU feed-forward networks · T ⊂ Rd to Rv, uniform norm | approximation rate: O(ωf(diam (T ) L−2/(d+1))) | Helped |
Surprising findings
- Minimal-width ReLU networks (width d+1) match the optimal rate, contrary to the expectation that narrow networks must sacrifice approximation efficiency.
Limitations
- Uniform-norm result uses width d+11 and only attains the nearly optimal rate O(L^{-2/(d+1)}) rather than the optimal rate.
- Constants depend strongly on d and the proofs are worst-case; the dependence on d is not improved.
- Optimality lower bound relies on VC-dimension arguments; for smooth-activation networks the bound is not known to be tight.
Experimental setup
Metrics: Lp approximation error uniform approximation error bound
Baselines: Yarotsky 2018 Shen et al. 2022b Park et al. 2020 Hanin & Sellke 2017 Cai 2022 Kim et al. 2023
Builds on: Yarotsky 2018 bit-extraction construction Shen et al. 2022 deep ReLU approximation Park et al. 2020 minimal width universality Zhang et al. 2023 ReLU variant equivalence
Closest papers by meaning
- Minimum width for universal approximation using ReLU networks on compact domain (ICLR 2024 · similarity 0.93)
- Characterizing ResNet's Universal Approximation Capability (ICML 2024 · similarity 0.93)
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.89)
- Minimum Width for Universal Approximation using Squashable Activation Functions (ICML 2025 · similarity 0.88)
- Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training (ICML 2025 · similarity 0.88)
- Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classes (ICML 2024 · similarity 0.88)
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.