Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity

Zilan Cheng; Li-Lian Wang; Zhongjian Wang

cs.LGSep 28, 2026

Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity

Authors: Zilan Cheng, Li-Lian Wang, Zhongjian Wang

Organizations: Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore.

Abstract

We study the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate Hölder-continuous functions on $[0,1]^d$ and the associated encoding complexity. For $d\geq 2$ , we construct a fixed, explicitly defined activation function for which a closed-form network with two hidden layers of widths $d$ and $1$ achieves arbitrary accuracy in the uniform norm. We prove that $d+1$ is the exact minimum total number of hidden neurons among standard feedforward networks with locally integrable activations and affine outputs. We further give a simpler construction using a single elementary activation that combines the floor and exponential functions. This construction requires three hidden layers of widths $d$ , $1$ , and $2$ , only two neurons above the minimum. If a skip connection is allowed, widths $d$ , $1$ , and $1$ suffice. These constructions use explicit grid addressing and integer encoding of quantized function values. For a bounded $α$ -Hölder class, they require $O(\varepsilon^{-d/α}\log(1/\varepsilon))$ bits, matching the metric-entropy lower bound up to a logarithmic factor.

Figures & tables

Reference	Neurons	Depth	Activation	Parameters
[ 11 ]	$9d+3$	2	analytic sigmoidal	existence
[ 6 ]	$3d+2$	2	$C^{\infty}$ sigmoidal	existence
[ 3 ]	$3d+2$	2	computable $C^{\infty}$ sigmoidal	existence
[ 18 ]	$d+2$ (skip)	3	two: floor and analytic, elementary	existence
	$O(d^{2})$	$O(1)$	two: $\sin$ and $\arcsin$ , elementary	existence
	$O(d^{2})$	$O(1)$	$C^{1}$ sigmoidal, elementary	existence

Table 1 : Comparison of fixed-size universal approximators on

[0,1]^{d}

. Unless “two” is indicated, a single activation is used. ∗ Optimal among all locally integrable activations for

d\geq 2

(Theorem 3.4 ).

Panel of Figure 1 — Figure 1 : Position encoding with $M=3$ .

Figure 2 :

\varrho

[-2,S_{3})

, or equivalently,

[-2,0)\bigcup\big(\bigcup_{n=1}^{2}\bigcup_{j=0}^{(n+1)^{n}-1}\bigcup_{r=0}^{n-1}I_{n,j,r}\big)

Figure 3 : Architecture of the network

\Phi^{\varrho}_{f,\varepsilon}

in Theorem 3.1 . The

d

neurons in the first hidden layer quantize the input coordinates, whose weighted combination forms the cell address

r(\bm{x})

; the neuron in the second hidden layer decodes the corresponding quantized value from the stored integer

N_{f}

. The network has

d+1

hidden neurons in total.

Figure 4 : Numerical verification of Theorem 3.1 for the approximation of $f_{4}$ by $\Phi^{\varrho}_{f_{4},\varepsilon}$ . Top: The target function $f_{4}$ and the network outputs for $\varepsilon=2^{-1},2^{-2},2^{-3}$ ( $M=74,147,293$ ). Bottom: The sup-norm error over the $3{,}004$ test points versus $\varepsilon$ , and the absolute errors $|f_{4}-\Phi^{\varrho}_{f_{4},\varepsilon}|$ on a $161^{2}$ grid. The error plot additionally includes $\varepsilon=2^{-4},2^{-5}$ .

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5 :

\varrho_{c}

[-2,S_{3})

, to be compared with

\varrho

in Figure 2 . Each jump of

\varrho

at an integer

k

is replaced by a linear ramp on

(k-w_{k},k)

, of length

\tfrac{1}{2}

for

k\geq 0

and of geometrically shrinking length

2^{k-1}

for

k<0

$Q_{\ell}$	$\bm{x}^{(\ell)}$	$\ell$	$Q_{\ell}$	$\bm{x}^{(\ell)}$	$\ell$	$Q_{\ell}$	$\bm{x}^{(\ell)}$	$\ell$	$Q_{\ell}$	$\bm{x}^{(\ell)}$	$\ell$
$I_{1}\times I_{1}$	$(0,0)$	$(0)_{4}$	$I_{2}\times I_{1}$	$(\frac{1}{3},0)$	$(1)_{4}$	$I_{3}\times I_{1}$	$(\frac{2}{3},0)$	$(2)_{4}$	$I_{4}\times I_{1}$	$(1,0)$	$(3)_{4}$
$I_{1}\times I_{2}$	$(0,\frac{1}{3})$	$(10)_{4}$	$I_{2}\times I_{2}$	$(\frac{1}{3},\frac{1}{3})$	$(11)_{4}$	$I_{3}\times I_{2}$	$(\frac{2}{3},\frac{1}{3})$	$(12)_{4}$	$I_{4}\times I_{2}$	$(1,\frac{1}{3})$	$(13)_{4}$
$I_{1}\times I_{3}$	$(0,\frac{2}{3})$	$(20)_{4}$	$I_{2}\times I_{3}$	$(\frac{1}{3},\frac{2}{3})$	$(21)_{4}$	$I_{3}\times I_{3}$	$(\frac{2}{3},\frac{2}{3})$	$(22)_{4}$	$I_{4}\times I_{3}$	$(1,\frac{2}{3})$	$(23)_{4}$
$I_{1}\times I_{4}$	$(0,1)$	$(30)_{4}$	$I_{2}\times I_{4}$	$(\frac{1}{3},1)$	$(31)_{4}$	$I_{3}\times I_{4}$	$(\frac{2}{3},1)$	$(32)_{4}$	$I_{4}\times I_{4}$	$(1,1)$	$(33)_{4}$

Appendix

Table 2 : Position encoding example for

d=2

and

M=3

, where

I_{1}=[0,\frac{1}{3})

I_{2}=[\frac{1}{3},\frac{2}{3})

I_{3}=[\frac{2}{3},1)

, and

I_{4}=\{1\}

Figure 6 : Architecture of the elementary network

\Phi^{\sigma}_{f,\varepsilon}

in Theorem 4.1 . It has hidden-layer widths

(d,1,2)

and

d+3

hidden neurons in total.

Figure 7 : Architecture of the elementary network with a skip connection,

\Phi^{\sigma,\mathrm{skip}}_{f,\varepsilon}

, in Theorem 4.1 . It has hidden-layer widths

(d,1,1)

and

d+2

hidden neurons in total.

$f$	$\varepsilon$	$\delta$	$M$	$K$	$B$	$\operatorname{bit}(A_{f})$	$\operatorname{bit}(N_{f})$	$\displaystyle\tfrac{\operatorname{bit}(A_{f})}{K\log_{2}B}$	$\displaystyle\tfrac{\operatorname{bit}(N_{f})}{n\log_{2}(n+1)}$	$E_{\varrho}$	$E_{\sigma}$	$E_{\sigma,\mathrm{skip}}$
$f_{1}$	$2^{-1}$	$2^{-2}$	13	196	16	782	1 497	0.9974	1.0021	0.3275	0.3275	0.2611
$f_{1}$	$2^{-2}$	$2^{-3}$	26	729	32	3 643	6 938	0.9995	1.0006	0.1760	0.1760	0.1438
$f_{1}$	$2^{-3}$	$2^{-4}$	51	2 704	64	16 222	30 834	0.9999	1.0001	0.0912	0.0912	0.0762
$f_{1}$	$2^{-4}$	$2^{-5}$	101	10 404	128	72 826	138 847	1.0000	1.0000	0.0416	0.0416	0.0335
$f_{1}$	$2^{-5}$	$2^{-6}$	202	41 209	256	329 670	631 770	1.0000	1.0000	0.0223	0.0223	0.0186
$f_{1}$	$2^{-6}$	$2^{-7}$	403	163 216	512	1 468 942	2 826 326	1.0000	1.0000	0.0116	0.0116	0.0097

Appendix

Table 3 : Parameters, encoding bit lengths, and empirical errors for the three network constructions on

f_{1},\ldots,f_{6}

. The test set

\mathcal{X}_{\mathrm{test}}

contains

3{,}004

points for

f_{1},\ldots,f_{4}

and

3{,}008

points for

f_{5},f_{6}

. The empirical errors are

E_{\varrho}:=\max_{\bm{x}\in\mathcal{X}_{\mathrm{test}}}|f(\bm{x})-\Phi^{\varrho}_{f,\varepsilon}(\bm{x})|

E_{\sigma}:=\max_{\bm{x}\in\mathcal{X}_{\mathrm{test}}}|f(\bm{x})-\Phi^{\sigma}_{f,\varepsilon}(\bm{x})|

, and

E_{\sigma,\mathrm{skip}}:=\max_{\bm{x}\in\mathcal{X}_{\mathrm{test}}}|f(\bm{x})-\Phi^{\sigma,\mathrm{skip}}_{f,\varepsilon}(\bm{x})|

Figure 8 : Numerical verification of Theorem 3.1 for the approximation of the 2D function $f_{1}$ by the three-neuron network $\Phi^{\varrho}_{f_{1},\varepsilon}$ . The panels are arranged as in Figure 4 , with $\varepsilon=2^{-1},2^{-2},2^{-3}$ ( $M=13,26,51$ ); the error plot additionally includes finer networks down to $\varepsilon=2^{-7}$ .

Figure 9 : Numerical verification of Theorem 3.1 for the approximation of the 2D function $f_{2}$ by the three-neuron network $\Phi^{\varrho}_{f_{2},\varepsilon}$ . The panels are arranged as in Figure 4 , with $\varepsilon=2^{-1},2^{-2},2^{-3}$ ( $M=49,196,784$ ).

Figure 10 : Numerical verification of Theorem 3.1 for the approximation of the 2D function $f_{3}$ by the three-neuron network $\Phi^{\varrho}_{f_{3},\varepsilon}$ . The panels are arranged as in Figure 4 , with $\varepsilon=2^{-1},2^{-2},2^{-3}$ ( $M=76,152,304$ ); the error plot additionally includes finer accuracy down to $\varepsilon=2^{-5}$ .

Panel of Figure 11 — Figure 11 : Numerical verification of Theorem 3.1 for the approximation of the 3D function $f_{5}$ by the four-neuron network $\Phi^{\varrho}_{f_{5},\varepsilon}$ . From top to bottom, the panels show the $x_{1}x_{2}$ , $x_{2}x_{3}$ , and $x_{1}x_{3}$ sections, with the remaining coordinate fixed at $1/4$ . Within each panel, the top row contains the target and the network outputs for $\varepsilon=2^{-1},2^{-2},2^{-3}$ ( $M=16,32,63$ ), and the bottom row contains the corresponding absolute errors.

Panel of Figure 12 — Figure 12 : Numerical verification of Theorem 3.1 for the approximation of the 3D function $f_{6}$ by the four-neuron network $\Phi^{\varrho}_{f_{6},\varepsilon}$ . The sections and panels are arranged as in Figure 11 , with $\varepsilon=2^{-1},2^{-2},2^{-3}$ and $M=11,22,44$ .

Panel of Figure 13 — Figure 13 : Sup-norm errors for the three network constructions applied to $f_{1},\ldots,f_{6}$ , evaluated in exact arithmetic over $3{,}004$ test points for $f_{1},\ldots,f_{4}$ ( $d=2$ ) and $3{,}008$ test points for $f_{5}$ and $f_{6}$ ( $d=3$ ). Each test set consists of $2{,}000$ random points, $1{,}000$ boundary points, and the $2^{d}$ corners. The exact and elementary networks attain identical maximal errors and are therefore represented by a single curve, while the skip-connection network is shown separately. All errors remain below the prescribed accuracy $\varepsilon$ .

Explore similar work

Aug 2, 2026cs.LG

Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View

Traditional approximation theory measures convergence rates in terms of the number of parameters or degrees of freedom. However, practical computation operates under finite precision: parameters must be encoded using a finite number of bits. Therefore, approximation efficiency should be evaluated in terms of computational bit complexity, which is intrinsically connected to the metric entropy of the underlying function class. In this work, we develop a unified approximation framework based on binary encoding and metric entropy. We analyze classical methods (including polynomial approximation, sparse grids, and finite elements) as well as shallow and deep neural networks, and compare their approximation rates for function classes with comparable metric entropy. We observe that, when evaluated in terms of bits, most classical methods are in general suboptimal relative to the intrinsic limits dictated by metric entropy, while neural network methods may exhibit different behaviors. We show that when complexity is measured in bits rather than parameters, no method fundamentally exceeds the approximation order achieved by classical approaches. Our results also indicate that many seeming advantages of neural networks, including dimension-independent rates and superconvergence phenomena, stem from differences in function class complexity rather than intrinsic architectural superiority. In this sense, the traditional curse of dimensionality can be misleading; the fundamental limitation is instead a curse of bit complexity, governed by metric entropy.

Tong Mao, Jinchao Xu

King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia

Neural Approximations Approximation Neural Network Bits

Ask PDF

May 20, 2026cs.LG

Approximation Theory for Neural Networks: Old and New

Universal approximation theorems provide a mathematical explanation for the expressive power of neural networks. They assert that, under mild conditions on the activation function, feedforward neural networks are dense in broad function classes, such as continuous functions on compact subsets of

\mathbb{R}^d

L^p

spaces, or Sobolev spaces. Over the past four decades, these qualitative universality results have evolved into a rich quantitative theory addressing approximation rates, parameter efficiency, and the role of architectural features such as depth and width. This survey presents several glimpses into this theory. We review classical density results for single-hidden-layer networks, as well as quantitative bounds that relate approximation error to network size and smoothness assumptions on target functions. Particular emphasis is placed on depth--width trade-offs and on results demonstrating that deeper architectures can achieve superior parameter efficiency for structured function classes. In addition to standard feedforward neural networks, we also review recent developments on Kolmogorov--Arnold Networks (KANs), which offer an alternative architectural paradigm and whose approximation-theoretic properties have begun to attract significant theoretical attention.

Soumendu Sundar Mukherjee, Himasish Talukdar

Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata

Neural Approximations Approximation Neural Network Kolmogorov-Arnold Networks Multilayer Perceptrons Feed-Forward+1

Ask PDF

Sep 22, 2026stat.ML

Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression

The statistical accuracy of neural networks depends on both their approximation power and the complexity of the class fitted from data. While increasing network size is a natural way to improve approximation, parameter magnitude provides another resource whose role must be quantified in both respects. We establish a sharp width--magnitude tradeoff at fixed depth using one elementary bounded

1

-Lipschitz Dyadic--Triangular Activation. For the unit

β

-Hölder ball on

[0,1]^d

with

0<β\leq1

, the optimal

L^p

approximation error for

0<p<\infty

is of order

[N^2\log(eNT)]^{-β/d}

when the network width satisfies

N\geq2d+3

and the parameter magnitudes are bounded by

T\geq1

. Matching lower bounds hold for every fixed globally Hölder activation; its Hölder exponent affects the constants but not the rate. Under bounded design densities and independent centered sub-Gaussian noise, approximate least squares over the full clipped class at depth

23

attains the classical Hölder minimax risk

\mathcal{O}(M^{-\frac{2β}{2β+d}})

without logarithmic loss whenever

N^2\log(eNT)\asymp M^{\frac{d}{2β+d}}

, where

M

is the sample size. This yields a continuum of statistically optimal choices, ranging from unit parameter radius to fixed network size. At fixed size, four hidden layers with at most

8d+7

nonzero parameters give a near-optimal radius, while six layers with at most

8d+27

attain the optimal order

\log T=\mathcal{O}(η^{-d/β})

at approximation error

η

. The same decoding method also yields fixed-size Transformer approximation.

Baicheng Li, Zuowei Shen, Haizhao Yang +1

Department of Mathematics, University of Maryland, College Park, MD 20742-4015, USA. · Department of Mathematics, National University of Singapore, Singapore 119076. · Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China.

Neural Approximations Approximation Minimax Loss Function Network Science Trade-Off+1

Ask PDF