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

arXiv:2609.35628v1 Announce Type: new Abstract: We study the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate Holder-continuous functions on [0,1]^d and the associated encoding complexity. For dgeq 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 alpha-Holder class, they require O(arepsilon^{-d/alpha}log(1/arepsilon)) bits, matching the metric-entropy lower bound up to a logarithmic factor.

Source: arXiv cs.LG | 2026-09-29