Source-linked AI summary
Optimal Approximation Rate of ReLU Networks in terms of Width and Depth
Zuowei Shen, Haizhao Yang, Shijun Zhang
TL;DR
The paper addresses the gap between nearly optimal and optimal approximation rates for ReLU networks as width and depth vary. By constructive network design, it derives modulus-of-continuity and Hölder rates, proves separate optimality, and extends the analysis to bounded domains and fixed-depth parameter counts.
Problem
Existing ReLU approximation results for continuous functions were optimal in width and depth only up to a logarithmic term.
Method
The paper constructs fully connected feed-forward ReLU networks using bit extraction, efficient step-function approximations, and grid-based function-value matching.
Results
O(√d ω_f((N^2L^2 ln N)^−1/d)) is achieved for continuous functions, with the corresponding Hölder rate optimal up to a constant separately in width and depth.
Takeaways & Limitations
The analysis extends to continuous functions on bounded subsets, including a fixed-depth one-dimensional Lipschitz rate of O(λ/(W ln W)) with W = O(N^2).
Takeaways & Limitations
Simultaneous width-depth optimality excludes a region characterized by C1 ≤ N ≤ LC2, and the conclusion discusses further improvements through other function spaces or activation functions.
Abstract
from arXiv · showhide
This paper concentrates on the approximation power of deep feed-forward neural networks in terms of width and depth. It is proved by construction that ReLU networks with width $\mathcal{O}\big(\max\{d\lfloor N^{1/d}\rfloor,\, N+2\}\big)$ and depth $\mathcal{O}(L)$ can approximate a Hölder continuous function on $[0,1]^d$ with an approximation rate $\mathcal{O}\big(λ\sqrt{d} (N^2L^2\ln N)^{-α/d}\big)$, where $α\in (0,1]$ and $λ>0$ are Hölder order and constant, respectively. Such a rate is optimal up to a constant in terms of width and depth separately, while existing results are only nearly optimal without the logarithmic factor in the approximation rate. More generally, for an arbitrary continuous function $f$ on $[0,1]^d$, the approximation rate becomes $\mathcal{O}\big(\,\sqrt{d}\,ω_f\big( (N^2L^2\ln N)^{-1/d}\big)\,\big)$, where $ω_f(\cdot)$ is the modulus of continuity. We also extend our analysis to any continuous function $f$ on a bounded set. Particularly, if ReLU networks with depth $31$ and width $\mathcal{O}(N)$ are used to approximate one-dimensional Lipschitz continuous functions on $[0,1]$ with a Lipschitz constant $λ>0$, the approximation rate in terms of the total number of parameters, $W=\mathcal{O}(N^2)$, becomes $\mathcal{O}(\tfracλ{W\ln W})$, which has not been discovered in the literature for fixed-depth ReLU networks.
1 Introduction
The paper studies approximation error for ReLU networks and constructs networks whose rates depend quantitatively on width and depth. It establishes optimality up to constants for Hölder functions separately in width and depth, while extending the analysis to broader continuous-function settings.
- Motivation: The paper focuses on approximation error for ReLU networks, distinct from optimization and generalization errors.Its analysis is independent of data samples and deep-learning algorithms.
- Problem: Earlier results achieved rates for continuous functions that were optimal in N and L only up to a logarithmic gap.The paper identifies removing this gap as technically challenging.
- Main result: O(√d ω_f((N^2L^2 ln N)^−1/d)) is obtained for arbitrary continuous f on [0,1]^d using width O(N) and depth O(L).The construction provides explicit prefactors when the modulus of continuity ω_f is known.
- Extensions: The analysis extends to continuous functions on bounded subsets of R^d and uses constructive techniques including novel bit extraction and more efficient step-function networks.The construction also composes a discretizing map with a network matching function values on grid points.
- Extensions: For one-dimensional Lipschitz functions, fixed-depth networks with 31 hidden layers and O(W) parameters achieve O(λ/(W ln W)).Here W = O(N^2), and the paper presents this as better than known fixed-depth ReLU results.
- Optimality: The Hölder rate is optimal up to a constant in width and depth separately, with simultaneous optimality except in a specified small region of the N-L plane.The exceptional region is characterized by C1 ≤ N ≤ LC2.
2 Theoretical analysis
The paper constructs ReLU networks that approximate continuous functions while controlling width and depth, then proves the resulting rates are optimal up to constants. Its analysis uses piecewise approximations, trifling regions, VC-dimension lower bounds, and extension from hypercubes to bounded domains.
- Constructive approximation: The construction approximates continuous functions by piecewise constant targets outside a trifling region, avoiding discontinuities that ReLU networks cannot represent directly.The trifling region smooths the piecewise constant approximation near discontinuity boundaries.
- Optimality: The approximation rate is optimal for Hölder([0,1]^d, α, λ), with VC-dimension determining a best-possible lower bound.The proof constructs Hölder functions whose approximating network class shatters O(ε^(-d/α)) points.
- Irregular bounded domains: The analysis extends from [0,1]^d to bounded E ⊆ [−R,R]^d by extending the target function to a hypercube while preserving its modulus of continuity.The resulting networks retain width C1 max{d⌊N^(1/d)⌋, N + 2} and depth 11L + C2.
3 Proof of Theorem 2.1
The proof approximates an arbitrary continuous function by partitioning the domain, mapping each region to an index, and fitting sampled values with a deep ReLU network. This construction achieves width O(N) and depth O(L) while controlling approximation outside a small trifling region.
- Index encoding: A step-function network Φ1 maps every x in Qβ to its d-dimensional index β.The coordinatewise step functions are implemented using Proposition 3.1.
- Point fitting: The network φ2 maps each index β approximately to the sampled value f(xβ), reducing the multidimensional point-fitting problem to a one-dimensional construction.A linear map ψ1 encodes β, and ψ2 fits the resulting one-dimensional samples.
- Error control: Outside the trifling region, φ = φ2 ○ Φ1 approximates f through the chain φ(x) ≈ f(xβ) ≈ f(x).The trifling region smooths the discontinuities of the piecewise-constant approximant and can have arbitrarily small measure.
- Bit extraction: The proof uses bit extraction to encode and recover many binary values efficiently, enabling the point-fitting construction with width O(N) and depth O(L).The method stores bits in a binary number and extracts individual bits with a deep ReLU network.
- Final network: The final architecture combines the index encoder and point-fitting network with width max{O(dN^(1/d)), O(N)} and depth O(L).The construction uses Propositions 3.1 and 3.2 to implement the two components.
4 Proofs of propositions in Section 3.1
The proposition proofs build ReLU subnetworks for piecewise-linear functions, step functions, and point fitting. Their composition supplies the width-depth bounds and the bit-extraction mechanism used in the main theorem.
- Basic ReLU constructions: Piecewise-linear functions with n breakpoints can be represented by one-dimensional ReLU networks with width n + 1.This is established by induction using ReLU representations of linear pieces.
- Composition: The final composition of the subnetworks yields width at most 16N + 30 and depth at most 6L + 10.The construction also preserves nonnegative output bounds through the final ReLU-based component.
- Bit extraction: Bit extraction stores Ln binary values in bin0.θ1θ2⋯θLn and extracts the required bit using a deep ReLU network.The construction handles partial sums of bits despite multiplication and comparison not being directly available as ReLU operations.
5 Conclusion and future work
The paper constructs ReLU networks with width O(N) and depth O(L) achieving an approximation rate governed by the modulus of continuity at scale (N^2L^2 ln N)^(-1/d).
- Conclusion: ReLU networks with width O(N) and depth O(L) approximate continuous functions on [0,1]^d at rate O(ωf((N^2L^2 ln N)^(-1/d))).For Hölder functions, the paper connects this rate to optimality in width and depth through VC-dimension.