The Cost of Robustness: Tighter Bounds on Parameter Complexity for Robust Memorization in ReLU Nets
This work addresses the theoretical understanding of robustness in neural networks for researchers, providing incremental improvements in bounds.
The paper tackles the problem of robust memorization in ReLU networks by establishing tighter upper and lower bounds on parameter complexity as a function of the robustness ratio, revealing that complexity matches non-robust memorization for small ratios but grows with increasing ratios.
We study the parameter complexity of robust memorization for $\mathrm{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 $ρ\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 $ρ$ is small, but grows with increasing $ρ$.