On the Optimal Memorization Power of ReLU Neural Networks
Gal Vardi, Gilad Yehudai, Ohad Shamir
Abstract
We study the memorization power of feedforward ReLU neural networks. We show that such networks can memorize any $N$ points that satisfy a mild separability assumption using $\tilde{O}\left(\sqrt{N}\right)$ parameters. Known VC-dimension upper bounds imply that memorizing $N$ samples requires $\Omega(\sqrt{N})$ parameters, and hence our construction is optimal up to logarithmic factors. We also give a generalized construction for networks with depth bounded by $1 \leq L \leq \sqrt{N}$, for memorizing $N$ samples using $\tilde{O}(N/L)$ parameters. This bound is also optimal up to logarithmic factors. Our construction uses weights with large bit complexity. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.
BibTeX
@inproceedings{
vardi2022on,
title={On the Optimal Memorization Power of Re{LU} Neural Networks},
author={Gal Vardi and Gilad Yehudai and Ohad Shamir},
booktitle={International Conference on Learning Representations},
year={2022},
url={https://openreview.net/forum?id=MkTPtnjeYTV}
}