Nonlinear Approximation via Compositions

Nonlinear approximation, formalized prominently by DeVore, selects dictionary elements adaptively rather than using one fixed linear space. Wavelets, radial basis functions, adaptive splines, and compressed sensing established the value of sparse representations. For Besov-type smoothness s, earlier constructions achieve roughly O(N^{-s/d}), while Xie and Cao obtained O(N^{-1/(2d)}) for Lipschitz functions. ReLU approximation studies by Yarotsky, Petersen–Voigtlaender, and others proved strong expressivity, but often used unknown constants, sufficiently large depth, or sufficiently large N. This paper targets explicit fixed-depth rates.

Define ε_L,f(N)=min_{φ∈D_L}||f−φ||, where D_L is a width-N, depth-L ReLU FNN dictionary. The bottleneck is to determine whether compositions improve the exponent of N, for which regularity classes, and at what depth the benefit saturates. The problem is hard because breakpoints and weights are jointly adaptive, ReLU compositions are nonlinear, and the target class may contain merely Hölder functions. A useful result must be explicit for arbitrary N, not only asymptotic or existential.

• �� It proves explicit bounds: 2νN^{-2α} for d=1,L≥2 and 2(2√d)^ανN^{-2α/d} for d>1,L≥3. • It analyzes network structure directly instead of encoding polynomial or spline approximants. • It establishes a general one-dimensional rate-doubling principle, O(N^{-η})→O(N^{-2η}). • It identifies depth saturation at L>3 in the N exponent. • It studies approximation efficiency under parallel hardware, linking mathematical expressivity to implementation cost.

• �� Define the dictionary atom as T^(L)∘⋯∘T^(1), with T^(i)(x)=σ(W_ix+b_i), uniform hidden width N, and a final linear map g. Input: target f and budget N; output: best φ in D_L. • Establish the one-layer base case. Lemma 2.1 proves that a width-N scalar-input ReLU network realizes CPL(N+1), with prescribed breakpoints and interpolation values. • Build the two-layer mechanism. Lemma 2.2 takes m(n+1)+1 samples and constructs a width-[2m,2n+1] network. A base function g0 fits coarse samples; pairs g_k^+,g_k^- selectively remove positive and negative residuals. • Control the residual recursively: f_{k+1}=f_k−σ(g_k^+)+σ(g_k^-). After n stages, all designated sample values vanish and the remaining support contracts to a don’t-care region. • For Hölder f, interpolate on a grid and use |f(x)−f(y)|≤ν||x−y||_2^α. The resulting grid scale gives N^{-2α} in one dimension and N^{-2α/d} in d dimensions. • Compare layer dependencies and parallel execution costs.

The paper is primarily theoretical. Lemmas 2.1 and 2.2 and Theorem 3.1 provide constructive guarantees; Section 4 contains numerical tests of parallel computation. The supplied text gives no named datasets, sample counts, hardware specification, optimizer settings, or complete result table, so no dataset score can be responsibly reported. Evaluation is expressed through L1 approximation error, width N, depth L, dimension d, Hölder order α, and constant ν. There is no conventional supervised-learning ablation table.

The central quantitative comparison is between the usual shallow scale O(N^{-α/d}) and the compositional scale O(N^{-2α/d}). In d=1, depth two already gives the explicit bound 2νN^{-2α}; in d>1, depth three gives 2(2√d)^ανN^{-2α/d}. The arbitrary-function corollary is stronger in scope than the Hölder theorem: any one-dimensional O(N^{-η}) dictionary rate can be squared in exponent. Adding layers beyond three does not improve the asymptotic N exponent.

The theory can guide sparse neural representations for low-regularity scientific functions, numerical PDE surrogates, compression, denoising, and adaptive approximation. Practitioners need an estimate of α, dimension d, a target norm, and an optimizer capable of finding a near-best network. The parallel-computing conclusion is directly relevant to GPU or multicore implementations: when available cores exceed N, wide shallow architectures can expose more independent work than very deep narrow chains.

The bounds describe approximation capacity, not the outcome of training. Finding the constructive weights may be difficult, and backpropagation, initialization, finite data, regularization, and generalization are not analyzed. Uniform-width assumptions may be inefficient for anisotropic functions, while grid-based multidimensional constructions retain dimension dependence. The provided paper text does not establish standard dataset performance, and the parallel claim depends on hardware, memory bandwidth, synchronization, and communication costs. Future work should integrate approximation and optimization theory, test nonuniform architectures, and extend the rate-doubling principle to higher dimensions and other activations.