Title: Is Sequence Significant? Bridging the Law of Robustness and Robust Generalization

Abstract: An unresolved issue identified by Bubeck and Selke (2021) involves the relationship between the Law of Robustness and robust generalization error. The Law of Robustness posits that models must be overparameterized to achieve robust interpolation, meaning the resulting interpolating function must adhere to Lipschitz continuity. Expanding on this, Wu et al. (2023) demonstrated that for any data distribution, the Lipschitz constant scales as $L = \Omega(n^{1/d})$. Meanwhile, robust generalization investigates whether a low robust training loss guarantees a correspondingly low robust test loss. This phenomenon can be analyzed through statistical learning frameworks, specifically using Rademacher complexities; notably, a bound on the Rademacher complexity of the robust loss class provides a limit on the Lipschitz nature of the function class. Leveraging this relationship, we establish an explicit connection between the two concepts across arbitrary data distributions. (i) We demonstrate that the scaling order of the Lipschitz bound is preserved when evaluating the global Rademacher complexity of robust loss classes. (ii) Conversely, at a local level—focusing on function subsets with minimal empirical error—the Lipschitz bound’s order varies depending on the perturbation radius $\rho$ and the localized concentration component $\sqrt{r/n}$.

Source: arXiv Generated at: 2026-06-04 00:00:00 UTC