An Upper-Bound on the Required Size of a Neural Network Classifier

There is growing interest in understanding the impact of architectural parameters such as depth, width, and the type of activation function on the performance of a neural network. We provide an upper-bound on the number of free parameters a ReLU-type neural network needs to exactly fit the training data. Whether a net of this size generalizes to test data will be governed by the fidelity of the training data and the applicability of the principle of Occam's Razor. We introduce the concept of s-separability and show that for the special case of (c-1)-separable training data with c classes, a neural network with (d + 2c) parameters can achieve 100% training classification accuracy, where d is the dimension of data. It is also shown that if the number of free parameters is at least (d+ 2p), where p is the size of the training set, the neural network can memorize each training example. Finally, a framework is introduced for finding a neural network achieving a given training error, subject to an upper-bound on layer width.