Optimal approximation of smooth functions by ReLU neural networks
Abstract
We study uniform approximation of the Hölder ball $\mathcal H_1^s([0,1]^D)$ by fully connected ReLU networks. Except in the one-dimensional Lipschitz case, existing constructions remain separated from the information-theoretic efficiency limit. This article closes the gap for every $s>0$ and $D\ge1$: networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ attain uniform approximation error of order $(N^2L^2\log N)^{-s/D}$. No relation between width and depth is required. The construction uses new encoding and decoding mechanisms that exploit higher-order finite-difference bounds for local Taylor coefficients of the target function. As a statistical consequence, empirical risk minimizers over the corresponding clipped network classes attain the minimax regression rate $n^{-2s/(2s+D)}$ without additional logarithmic factors. The paper also gives a detailed exposition of the key approximation techniques, covering both established and new mechanisms.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper closes the gap between existing ReLU network approximation constructions and the information-theoretic efficiency limit for Hölder smooth functions, establishing optimal rates for width, depth, and parameter magnitude. This is a significant theoretical contribution that resolves a major open problem in neural network approximation theory, providing a complete characterization of the capacity of ReLU networks for smooth function approximation.
Methodology
The paper presents a rigorous theoretical framework for the uniform approximation of Hölder smooth functions by ReLU neural networks. The core innovation is a "higher-order point-fitting" mechanism that exploits the regularity of local Taylor coefficients to compress their storage within the network weights. By using higher-order finite differences and a segmented discrete Taylor-Newton recursion, the authors achieve an approximation error of $(N^2L^2\log N)^{-s/D}$ with bounded parameter magnitudes ($O(1)$). This closes the gap between existing constructions and the information-theoretic efficiency limit for all smoothness orders $s>0$ and dimensions $D\ge1$. The methodology is highly sophisticated, combining established techniques like bit-extraction and median smoothing with novel encoding strategies that preserve smoothness during the flattening of multivariate coefficient grids via Hermite interpolation bridges.
Results & evaluation
As a pure theory paper, there are no empirical experiments, datasets, or benchmark comparisons. The "evaluation" consists of mathematical proofs establishing upper bounds on approximation error and matching lower bounds via metric entropy arguments. The statistical consequence (minimax regression rates) is derived theoretically.
Reproducibility
The paper is highly reproducible in the mathematical sense. It provides self-contained proofs for all key components, including simplified versions of standard techniques. The construction is explicit, and the bounds are tight. However, without code, practical implementation of these specific network architectures for real-world data is not directly demonstrated.
Limitations
The results are limited to uniform approximation on the unit cube $[0,1]^D$ for Hölder classes. The lower bound relies on metric entropy, which may not capture all aspects of practical learning dynamics. The paper does not address the optimization landscape or the trainability of these networks, which is a significant gap between theoretical optimality and practical deep learning.
Broader impact
This work provides a definitive answer to a long-standing question in neural network approximation theory. It establishes that ReLU networks are optimal approximators for smooth functions in terms of width, depth, and parameter magnitude. This has implications for understanding the capacity of neural networks and the theoretical limits of nonparametric regression. It may influence future theoretical work on network architectures and the design of approximation schemes for other function classes. The paper closes the gap between existing ReLU network approximation constructions and the information-theoretic efficiency limit for Hölder smooth functions, establishing optimal rates for width, depth, and parameter magnitude. This is a significant theoretical contribution that resolves a major open problem in neural network approximation theory, providing a complete characterization of the capacity of ReLU networks for smooth function approximation.
Author of this paper? Send a correction.