Optimal robust Memorization with ReLU Neural Networks

Memorization with neural networks is to study the expressive power of neural networks to interpolate a finite classification dataset, which is closely related to the generalizability of deep learning. However, the important problem of robust memorization has not been thoroughly studied. In this paper, several basic problems about robust memorization are solved. First, we prove that it is NP-hard to compute neural networks with certain simple structures, which are robust memorization. A network hypothesis space is called optimal robust memorization for a dataset if it can achieve robust memorization for any budget less than half the separation bound of the dataset. Second, we explicitly construct neural networks with O(N n) parameters for optimal robust memorization of any dataset with dimension n and size N . We also give a lower bound for the width of networks to achieve optimal robust memorization. Finally, we explicitly construct neural networks with O(N n log n) parameters for optimal robust memorization of any binary classification dataset by controlling the Lipschitz constant of the network.