Source-linked AI summary
Deep Network Approximation Characterized by Number of Neurons
Zuowei Shen, Haizhao Yang, Shijun Zhang
TL;DR
The paper asks how to quantify deep ReLU FNN approximation when width and depth are chosen arbitrarily, addressing prior rates with unknown constants or asymptotic restrictions. It constructs networks with explicit width-depth error bounds, extends the analysis to neighborhoods of low-dimensional manifolds, and shows nearly tight rates for Hölder functions. The results provide a quantitative basis for network-size selection, while the theory assumes full access to the target function and does not directly model noisy-observation regression.
Problem
Prior theories often give implicit asymptotic rates with unknown prefactors or require sufficiently large widths and depths, leaving simultaneous characterization of arbitrary N and L unresolved.
Method
The paper constructs ReLU FNN approximants using explicit width-depth bounds, a modified bit-extraction technique, and nearly isometric projection for manifold-neighborhood domains.
Results
ReLU FNNs achieve O(√d ω_f(N^-2/dL^-2/d)) for continuous functions and O(√d λN^-2α/dL^-2α/d) for Hölder functions, with the latter nearly asymptotically tight.
Takeaways & Limitations
The width-depth characterization gives explicit guidance for selecting ReLU FNN sizes and can reduce the relevant dimension from d to d_δ near low-dimensional manifolds.
Takeaways & Limitations
The theory assumes the target function is fully accessible, whereas practical regression usually has limited noisy observations; optimization to global minimizers is also not guaranteed.
Abstract
from arXiv · showhide
This paper quantitatively characterizes the approximation power of deep feed-forward neural networks (FNNs) in terms of the number of neurons. It is shown by construction that ReLU FNNs with width $\mathcal{O}\big(\max\{d\lfloor N^{1/d}\rfloor,\, N+1\}\big)$ and depth $\mathcal{O}(L)$ can approximate an arbitrary Hölder continuous function of order $α\in (0,1]$ on $[0,1]^d$ with a nearly tight approximation rate $\mathcal{O}\big(\sqrt{d} N^{-2α/d}L^{-2α/d}\big)$ measured in $L^p$-norm for any $N,L\in \mathbb{N}^+$ and $p\in[1,\infty]$. More generally for an arbitrary continuous function $f$ on $[0,1]^d$ with a modulus of continuity $ω_f(\cdot)$, the constructive approximation rate is $\mathcal{O}\big(\sqrt{d}\,ω_f( N^{-2/d}L^{-2/d})\big)$. We also extend our analysis to $f$ on irregular domains or those localized in an $\varepsilon$-neighborhood of a $d_{\mathcal{M}}$-dimensional smooth manifold $\mathcal{M}\subseteq [0,1]^d$ with $d_{\mathcal{M}}\ll d$. Especially, in the case of an essentially low-dimensional domain, we show an approximation rate $\mathcal{O}\big(ω_f(\tfrac{\varepsilon}{1-δ}\sqrt{\tfrac{d}{d_δ}}+\varepsilon)+\sqrt{d}\,ω_f(\tfrac{\sqrt{d}}{(1-δ)\sqrt{d_δ}}N^{-2/d_δ}L^{-2/d_δ})\big)$ for ReLU FNNs to approximate $f$ in the $\varepsilon$-neighborhood, where $d_δ=\mathcal{O}\big(d_{\mathcal{M}}\tfrac{\ln (d/δ)}{δ^2}\big)$ for any $δ\in(0,1)$ as a relative error for a projection to approximate an isometry when projecting $\mathcal{M}$ to a $d_δ$-dimensional domain.
1 Introduction
The paper addresses the open problem of simultaneously characterizing width and depth in deep ReLU FNN approximation. It provides explicit, nearly optimal rates for continuous and Hölder functions, extends the analysis to low-dimensional manifold neighborhoods, and discusses practical network sizing and limitations.
- Motivation: Existing approximation theories often provide asymptotic rates, unknown prefactors, or results only for sufficiently large widths and depths.This leaves explicit error estimation for arbitrarily chosen network sizes unresolved.
- Main results: The paper establishes an explicit approximation framework for continuous functions with width O(N) and depth O(L), achieving rate O(√d ω_f(N^-2/dL^-2/d)).The construction uses analysis based on FNN structure and a modified bit-extraction technique.
- Practical implications: The width-depth characterization is more generic than parameter-count characterizations and can guide practical network-size selection.The paper notes that width and depth imply the corresponding nonzero-parameter characterization, but not conversely.
- Main results: For Hölder functions of order α and constant λ, the rate becomes O(√d λN^-2α/dL^-2α/d) and is nearly asymptotically tight.The lower-bound argument uses nearly tight VC-dimension bounds, showing that the width-depth dependence cannot substantially improve for the stated function class.
- Low-dimensional domains: For data near a low-dimensional manifold, projection and approximation yield networks whose size depends on d_δ rather than the ambient dimension d.The projection parameter δ balances isometry quality against dimension reduction, while Theorem 1.2 gives the resulting width and depth bounds.
- Limitations: The theory assumes full access to the target function, whereas regression applications typically provide only limited noisy observations.In that setting, the approximation theory characterizes a lower bound for regression bias rather than the full stochastic regression error.
2 Approximation of continuous functions
The section constructs ReLU FNNs for continuous-function approximation using piecewise-constant surrogates outside a small trifling region, with explicit width, depth, and near-optimality bounds.
- Construction: ReLU FNNs approximate continuous f by implementing a piecewise-constant surrogate outside a trifling region near discontinuities.The construction partitions [0,1]^d into important regions and uses ReLU networks to approximate the surrogate there.
- Approximation guarantee: Theorem 1.1’s rate extends to p = ∞ using a technique that controls approximation error inside the trifling region.Earlier continuous-function results addressed p ∈ [1,∞), while the later technique enables the uniform-norm case.
- Optimality: The approximation rate is nearly tight for Bλ(Cα([0,1]^d)); rates with stronger separate improvements in N or L are unattainable.The lower bound uses VC dimension and constructs Hölder functions that shatter more points than the network class can support under such rates.
3 Proof of Theorem 2.1
The proof constructs an almost piecewise-constant ReLU approximation by partitioning the domain, encoding each subregion by an index, and fitting function values through composed subnetworks.
- O(N^2L^2) partition pieces yield an intermediate piecewise-constant approximation with error scaling O(N^-2/dL^-2/d).
- The trifling region excludes neighborhoods of discontinuities, allowing a continuous ReLU network to implement the piecewise-constant approximation elsewhere.
- The construction uses width O(N) and depth O(L), with bit extraction enabling efficient storage and extraction of L binary bits.
- The vector subnetwork Φ1 maps every sub-cube Qβ to its d-dimensional index β.
- The second subnetwork maps each index β approximately to the representative value f(xβ) through auxiliary sets, a piecewise-linear function g, and point fitting.
4 Neural networks approximation and evaluation in practice
The paper extends approximation from cubic domains to irregular domains and neighborhoods of low-dimensional manifolds, while discussing practical algorithms and limitations of optimization.
- Practical evaluation: The proved approximation rate may not currently be observable because no existing optimization algorithm guarantees identification of a global minimizer.
- Irregular domains: Theorem 4.3 extends uniformly continuous functions from irregular domains to ReLU FNNs by first extending the function to a cubic domain and then restricting the network.
- Low-dimensional manifolds: A nearly isometric projection A maps the manifold into dδ dimensions while approximately preserving pairwise distances.
- Low-dimensional manifolds: The projected function is defined by selecting a unique representative from each fiber, whose points lie within a ball of radius O(ε).
- Low-dimensional manifolds: When ε = O(N^-2/dδL^-2/dδ), the manifold-neighborhood approximation term becomes O(ω_f(O(N^-2/dδL^-2/dδ))).
- Practical evaluation: The resulting two-step learning strategy projects high-dimensional data into a low-dimensional space before applying deep learning, with good results claimed with high probability.
5 Conclusion and future work
The paper gives explicit, nearly optimal approximation rates for ReLU FNNs in terms of width and depth, extending the analysis to low-dimensional domains and parallel-computing choices. It also identifies architecture and activation-function generalizations as future work.
- The paper targets quantitative, simultaneous characterization of ReLU FNN approximation power in width and depth for continuous functions.
- O(N) width and O(L) depth achieve approximation rate √dω_f(N^-2/dL^-2/d) for continuous functions on a d-dimensional cube.
- √dλN^-2α/dL^-2α/d is the rate for Hölder functions of order α, and it is nearly asymptotically tight.
- The analysis extends to irregular domains and essentially low-dimensional data localized near a smooth manifold.
- For parallel computing, depth O(1) is preferred with sufficiently many cores, width O(d) with O(1) cores, and intermediate widths between O(√p) and O(p) for moderate p.
- The analysis is limited to fully connected feedforward networks with ReLU, leaving other architectures, activations, residual connections, and function spaces for future work.