We study universal finite sample expressivity of neural networks, defined as the capability to perfectly memorize arbitrary datasets. For scalar outputs, existing results require a hidden layer as wide as $N$ to memorize $N$ data points. In contrast, we prove that a 3-layer (2-hidden-layer) ReLU network with $4 \sqrt {N}$ hidden nodes can perfectly fit any arbitrary dataset. For $K$-class classification, we prove that a 4-layer ReLU network with $4 \sqrt{N} + 4K$ hidden neurons can memorize arbitrary datasets. For example, a 4-layer ReLU network with only 8,000 hidden nodes can memorize datasets with $N$ = 1M and $K$ = 1k (e.g., ImageNet). Our results show that even small networks already have tremendous overfitting capability, admitting zero empirical risk for any dataset. We also extend our results to deeper and narrower networks, and prove converse results showing necessity of $\Omega(N)$ parameters for shallow networks.

研究了ReLU网络的有限样本表达能力，证明了3层ReLU网络可以通过利用深度，并需要大约根号N个节点即可完美记忆大多数N个数据点，并证明大约根号N个节点是记忆N个数据点的必要和充分条件，同时证明当W = Omega（N）时，L层网络的带权参数可以记忆N个数据点。在全局位置假设下分析了负残差网络的记忆能力，并研究了随机梯度下降的动力学，证明了当在经验风险的记忆全局最小值附近初始化时，SGD可以很快找到风险更小的附近点。

小型ReLU网络具有强大的记忆能力：记忆容量的严密分析