Provable Memorization via Deep Neural Networks using Sub-linear Parameters
This work provides a theoretical foundation for understanding the efficiency of deep networks in memorization, which is incremental but relevant for researchers in neural network theory and optimization.
The paper tackles the problem of memorizing arbitrary input-label pairs with neural networks, showing that deeper networks with only O(N^{2/3}) parameters can memorize N pairs under mild input separation conditions, compared to the known O(N) requirement for shallow networks.
It is known that $O(N)$ parameters are sufficient for neural networks to memorize arbitrary $N$ input-label pairs. By exploiting depth, we show that $O(N^{2/3})$ parameters suffice to memorize $N$ pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width $3$) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works on the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.