Memory Capacity of Neural Networks with Threshold and Rectified Linear Unit Activations
Roman Vershynin
Abstract
Overwhelming theoretical and empirical evidence shows that mildly overparametrized neural networks---those with more connections than the size of the training data---are often able to memorize the training data with 100% accuracy. This was rigorously proved for networks with sigmoid activation functions [M. Yamasaki, Proceedings of the International Conference on Artificial Neural Networks, 1993, pp. 546--549; G.-B. Huang, IEEE Trans. Neural Netw., 14 (2003), pp. 274--281] and, very recently, for rectified linear unit (ReLU) activations [C. Yun, S. Sra, and A. Jadbabaie, Proceedings of the Conference on Neural Information Processing Systems, 2019, pp. 15532--15543]. Addressing a open question of Baum [J. Complexity, 4 (1988), pp. 193--215], we prove that this phenomenon holds for general multilayered perceptrons, i.e., neural networks with threshold activation functions, or with any mix of threshold and ReLU activations. Our construction is probabilistic and exploits sparsity.