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