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

Abstract

We study the parameter complexity of robust memorization for $\mathrm{ReLU}$ networks: the number of parameters required to interpolate any given dataset with $\hat{I}\mu$-separation between differently labeled points, while ensuring predictions remain consistent within a $\hat{I}¼$-ball around each training sample. We establish upper and lower bounds on the parameter count as a function of the robustness ratio $\ddot{I}=\hat{I}¼/\hat{I}\mu$. Unlike prior work, we provide a fine-grained analysis across the entire range $\ddot{I}\in (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 $\ddot{I}$ is small, but grows with increasing $\ddot{I}$.

Accepted to NeurIPS 2025, 72 pages, 8 figures