Provable Memorization via Deep Neural Networks using Sub-linear Parameters

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.

References in corpus (7)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Optimal approximation of continuous functions by very deep ReLU networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• Identity Matters in Deep Learning
• Optimization Landscape and Expressivity of Deep CNNs
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
• Memory capacity of neural networks with threshold and ReLU activations

Cited by in corpus (4)

• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Bayesian Statistics Guided Label Refurbishment Mechanism: Mitigating Label Noise in Medical Image Classification
• On the Optimal Memorization Power of ReLU Neural Networks