Neural networks and rational functions

Abstract

Neural networks and rational functions efficiently approximate each other. In more detail, it is shown here that for any ReLU network, there exists a rational function of degree $O(\text{polylog}(1/\epsilon ))$ which is $\epsilon$-close, and similarly for any rational function there exists a ReLU network of size $O(\text{polylog}(1/\epsilon ))$ which is $\epsilon$-close. By contrast, polynomials need degree $\Omega (\text{poly}(1/\epsilon ))$ to approximate even a single ReLU. When converting a ReLU network to a rational function as above, the hidden constants depend exponentially on the number of layers, which is shown to be tight; in other words, a compositional representation can be beneficial even for rational functions.

To appear, ICML 2017

References in corpus (3)

• Representation Benefits of Deep Feedforward Networks
• Reliably Learning the ReLU in Polynomial Time
• Error bounds for approximations with deep ReLU networks

Cited by in corpus (8)

• Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• Polynomial Regression As an Alternative to Neural Nets
• Sum-Product-Quotient Networks
• Consistent Sparse Deep Learning: Theory and Computation
• Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis
• A probabilistic framework for multi-view feature learning with many-to-many associations via neural networks
• On representation power of neural network-based graph embedding and beyond