# The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets

arXiv: https://arxiv.org/abs/2510.24643 · HTML: https://mlsanity.com/paper/2510.24643/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2025.

## Abstract (arXiv)

We study the parameter complexity of robust memorization for ReLU networks: the number of parameters required to interpolate any given dataset with ε-separation between differently labeled points, while ensuring predictions remain consistent within a μ-ball around each training sample. We establish upper and lower bounds on the parameter count as a function of the robustness ratio ρ = μ / ε. Unlike prior work, we provide a fine-grained analysis across the entire range ρ ∈ (0,1) and obtain tighter upper and lower bounds that improve upon existing results. Our findings reveal that the parameter complexity of robust memorization matches that of non-robust memorization when ρ is small, but grows with increasing ρ.