Size and depth of monotone neural networks: interpolation and approximation
This addresses theoretical limitations in neural network design for monotone functions, which is incremental but relevant for domains like economics or optimization.
The paper tackles the expressive power and efficiency of monotone neural networks with non-negative weights, showing that any monotone function over [0,1]^d can be approximated within arbitrarily small error by a depth-4 network, improving upon the previous depth of d+1 for d>3, and finds that some monotone functions require exponential size in monotone networks but are efficient in unrestricted networks.
We study monotone neural networks with threshold gates where all the weights (other than the biases) are non-negative. We focus on the expressive power and efficiency of representation of such networks. Our first result establishes that every monotone function over $[0,1]^d$ can be approximated within arbitrarily small additive error by a depth-4 monotone network. When $d > 3$, we improve upon the previous best-known construction which has depth $d+1$. Our proof goes by solving the monotone interpolation problem for monotone datasets using a depth-4 monotone threshold network. In our second main result we compare size bounds between monotone and arbitrary neural networks with threshold gates. We find that there are monotone real functions that can be computed efficiently by networks with no restriction on the gates whereas monotone networks approximating these functions need exponential size in the dimension.