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

Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View
Aug 2, 2026Tong Mao, Jinchao XuNeural Approximations Approximation
King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia
Approximation Theory for Neural Networks: Old and New
May 20, 2026Soumendu Sundar Mukherjee, Himasish TalukdarNeural Approximations Approximation
Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata
Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression
Sep 22, 2026Baicheng Li, Zuowei Shen, Haizhao Yang +1Neural Approximations Approximation
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.

Aug 2, 2026, cs.LGJ/K move · Enter open · S save

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

Tong Mao, Jinchao Xu

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

Neural Approximations Approximation Neural Network Bits

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Approximation Theory for Neural Networks: Old and New

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