Research map / Learning theory and algorithms / Sample complexity
The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
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.
Characterizes the parameter complexity of robust memorization in ReLU networks as a function of the robustness ratio, giving tighter upper and lower bounds across the full range of the ratio.
Problem
How many parameters a ReLU network needs to interpolate any dataset with epsilon-separated labels while keeping predictions constant within a mu-ball around each training point, as a function of the robustness ratio mu/epsilon.
Approach
Shows that robust memorization complexity depends only on the ratio mu/epsilon; proves a width lower bound via null-space/basis distance arguments and a VC-dimension lower bound for small ratios, and gives three-regime constructions using strengthened Johnson-Lindenstrauss projection and grid-based lattice mapping with sequential memorization.
Key results
- For robustness ratio below 1/(5N sqrt(d)), robust memorization is achieved with O~(sqrt(N)) parameters, matching the classical memorization lower bound.
- Lower bound P = Omega((0.17^2 min{N,d}+1)d + min{1/sqrt(1-0.17^2), sqrt(d)} sqrt(N)) holds for all robustness ratios in (0,1).
- For large ratios the construction uses O~(N d^2 0.17^4) parameters, improving on the prior O~(N d^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed small-ratio robust memorization construction | ReLU networks · Robust memorization, 0.17 ∈ (0, 1/(5N√d)] | sufficient parameter count: \tilde{O}(\sqrt{N}) | Helped |
| Increase the robustness ratio into the moderate regime | Proposed ReLU construction · Robust memorization, 0.17 ∈ (1/(5N√d), 1/(5√d)] | sufficient parameter count: \tilde{O}(N d^{\frac{1}{4}} 0.17^{\frac{1}{2}}) | Mixed |
| Increase the robustness ratio into the large regime | Proposed ReLU construction · Robust memorization, 0.17 ∈ (1/(5√d), 1) | sufficient parameter count: \tilde{O}(N d^{{2}} 0.17^{{4}}) | Hurt |
| Reduce the robustness ratio below 1/(5N√d), compared with classical memorization | ReLU networks · Robust memorization, 0.17 < 1/(5N√d) | parameter complexity: \tilde{O}(\sqrt{N}) | No clear effect |
| Increase the robustness ratio | Robust memorization · 0.17 ∈ (0, 1) | required parameter count | Hurt |
Surprising findings
- For small robustness ratios, robust memorization costs no more parameters than non-robust memorization.
Limitations
- A gap between upper and lower bounds remains for intermediate robustness ratios.
- Results are stated in terms of parameter counts including zero entries; nonzero-count variants are only discussed.
- The VC-based lower bound does not improve beyond sqrt(Nd) for ratios above sqrt(1-1/d).
Experimental setup
Baselines: Bubeck et al. robust memorization upper bound O(Nd^2) Bubeck et al. logarithmic width construction Vardi et al. lower bound sqrt(Nd)
Builds on: Johnson-Lindenstrauss lemma VC-dimension bounds for ReLU networks
Closest papers by meaning
- OPTIMAL ROBUST MEMORIZATION WITH RELU NEURAL NETWORKS (ICLR 2024 · similarity 0.93)
- Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity (NeurIPS 2019 · similarity 0.91)
- On the Optimal Memorization Power of ReLU Neural Networks (ICLR 2022 · similarity 0.91)
- To Grok or not to Grok: Disentangling Generalization and Memorization on Corrupted Algorithmic Datasets (ICLR 2024 · similarity 0.87)
- A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations (ICML 2025 · similarity 0.87)
- On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.