Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
Chulhee Yun MIT Cambridge, MA 02139、Suvrit Sra MIT Cambridge, MA 02139、Ali Jadbabaie MIT Cambridge, MA 02139
Abstract
We study finite sample expressivity, i.e., memorization power of ReLU networks. Recent results require $N$ hidden nodes to memorize/interpolate arbitrary $N$ data points. In contrast, by exploiting depth, we show that 3-layer ReLU networks with $\Omega(\sqrt{N})$ hidden nodes can perfectly memorize most datasets with $N$ points. We also prove that width $\Theta(\sqrt{N})$ is necessary and sufficient for memorizing $N$ data points, proving tight bounds on memorization capacity. The sufficiency result can be extended to deeper networks; we show that an $L$ -layer network with $W$ parameters in the hidden layers can memorize $N$ data points if $W=\Omega(N)$ . Combined with a recent upper bound $O(WL\log W)$ on VC dimension, our construction is nearly tight for any fixed $L$ . Subsequently, we analyze memorization capacity of residual networks under a general position assumption; we prove results that substantially reduce the known requirement of $N$ hidden nodes. Finally, we study the dynamics of stochastic gradient descent (SGD), and show that when initialized near a memorizing global minimum of the empirical risk, SGD quickly finds a nearby point with much smaller empirical risk.
中文速览
过去的研究要让神经网络记住 N 个数据点，通常需要至少 N 个隐藏节点，代价极高。这篇论文证明，只需利用网络的深度，一个仅有 O(√N) 宽度的三层 ReLU 网络就能完美记住绝大多数 N 点数据集，并进一步给出了记忆容量（memorization capacity）关于宽度 Θ(√N) 的紧上下界。研究还把结论推广到残差网络（ResNet）和更深的全连接网络，在一般位置假设下大幅降低了已知的节点数需求；此外，论文还分析了随机梯度下降（SGD）在接近记忆型全局极小值时的动态行为，证明 SGD 能快速收敛到经验风险极小的邻近点。这些结果为理解深度网络为何能以远小于数据量的参数量拟合训练集提供了更紧的理论保障，对深度学习的理论分析具有重要意义。
原文 arXiv:1810.07770;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1810.07770v3