ReLU Networks Achieve Optimal Rates Approximating Smooth Functions, Removing Log Factor in Statistical Regression

From Information-Theoretic Limits to Explicit Construction: The "Last Piece" of ReLU Approximation

Approximating smooth functions with ReLU networks has long been a central problem in deep learning theory. Information theory established the efficiency limit long ago, but constructive proofs lagged behind—except for the simplest one-dimensional Lipschitz case, existing network constructions all fell short of this limit. A recent paper claims to close this gap: for any smoothness $s>0$ and dimension $D\ge1$, ReLU networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ can achieve uniform approximation error $(N^2L^2\log N)^{-s/D}$, with no fixed relationship required between width and depth.

The significance of this result extends beyond approximation theory. As a statistical corollary, empirical risk minimization (ERM) over the corresponding truncated network class achieves the minimax regression rate $n^{-2s/(2s+D)}$ with no extra logarithmic factor. While many prior works could prove consistency of ERM, their rates always carried a $\log n$ "tail"—this paper removes it.

Core Results: Approximation Rate and Network Size

Meaning of the Error Order $(N^2L^2\log N)^{-s/D}$

The standard measure of approximation efficiency is the uniform error on the Hölder ball $\mathcal H_1^s([0,1]^D)$. The error order given in the paper can be understood in two parts: $N$ controls width, $L$ controls depth, the total number of parameters is roughly proportional to $N^2L^2$, and the $\log N$ factor is a slight cost incurred by the encoding mechanism in the construction.

Compared with classical results, this rate matches the information-theoretic lower bound in its dependence on $s$ and $D$, differing only in constants and that logarithmic factor. More importantly, width and depth can be chosen independently—deep-and-narrow or wide-and-shallow networks both achieve the same error order, which theoretically echoes the empirical question in practical network design of "how to trade off width and depth."

Hölder ball and smoothness parameter: The Hölder space $C^s$ consists of functions whose derivatives up to order $\lfloor s\rfloor$ are bounded, and whose highest-order derivative satisfies Hölder continuity with exponent $s-\lfloor s\rfloor$. The Hölder ball $\mathcal H_1^s([0,1]^D)$ further requires all such semi-norms to be at most 1, making it a bounded set of smooth functions. The larger the smoothness $s$, the more "regular" the function and the more efficiently it can be approximated by polynomials or piecewise linear structures; the smaller $s$ is (approaching 0), the rougher the function and the harder the approximation. The exponent form $s/D$ in the error order reflects the classical "effective smoothness" in nonparametric statistics: the higher the dimension $D$, the more the approximation benefit of a given smoothness is diluted—this is the quantitative manifestation of the curse of dimensionality in approximation theory.

Information-theoretic lower bound and construction gap: The information-theoretic lower bound in approximation theory states: for any function in the Hölder ball, the uniform approximation error of any model described by $M$ parameters (including ReLU networks) cannot be lower than order $c M^{-s/D}$. Here $M$ can be understood as the effective number of network parameters. Therefore an ideal error order should be proportional to the $-s/D$ power of the parameter count. The $N^2L^2$ in this paper roughly corresponds to the parameter count, and $(N^2L^2\log N)^{-s/D}$ differs from the lower bound only by a $\log N$ factor—this is what "order-optimal" means. Most prior constructions either had a worse relationship between parameter count and error, or required width and depth to satisfy specific ratios, and thus could not simultaneously match the lower bound while maintaining architectural freedom.

Engineering Significance of Parameter Magnitude $O(1)$

Many approximation constructions rely on exponential growth of parameters, making the network numerically unrealizable. This paper keeps parameter magnitude at the constant level, meaning weights need not reach overflow-inducing orders, which is more friendly to fixed-point or low-precision deployment. Although the paper itself is theoretical work, this constraint brings the construction one step closer to practically trainable networks.

Construction Approach: Encoding Local Taylor Coefficients with High-Order Finite Differences

The technical core of the paper is a new encoding and decoding mechanism that uses high-order finite difference bounds to approximate the local Taylor coefficients of the target function. Simply put, ReLU networks can be viewed as performing piecewise linear interpolation on intervals, but to achieve the optimal rate in high dimensions, the network must be able to "recognize" the local high-order expansion structure of the function.

The authors do not rely on a special ratio between depth and width; instead they design a general encoding framework that compresses Taylor coefficient information into the network's weights and biases. High-order finite differences play a dual role here: it is both an analytical tool for controlling coefficient approximation error and a constructive tool for converting discrete differences into computations the network can implement.

The paper also devotes considerable space to reviewing existing and new mechanisms in approximation techniques; for readers wishing to enter this direction, this exposition is itself valuable for reference.

Statistical Consequences: ERM Achieves Minimax Rate Without Log Factor

The value of approximation-theoretic results is often reflected in statistical learning theory. Given $n$ samples, performing empirical risk minimization over the truncated ReLU network class, the paper proves that its regression risk converges at rate $n^{-2s/(2s+D)}$, matching the minimax lower bound up to constants.

This rate is exactly the classical result in nonparametric regression: when the target function belongs to the $s$-order Hölder class, no estimator can converge faster than $n^{-2s/(2s+D)}$. Prior ERM analyses based on neural networks usually had an extra $\log n$ factor, which could only be removed with more refined model selection or early stopping strategies. This paper directly eliminates the logarithmic gap by improving the approximation construction, showing that statistically the ReLU network class is already "good enough" and requires no additional tricks to compensate for approximation error.

Minimax rate: In nonparametric regression, given $n$ independent samples $(X_i,Y_i)$, if the true regression function $f$ belongs to the $s$-order Hölder ball, then any estimator $\hat f$ has a worst-case mean squared error lower bound $c n^{-2s/(2s+D)}$, where the constant $c$ does not depend on $n$. This lower bound consists of a tradeoff between estimation error (determined by sample size) and approximation error (determined by model complexity). An estimator achieving this lower bound is called minimax optimal. For ReLU networks, if the network class is rich enough to approximate the Hölder ball to the corresponding accuracy while its complexity is controlled to avoid overfitting, then ERM can achieve this rate. The contribution of this paper is constructing a network class that simultaneously satisfies "optimal approximation accuracy" and "bounded parameter magnitude," so that the complexity analysis of ERM no longer incurs an extra logarithmic penalty.

ERM and the source of the logarithmic factor: Standard analysis of empirical risk minimization (ERM) over neural network classes usually controls generalization error via covering numbers or VC dimension, and these complexity measures often introduce $\log n$ or $\log M$ factors. In addition, if the approximation error itself carries a logarithmic term, the total error will accumulate the logarithmic gap. This paper eliminates the logarithmic cost in the approximation construction (except for $\log N$) and carefully controls network parameter magnitude, so that the convergence rate of ERM matches the minimax lower bound up to constants, without post-processing such as early stopping or model selection.

Boundaries and Open Questions

The paper's setting is uniform approximation and Hölder balls, with parameters truncated to $O(1)$ magnitude. These conditions cover the main cases of smooth function approximation, but there is still room for extension: whether ERM over the truncated network class is easy to find in practical optimization (the optimization landscape problem), and whether the conclusions can be extended to non-uniform error or more general function spaces—the paper does not answer these.

From the perspective of theoretical progress, the main contribution of this work is providing a complete, order-optimal constructive proof and connecting the chain between approximation and statistics. For researchers interested in neural network expressiveness, nonparametric regression rates, or ReLU network theory, this is a paper worth reading carefully.

One-line Summary

ReLU networks achieve the information-theoretic optimal rate in approximating smooth functions, and ERM achieves the minimax regression rate without a logarithmic factor.

Paragraph Summary

This paper addresses a long-standing gap in ReLU network approximation of smooth functions: for any smoothness $s>0$ and dimension $D\ge1$, it constructs networks with width $O(N)$, depth $O(L)$, and parameter magnitude $O(1)$ that achieve uniform approximation error $(N^2L^2\log N)^{-s/D}$, with no fixed ratio required between width and depth. This rate matches the information-theoretic lower bound in its dependence on $s$ and $D$, differing only by constants and a logarithmic factor. The core of the construction is using high-order finite differences to encode the local Taylor coefficients of the target function, compressing information into network weights via a new encoding/decoding mechanism. As a statistical corollary, empirical risk minimization over the truncated network class achieves the minimax regression rate $n^{-2s/(2s+D)}$, eliminating the $\log n$ factor common in prior analyses. The paper also systematically reviews existing and new mechanisms in approximation techniques, offering reference value for theoretical researchers.