It is well known that modern deep neural networks are powerful enough to
memorize datasets even when the labels have been randomized. Recently,
Vershynin (2020) settled a long standing question by Baum (1988), proving that
\emph{deep threshold} networks can memorize $n$ points in $d$ dimensions using
$\widetilde{\mathcal{O}}(e^{1/\delta^2}+\sqrt{n})$ neurons and
$\widetilde{\mathcal{O}}(e^{1/\delta^2}(d+\sqrt{n})+n)$ weights, where $\delta$
is the minimum distance between the points. In this work, we improve the
dependence on $\delta$ from exponential to almost linear, proving that
$\widetilde{\mathcal{O}}(\frac{1}{\delta}+\sqrt{n})$ neurons and
$\widetilde{\mathcal{O}}(\frac{d}{\delta}+n)$ weights are sufficient. Our
construction uses Gaussian random weights only in the first layer, while all
the subsequent layers use binary or integer weights. We also prove new lower
bounds by connecting memorization in neural networks to the purely geometric
problem of separating $n$ points on a sphere using hyperplanes.

本篇论文证明了深度阈网络使用近似线性的神经元与权重便可实现存储数量为 n 在 d 维度的数据。同时，藉由将神经网络存储与纯几何问题上的超平面分离联系起来，论文也证明了一些新的下界。