PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zilan Cheng, Li-Lian Wang, Zhongjian Wang

arXiv:2609.35628v1cs.LGcs.NEstat.ML

TL;DR

The paper studies the minimum hidden-neuron count for arbitrary-accuracy approximation of Hölder functions and the storage cost of fixed-size networks. It gives explicit constructions and proves a matching neuron-count minimum, with bit complexity near the information-theoretic lower bound up to a logarithmic factor.

  • Problem

    The paper asks how few hidden neurons suffice for arbitrary-accuracy approximation and how much parameter storage fixed-size approximators require.

    Source: §1 · pp. 1–2

  • Method

    The constructions use explicit activations and grid-based integer encodings of quantized function values.

    Source: §1 · p. 2

  • Results

    d + 1 hidden neurons are necessary and sufficient for the stated Hölder class, and construction bit complexity is Θ(ε^-d/α log(1/ε)) versus a lower bound of Ω(ε^-d/α).

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The constructions attain the minimum neuron count and are information-theoretically near-optimal in bit complexity up to a logarithmic factor.

    Source: §1 · pp. 2–3

    The results concern representational capacity rather than practical training; the lookup activation can be computationally expensive, and its encoding integers may exceed standard fixed-precision arithmetic.

    Source: §7 · p. 11

Abstract

from arXiv · show

We study the minimum number of hidden neurons required for arbitrary-accuracy approximation of multivariate H\"older-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 $\alpha$-H\"older class, they require $O(\varepsilon^{-d/\alpha}\log(1/\varepsilon))$ bits, matching the metric-entropy lower bound up to a logarithmic factor.

1 Introduction

The introduction asks how few neurons can support arbitrary-accuracy approximation and what fixed-size networks cost in stored bits. It presents an exact neuron-count result, simpler elementary-activation constructions, and near-optimal storage complexity.

1 Introduction

  • The prior smallest reported count was 3d + 2 neurons, while a smaller d + 2-neuron construction used different activations and skip connections.The introduction states that no lower bound beyond requiring the first layer to see the whole input was previously known.Source: §1 · p. 1
  • d + 1 hidden neurons are necessary and sufficient for arbitrary L∞ approximation of the stated Hölder class, using a two-layer (d, 1) network.The lower bound applies at any depth to networks with locally integrable activations; its proof uses a first-layer rank argument and the non-density of fixed-size sums of ridge functions.Source: §1 · p. 2
  • Θ(ε^-d/α log(1/ε)) bits suffice, while the stated lower bound is Ω(ε^-d/α), making the constructions near-optimal up to a logarithmic factor.Bit complexity is defined as the total binary length of rational network parameters.Source: §1 · p. 2
  • The optimal-count activation is an explicit but intricate piecewise-constant function that encodes digits of integers in every base.The paper also reports exact-arithmetic verification of its closed-form construction.Source: §1 · pp. 2–3
  • The single elementary activation yields explicit networks with d + 3 neurons, or d + 2 with one skip connection, and rational closed-form parameters.The activation is described as elementary when given by a finite formula in finitely many standard functions; these constructions permit exact-arithmetic evaluation.Source: §1 · pp. 2–3

2 Setting

The setting fixes the network architecture and activation while allowing parameters to depend on the target function and accuracy. Its constructions use grid cells and quantized function values to produce an approximation.

2 Setting

  • The Hölder-class setting uses dimension d, exponent α ∈ (0, 1], and positive parameters λ and R.R is assumed to be a positive integer when integer-valued network parameters are needed.Source: §2 · p. 3
  • A feedforward network applies an activation componentwise in hidden layers and uses an affine output from the final hidden layer.The setting also permits skip networks whose affine output depends on all hidden layers.Source: §2 · p. 3
  • For rational parameters, bit complexity is the total binary length of the network's weights and biases.The passage defines the binary length of integers and rationals, including a sign bit for rationals.Source: §2 · p. 4
  • Grid quantization assigns each input a cell address whose base-(M + 1) digits are the coordinate grid indices.The cells have representatives within 1/M in the infinity norm; Figure 1 illustrates position encoding with M = 3.Source: §2 · p. 4, Figure 1 · p. 5
  • The construction outputs the quantized value associated with the input's cell, with grid and quantization choices selected to keep the approximation error below ε.The stated scales are M = Θ(ε^-1/α), K = Θ(ε^-d/α), and B = Θ(ε^-1).Source: §2 · p. 4

3 Optimal neuron count: d + 1 hidden neurons

An explicit two-hidden-layer network of widths (d, 1) uses d + 1 neurons to approximate Hölder functions arbitrarily accurately in the uniform norm. For d ≥ 2, this count is optimal among the stated feedforward networks.

3.1 Sufficiency: an explicit (d, 1) network

  • For d ≥ 2, d + 1 hidden neurons are both sufficient and necessary for arbitrary-accuracy uniform approximation of the stated Hölder class.The construction uses widths (d, 1), and the lower bound applies across network depths.Source: §3.1 · p. 6, §3.2 · p. 7
  • The first layer quantizes input coordinates into a cell address, and one second-layer neuron decodes that cell’s quantized function value from an encoded integer.The activation uses a floor branch for addressing and a digit-extraction branch for decoding.Source: §3.1 · pp. 5–6

3.2 Necessity: no network with d hidden neurons is universal

  • No network with fewer than d + 1 hidden neurons achieves arbitrary accuracy: the first layer needs at least d neurons, while a fixed-width single-hidden-layer network is insufficient.These two activation-independent obstructions establish the lower bound for d ≥ 2.Source: §3.2 · p. 7
  • The optimal-count result is scoped to d ≥ 2; for d = 1, a single hidden neuron can suffice, and continuous activations cannot attain the optimal count for uniform approximation at least when d = 2.For d = 2, the continuous-activation obstruction concerns three neurons without skip connections; continuous activations can achieve arbitrary accuracy in Lp for finite p.Source: §3.2 · p. 7

4 Elementary activation: d + 3 neurons (or d + 2 with a skip)

The elementary activation combines floor and exponential operations to retrieve quantized values stored as digits of a base-B integer. The construction uses d+3 hidden neurons, or d+2 with a skip connection, with rational parameters given in closed form.

4 Elementary activation: d + 3 neurons (or d + 2 with a skip)

  • The elementary activation replaces the lookup mechanism with radix arithmetic, retrieving a quantized value by extracting the digit indexed by the input’s grid address.The stored values form a base-B integer; digit recovery uses floor operations, motivating an activation that combines floor and exponential functions.Source: §4 · pp. 7–8
  • The no-skip network has widths (d, 1, 2), or d+3 hidden neurons, with the floor and exponential branches selected by its pre-activations.The hidden-layer operations produce the addressed quantized value for the affine output.Source: §4 · p. 8
  • With a skip connection, the network has widths (d, 1, 1), or d+2 hidden neurons, because the second-layer value’s fractional part contributes less than the quantization step.The output can read the second hidden layer directly, dispensing with one third-layer neuron.Source: §4 · p. 8
  • Both constructions use a single shared elementary activation and rational parameters specified in closed form.The skip variant is defined alongside the no-skip construction in Theorem 4.1.Source: §4 · p. 8

5 Bit Complexity of Fixed-Size Approximators

The paper measures the storage cost of fixed-size approximators by the binary length of their rational parameters. Its constructions are optimal up to a logarithmic factor, while a lower bound makes polynomial storage in accuracy unavoidable.

5 Bit Complexity of Fixed-Size Approximators

  • The target function is encoded by a single integer, whose size grows as the prescribed accuracy improves.Bit complexity is computed from the rational network parameters, including the encoding integer.Source: §5 · pp. 8–9
  • The constructions’ bit complexity is Θ(ε^-d/α log(1/ε)), matching the information-theoretic lower bound up to a logarithmic factor.The lower bound is Ω(ε^-d/α), so the polynomial storage requirement cannot be removed for finite-bit implementations of fixed-size universal approximators.Source: §5 · p. 9
  • These superexpressive activation-based network classes have infinite VC dimension, so neuron or parameter counts alone do not control their statistical complexity.The passage establishes this for the (d, 1) class and the classes in Theorem 4.1.Source: §5 · p. 9

6 Numerical verification in exact arithmetic

The authors evaluate the explicit constructions in exact arithmetic on selected two- and three-dimensional targets. Across the tested points and accuracies, observed errors stay below ε, as guaranteed by the theorem.

6 Numerical verification in exact arithmetic

  • Exact-arithmetic evaluation checks the construction for d=2 and d=3, where encoding integers can reach about 10^7 bits and require arbitrary precision.The targets include four functions on [0,1]^2 and two on [0,1]^3; the finest tested accuracy was chosen so bit(Nf) was on the order of 10^7 bits.Source: §6 · pp. 9–11
  • Figure 4 displays f4, network outputs, and pointwise errors at ε=2^-1, 2^-2, and 2^-3, with maximal errors plotted across additional tested accuracies.The pointwise-error display uses a 161-by-161 grid, while maximal errors are computed over the full test set.Source: §6 · p. 10, Figure 4 · p. 10
  • All observed errors are below ε on the exactly represented test points for the evaluated two- and three-dimensional targets.The test sets include random dyadic points, boundary points, and corners; the reported maximum is over 3,004 points for d=2 and 3,008 for d=3.Source: §6 · p. 10

7 Discussion

The discussion distinguishes representational capacity from practical training and identifies unresolved questions about neuron counts, activation regularity, and storage complexity. Appendix arguments support the activation’s digit extraction and the lower-bound results.

7 Discussion

  • The constructions establish representational capacity, but their integer encodings may exceed standard floating-point precision, and evaluating the lookup activation can be computationally expensive.The authors distinguish these results from practical gradient-descent-based function fitting.Source: §7 · p. 11
  • Open questions include attaining d+1 neurons with an elementary discontinuous activation, finding the continuous-activation uniform minimum, and removing the logarithmic storage factor.The paper also asks whether d+2 neurons can suffice without a skip connection.Source: §7 · p. 11

A Details of Section 3.1

  • The activation is well defined because its indexed unit intervals partition successive blocks, and its digit-extraction identity recovers the selected base-(n+1) digit.The proof also establishes local boundedness, Borel measurability, and local integrability.Source: A Details of Section 3.1 · pp. 12–13

B.1 Proof of Proposition 3.2

  • When the first layer has fewer than d neurons, a kernel direction leaves its output unchanged while the constructed Hölder function changes by ζ2^-α.This supplies an error lower bound for networks whose first layer cannot distinguish those inputs.Source: §B.1 · p. 13

B.2 Proof of Proposition 3.3

  • For the one-hidden-layer lower bound, directional derivatives annihilate the ridge terms, while the corresponding derivative of a smooth test function yields a positive uniform error bound.The proof rescales the test function into the Hölder class before applying the bound.Source: §B.2 · p. 14

B.3 Proof of Theorem 3.4

The proof establishes that arbitrary-accuracy approximation requires at least d + 1 hidden neurons, matching the construction’s neuron count. The accompanying parameter lists specify the Section 4 constructions and their skip variant.

B.3 Proof of Theorem 3.4

  • The lower-bound proof treats architectures of depth at least two and depth one as separate cases, ruling out arbitrary-accuracy approximation in each.The cases use the obstructions from Propositions 3.2 and 3.3, respectively.Source: §B.3 · p. 15
  • |n| ≥ d + 1: no feedforward network with at most d hidden neurons and locally integrable activation achieves arbitrary-accuracy approximation.For depth at least two, the first layer has fewer than d neurons; the one-layer case is handled separately.Source: §B.3 · p. 15

C Details and Proofs of Section 4

  • The Section 4 parameter lists give weights and biases for the constructions, including a skip variant whose listed parameters are integers or dyadic rationals.The skip-variant list specifies output weights on v and wskip and its output bias.Source: C Details and Proofs of Section 4 · p. 15

C.1 Proof of Theorem 4.1

The approximation bound combines quantization on each grid cell with the Hölder variation between a point and its cell representative. The network’s grid-cell output differs from the quantized value by less than δ.

C.1 Proof of Theorem 4.1

  • The grid-cell output is bfℓ + δηℓ, with 0 ≤ δηℓ < δ, while the target value at the cell representative differs from bfℓ by less than δ.These bounds compare the network output and the quantized target at x(ℓ).Source: §C.1 · p. 15
  • At each grid representative x(ℓ), the network’s error is less than δ by comparing the two δ-sized quantization offsets.The passage expresses the difference as |(f(x(ℓ)) − bfℓ) − δηℓ|.Source: §C.1 · p. 15
  • Within a grid cell, the Hölder variation is bounded by λM^-α ≤ ε/2, which combines with the grid-representative estimate to establish the claimed error bound.The proof uses the triangle inequality to pass from x(ℓ) to x.Source: §C.1 · p. 15

D Proof of Theorem 5.1

The bit-complexity analysis bounds the encoding cost of the integer function code and network parameters for fixed d, α, λ, and R. The section also establishes that continuous activations cannot achieve arbitrary-accuracy uniform approximation with the (2, 1) architecture.

D Proof of Theorem 5.1

  • For fixed d ≥ 2, α, λ, and R, the encoding parameter scales satisfy M = Θ(ε^-1/α), K = Θ(ε^-d/α), B = Θ(ε^-1), and log2 B = Θ(log(1/ε)).These asymptotics are considered as ε tends to zero.Source: D Proof of Theorem 5.1 · p. 15

D.1 Bit complexity of Af

  • The integer code Af has at most O(ε^-d/α log(1/ε)) bits uniformly over the bounded Hölder class.The bound follows from bit(Af) ≤ K log2 B.Source: §D.1 · p. 15

D.2 Bit complexity of Φσ f,ε and Φσ,skip

  • The parameter-count analysis bounds the network encoding costs using bit(Af) and O(d^2 log(1/ε)) contributions from earlier layers.The third and output layers contribute O(bit(Af) + log(1/ε)); the stated parameter lists include the skip variant.Source: §D.2 · pp. 15–16

D.3 Bit complexity of Φϱ

  • bit(Nf) = Θ(ε^-d/α log(1/ε)) for every f in the class, giving a matching-order lower bound on this integer encoding length.The argument uses n = K = Θ(ε^-d/α) for small ε.Source: §D.3 · p. 16

E Continuous activations: uniform obstruction and Lp construction

  • A continuous activation does not suffice for arbitrary-accuracy uniform approximation with d + 1 hidden neurons, already when d = 2.The paper identifies the discontinuity of the activation in Theorem 3.1 and states this obstruction for continuous activations.Source: E Continuous activations: uniform… · p. 16

E.1 A uniform-approximation obstruction for (2, 1) networks

  • For d = 2, every continuous-activation architecture with widths (2, 1) has a positive uniform-approximation error gap for a function in the Hölder class.The proof derives an absolute positive gap for the constructed function, then rescales it into the class.Source: §E.1 · pp. 16, 18, 19

E.2 Lp approximation with d + 1 hidden neurons

A fixed continuous activation supports Lp approximation with the (d, 1) architecture by smoothing jumps over geometrically shrinking intervals on the negative axis. The construction retains the stated bit-complexity order of the discontinuous-activation uniform-norm construction.

E.2 Lp approximation with d + 1 hidden neurons

  • ϱc smooths the jumps of ϱ over transition intervals whose lengths shrink geometrically along the negative axis.The first-layer arguments are shifted into the negative axis so the total length of the transition intervals there is negligible.Source: §E.2 · p. 19
  • Outside the exceptional set Λ, the construction recovers the grid indices and integer code, yielding the stated pointwise error bound there.For all x, the passage also bounds z(x) between 0 and n.Source: §E.2 · p. 20
  • The fixed continuous activation ϱc supports Lp approximation to accuracy ε with hidden-layer widths (d, 1).The activation is independent of f, ε, p, and d.Source: §E.2 · p. 20
  • For d ≥ 2, the continuous-activation Lp construction has the same asymptotic bit complexity as the discontinuous-activation L∞ construction.The dominant term bit(Nf) is unchanged at Θ(ε^-d/α log(1/ε)).Source: §E.2 · p. 21

F Additional Figures and Tables

Appendix F collects examples of position encoding, network architectures, and numerical verification for the constructions. Its results include empirical errors below the prescribed accuracy on the reported test sets.

Position encoding and architectures

Numerical results (Figures 8–13)

  • Table 3 reports parameters, encoding bit lengths, and empirical errors for three constructions on f1–f6.Its test sets contain 3,004 points for f1–f4 and 3,008 points for f5–f6.Source: Table 3 · p. 22
  • Figures 8–10 report numerical verification of Theorem 3.1 for approximating 2D functions f1–f3 with three-neuron networks, at respective M values 13, 26, 51; 49, 196, 784; and 76, 152, 304.Source: Figure 8 · p. 23, Figure 9 · p. 23, F Additional Figures and Tables · p. 23
  • All empirical errors remain below the prescribed accuracy ε across the reported test sets for f1–f6.The exact and elementary networks have identical maximal errors; the skip-connection network is shown separately.Source: Figure 13 · p. 26

Related papers

Loading 2609.35628v1…