Research map / Learning theory and algorithms / Sample complexity

Generalizablity of Memorization Neural Network

NeurIPS 2024 · Learning theory and algorithms › Sample complexity · approach: PAC learnability theory · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first theoretical analysis of generalization of memorization neural networks on i.i.d. data, deriving parameter-count and sample-complexity bounds (N_D, S_D) and showing fixed-width or optimal-size memorizers can fail to generalize.

Problem

Whether neural networks that memorize (interpolate) an i.i.d. training set can generalize, and what parameter counts and sample sizes are needed for generalizable memorization.

Approach

Treats memorization as a learning algorithm over i.i.d. datasets from separated binary distributions; builds O(sqrt(N))-parameter and constant-parameter memorizers, shows width must be at least input dimension for generalization, and derives sample complexity bounds tied to a memorization parameter complexity N_D and an efficient complexity S_D.

Key results

• Memorization networks of width 6 and O(sqrt(N) ln(Nn/c)) parameters exist for i.i.d. datasets (Theorem 4.1).
• Networks with width below input dimension n can fail: for some distributions, any width-w memorizer has accuracy at most 0.51 (Theorem 5.1).
• Sample complexity for memorization with N_D parameters is exactly O(N_D^2); general lower bound Omega(N_D^2) (Theorems 6.1, 6.5).

Surprising findings

• Memorization networks with the optimal O(sqrt(N)) parameters can have poor generalization for most distributions, even with unlimited data.
• The efficient memorization algorithm does not beat SGD-trained networks on CIFAR-10 in test accuracy.

Limitations

• N_D and S_D are not computable in closed form and no method to estimate them is given
• Efficient generalizable memorization algorithm uses O(N^{2n}) parameters and is not competitive empirically on CIFAR-10
• Efficient memorization with O(N_D^2) samples is shown NP-hard-type (conjectured not efficient in general)

Experimental setup

Datasets: CIFAR-10 (experiments in appendix I)

Benchmarks: CIFAR-10

Metrics: test accuracy

Baselines: Vardi et al. O(sqrt(N)) memorization Park et al. O(N^2/3) memorization

Builds on: Vardi et al. memorization with optimal parameters Park et al. sublinear memorization interpolation learning (Bartlett et al.) VC dimension bounds for ReLU networks robust memorization (Yu et al.)

Closest papers by meaning

• Learning and Memorization (ICML 2018 · similarity 0.90)
• Unveiling Memorization–Generalization Coexistence: A Case Study on Arithmetic Tasks with Label Noise (NeurIPS 2026 · similarity 0.88)
• The Pitfalls of Memorization: When Memorization Hurts Generalization (ICLR 2025 · similarity 0.88)
• To Grok or not to Grok: Disentangling Generalization and Memorization on Corrupted Algorithmic Datasets (ICLR 2024 · similarity 0.86)
• A mathematical theory of balancing relational generalization and memorization (NeurIPS 2026 · similarity 0.84)
• Fisher information and the geometry of memorization in neural networks (NeurIPS 2026 · similarity 0.84)