Abstract
We study the parameter complexity of robust memorization for $\mathrm{ReLU}$networks: the number of parameters required to interpolate any given datasetwith $\epsilon$-separation between differently labeled points, while ensuringpredictions remain consistent within a $\mu$-ball around each training sample.We establish upper and lower bounds on the parameter count as a function of therobustness ratio $\rho = \mu / \epsilon$. Unlike prior work, we provide afine-grained analysis across the entire range $\rho \in (0,1)$ and obtaintighter upper and lower bounds that improve upon existing results. Our findingsreveal that the parameter complexity of robust memorization matches that ofnon-robust memorization when $\rho$ is small, but grows with increasing $\rho$.