Interpolation with deep neural networks with non-polynomial activations: necessary and sufficient numbers of neurons

Abstract

The minimal number of neurons required for a feedforward neural network to interpolate $n$ generic input-output pairs from ${\mathbb{R}}^d\times {\mathbb{R}}^{d^{\prime }}$ is $\hat{I}˜(\sqrt{n{d}^{\prime }})$. While previous results have shown that $\hat{I}˜(\sqrt{n{d}^{\prime }})$ neurons are sufficient, they have been limited to sigmoid, Heaviside, and rectified linear unit (ReLU) as the activation function. Using a different approach, we prove that $\hat{I}˜(\sqrt{n{d}^{\prime }})$ neurons are sufficient as long as the activation function is real analytic at a point and not a polynomial there. Thus, the only practical activation functions that our result does not apply to are piecewise polynomials. Importantly, this means that activation functions can be freely chosen in a problem-dependent manner without loss of interpolation power.

V2: reframed in terms of number of neurons, proved the necessary condition, and extended the sufficient condition beyond three layers