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

2025-10-28 · Yujun Kim, Chaewon Moon, Chulhee Yun arxiv

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 $ρ$.

📄 PDF Abstract BibTeX arXiv:2510.24643

Code (0)

등록된 구현이 없습니다.

Tight lower bounds for Dynamic Time Warping

2021-02-14 · Geoffrey I. Webb, Francois Petitjean

Dynamic Time Warping (DTW) is a popular similarity measure for aligning and comparing time series. Due to DTW's high computation time, lower bounds are often employed to screen poor matches. Many alternative lower bounds…

Computational Efficiency Dynamic Time Warping Time Series Time Series Analysis

Tight Verification of Probabilistic Robustness in Bayesian Neural Networks

2024-01-21 · Ben Batten, Mehran Hosseini, Alessio Lomuscio

We introduce two algorithms for computing tight guarantees on the probabilistic robustness of Bayesian Neural Networks (BNNs). Computing robustness guarantees for BNNs is a significantly more challenging task than verify…

Globally-Robust Neural Networks

2021-02-16 · Klas Leino, Zifan Wang, Matt Fredrikson

The threat of adversarial examples has motivated work on training certifiably robust neural networks to facilitate efficient verification of local robustness at inference time. We formalize a notion of global robustness,…

Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks

2020-04-28 · ICML 2020 1 · Pranjal Awasthi, Natalie Frank, Mehryar Mohri

Adversarial or test time robustness measures the susceptibility of a classifier to perturbations to the test input. While there has been a flurry of recent work on designing defenses against such perturbations, the theor…

Adversarial Robustness

PAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory

2026-04-19 · Chenyang Wang, Yun Yang arxiv

We derive explicit non-asymptotic PAC-Bayes generalization bounds for Gibbs posteriors, that is, data-dependent distributions over model parameters obtained by exponentially tilting a prior with the empirical risk. Unlik…