Optimal approximation of smooth functions by ReLU neural networks

1 Introduction

• The introduction frames quantitative network-size and accuracy bounds as a central approximation problem, beyond qualitative universal approximation results.The cited universal approximation theorems establish approximation of continuous functions on compact sets but do not quantify the required network size or achievable accuracy.Source: §1 · p. 1
• Earlier work approached the benchmark but retained overheads in width or depth, or did not track or tightly bound parameter magnitudes.The cited constructions include exceptions for particular smoothness or dimension settings.Source: §1 · p. 2
• The explicit ReLU construction has width O(N), depth O(L), and parameter magnitude O(1), with no imposed relation between width and depth.Source: §1 · p. 3
• Higher-order finite-difference bounds make local Taylor coefficients more compressible: the construction stores quantized differences and reconstructs coefficients by a segmented discrete Taylor–Newton recursion.For D ≥ 2, Hermite interpolation bridges preserve the difference bounds when flattening the coefficient grid.Source: §1 · p. 3
• The paper presents the construction and proof ideas in an expository section, alongside simplified reviews of established techniques.Detailed proofs are placed in the appendices.Source: §1 · p. 3

2 Setup and Notation

• Uniform norms and the modulus of continuity provide notation for measuring function size and variation over nearby points.The modulus takes the supremum of |f(x) − f(y)| over points within a specified sup-norm distance.Source: §2 · p. 3
• The Hӧlder class is defined through smoothness and boundedness conditions, with order s−1 derivatives required to be Lipschitz when s is an integer.The setup takes m = ⌈s⌉−1 and requires the functions to be m times continuously differentiable.Source: §2 · p. 4
• The paper considers fully connected feedforward networks with ReLU activation and defines their depth, maximum width, and parameter magnitudes.Layer weights and biases determine each layer’s maximum parameter magnitude.Source: §2 · p. 4
• The notation eF scales width, depth, and parameter bounds by a constant independent of those bounds.That constant may depend on the target function’s smoothness and dimension.Source: §2 · p. 4
• Covering numbers count the smallest finite ε-cover of a function class, and their logarithms are called metric entropy.The setup also uses ≲, ≳, and ≍ for comparisons up to constants, with unqualified logarithms taken to be natural.Source: §2 · p. 4

3.1 Optimal Approximation

• Width O(N), depth O(L), and parameter magnitude O(1) achieve uniform error of order (N^2L^2 log N)^(-s/D), with no width–depth relation required.Source: §3.1 · p. 5
• For s>1, the rate improves prior bounds; general-s predecessors missed a factor (log N)^(s/D) and incurred entropy or depth overheads.Source: §3.1 · pp. 5–6
• The lower bound matches ϵN,L even for parameters growing polynomially in width, making this the exact approximation rate in that regime.Source: §3.1 · p. 5
• When CϵN,L < 1/4, no class attaining this accuracy has smaller metric entropy, up to constant factors.Source: §3.1 · pp. 5–6
• If log B ≫ log N, parameter growth adds entropy beyond what is needed; optimality against arbitrary parameters is shown when L ≤ poly(N), while larger-depth regimes remain open.Source: §3.1 · p. 6

3.2 Statistical Consequence

• Approximate ERMs over clipped network classes attain a minimax-optimal regression rate for, e.g., uniform designs, removing polylogarithmic factors from previous bounds.Source: §3.2 · p. 7

4.1 The Canonical Taylor-Network Construction

• The canonical network localizes each input to a grid cell, retrieves its Taylor coefficients, evaluates and sums local monomials, then smooths errors near cell boundaries.Coefficient retrieval is the information bottleneck: treating coefficients as unrelated values leaves a logarithmic gap, addressed by higher-order differences and Hermite-bridge flattening.Source: §4.1 · p. 8

4.2 Piecewise-Linear Interpolation

• Width O(N) and depth O(L) suffice to fit N^2L knots using piecewise-linear interpolation, extended to N^2L knots by accumulating increments across blocks.The interpolation result assumes polynomially bounded knot locations and values and minimum knot spacing at least (NL)^−p.Source: §4.2 · p. 9

4.3 Storing and Retrieving Local Taylor Coefficients

• Encoded retrieval stores batches of coefficients as digit strings, but storing each coefficient independently at accuracy K^−s costs order log(NL) digits and creates logarithmic overhead.The paper extends digit extraction to bases ζ ≥ 3 with a reduced alphabet, enabling bounded integers to be stored directly.Source: §4.3 · pp. 10–11

4.4 Higher-Order Point Fitting

• For s > 1, higher-order smoothness makes values more compressible, enabling width N and depth L to fit J ≍ N^2L^2 log N smooth values, with labels supplying the log N factor.The network parameters remain bounded by a factor polylogarithmic in N and independent of L.Source: §4.4 · pp. 12, 14

4.5 Smooth Flattening of Coefficient Tables

• Hermite bridges inserted between lexicographically ordered grid rows preserve the finite-difference bounds needed to flatten multivariate coefficient arrays for smooth point fitting.The coefficient function for multi-index α has remaining smoothness s − ∥α∥1, which determines its target accuracy and difference order.Source: §4.5 · pp. 14–16

4.6 Monomials, Localization, and Smoothing

• The remaining modules are standard ReLU constructions, reviewed for completeness and to track parameter magnitudes.Source: §4.6 · p. 16

4.6.1 Squares, Multiplication, and Monomials

• Polarization turns square-function networks into approximate multiplication modules, which can be chained to approximate monomials while tracking parameter magnitudes.The square construction is expressed using the sawtooth, and explicit magnitude tracking supports sharp entropy bounds.Source: §4.6.1 · pp. 16–17

4.6.2 Localization

• A staircase localization network returns the lower grid corner away from thin boundary strips, enabling cellwise Taylor approximation.The multivariate map is exact on most of the cube but can fail in the exceptional strip region.Source: §4.6.2 · pp. 17–18

4.6.3 Median Smoothing

• Median smoothing evaluates one network at 2D + 1 diagonal shifts, so at most D values are corrupted and the median remains close to the target.The error is bounded by ε + ω_f(Dδ); the median can also be computed exactly without sorting, using differences of sums of largest entries.Source: §4.6.3 · pp. 18–19

4.7 Completing the Proof

• Combining coefficient fitting, monomial networks, localization, and median smoothing gives a uniform error bound on the whole cube, with parameter magnitudes transferred to at most 1.The transfer preserves the width and depth orders.Source: §4.7 · p. 20

5 Discussion

• (N^2L^2 log N)^-s/D is the exact approximation rate for Hölder balls, attained with bounded parameters and no width–depth constraint.Suitable network classes also yield the minimax regression rate without redundant polylogarithmic factors.Source: §5 · p. 20
• The lower bound establishes optimality when parameters grow at most polynomially in width, while whether large parameters help when log L ≫ log N ≫ 1 remains open.In that regime, the best-known upper and lower bounds on ReLU VC dimension diverge.Source: §5 · pp. 20–21
• The analysis covers Hölder-smooth targets without further structure; adapting the construction to compositional functions or classes of low-dimensional sets remains an open direction.The paper notes that the latter adaptation is unresolved for which classes of sets.Source: §5 · p. 21
• Smoothness improves approximation efficiency twice: it reduces the Taylor remainder and makes local Taylor coefficients more compressible.The paper proposes that information stored in a network may inherit target regularity and be compressed accordingly.Source: §5 · p. 21

AI Use Statement

• The final write-up used models to check, simplify, and restructure proofs and auxiliary results, generate expository figures, and polish the text.The main results and proof strategies were developed in summer 2025; the final write-up began around May 2026.Source: AI Use Statement · p. 21

Appendix A. Network Calculus

• Appendix A establishes closure of bounded-parameter network classes under parallelization, composition, padding, and affine combination for fixed collections.It also presents a magnitude-to-width transfer, trading parameter magnitude for width rather than added depth.Source: Appendix A · pp. 23–24

Appendix B. Proofs of the Propositions in Section 4

• Appendix B presents proofs of the propositions from Section 4 in their order of appearance.Source: Appendix B · p. 26

B.1 Proof of Proposition 4.1

• The two-layer interpolation lemma represents a piecewise-linear interpolant through separated data points, with parameter magnitude bounded in terms of knot spacing, label range, and knot count.Its assumptions include constant extension outside the interpolation interval.Source: §B.1 · p. 26
• The proof groups knots into at most 2L blocks, constructs blockwise interpolation increments, and telescopes them to recover the target interpolant.Input rescaling ensures a separation of at least (NL)^-2p; padding blocks preserves the interpolant.Source: §B.1 · p. 28
• The normalized interpolant is realized with width 4N and depth 2K, then rescaled with bounded parameters to meet the stated depth bound.The displayed bound is (⌈5p⌉ + 18)L.Source: §B.1 · p. 28

B.2 Proof of Proposition 4.2

• For each leading-digit word b, the proof associates a prefix value t_b and bounds the contribution of subsequent digits to locate its admissible input interval.The tail bound uses the restriction that digits are at most ζ − 2.Source: §B.2 · pp. 28–29
• The network is designed to output the leading digits b together with the affine remainder ζ^n(θ − t_b).Source: §B.2 · p. 28
• Figure 8 shows admissible inputs in shaded intervals: the first two coordinates are constant within each interval, while the remainder coordinate is affine.Across the gaps, all coordinates are affine; the resulting map has slopes bounded by ζ^(n+2) and is realized by a ReLU network.Source: Figure 8 · p. 29, §B.2 · p. 29

B.3 Proof of Proposition 4.3

• Base-ζ digit storage of shifted h-th differences lets the decoder reconstruct rounded sequence values by recursively evaluating a discrete Taylor formula.Under the stated sequence bounds, the decoder returns y_k for k=1,...,T.Source: §B.3 · p. 30

Step 1: Segment recursion

• Each segment processes q positions, using stored differences to compute their values and update the finite-difference state for the next segment.The decoder composes L such segments.Source: Step 1: Segment recursion · p. 30, Figure 9 · p. 31

Step 2: Component networks

• The segment recursion is implemented with networks for difference streaming, the discrete Taylor maps Y and U, and a gate that selects the requested position.The stream network supplies the stored differences; Y and U compute values and updated state.Source: Step 2: Component networks · pp. 31–32

Step 3: Segment network and decoder

• Only the segment containing k contributes y_k; other segments are gated to zero, yielding a segment network with width and weights of order at most N.Composing L segment networks gives the decoder.Source: Step 3: Segment network and decoder · p. 32

Step 1: Block decomposition

• The sequence indices are partitioned into consecutive blocks of length at most Lq, and networks recover each block index and within-block position from i/J.The staircase ϕ_block and sawtooth ϕ_pos provide those indices.Source: Step 3: Segment network and decoder · p. 32, Step 1: Block decomposition · pp. 33–34

Step 2: Fitting the blocks

• Rounding each block permits the common decoder to fit its values, while interpolated block parameters combine the fits into a network in the claimed class.The rounding error is bounded by λ; the resulting network belongs to eF_1,1(N,L,N).Source: Step 2: Fitting the blocks · p. 34

B.4 Proof of Proposition 4.4

• For each multi-index, derivative samples on the grid are organized into K^(d−1) rows, each containing K values as one coordinate varies.In two dimensions, fixing the second grid coordinate defines each row.Source: §B.4 · pp. 34–35
• Hermite interpolation bridges neighboring row functions so the joined function is C^(h−1) with uniformly bounded derivatives through order h−1.Endpoint derivatives determine each bridge polynomial of degree at most 2h−1.Source: §B.4 · p. 35
• The resulting sequence preserves the embedded grid samples while satisfying finite-difference bounds that scale with the grid resolution.The proof extends the row construction to higher dimensions and handles K<h+1 separately.Source: §B.4 · pp. 35–37

B.5 Proof of Proposition 4.5

• Normalized Taylor-coefficient arrays are embedded into sequences whose finite differences obey bounds determined by grid resolution and derivative order.Proposition 4.3 is applied to fit the coefficients, and the resulting coefficient networks satisfy the stated bound.Source: §B.5 · p. 37

B.6 Proof of Proposition 4.6

• A dyadic linear interpolant of x^2 yields a square network, which is combined into a multiplication network and composed to form monomial networks.The monomial construction carries input coordinates through identity units and gives width at most (D+6)N with depth at most 4kL.Source: §B.6 · pp. 38–39

B.7 Proof of Proposition 4.7

• The bounded-weight staircase construction extends the approach of Shen et al. (2022, Proposition 3.1) by realizing a fine staircase through two nested coarser staircases.The resulting network has width O(N), depth O(L), and weight bound O(N).Source: §B.7 · p. 39

B.8 Proof of Proposition 4.8

• Taking the median of 2D+1 shifted evaluations gives error at most ε + ω_f(Dδ).The proof realizes this median construction with parallel copies of the approximant and a combining network.Source: §B.8 · p. 40

C.1 Proof of Theorem 3.1

• The final-network proof assumes K is sufficiently large after handling the small-K case with the zero network, and then constructs the network in Fig. 1.The small-K case is bounded using the stated condition on N, L, and q.Source: §C.1 · p. 40

Step 1: Parameters and coefficient retrieval

• Coefficient networks are clipped to [−1,1] without increasing their approximation error before they are used in the construction.The coefficient-network width grows by a factor O(Dm).Source: Step 1: Parameters and coefficient… · p. 41

Step 2: Localization

• A staircase network localizes inputs to grid cells, with D parallel staircases increasing the width by a factor D.Outside the localized region, the proof expresses the input as a grid point plus an offset.Source: Step 2: Localization · p. 41

Step 3: Product and monomial networks

• Monomial networks approximate u^α uniformly with error O(N^−⌈5s/D⌉L), bounded by K^−s.The networks take values in [0,1].Source: Step 3: Product and monomial networks · p. 41

Step 4: Local Taylor approximation

• The local Taylor-term error is bounded by combining coefficient and monomial approximation errors, each scaled using the local offset.The proof uses the coefficient bound and |u^α| ≤ K^−||α||_1.Source: Step 4: Local Taylor approximation · p. 42

Step 5: Smoothing

• Smoothing increases width by a factor 2D+1 and adds O(log D) layers, after which parameter magnitudes are reduced to one.The other constants depend only on s and polynomially on D.Source: Step 5: Smoothing · p. 42

• An ϵ-cover of G yields a 3ϵ-cover of H when every element of H is within ϵ of G.The proof selects an approximant in G within 2ϵ, then applies the triangle inequality to the cover of G.Source: §C.2 · p. 42
• Combining approximation-to-covering conversion with entropy bounds for Hölder balls and ReLU networks gives the stated covering-number comparison.The network-side bound scales as N^2L^2 log(NB) + N^2L log(1/e_N,L,B).Source: §C.2 · p. 43
• Both quantities in (3.2) are of order N^2L^2 log N.This is the entropy comparison used for the optimality results.Source: §C.2 · pp. 42–43

• Because clipping is nonexpansive in the uniform norm, a cover of F_{N_n,L_n} induces a cover of G_n.The proof then applies the covering-number bound of Ou and Bölcskei (2026, Theorem 2.1).Source: §C.3 · p. 44
• The constant A depends only on s and D, and log(1/r_n) is bounded by a constant multiple of L_n log N_n.The latter follows from (3.4).Source: §C.3 · p. 44
• For the finitely many n with Cr_n ≥ 1/2, the claim holds trivially because the uniform estimation error is at most 2.Source: §C.3 · p. 44