{"ID":2849238,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.24643","arxiv_id":"2510.24643","title":"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 $ε$-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 $ρ$.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.24643","url_pdf":"https://arxiv.org/pdf/2510.24643v1","authors":"[\"Yujun Kim\",\"Chaewon Moon\",\"Chulhee Yun\"]","published":"2025-10-28T17:09:43Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.AI\"]","methods":"[]","has_code":false}