How can a neural network approximate all functions when the weights are not allowed to grow exponentially?

Question

It has been proven in the paper "Approximation by Superpositions of a Sigmoidal Function" (by Cybenko, in 1989) that neural networks are universal function approximators. I have a related question.

Assume the neural network's input and output vectors are of the same dimension $n$. Consider the set of binary-valued functions from $\{ 0,1 \}^n$ to $\{ 0,1 \}^n$. There are $(2^n)^{(2^n)}$ such functions. The number of parameters in a (deep) neural network is much smaller than the above number. Assume the network has $L$ layers, each layer is $n \times n$ fully-connected, then the total number of weights is $L \cdot n^2$.

If the number of weights is not allowed to grow exponentially as $n$, can a deep neural network approximate all the binary-valued functions of size $n$?

Cybenko's proof seems to be based on the denseness of the function space of neural network functions. But this denseness does not seem to guarantee that a neural network function exists when the number of weights are polynomially bounded.

I have a theory. If we replace the activation function of an ANN with a polynomial, say cubic one，then after $L$ layers, the composite polynomial function would have degree $3^L$. In other words, the degree of the total network grows exponentially. In other words, its "complexity" measured by the number of zero-crossings, grows exponentially. This seems to remain true if the activation function is sigmoid, but it involves the calculation of the "topological degree" (a.k.a. mapping degree theory), which I have not the time to do yet.

According to my above theory, the VC dimension (roughly analogous to the zero-crossings) grows exponentially as we add layers to the ANN, but it cannot catch up with the doubly exponential growth of Boolean functions. So the ANN can only represent a fraction of all possible Boolean functions, and this fraction even diminishes exponentially. That's my current conjecture.

Answer 1

What is Proven

The question references the proof of Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems.

The 1989 proof stated that the network, made of activations that were required to be, "Of continuous sigmoidal non-linearity," could, "Uniformly approximate any continuous function of n real variables," so, as the question stated, the proof doesn't directly apply to 1-bit discrete outputs. Note that the network is expected to merely approximate the desired circuit behavior.

The question defines the system as an arbitrary mapping from input bit vector

$I: { i_1, \; \dots, \; i_n}$

to output bit vector

$O: { o_1, \; \dots, \; o_n}$

It was further back proven that such a mapping can be accomplished with one Boolean expressions for each output bit. For all $2^n$ possible input vector permutations, there exists a Boolean expression made up of AND and NOT operations that calculates a result that matches any arbitrary logical truth table.

There are techniques for reducing redundancy in the array of Boolean expressions, which is critical to VLSI chip layout.

Without the retention of state anywhere in the network other than the attenuation matrix (parameters), the system is not Turing complete. However, with regard to the ability to realize Boolean expressions in describing the mapping, given an arbitrary number of layers, the network is complete.

Estimating Layer Depth Requirements

Only one inner layer is required in the 1989 proof, so how many layers would it take for an accurate n-bit-to-n-bit mapping to be learned?

The question proposes that there are $2^n$ to the power of $2^n$ permutations. The mapping of each input bit vector to the desired output bit state can be represented by a truth table of $n$ binary dimensions.

Each output is an independent bit, meaning the $2^n$-bit representations of unique Boolean functions that could produce each output bit is not tied to any other output channel. As would be expected, there are $2n$ freedoms of motion for the mapping of I to O.

For the case where the input is a bit vector of $n$ bits, where $n$ is the number of activations for any one of $L$ layers, the total number of activations in the network $a_t$ and the total number of scalar elements for all attenuation matrices (the parameters that represent training state) $q_t$ for the network is as follows.

$a_t = \sum_{\, 0 = v}^{L - 1} \; n_v$

$= n \, L$

$p_t = \sum_{\, 0 = v}^{L - 2} \; n_v^2$

$= n^2 \, (L-1)$

If IEEE 64 bit floating point numbers are used for each element in the attenuation matrix, we can calculate the number of bits available in the training parametrization.

$b_t = 64 \, (L - 1) \, n^2$

It would be normal today to use ReLU, leaky ReLU, or some other more quickly convergent activation instead of sigmoid for all layers but the last and use a simple binary threshold for the last.

Thus we have a formulation of the information theory comparison inferred by the question, and can reduce it.

$2^{2n} \le 64 \, (L - 1) \, n^2$

$L \ge 1 + \frac {2^{2n-6}} {n^2}$

This is a rough threshold. For a highly reliable training for the binary inputs to binary outputs, the number of layers should be well above the threshold.

Below the threshold the trainability of the mapping will degrade to an inadequate approximation for most applications because of signal saturation in the back propagation mechanism.