Provable Memorization via Deep Neural Networks using Sub-linear Parameters

Sejun Park, Jaeho Lee, Chulhee Yun, Jinwoo Shin
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3627-3661, 2021.

Abstract

It is known that $O(N)$ parameters are sufficient for neural networks to memorize arbitrary $N$ input-label pairs. By exploiting depth, we show that $O(N^{2/3})$ parameters suffice to memorize $N$ pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width 3) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works on the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-park21a, title = {Provable Memorization via Deep Neural Networks using Sub-linear Parameters}, author = {Park, Sejun and Lee, Jaeho and Yun, Chulhee and Shin, Jinwoo}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {3627--3661}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/park21a/park21a.pdf}, url = {https://proceedings.mlr.press/v134/park21a.html}, abstract = {It is known that $O(N)$ parameters are sufficient for neural networks to memorize arbitrary $N$ input-label pairs. By exploiting depth, we show that $O(N^{2/3})$ parameters suffice to memorize $N$ pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width 3) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works on the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.} }
Endnote
%0 Conference Paper %T Provable Memorization via Deep Neural Networks using Sub-linear Parameters %A Sejun Park %A Jaeho Lee %A Chulhee Yun %A Jinwoo Shin %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-park21a %I PMLR %P 3627--3661 %U https://proceedings.mlr.press/v134/park21a.html %V 134 %X It is known that $O(N)$ parameters are sufficient for neural networks to memorize arbitrary $N$ input-label pairs. By exploiting depth, we show that $O(N^{2/3})$ parameters suffice to memorize $N$ pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width 3) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works on the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.
APA
Park, S., Lee, J., Yun, C. & Shin, J.. (2021). Provable Memorization via Deep Neural Networks using Sub-linear Parameters. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:3627-3661 Available from https://proceedings.mlr.press/v134/park21a.html.

Related Material