The Price of Robustness:  Stable Classifiers Need Overparameterization
Authors: Jonas von Berg
Adalbert Fono
Massimiliano Datres
Sohir Maskey
Gitta Kutyniok
Venue: ICLR 2026 Poster (2026)
Keywords: concentration inequalities
isoperimetry
robustness
stability
classification problems
generalization
overparameterization
Primary area: learning theory
TL;DR: We show that interpolating classifiers can only be stable, and thus generalize well, if they are sufficiently overparameterized.

Abstract: The relationship between overparameterization, stability, and generalization remains incompletely understood in the setting of discontinuous classifiers. We address this gap by establishing a generalization bound for finite function classes that improves inversely with _class stability_, defined as the expected distance to the decision boundary in the input domain (margin). Interpreting class stability as a quantifiable notion of robustness, we derive as a corollary a _law of robustness_ for classification that extends the results of Bubeck and Selke beyond smoothness assumptions to discontinuous functions. In particular, any interpolating model with $p \approx n$ parameters on $n$ data points must be _unstable_, implying that substantial overparameterization is necessary to achieve high stability. We obtain analogous results for (parameterized) infinite function classes by analyzing a stronger robustness measure derived from the margin in the co-domain, which we refer to as the _normalized co-stability_. Experiments support our theory: stability increases with model size and correlates with test performance, while traditional norm-based measures remain largely uninformative.

Published as a conference paper at ICLR 2026
THE PRICE OF ROBUSTNESS: STABLE CLASSIFIERS NEED OVERPARAMETERIZATION
Jonas Berg & Adalbert Fono & Massimiliano Datres & Sohir Maskey'& & Gitta Kutyniok! I Seiiig-Mxxinnlian--nnveee Munich, Germany
München
Munich Center for Machine Learning (MCML) (berg, fono, datres, kutyniok A @math h. 1mu de sohir maskeyyallpph aapphe reseharheeeccchcoom com
ABSTRACT
The relationship between overparameterization,, stability, and generalization re- mains incompletely understood in the setting of discontinuous classifiers. We address this gap by establishing generalization bound for finite function classes that improves inversely with class stability, defined as the expected distance to the decision boundary in the input domain (margin). Interpreting class stabil- ity as a quantifiable notion of robustness, we derive as corollary a law of ro- bustness for classification that extends the results of Bubeck and Sellke beyond smoothness assumptions to discontinuous functions. In particular, any interpolat- ing model with p n parameters on data points must be unstable, implying that substantial overparameterivation is necessary to achieve high stability. We obtain analogous results for (parameterized) infinite function classes by analyzing a stronger robustness measure derived from the margin in the codomain, which we refer to as the normalized co-stability. Experiments support our theory: stability increases with model size and correlates with test performance, while traditional norm- norm-based measures remain largely uninformative.
INTRODUCTION
The generalization behavior of overparameterized neural networks presents fundamental challenges to classical statistical learning theory. Traditional complexity measures, such as parameter counts or spectral norms of weights, form the basis of many generalization bounds, including those derived from VC dimension theory (Sain 1996) and Rademacher complexity (Bartlett & Mendelson 2002). However, these approaches do not adequately explain several empirical phenomena, e.g., double descent (Belkin et al. 2019) and benign overfitting (Bartlett et al.) 2020). The occurrence of dou- ble descent illustrates that the test eтror, after initially increasing near the interpolation threshold, can improve as the model size continues to grow. Similarly, the phenomenon of benign overfit- ting demonstrates that models that perfectly interpolate noisy training data can nonetheless achieve strong generalization. Such findings expose the limitations of norm- and size-based complexity measures as predictors of generalization.
large-scale empirical study evaluating more than forty complexity measures found that many norm-based quantities not only fail to correlate with generalization, but often even correlate nega- tively (Jiang al. 2019). Beyond optimization-rrlated metrics, one of the few quantities that con- sistently correlated with generalization closely related to the notion (co-) (oo))stabllity we develop in this work. This aligns with an emerging perspective: generalization in modern networks is governed less by model size norms, and more by the stability/ robustness of predictions under input perturbations (Soloff et al., 2025 Ghosh & Belkin 20023 Zhang et al. 2022). Related insights also arise from the literature algorithmic sta- bility (Bousquet& & Elisseefi] (002)) and flat minima (Keskar et al. (017). However, most theoretical results in this direction are restricted linear models.
the margin, i.c., the distance to the decision boundary,
"now at Aleph Alpha Research
University of Tromso, D..R-German Acrospace Center

---

Published as a conference paper at ICLR 2026
An exception is the universal law of robustness of Bubeck & Sellke (202I), distributional assumptions, establishes a formal link between robustness, generalization, and over- parameterization: smoothness and overparameterization need to balance in order to ensure good generalization while overfitting. The law of robustness relies on the assumption that the function class is Lipschitz, which makes it inadequate for classifiers whose codomain is discrete by design. We therefore take a step toward the open challenge posed in Bubeck & Sellke (2021 p. 4): "[...] it is an interesting challenge to understand for which notions of smoothness there tradeoff with size." Specifically, we introduce class stability and normalized co-stability as geometric smooth- ness measures that extend robustness laws to classification. is essential: simply focusing the Lipschitz constant of an underlying score function g. where the classifier is of type / == arg max og, not informative. In particular, since g can be arbitrarily rescaled without changing the predictions of f. its Lipschitz constant does not need to reflect the geometry of the decision boundary (Liu & Hansen 2024).
which, under mild
fact, replacing Lipschitz continuity
Paper Roadmap. We discuss related work in Section 2 Section 3 introduces class stability and the isoperimetry assumption, a concentration property of the data that underlies our analysis. Sec- tion f presents generalization bound for finite hypothesis classes and examines its implications for overparameterization.. In Section we extend the framework to infinite function classes via the notion of normalized co-stability. Our theoretical predictions are tested experimentally on MNIST and CIFAR-I0 in Section Finally, Section concludes with discussion of open directions.
Contributions. We provide a summary of our main results.
1) We prove that, under an isoperimetry assumption on the data distribution, the data-dependent Rademacher complexity of finite hypothesis class of classifiers can be bounded in terms of the minimum class stability. This yields an improved generalization bound for discontinuous classifiers (Theorem 4. which tightens as stability increases.
2) We show that in the classically parameterized regime (#parameters #samples), any interpolating classifier must be unstable (Corollary ( with high probability. Consequently, achieving both near- perfect fitting and high class stability requires substantial overparameterization of order p s nd.
3) We extend the framework to infinite function classes by considering classifiers of the form f(x) := arg max (xr), where Go a parameterized Lipschitz-continuuur (in both x and w) score function. This enables to define robustness measure the normalized co-stability- -, based on output score margins, and derive a corresponding generalization bound (Theorem 13)) The added regularity also results in law of robustness for infinite function classes (Corollary 15).
4) We empirically validate our theoretical predictions on MNIST and CIFAR-10. Stability and nor- malized co-stability increase with network width and exhibit the same qualitative scaling test accuracy, highlighting the central role of (normalized co-) co-)stability in overparameterized generaliza- tion.
Taken together, our results extend the law of robustness to discontinuous classifiers and highlight stability as central factor in understanding generalization in modern networks.
RELATED WORK
Smoothness-basd generalization. Our work is inspired by the law of robustness of Bubeck & Seilke (2021), which shows that regression with Lipschitz predictors generalizes when smoothness and overparameterization are properly balanced. Subsequent works have extended this perspective: for example, Zhu et al.] (223)) investigate how width, depth, and initialization affect robustness, while more recent studies Das et al. (2025) establish refined smoothness generalizzennnnnnnnn trade-offs for wider range of loss landscapes.
Margin- based generalization. Classical generalization bounds combine margin term, defined with respect to a score function, with a capacity measure - for example, dectrally-noormalize mar- gin bounds (Bartlett et al., 2017) or path-norm bounds (Neyshabur et al. 2018). Recent extensions include multi-class margin bounds in terms of margin- morgiiinormliieed geometric complexity (Munn) et al. 2024 These approaches closely aligned with normalized co-stability perspective:
2

---

Published as a conference paper at ICLR 2026
both control codomain margin while coupling it to regularity property of the score function, and both recover inverse- -arrsnn scaling.
Input-space margin bounds have also been studied, yielding that generalization is controlled by the minimum robustness radius (Sokolic et al. 2017), while cample-complextee lower bounds show that adversarial robustness increases the VC dimension (Gao al.. 2019). Our notion of class stability differs: it is the expected input margin the average distance to the decision boundary under the data distribution rather than minimum or an empirical quantile. This measure is closely tied to robustness (Fawzi et al. 2016 Gilmer et al., 2018 and induces data-dependent bounds that track generalization.
Limits of uniform generalization bounds. Uniform convergence-based bounds are often vacu- ous in overparameterized networks (Nagarajan & Kolter 2021), since SGD appears to find solutions at a macroscopic level (supporting generalization) but with microscopic fluctuations that break uni- form analyses. Our bounds remain uniform but depend on macroscopic, dnstributionddepeddnr quantities: the Rademacher complexity our applied technique to derive generalization bounds - controlled by stability (or ro-stability). Whether this structure avoids the vacuity identified by Nagarajan & Kolter (2021) remains open.
Stability, robustness, and implicit bias. Algorithmic stability (Bousquet & Elisseefff 2002 and the flat minima literature (Keskar et al., 2017) argue that robustness under perturbations drives gen- cralization. More recently Zou et al. (2024) derive out-of-distribution generalization bounds based on the sharpness of the learned minima. Our contribution is to extend stability- based perspective to discontinuous neural classifiers, both theoretically and empirically. Complementary work on im- plicit bias shows that gradient descent favors solutions with small number of connected decision regions, a proxy for large input-space margin (Li et al. 2025). This suggests that optimization dy- namics may implicitly favor the same geometric simplicity that our stability-basee bounds capture.
Dittr--Diitribution Generalization. Classically and also in our analysis, generalization is based on the independently and identically distributed assumption on the data, in particular, the test data are generated from the same distribution as the training data coined In-Distribution (ID) generalization. In contrast,
(OOD) generalization aims to study the generalization performance under distributional shifts. To make the problem tractable the potential shifts are constrained to, for instance, spurious correlations covariate shifts. In the OOD setting the connection between over- parameterization and generalization has been studied in a series of theoretical works with positive
Hao et al. (022) and negative results Sagawa et al. 2020 Wald et al. (2024).
Adversarial robustness can be viewed as a special case of OOD generalization, where the distri- butional shift is constrained to lie within perturbation set Sinha al. (2020). In this sense, our stability- based analysis conceptually connected to OOD generalization. However, our results do not provide explicit bounds on OOD error; instead, we focus on ID generalization under the assump- tion that the classifier satisfies given level of adversarial robustness expressed as the margin.
3 PRELIMINARIES AND NOTATION
In the following, we provide background on the key concepts underlying our analysis, namely sta- bility, generalization, and isoperimetry. For clarity of exposition, we present our results in the binary classification setting. The extension multi-class problems follows by a one-vs-all reduction; Appendix F for details. Thus, let (X' x [-1,1] 1), 11) be a probability measure space with X' C Rd bounded and F. C [f/S= X - {11 set of classifiers. The goal is to find stable function I E F minimizing a bounded loss function L (-1, 1 + R_ on n i.i.d. samples (æ,, (I4,W:) ~ A natural loss in the classification setting is the 0-1 loss f0-1 (y.'()))))== Lyzy' In this setup, following a similar approach as in Liu & Hansen (2024), we define the class stability of f as the expected distance of sample to the decision boundary X, thereby capturing the average robustness of classifier f to input perturbations.
3

---

where R, (9) denotes the Rademacher complexity of general function class G, defined as Published as a conference paper at ICLR 2026
Definition 1 (Margin and Class Stability). Let fet + {-1,1). The signed distance function dy of f at x E X is defined as
d(x, ( if(()) = -d((z, (f(()) -11
dy(z)
where d(x, A):= yea || 2l12- We define the (unsigned) margin h the absolute value of the signed distance function,
ht((2) == [dy(z)] =nmpl==nf[lll== [1]
=112 f(2) * f(z), 2 X}.
The class stability S()) of f is its expected margin under the data distribution:
S()) == E[hy]-
Remark 2. The signed distance function d is 1-Lipschitz if X is path-connected. Moreover, if sgn(0) 1 and ({1}) is closed in X, then f admits the representation f sgn Appendix for details).
sgn odg (see
Our goal is to relate the class stability to the Rademacher complexity of a function class, which, in turn, connects generalization bounds through classical results (Bartlett & Mendelson 2002). In particular, for bounded loss |e] I a, the difference between the population risk Re())
[()(f(x)) y)] and the empirical risk Re(f) == E {(f(x:), y4) is bounded with probability at least over the samples by
2 log((2/0)
sup ( Re(f)) 2 (eo aay fET
1 B n2
R
sup DEG
with (o:) i.i.d. Rademacher random variables. To obtain bound in Equation in terms of Rn,a (F), note that Rm, (f o F) < (FF, holds under certain conditions on the loss, we have
Rn o F) 2 (F), i.e., ne,C==
whereas for L- L-Lisschitz losses C L holds, see Bartlett & Mendelson (2002); SSawltz & Ben-David (2014) for detailed explanations. Overall, it therefore suffices to bound ( in terms of the class stability of functions words, the key step is to control how well stable functions can fit random labels, which requires structural assumptions
F in order to link generalization stability. In other
the input distribution. We discuss detail in Appendix [ why such assumptions are unavoidable. A natural and widely used condition is isoperimetry. which guarantees sharp concentration for bounded sipshitz-continnust Definition (Isoperimetry). A probability measure on X' C Rd satisfies c-isoperimetry for any bounded finisschitz,uunctioo X + I. and any 2 0,
functions (Bubeck & Sellke (202I).
.12 ((]f(=) E 2 t) S 2e 2.17
Isoperimetry is, for instance, satisfied by Gaussian measures and the (normalized) volume mea- sure on Riemannian manifolds with positive curvature, such as the uniform measure on the sphere (Vershynin] 2018 Bubeck & Sellke 2021). Consequently, under the manifold hypothesis, the rele- vant dimension in our bounds can interpreted as the intrinsic manifold dimension rather than the ambient dimension.
4 A LAW OF ROBUSTNESS FOR CLASSIFICATION
In this section, we establish law of robustness for classification, extending
trade-offs to discontinuous functions. Classical results for smooth functions characterize robustness via the Lipsehitz constant, which is ill-defined for classifiers with discrete outputs. To address this, follow the general strategy of Bubeck & Sellke (2021) (see Appendix Alfor details), but replace their use Lipschitz continuity with our notion of class stability (Definition I]. Formally, we proceed under the following assumptions:
4

---

Published as a conference paper at ICLR 2026
(HI) (X'(-11,1) is probability space with bounded sample space X' and c-isoperimetric marginal distribution μxx
(H2) the considered hypothesis class F of classifiers f 1-1, is finite, that is |F| cc.
These conditions ensure concentration of measure in the input space and allow complexity control a union bound. With this structure in place, class stability can be related to the Rademacher complexity, leading to the bound stated below.
Theorem 4 (Rademacher Bound), Suppose Assumptions (H1) and (H2) hold, and that minjer S(f) S 0 with log [F 2
1. The Rademacher complexity satisfies
Vc log [F]
R (F) I K1 max
(4)
VV''
S
nvd
for an absolute constant K1
2. If. in addition,
((1) is closed and X path-connecied, the bound sharpens
Ve
log
ds²
8c )
Ra (F) S K2 max
2 2exp(
(5)
VVn
S
nd
for another absolute constant K₂ >
Proof sketch. Equation D obtained via Lipschitz surrogate argument combined with isoperime- try. The refined bound in Equation 5 further leverages the representation f = sgn od, (Remark using that large stability ensures de remains well separated from the discontinuity at O. Complete details are provided in Appendix
Remark 5. In contrast to Bubeck Sellke (202)) where stability is measured by the minimal Lipschitz constant of the function class, initial bound in Theorem inncurremincureed incurred additional factor Vlog FFlm in the regime log [F 2 By assuming mild regularity conditions, we can eliminate this gap and recover the same scaling as in Bubeck Sellke (2027).
The key insight of Theorem 4 combined with the classical generalization bound in Equation is that good generalization can still be achieved in the highly overparameterized regime- - -provided the classifiers exhibit sufficiently high class stability. Indeed, the presence Y in front of /log [F] in Equation Fadd Equation indicaaes that class stability affects the effective complexity of the model class, potentially mitigating the risks of overfitting in large models. Note that, using a uniform discretization, finite approximation of infinite function class parameterized with p parameters over a bounded subset of Rº satisfies log [ E (p).. In this sense, log [F reflects the number of model parameters. Therefore, when the number parameters p z log much larger than n, the second term in the maximum in Equation 5 dominate and the bounds becomes small if S scales at least in the order of V
We are now ready state our law robustness for discontinuous functions, obtained as direct corollary of the refined Rademacher bound in Equation 5f Theorem 4
Corollary (Law of Robustness for Discontinuous Functions). Assume (HI), (H2), and the addi- tional conditions in 2. of Theorem 7 hold. Let == log [ 2 Fix e, 8 E (0, 1) and consider the 0-1 loss lo-s. There exists an absolute constant K > such that, if
1. the minimal risk R == minjer (f satisfies R' 2 E. and
2. the sample size n is large enough to ensure (i) K. S/ and (ii) 2log(2/8)
then with probability least 1 1-6 8 (over the sample), the following holds uniformly for all f E F:F
3K clog [F
Sc
6K
Ro- < R
s(f) <
max
log
(6)
nd
It is worth noting that framework readily extended mixtures of c-isoperimetric distributions.
5

---

Published as a conference paper at ICLR 2026
Proof sketch. Apply the Rademacher bound (Theorem 4 to the high-stability subset Fs. := (f F [(f) S.}. For S. chosen large enough, such functions cannot achieve empirical risk below R any interpolating classifier with risk < R must lie outside Fs., ie.. must satisfy
S()) < S.. The full proof is provided in Appendix D
Remark As in Bubeck Sellke (2027). we assume R > corresponding to a setting which the hypothesis class does not achieve zero classification error. This accounts for inherent label noise or model misspecification. Unlike Bubeck & Selike (2021), which assumes Lipschitz-continnon losses, our analysis directly addresses the discontinuous 0-1 loss, making it more natural for clas- sification tasks. The overall proof strategy, however, extends to arbitrary losses provided one can derive an appropriate bound the Rademacher complexity of the composed function class, in Equation 2
Remark Importandl, this result also covers intrinsically discontinuous classifiers, such as quan- tized neural networks and spiking neural networks. Moreover, since self-attention is in general not Hipschitz-continnone Kim et al. (202)), our framework appeerr particularly well-suited to the anal- ysis of overparameterizztion of transformers, which underlie most tatte-ofthhearn language models.
From Equation we conclude that achieving both low training error and high stability requires pa- rameterization on the order p nd. This necessity arises in the high-dimensional regime, since when is large the first term in the maximum dominates for 2 n. This reinforces our central message: overparameterization may not harm generalization, but on the contrary, is necessary for achieving robustness and good fitring in classification. Notably, modern neural networks, includ- ing large language models (LLMs) (Brown et al.] (2220). are trained in heavily overparameterized regimes: Even though recent scaling laws |Hoffmann et al. (2022) suggest a balance between model and data size, contemporary language models still operate deep in the overparameterized interpo- lation regime, where their capacity is sufficient to achieve near-zero training loss. Therefore, our result may help to understand why such models still do generalize effectively.
A LAW OF ROBUSTNESS FOR INFINITE FUNCTION CLASSES
In Theorem our analysis does not straightforwardly extend infinite function classes. The usual proof strategy via covering numberr argument requires closeness in parameter space to imply close- ness in function space. Bubeck & Sellke (202T), this is enforced via Lipschitz continuity in the parameters of the function class, but such condition is in general meaningless for discontinuous classifiers.
To overcome this, restrict our attention to function classes with additional structure and introduce a strengthened stability notion. Specifically, we impose a representation analogous to Remark 2 namely,
(H3) The hypothesis class has the form F sgn oG, where & {sw X [-1,1] W) is parameterized family Lipsehitz functions. The parameter space W C R2 bounded with diam(W) < W, and the parameterization I Lipschitz:
gww <
J || - w2ll-
The extension from finite to infinite classes requires not only (i) Lipschitz continuity in w, but also (ii) that the scores 9n (2) stay quantitatively away from zero, that small parameter perturbations cannot cause arbitrary label flips. Class stability alone does not suffice to ensure (ii), as the following example demonstrates.
Example 9 (Class stability does not prevent discontinuity). Let G = (x) w tanh(x)) w [-1, The parameterization Lipschitz since
I1ow; 9wzll |l I || w2ll
For w1 = and W22 = -,, ||w w2ll < s, yet
|| sgn (gw, (z)) sgn(gwz (x)) =
for almost all x. Each classifier has a single boundary point (hence high class stability), but param- eler proximity does not imply classifier proximity.

---

Published as a conference paper at ICLR 2026
To guarantee property (ii), we introduce robustness measure in the codomain.
Definition (Co-margin and Co-stability). Let f sgn og : X (-1,1)) The co-margin at is
(r(a) = 1g(x)b
and we denote the normalized co-margin as
(x) = 1g(x))|
L(g)
where L(g) is the Lipschitz constant of g. The co-stability is then the expected co-margin
(g) == E[)z(z)),
and the normalized co-stability is accordingly defined as the expected normalized co-margin
(g) := E(h)
Remark 11 (Representation dependence). Unlike class stability S(f), which depends only on the decision boundary of f. the co-stability S" (g) and its normalized form S" depend on the partic- ular representation f = sgn og. Different score functions g inducing the same classifier f can yield different values of (g) and 5* (g). For the specific representation sgn od, from Lemmal 18
however, both measures coincide: (g) = 5t (g) = S()).
Imposing (4) 2 8* 0 ensures that scores remain, on average, non-trivial distance away from zero. Together with (H3), co-stability provides the continuity and separation properties required for infinite-class generalization bounds.
Before turning to the formal statement of this fact, we want to discuss the relation of class stability and co-stability, The connection between input- and codomain-baan based margins is immediate since
hg (x)
hz)()).
T(g))
By [gg)-Lipschizz continuity, moving x by changes g(æ) by at most L(g)r, so flipping the predic- tion requires r 2 |g(x))/T[()) (gg). Taking expectations yields
S(f) Z (g)
(7)
Thus normalized co-stability lower-bounds class stability. This inequality highlights two levers for improving generalization: increasing S* (g) or decreasing I(g). Importantly, 5* (0)), like S(f), is invariant to input rescaling and therefore serves as natural robustness measure.
Remark 12. A related ratio. R.,' appears in Bartlett et al. (017)) where f is the minimum margin and R a spectral complexity term controlling Lipschitzness. Empirically, Lipschitz margin training, which enforces
(*(g) Z C,
improves adversarial robustness (Tsuzuku et al. 2018). Moreover, Béthume et al. 22022 Corollary 2) show that among maximally accurate classifiers, there exists 1-Lipschitz solution that achieves maximal co-margins and satisfies S(f)) (g).. In particular, the Bayes classifier admits the representation sgn odg, which fulfills these properties.
Combining Theorem 4 with Equation 7 the Rademacher complexity of finite function class F = sgn og can be bounded in terms of normalized co-stability as
{
log [ nd
dS-2
Rn,a(F) S K2 max
(
Vc S
2 2exp
T,280
where S* >> and L > are bounds on the minimal co-stability and maximal Lipschitz constant, respectively. Under condition (H3), the statement can be extended to infinite function classes.
Theorem 13. Suppose (H1) and (H3) hold, and that S* (g) > S > O and L(g) < for all E G.
Assume further that
Then, for any covering precision E 0.
Vi:
LIPP P
ds²2 J
R (F) S K max
nd V
clog 1 60WJE-1). 2exp
8cI22 St 1 {..
(8)
where K > O is an absolute constant independent of p, n. d, S² ,c, I J,

---

Published as a conference paper at ICLR 2026
Proof sketch. The proof follows the previously mentioned E-net approach, standard in infinite-class settings. The Lipschitz continuity in w (from (H3)) controls the covering number of g at scale é, while co-stability ensures that small perturbations in do not induce flips through the sgn mapping. The additional term gr é reflects the residual error introduced by the discretization. See Appendix for more details.
I. shows that generalization depends jointly on the average prediction Remark 14. The factor 3F
confidence 5*(g) (g) and the Lipschitz constant L(g), the latter quantifying robustness of predicted probabilities. This aligns with empirical findings (Khromov & Singh 2024- Gambu ef al. [202]] Gouk et al. 2020: Sanyal et al. 2020 Béthune et al. (022). which report that smaller Lipschitz constants rypically improve generalization, and in some cases exhibit a double dessent behavior.
We obtain with the same reasoning as in Corollary 6 the following law of robustness for Lipschitz- regular infinite function classes.
Corollary 15 (Law of Robustness for Infinite Function Classes). Assume (H1) and (H3), and fix e, 8 E (0,) 1). Consider the 0-1 loss lo There exists an absolute constant K > such that, if
1. the minimal risk R == jnf Ro-((f) satisfies R 2 E, and
V < and (ii) 22lug(2/8)
2. the sample size n is large enough so that (i)
2'
then with probability at least 1 - for all Ě >> O, the following holds uniformly for all G and fg = 8gn g:
(9) L(g)
3K
P V nd +ooloog((+oow.00 60W V Sc
6K
(fa) S -5
max
log
Remark 16. As in Bubeck & Sellke 2202)) we require W and J to be at most polynomial in (n, d. p) so that they do not affect the asymptotic scaling. In the case of feedforward neural networks, Bubeckk & Sellke (2027) further show that when the data distribution is concentrated in a ball of radius R, suffices assume that W is polynomially bounded.
Analogous to the finite-class case, we conclude that Lipschitz-regular classifiers must be overpa- rameterized of order nd to achieve both low training error and high normalized co-stability. Without sufficient parameter capacity relative to sample size and ambient dimension, robustmess cannot be guaranteed: models may fit the training data, but will necessarily exhibit either large Lipschitz con- stants of the score function or low co-stability, reflecting weak confidence in their predictions. Thus, overparameterizattoo emerges as a necessary condition for robustness, reflecting a structural con- straint imposed by geometry and probability rather than mere byproduct of contemporary training practice.
EXPERIMENTS
We empirically investigate how class stability and co-stability scale with model size in interpolating networks.
Experimental setup. We train fully connected MLPs with four or eight hidden layers and widths w. E {128, 256, 512, 1024, 2048) on MNIST and CIFAR-10. On CIFAR-10, we additionally eval- uate CNNs with widths w (128, 256, 512, 1024). On MNIST, consider Heaviside-activatio MLPs to probe whether the observed scaling extends to discontinuous score functions. All models are trained to least 99% training accuracy, yielding near-interpolating solutions.
Class Stability. We estimate empirical class stability S(ʃ) via adversarial perturbations. For each input, we increase the perturbation radius r along predefined grid (f1....,Ty) until the classifier's 's prediction changes. The minimal successful radius is recorded as the distance to the decision boundary for that sample, and S(J) is reported as the average over the dataset.
Normalized Co-Stability. The empirical co-stability (g) is computed via the multi-class margin
93 (x(x) max ge (z). **)
j = arg max gx())
8

---

Published as a conference paper at ICLR 2026
CIFAR10 MLP, depth
CIFAR10 MLP, depth
0.450
0.425
51.0
51.0
0.400
50.5
0.016
50.5
Accuracy 1%
Sifi
0.375
Accuracy
((g)
0.350
50.0
0.014
50.0
0.325
49.5
49.5
0.300
5/0)
5igi Arc (teet)
0.275
Acc (test)
0.010
48.5
48.5
Parameters
1e7
Parameters
1e7
Figure 1: 8-layer MLPs on CIFAR-10. Class stability S(f) (left) and normalized co-stability S (g)//(g) (right) as function of model size. The configuration with w 128 excluded since it failed to attain 99% training accuracy after 400 epochs.
averaged the dataset; see Appendix F for details about the multi-class setting. We estimate the Lipschitz constant L(g) using the efficient ECLIPSE method (Xu & Sivaranjani 2024), and report the normalized ratio S (g) L(g) as a function of model size.
Results. Figure Tillustrates the behaviour for MLPs on CIFAR-10. Both stability measures increase with width and follow the same qualitative trend as accuracy. In contrast, standard weight norms (or their inverses) exhibit different width-scaling and do not track test accuracy comparably. The observed saturation of (normalized co- )stability aligns with theoretical intuition: the Bayes classifier admits a finite (normalized co- co-)sstailitty level, and pushing beyond this level necessarily reduces accuracy an instance of the robustness/accuracy trade-off extensively discussed the literature (Zhang et al. 2019 Tsipras al. 2019: Bétthune et al. 2022). Accordingly, we expect stability to plateau once models approach the Bayes decision boundary. For CIFAR-10, test accuracy in our experiments remains around 50%, which is far below the Bayes optimal. Nevertheless, the same reasoning applies relative to the best classifier achievable within the restricted MLP hypothesis class considered here.
CNN experiments (Figure display the same qualitative scaling of class stability with model size.
CIFAR10 CNN,
CIFAR10 CNN, depth
0.16
0.15
0.155
88
0.150
0.14
0.13
82
Accuracy [%6]
0.145
0.140
-66
Accuracy
0.135
0.11
85
0.10
0.130
0.09
0.125
0.08
trest
0.120
S1D Ace
83
0.0
0.5
1.0
1.5
2.0
2.5
0
2
Parameters
Parameters
1e7
Figure 2: Class stability S(f) for 4- and 8-layer CNNs trained CIFAR-10.
The Heaviside MLP experiments (Figure B) show that the observed stability scaling persists even for discontinuous score functions. This suggests that the Lipschitz assumption employed to extend Theorem 4 to infinite function classes is primarily technical rather than intrinsic to the stability- model size relationship.

---

Published as a conference paper at ICLR 2026
MNIST
MNIST T
1.89
1.72
97.8
1.88
1.70
1.87
97.6
97.6
Accuracy
1.66
97.4
99.4
1.84
1.64
97.2
1.83
1.60
5/0
Acc (test)
97.0
1.82
SIB Arc (test)
1.81
0.00
0.25
0.50
0.75
1.00
1.25
0.0
0.5
1.5
2.0
3.0
Parameters
167
Parameters
1e7
Figure 3: Class stability S(f) for layer and 8- 8-layer Heaviside-activation MLPs trained on MNIST.
7 DISCUSSION AND FUTURE WORK
Our results identify class stability and codomain analogue, normalized co-stability, as principled quantities linking overparameterizzaion, generalization, and robustness for discontinuous classifiers. While we provide geometric laws of robustness for finite and infinite hypothesis classes, and our experiments support their validity, several directions remain open.
Empirical directions. Computing class stability S(f) and Lipschitz constants L(g) of neural net- works is NP-hard (Katz et al. 2017 Weng et al. 2018 Scaman & Virmaux 2019). limiting the direct use of (normalized co- Jstabilityyy training. However practical relaxations exist: normalized co-stability underlies Lipschitz margin training Tsuzuuuu et al. 2018). while input-space stability is
related adversarial training (Madry al.) 2018 Goodfellow et al. 2013). Biasing optimization explicitly toward (co-)stable solutions is therefore a promising empirical direction.
Another direction is to investigate how isoperimetric structure and related concentration phenomena manifest in real datasets and how they affect classifier stability. To isolate the role of the isoperimet- ric scale in a controlled setting, we consider a toy experiment with synthetic Gaussian data. Increas- ing the variance, and thus reducing concentration, leads to deterioration of the stability- scaling (Figure 4 Appendix (A). The question of whether real data exhibit comparable geometric structure connects naturally the manifold hypothesis: normalized Riemannian volume measures on positively curved manifolds satisfy isoperimetric inequalities. This raises the question of whether robustness laws fail empirically when the effective dimension of the data manifold is small.
Theoretical directions. Our framework also motivates the exploration of alternative geometric complexity measures. Do quantities such as sharpness of the loss landscape obey robustness laws analogous those for (normalized co- co))stability? Another question concerns sufficiency: we estab- lish that overparameterization is necessary for generalization, but is it also sufficient under suitable optimization? Bombari et al. (2023) prove sufficiency for Lipschitz regression in the NTK regime but show that it fails for random features model. Extending such results to discontinuous classifiers may reveal qualitative differences.
Finally, the role of implicit bias remains unclear. Does gradient descent or SGD exhibit bias toward classifiers with higher (normalized co- ro-)stabilitt, as suggested by analogous results on region counts (Li al. 2025 Establishing such bias would explain why stable solutions emerge in practice.
Overall, our findings suggest that stability -baee laws capture a core structural constraint of mod- overparameterized learning. Developing efficient estimators, stronger empirical validation. and deeper theoretical connections (e.g., with sharpness and optimization bias) are promising next steps toward unified understanding of generalization and robustness.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Jonas von Berg, Massimiliano Datres and Gitta Kutyniok acknowledge support by the project "Next Generation AI Computing (gAln)," funded by the Bavarian Ministry of Science and the Arts and the Saxon Ministry for Science, Culture, and Tourism as well as by the Hightech Agenda Bavaria.
Jonas von Berg and Gitta Kutyniok are also grateful for partial support from the Konrad Zuse School of Excellence in Reliable Al (DAAD).
Additionally, Jonas von Berg, Gitta Kutyniok, Adalbert Fono, Massimiliano Datres and Sohir Maskey acknowledge support by the Munich Center for Machine Learning (MCML).
Gitta Kutymiok furthermore acknowledges support by the German Research Foundation under Grants DFG-SPP-2298,, KU 1446/31-1 and KU 1446/32-1, and by the Bavarian Ministry for Digital Affairs.
ETHICS STATEMENT
This work focuses on the theoretical analysis of generalization in machine learning and does not involve experiments on human subjects, sensitive personal data, or applications with direct societal risks. The datasets referenced are publicly available, and private restricted data was used. Potential ethical concerns related to misuse are minimal, as the contributions are mainly theoretical and methodological.
ACKNOWLEDGMENT OF LLM USE
We explicitly acknowledge that large language models (LLMs) were used solely for polishing code, improving sentence clarity, and refining grammar. They were not used for generating research ideas, proofs, results.
REPRODUCIBILIT STATEMENT
We have taken multiple steps to ensure reproducibility of our results. All theoretical claims accompanied by rigorous proofs, presented in detail the appendix. Assumptions underlying the theorems are explicitly stated, and definitions given in full to allow independent verification.
REFERENCES
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Telgarsky. Spectrally margin bounds for neural networks, 2017. URL https:///////:xii..o.m wttp:/o///aab////oo 1706. 08498
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):46-4482 2002.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30663330077 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bari-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-1553 2019.
Simone Bombari, Shayan Kiyani, and Marco Mondelli. Beyond the universal law of robustness: Sharper laws for random features and neural tangent kernels, 2023, URL https://tpa..ttt.. org/abs 2302.600.. 62.99
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526. 2002.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz

---

Published as a conference paper at ICLR 2026
Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, 1lya Sutskever, and Dario Amodei. Language models are shotshot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL https:://proceeddnggg neurips wwtpppppppppp.....p ffless/apper/2020. F11//997cc6500001111188222222222 Paper,
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34:2881 1-28822, 2021.
Louis Béthune, Thibaut Boissin, Mathieu Serrurier, Franck Mamalet, Corentin Friedrich, and Al- berto González-Sanz. Pay attention your loss: understanding misconceptions about 1-lipschitz neural networks, 2022. URL htlthtts::: arwii.iivv....... http://awxx.....///////0000
05097
Santanu Das, Jatin Batra, and Piyush Srivastava. A direct proof of a unified law of robustness for bregman divergence losses, 2025. BuRKhhttsss//axii.ooor/bbbbbbb/p
16639
Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. of robustness to adversarial perturbations, 2016. URL UKLLAttess//aaa....rr///////22/2
Matteo Gamba, Hossein Azizpour, and Märten Björkman. On the lipschitz constant of deep net- works and double descent, 2025. UBL.http.../aaxxxx.orr///////2/2 12309
Ruiqi Gao, Tianle Cai, Haochuan Li, Liwei Wang, Cho-Jui Hsieh, and Jason D. Lee. Convergence of adversarial training overparametrized neural networks, 2019. URL WRR.https::/axxiv.orr
abs 1106/ 07916
Nikhil Ghosh and Mikhail Belkin. A universal trade-off between the model size, test loss, and training loss of linear predictors, 2023. htt.:ttts///a........ www./bgg///oo..oo.ooo.o....o...r /td.s///2.... 2200 11.07.16600
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Watten- berg, and Ian Goodfellow. Adversarial spheres, 2018. URL
org. org/abs/
18C1.021 02774]
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations (ICLR), 2015. URI. https:
//axxiv.org/abs////
6572
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. Regularisation of neural networks by enforcing lipschitz continuity, 2020. URL htttpp://aaxiv.oo/////bbba
04368
Yifan Hao, Yong Lin, Difan Zou, and Tong Zhang. On the benefits of over-parrameterization for out-of-distribution generalization, 2024. URL
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hen- nigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimat large language models, 2022. URL https: /tte:///axxiii org/ abs/
2203. 15556
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them, 2019. URL
1912. 02178
Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https:
gi github. 1 posts// s/ /mmun//
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An effi- cient smt solver for verifying deep neural networks, 2017. URL htLhhtts:: pettps://arxiv. .rgg abs/
T702. 01135
12

---

Published as a conference paper at ICLR 2026
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch batch training for deep learning: Generalization gap and sharp minima. In International Conference Learning Representations, 2017.
Grigory Khromov and Sidak Pal Singh. Some fundamental aspects about lipschitz continuity of org/ abs 2302 10886
neural networks, 2024.
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention,
2021. UtLps:t:://axxx
02000.040000000000 04710
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference Learning Representations (ICLR), 2015. URL https://arxix: orgg/
abs / 1.412.9880
Mojzesz Dawid Kirszbraun. Über die zusammenziehende und lipschitzsche tranfrrmmionnttmnnnnnnn Fun- damenta Mathematicae, 22:77-108, 1934. URL hattps::/apl..eeanttcc.e... orr
CorpusID:1172500
Jingwei Li, Jing Xu, Zifan Wang, Huishuai Zhang, and Jingzhao Zhang. Understanding nonlin- implicit bias via region counts in input space, 2025. URL //L/:pss///axxv.orr///a..
Z. N. D. Liu and A. C. Hansen. Do stable neural networks exist for classification problems? - new /ttp:////////../////28
view on stability in ai, 2024. URL
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learming Representations (ICLR), 2018. URL htthtttss///aaitaa
hhtp://b//110 06083
Edward James McShane. Extension of range of functions. Bulletin of the American Mathmmatiaal Society, 00:837-842, 1934. URL 38462037
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2574-2582, 2016. doi: 10.1109/VVP...206.222.
Michael Munn, Benoit Dherin, and Javier Gonzalvo. margin-based multiclass generalization
bound via geometric complexity, 2024. URL/ttpp::/aarwv..rrr//aas
18590
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning, 2021. URL httpp:://aaxxi..cc////////22222/
Behnam Neyshabur, Zhiyuan L.,, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of overpparametrizaaioon in generalization of neural networks, 2018. URL
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL http: http:::///ppperr.....pppppp 9015 wywtrch-ttto an watprn---a-mmmmaaaaaaa immprtteiieeee sty styyeeeiiiee pdf
h high- htt.:///weeett.eeooooooooooorrnr deepee learning Librarrr......
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox benchmark the robustness of machine learning models. arXiv preprint arXiv 2017. URI. https:
//axxiv.rrg//a/oo /170. 04131
Philippe Rigollet and Jan Christian Hütter. High-dimensional statistics, 2023. URL https://
arxiv. wtt.o//g//ab////a///
13

---

Published as a conference paper at ICLR 2026
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. In Proceedings of the 37th International Conference Machine Learning, ICML'20. JMgR. 2020.
Stephan R Sain. The nature of statistical learning theory, 1996.
Amartya Sanyal, Philip Torr, and Puneet Dokania. Stable rank normalization for improved generalization in neural networks and gans. In International Conference on Learning Represen- tations, 2020. URL
wttp://wwwwwe.e/ouuoee....a -et.::/ooooumii2---e------ HlenKkrFDB
Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation, 2019. URL
alsc:///bb/180...... 10965
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distribu-
tional robustness with principled adversarial training, 2020. URL https://arxiv..
abs/1710.10573
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265 4280, August 2017. ISSN 1941-0476. doi: 10.1 2011009099,001,.7700003 URL http: dx. dei www.oooow...ooooooooooe/o 1109/
TSP 2017.2708000 2708099
Jake A. Soloff, Rina Foygel Barber, and Rebecca Willett. Building a stable classifier with the inflated argmax, 2025. URL
14064
Dimitris Tsipras Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy, 2019. URL http::tt////// http://awwxiir.gr...../ wttggbs/aaaa...o/oe/es///// 12152
Yusuke Tsuzuku, Issci Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certifica- tion of perturbation invariance for deep neural networks, 2018. httph:ttt///aiiiiie
abs/ 1802. 04034
Roman Vershynin. Digge-Dimesional Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Yoav Wald, Gal Yona, Uri Shalit, and Yair Carmon. Malign overfitting: Interpolation can provably preclude invariance, 2024.
Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S. Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks, 2018. URL MtLLtttts///axiii org/ abs
Yuezhu Xu and S. Sivaranjani. Relipse: Efficient compositional lipschitz. constant es- timation for deep neural networks. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural In- formation Processing Systems, volume 37, pp. 10414-10441. Curran Associates, Inc., 2024. URL https://proceddnng. www..ss.eerip.... cwtppcprppppe..eceeeeeeeeeee...e httpapperr.lllleeppee//222... Paper het.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Rethinking lipschitz networks and certified robustness: A boolean function perspective, 2022. URL http:::://xx...o///////aaaa
01787
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael Jor- dan. Theoretically principled trade-off between robustness and accuracy, 2019. URL https: 98573
14

---

Published as a conference paper at ICLR 2026
Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization), 2023. URL https: arxiv. orq/ abs/ 2209. 07263
Yingtian Zou, Kenji Kawaguchi, Yingnan Liu, Jiashuo Liu, Mong-Li Lee, and Wynne Hsu, Towards robust out-of-distribution generalization bounds via sharpness, 2024. URL fctps://arxiv.
crg/aba/2403. 06392
A THE NEED FOR ISOPERIMETRY
A.1 THEORETICAL IUSTIFICATION
Concentration inequalities essential tools in high-dimensional probability theory, providing bounds on the tail behavior of random variables. Next, we outline the key strategy from Bubeck & Sellke (Bubeck Sellke, 2021) for proving the law of robustness for regression, highlighting the importance of an additional assumption on the measure μ.. The authors employ the Lipschitz constant of function
measure of robustness, where small Lipschitz constant (i.e., 1) of the realization indicates a robust model. The basic idea is to leverage the Lipschitz continuity of functions f X' + R in conjunction with isoperimetric inequalities bound the probability
(9) That is, we aim to bound the probability of observing a model that both robust (i.e., has a small Lipschitz constant L(f)) and fits the data well (i.e., R(() zs O, meaning it nearly interpolates).
P(3f E F Rc(f) 0 A L(f) S L.) < 6.
By contraposition, this implies that with probability least 1 1 5, the following holds for all f e F:
R( = (() L. np.
(10)
Here, Lp(p, n, d) is an algebraic function the number of parameters p s log Fl (see the paragraph below Theorem 4 for details), the number of training samples and the input dimension d. It
satisfies (p, n. d) >> 1 in the non-overparameetrrize regime = n, thereby implying non- non-robust behavior.
A key ingredient in Bubeck Sellke (2021) I for proving (a variant of) Equation iss the isoperimetry assumption on the measure μ.. Isoperimetry, originating in geometry, provides upper bound on a set's volume terms of its boundary's surface area. In high dimensions, the principle of isoperimetry induces concentration of measure, where the measure of the e-neighborhood Ag of any set A with (AA) > 0 has measure p(Ag) - 1, and the complementary measure decays in the order of exp(-de This equivalent to the sub-Gaussian behavior of every bounded Lipschitz- continuous function stated in Definition 3 yielding concentration property for [f(z) E(f)
that depends on the Lipschitz constant L(f).
The induced concentration property allows us to bound the probability in Equation 9 leveraging the intuition that smaller Lipschitz constant limits the function's 'ss capacity to align with random labels. However, it is important to note that Equation 10 provides information about robustness within F only if
P(A E F: Re( N 0) 1
EF Re()) R 26
Otherwise, the implication becomes vacuous, as almost no function in F generalizes well, i.e., achieves near-zero empirical risk, begin with. Without imposing any assumptions μ,, Ho- effding's incquality already suffices to derive a Lipschizz-inddeeedden bound for any function X [1;
12
P(I[(x)- - R()) 2 S 2xxp
VI. 1 0.
(11)
Thus, to ensure that the probability in Equation 9 remains below d while simultancously allowing for P(3 E F Rf( = 0) > 8, any concentration inequality relying on the Lipschitz constant must exhibit sufficiently fast decay (in comparison with Equation [1] in the regime L(f) 2 1. This is necessary to yield a non-vacuous bound in Equation [0] which allows to assess robustness by the increase of the minimal Lipschitz constant T., even for T.
15

---

Published as a conference paper at ICLR 2026
For instance, McDiarmid's inequality applied to Lipschitz functions yields a tail bound of the order 2f2
exp(- diam(2 ), which is insufficient as decays faster than the Hoeffding bound only for L(f) < 2/ /id//ma)))) i.e., at least diam(X)) < 2 is required to include the (relevant) range L(J) >> of Lipschitz constants. This indicates that a certain restriction the admissible measures is indeed necessary to obtain non-vacuous statements, i.c., they can not be derived in full generality.
Notably, the c-isoperimetry condition in Equation leadd faster decay than the Hoeffding bound Equation when L(J)= < Vdc-1, making effective for functions with moderate Lipschitz con- stants in high-dimensional settings. Our goal is generalize this strategy to handle discontinuous functions, addressing the inherent challenges classification tasks.
A.2 EXPERIMENTS ON ISOPERIMETRY
To empirically investigate the role of the isoperimetric assumption in the relationship between curacy and stability, we conduct experiments on Gaussian data with increasing variance. We train 4-layer MIPs of varying width ensure comparable training conditions across widths, we first determine the number epochs re- quired for the smallest model to reach 99% training accuracy and then train all wider models for the same number of epochs. Under this training schedule, all models achieve 99% training accuracy. In this setting. the isoperimetric constant scales with the product of the variance and the ambient dimension 784, as follows from standard Gaussian concentration inequalities.
{128, 256, 512, 1024, 2048) on linear classification task. To
The first two plots in Figure 4 correspond the regime in which the isoperimetric scale e o2d remains (1). In this setting, stability increases with width and subsequently plateaus, mirroring the behaviour observed on MNIST and CIFAR-10. For larger values of this plateau structure disappears: stability becomes non-monotonic and decreases for sufficiently large widths.
These results indicate that the beneficial effect of overparameterization on stability is regime- dependent and can be disrupted when the underlying isoperimetric scale becomes large. However, confirming this behavior would require experiments across broader range network widths and systematic evaluation more complex datasets.
MLP, depth
GAUSS
MLP, depth
0.00115
0.0001
0.001
93.8
0.01266
0.00414
93.6
0.00413
0.01264
93.4
Accuracy (%6
0.00412
0.01262
93.2
90
0.01260
93.0
0.00410
0.01258
92.8
0.01256
92.6
0.00408
(best)
0.01254
92.4
0.00
0.25
0.50
0.75
1.00
1.25
0.00
0.25
0.50 0.75
1.00
1.25
Parameters
1e7
Parameters
1e7
GAUSS
MUP, deephh
GAUSS
depth
0.02795
0.005
93.6
0.0397
4² 0.01
0.02790
93.4
0.0396
0.02785
3
0.0395
93.0
0.02780
93.0
Accuracy
0.02775
92.8
92.5
0.02770
92.6
0.0393
0.02765
92.4
0.0392
92.0
0.02760
5ith
0.0391
0.02755
91.5
0.00
0.25
0.50
0.75
1.00
1.25
0.00
0.25
0.50
0.75
1.00
1.25
Parameters
1e7
Parameters
16

---

Published as a conference paper at ICLR 2026
GAUSS
MLP, depth
GAUSS
MLP, depth
57
0.05
0.0896
0.12775
93.0
0.0894
0.12750
92.5
0.12775
Accuracy [%
0.0892
5ifi
0.12700
0.0890
0.12675
0.0888
0.12650
91.0
0.0886
5:0
91.0
0.12625
5if
Acc need
AiC (teetl
90.5
0.0884
0.00
0.25
0.50
0.75
1.00
1.25
0.00
0.25
0.50
0.75 Parameters
1.00
1.25
Parameters
1e7
1e7
Figure 4: Class stability for 4-layer MLPs trained on Gaussian toy-data with different variances.
B THE SIGNED DISTANCE FUNCTION (REMARK 2
We collect the main properties of the signed distance function
dr(x)= = [dx,,/ ((-1)), if if)
1,
d(xe, if) = -11
where d(z, A) == inf || ul12.
Lemma 17. Let X' C RRd be bounded and path-connected, and let f X + {-1,1}. Then the signed distance function d is 1-Lipschitz.
This is a classical fact, a special case of the Eikonal equation. For completeness, we include direct proof inspired by Liu & Hansen 2024 Prop. 7.5).
Proof. Case 1: (xx = [(v). Assume w.l.o.g. f(x) = f(v) = 1. Let (zx), be a sequence in f ({-1)) with [dy, 2n) dy(x)l < 1 Then
(x) = d(I, f ({--1))
< d(x, 2n)
< || ull + d(y. 2n)
x || ull + (z) + n.
Letting + do and exploiting symmetry yields (dy(x) dy(ي)) I || y12-
Case 2: f(x) + f'v). Assume w.l.o.g. f(x) = 1, f(y) = -1 Consider the line segment =
{(1 t)x ty t [0, 1]} C X and define
W1 (1 f1 + tıv,
t := inf f((11 (((1-t)=:
ty) 1}} t)x -
to = sup(t: : f((1 - -)x + ty) = 1). Path-connectedness ensures f S 12, otherwise the midpoint between wi and W2 would be labeled both 1 and -1, contradiction.
W2 = (1 12)x + t2y,
Thus,
(dy(x) - dy(v)) d(z, 1- d(y, d(. |
wi 2 + 11 - w2 ll2
x
v112.
Lemma 18. Let X C Dd and f X + 1-1, 1} with f ((1}) closed. Then f can be represented
as
f(z) = sgn (x)).
where adopt the convention sgn
1
17

---

Published as a conference paper at ICLR 2026
Proof. If dy(x)) + O. the claim follows directly from the definition of dy. If dy(x) 0. then E ((1}) by closedness, so f(x) = = sgn(0).
Remark 19. Lemma 18 justifies the representation sgn ody used in the proof of Theorem This link between classifiers and their signed distance functions is what allows stability arguments be combined with smoothness-bass tools.
C PROOF OF THE RADEMACHER BOUND (THEOREM 4
In the regression setting, it is natural to restrict Lipschitz-continoous regressors, many com- monly used model classes (e.g., neural networks with bounded weights and Lipschitz activations) satisfy this property. This assumption enables quantitative statements about expected and achievable robustness. In contrast, this approach is not meaningful anymore in the classification setting as the considered classifiers are (except for trivial cases) discontinuous by design, i.e., they can not be cap- tured by a finite Lipschitz constant. Thus, statements about the robustness of classification models can not be derived via Lipschitz constants. This motivates the use of class stability as a replace- ment measure in the classification setting, which, however, is (inversely) related to Lipschitzness as highlighted and exploited in the subsequent proof of Theorem 4 For convenience, we repeat the statement with the corresponding assumptions.
(HI) (X, μ4) is probability space with bounded sample space X and c-isoperimetric measure μı; (H2) the considered hypothesis class F of classifiers f f-1, 1) is finite, that is |Fl < co. Theorem (Rademacher Bound). Suppose Assumptions (HI) and (H2) hold, and that min S(J) S > 0 with log [F] 2
1. The empirical Rademacher complexity satisfies
{
Ve. log |
Rn (F) I K1 max
(12)
Vni s nvd
for absolute constant K1
2. If. in addition, ((1)) is closed and X path connected, the bound sharpens to
Ve
log F
dss²
Rn & K2 max
expp
(13)
Vn'
S
nd
8c
for another absolute constant K2 >
Proof. 1. To begin, we explore the relationship between two measures of robustness: the Lipschitz constant T.J) and the class stability S(S) of F the set
A,(f) {ar X hy(x)) > S(f) -]
for 0 o
Observe that for 21 E A,() and x2 E X
0,
if f(x)) = f(x2)
21
< S()) -1 |||| x2|1
|1 32
if f( f(x2)
S(f)
ie., is - -ipscchtz A+(f) and, therefore, according the assumption S(f) S, any f F at most 5-7 Lipschitz on A,(f). Our strategy now is to apply the Rademacher bound based on Lipschitz functions of Bubeck & Sellke in Bubeck & Sellke (2021) to the restriction f(A,()) and additionally exploit isoperimetry to control the measure of the complement (f) We rely on two key facts:
18

---

Published as a conference paper at ICLR 2026
Fact 1: Every Lipschitz continuous function g : R. defined subset A X of a metric space, can be extended to a function G. X
R. preserving the same apply
Lipschitz constant (McShane (1934), Kirszbraun (9944)
This allows Lemma 4.1) to the 3-t"
isoperimetry and thereby the result in (Bubeck & Sellke 2021
Lipschitz extension Fj of f(A01)) (by w.l.o.g. restricting its codomain to |-1, 1) to obtain
log [F] 1
71
sup LEF
Σ
(a.)
C2 SC Vn +
5-t
nd
for some absolute constants C1, C2 > 0.
Fact 2: The margin hx(x)
X + R, is I-Lipschitz continuous with respect to the b--
norm (Liu & Hansen 2024 Prop. 7.5).
= This allows us to control PfA()f)) via
isoperimetry;
Rhhyl
dt2
dt²
P(A(())) = -hy S exp
2cL(h
=exp
2c
(14)
Via Fact 1, we can bound the Rademacher complexity by
n
Rm,,a (F)
sup SEF -=1
Σ (1r))
n1
n Σ
1
n o: - (T)
<
B
sup |EF
oi
F (sr+)
E
sup /EF
11
11
i=1
i=1
1
log |F
S Ci Vn
C2
5 5
+
sup
Σ o. - (x)
(15)
nd
fEF
To control the last term, we subdivide x into subsets on which specific samples achieve minimum margin. To that end, we fix 3/2 (the exact value is not crucial since it will be subsumed into the absolute constants) and define, for I C [r]].
S
A1 4 (
x 1Exx:iee = hy 2
Note, that (|)(()) Ag (f) and UIEP((n)) (f) is a disjoint partition of X". Thus, applying union bound yields for 0
S 3 Σ IP ( S
Σ ofls (xs(
sup fEF
Fer IEP((N)
Σ P JEF IEP(NN)
>r xrIEAA()) -o((s-
Σ of - Fy)(ss)
(AN()))((((()))) P(A(()).
(16)
We make the following observations:
By construction F, f holds on A' for all F.
As a mean-zero and bounded random variable with range [-2, o,(FF - (x)))) (via
Hoeffding's inequality) subgaussian with variance proxy (2-(-2))² 4 for every i [n]
Using the fact that the sum of independent subgaussian random variables with variance proxy o² itself subgaussian with variance proxy ko? (Rigollet & Hütter, 2023), we obtain for every Ç [n]
(the case = [n] being trivial) that
19

---

Published as a conference paper at ICLR 2026
a Σ olls - (z) > 8 A'(1)
SP [
oil -()(P)))))))
> >r 2r
iE/c
n.
S exp
2 2n4(n 111)
On the other hand, we get for I C [n] via Equation 14 that
"-
ds² n-1
P (A' & P (jer:: 2ÿ (f)) = PP E Ag ( < exp
28c
Inserting in Equation 16 and replacing the constants independent of the parameters of interest > then gives
(n, [FI, d, r,S, S, and (T) by c1, C2
(- r2c,
(n- - (
P
sup FEF
Σ o. - P)(
>
E E FEJ (EP(()))
exp
exp
To simplify the above expression, we want to find the maximal term in the sum and use this worst case as an upper bound over all terms in the sum. To that end, we introduce g [0,n] + R4 by
g(x) rda,
1 + (n x) dc2.
aiming to find its minima, which correspond to an upper bound on the sought worst-case term. Differentiating 9 yields the extrema
g'(x)
12a
1
dc
S
10
(n - x)²
14//=n n SV c2d
CIC
+ ((r)
(17)
We calculate the second derivatives to be g ) 0 and (0(x+) < O, thus only x- is minimum.
Now, there are two cases associated with the location of x- (taking into account that a(r) 0 for every r > 0).
Case (r)) S n.
Then, J- is a valid minimum in the considered range and therefore
P
sup fEF
Σ o Fa)(ss) 2r)
r2c1
a(rrdd5 C2
Σ Σ 2exp
(Ta(r)
exp
JEF (EP([N))(())
deze1
$ 2 exp -2rS8
:P)(n)r).
Case II: a(r) > n. Then, r_ < 0 is outside of the domain of g. However, the derivative satisfies g'(z) > 0 for any < x n since 24 > n. Therefore, g necessarily takes its minimal value at J = so that
n Σ
sup FEF
o - -o)(t) 2r)
r-e
ndS2 02
2xxp
exp
JEF IEP(IN)in))
r²c
ndS2 02
$ 2 exp
exp
= (r.
n
20

---

Published as a conference paper at ICLR 2026
Using Equation 17 the condition a(r) > n equivalent to r > ns ns//
ead
In this range, we have cse"
Pun)(r) ( since
c2d
c2d C
Pan n
= 2 exp de 62) PP -a)
C1C
and verifies that (r)) decays faster than (r)) when further increasing Therefore, conclude that for all r >>>
de2e1
sup SEF
2r) -r)s P() = 2|F exp -2rS
(18)
Further rewriting the expression, distinguishing between two cases with respect the magnitude of [F|2" yields the upper bounds:
Case 1: 1F S exp v
de2e1
We immediately obtain via Equation
18 that
de2c1
P
sup FET
a -o)(a-P)(aa))
>r) S 21 exp
-2r5
-rSy de2c1
S 2exp
2
doze1
S 2xxp
rS
3 Flo(([
c
<1
Case 2: 1F[2" > exp (rS)) dogei
V
In this case, the probability is trivially bounded by
2 r / degei
T
(22 2
sup P
Σ
ailf F()( >r
<
exx
log( Fl22)
fEJ
<1
Putting both cases together, we proved that for all r >>> 0
25 dezei
Σ oil - (xx(
sup FEF
>r)
< 2exp
3 3 (lg[(FFF12 (F122))
This tail bound shows that sup of F() is sub-exponential. Since the expected value of any sub-exponential random variable is up absolute constant given by its sub- exponential norm, which corresponds (up constant) to the parameter
3log([F12") in the tail 28 de201
bound Vershynin 2018). we obtain for a constant C3 > 0 that
log [F + n log 2
Σ o.lf Fy))s < C3
sup SEF
1=1
n
Finally, the desired bound on the Rademacher complexity follows via Equation 15
1
Rn,
sup fEF
f
n
1
1
log [F nd
Velog [F nvd
c j SV d'
G1
C2
Css
Cs
Vn
VV
21

---

Published as a conference paper at ICLR 2026
which, with the additional assumption log [F] n, gives the result in 1.
2. By Lemma 18
every f admits the representation f sgn ody. This lets follow the infinite- class analysis presented in detail in the proof Theorem without the s-net step in Equation 22 From Lemma 17 d is 1-Lipschitz, i.e., L(d,) 1 under the given conditions. Furthermore,
recalling the co-stability definition we get
(dy) = B[|dy]] = E[hy] = S(f).
Plugging this into the general bound in Equation gives the result.
C.I. COMPARISON TO STANDARD BOUND WITHOUT ACCOUNTING FOR STABILITY
Note that the crucial expectation in the derivation, i.e., the last term in Equation 15 be treated without linking it to the minimum class stability, Indeed, the expectation of the maximum of N subgaussians X1 X1...., XN with variance proxy o² scales
E max
Xxi|
S Sov (2N),
(19)
ISISN
see for instance Rigollet & Hütter
(2023).
Hence, in our case, as (x:) ) subgaussian oils (x;( is subgaussian with variance proxy 4n,
with variance proxy 4 and therefore 2;=1 we obtain
< I 2 (2 S C4 (V=+++ log F
o.l - - (at)
sup FEF
for some absolute constant C4 > 0. Neglecting the constants, this leads to the following comparison our bound in Equation 5
VC
log
F
S
nd
Thus, under the isoperimetry condition, our bound improves on the standard Rademacher complex- ity estimate whenever the class stability S exceeds /c/d, mild requirement in high-dimensional settings.
D PROOF OF THE LAW OF ROBUSTNESS (COROLLARY 6
Next, we provide the proof of Corollary which we repeat for convenience.
Theorem (Law of Robustness for Discontinuous Functions). Assume (H1), (H2), and the additional conditions in 2. of Theorem 4 hold. Let == log FF 2 n. Fix e, E (0, 1) and consider the 0-1 loss Ev11- There exists an absolute constant K such that,
1. the minimal risk R minser Rf-(ff satisfies R and
2. the sample size is large enough to ensure (i) Vn
K
< and (ii)
2 2lo((2/8)
<g
then with probability at least 1 - 8 (over the sample), the following holds uniformly for all f E F:
3K E
c clog [F
Sc log
6K
Ro-(ff < R -E
s(f) < max
nd
Proof. Let K > 0 be absolute constant such that Equation stability
holds, and define the threshold
3K
c cog F
8c d
6K
S. = S. d, = max
log
nid.
22

---

Published as a conference paper at ICLR 2026
Then, Theorem 4 together with condition 2(1), implies that
S. ve
log [
d.S
Rn S max
2cxp
sc/3,
Vn
nd
where Fs.. == (S E F S(J) 2 S.) is the subset of functions in F with stability at least S.. Hence, applying the generalization inequality Equation together with condition 2(ii), gives with probability 8:
2 2log(2/0)
sup (fa- - Ro- s (Rn. o Fs.) feFs.
(Fs. < E,
where we additionally used Equation 2 in the second step. In particular, we can bound the probability
P(V E Fs. (f) > R =) 2 P(V E Fs. Ra. Ro) <&) 2 1- 6,
where the first inequality follows from
(f) - (o) <
condition
R' -Fo- <f) = Ro-1(f) R² -E.
Decomposing this probability into two disjoint events
1 P Fs. Ro R - -) F Ro-1 > R =)
+ + Ro- < Rº -),,
(20)
enables to easily recognize that the expression exactly characterizes the probability that the fol- lowing implication, and thereby the result, holds uniformly for all f E F:
S()) < S.. Indeed, the implication above holds if, for a given data sample (I,, M either
R (f) S R
no function f F satisfies Ro-( S R - E. or
* any such f lies in Fs.. that is, S(f) < S.,
which is the case with probability least 8 due to Equation 20
E PROOF OF RADEMACHER BOUND FOR INFINITE FUNCTION CLASSES (THEOREM 13)
Here we show how to extend the result for finite function classes infinite function classes by covering argument, where the Lipschitz continuity of the parameterization turns out to be crucial. Please find the exact statement about the Rademacher complexity infinite function classes (of certain form) below, after restating our regularity hypothesis replacing (H2).
(H3) The hypothesis class F is of the form F sgn G. where G = {gw X (-1,1] E W) is parameterized class Lipschitz continuous functions. The parameter space W C IRP is bounded with diam(W) < W, and the parameterization is Lipschitz continuous, i.e.,
1|9 gwyl - J [|01 w2ll-
Theorem. Under assumptions (HI) and (H3), suppose that (*) S* and T(g) S T. for all g E G. Furthermore, assume that p 2 n. Then, for any covering precision & E> 0,
(F) S K max {VI. 3 & V 60WJE-1), 2exp
d ScL2
J
where K > O is absolute constant independent of p, n, d, St ,c J,
23

---

Published as a conference paper at ICLR 2026
Proof. Given any discontinuous classifier fw sgn og for 9w G, define its Lipschitz continuous approximation for >> as
f s ogw
where
- 1, t S -,, E |-7, 7
sg
2
This approximation satisfies the useful property that both Fy,. and the absolute difference If FiJl are Lipschitz continuous in both the input space X' and the weight space W, with
L sgn, 99w
sgm ogw)) L(sgn, ogw) [lgw]
(21)
Following the same strategy in the proof of Theorem with Lipschitz continuous approximations introduced above (see Equation 15 we obtain
coupled with a covering argument as in Bubeck & Sellke
2021
1
Rm,
sup s
fEF
-=1
1
sup JEF
oi (x4)
+ g
sup JEF
o. - (.((--F(aa)) FDMas)
Y1
i=1
C1
1 Vn + C
logg(1 + 60W JE
sup JEF
Σ o. Fyaa)
[Fel
Here the parameter& > is related to Eett of W, which we denote by Wg. Note, that | (1+ 60WJE- (see e.g. Vershynin 2018) Corollary 4.2.13) so the same holds true for the induced net
F& {sgn ogw WeJ, which also allows treat the remaining expectation by subdividing the supremum:
1
a arls - (a)
m
Σ
Σ cL F (a))
sup FEr
sup wrEWs
sup (e(s)
n
7
n
E
sup
Σ 1fwe
Pi ((x;)
71
mceW
Σ 15w - F(u((xs) - 1fw= - Flug [(xi]]
+
E
sup #2EW;
sup We (
(22)
By Lipschitz continuity of the parameterization and If Ffy as derived in Equation
we obtain
1h - Frul 1swe Ff
S f for any we We and Ba(we)
_
so that
J
E
sup wrWW, we (g((n))
sup
1 Fx;) - Ifwz Fs (
<
Via isoperimetry and using the same bound on the cardinality F3 as before, one concludes that the first expectation in Equation 22 is of the same form as Equation 19 with subgaussian variance proxy x² L2 en so that
72
72
E sup
Σ fswr (xxi)
E.,
sup Σ fww FY (2x)) Ellfw, Fl E.
n
w. E.
n
sup
[l Fywgll
wwEW;
<
C3
c
plog(1 (1 + GE-JE-1) + sup El],ww Fl w.EW;
nd
24

---

Published as a conference paper at ICLR 2026
Finally, for every E F,
B - Fyl]
Fy1|= =
- F)(2)) P(g(2) E [-7, 7))-
(23)
Choosing 7 - (g) we obtain by the definitions of co-margin, and once again isoperimetry (since the co-margin inherits the Lipschitzness from g by design)
((((x) e [->x))) [1(x)) (g)
(Ig(()) -5) 5¹(
s IP
( (o)
dS
dS
2exp
8cT.(g)2 (-
< 2exp
2 2xx
8c1.2
Putting it all together, we have
2J
ds
Rn)(FF & C1 - + +2 V
E + 2exp
5
8cT,2
F MULTI-CLASS CLASSIFICATION
In this section, we briefly outline how our results extend to categorical distributions with C E N classes. We assume that a classifier given by
f: 10.13
with exactly one non-zero entry for each E X. The additional regularity assumption (H3Y, the adaptations of the conditions in (H3) to the multi-class setting can be formalized follows.
(H3) The hypothesis class has the form F argmax cG, where G {gw X + [0, 1]c w W} is a parameterized family of Lipschitz functions. The parameter space W C R2 is bounded with diam(W) W, and the parameterization Lipschitz:
l1
Iwalloo S J [| - w2ll-
Thus, we can interpret E G as representing the class probabilities.
Remark 20. For binary classification, iee. 2, the classifiers are of the form f instead of f X - [-1,1}, as considered earlier. However, one can translate between these representations by post-composing with either
{0, 133,
a(21, ==
B(x) == st1 2-,1
By the contraction principle for Rademacher complexity, it is therefore sufficient to compute the complexity for one of these models.
As in the binary case, our proofs start by considering the Rademacher complexity of the function class F:
1 Rn,a( (F) Eo n
ogg (
2 Σ
Bgy of f
sup /EF
sup JEF
n
Each summand corresponds to a binary classification problem with one-vs-all classifier fy. Indeed, fy is 8th Lipschitz on (f).) Transforming via
f, ト 2f, 1: 11: 1-11,,
we can follow the same reasoning as in Appendix C obtaining, up to a linear factor of C, the same result the first part of Theorem 4 generalized to the multi-class setting.
25

---

Published as a conference paper at ICLR 2026
Table 1: Multi-class definitions.
Concept
Definition
Isoperimetry
(x) [| 2 1) < 2 2exp
di
2c1."
Rademacher complexity
Re, (F) = ; E
SuP
و (z 1
Margin
hy(x) = Σラ= (x).
11(()= = inf(ll> - 2112 f(z) J Rd)
Class stability
S(f) Σn S(f),
C
S(f)' E[hy!
Co-margin
kz(x)) Σ5 (1)()),
1g((x) max (0.g)(z) max (z)
Co-stability
(g) Ej= (g),
(n)(g) = E[hg']
Similarly, under assumption (H3), can write
2f 1 sgn max (x)). .f3
which allows us to proceed as in Appendix D to obtain a multi-class generalization of the second part of Theorem 4 and Theorem 13
The only minor difference lies in bounding the term in Equation 23
B[I, F 1l - (1))
max 9: (2)) S 7]
(f)
Choosing 7 = 8* (g) 2 we use that for all j. (x) max 9 (x)) > (z),,, which yields
((lg((x) max gx))
(0(0)
(())(()) (f) 2 ("(e)
if)
S 2expp
(g)²
8cL(g)
d
S 2exp
ds*2 KcL?
exp
8c
We conclude that all of our results extend to the multi-class case. Moreover, the measure used in our MNIST and CIFAR-10 experiments (Section 6 is the correct generalization.
G EXPERIMENTAL DETAILS FOR STABILITY MEASUREMENT
Training setup. We trained fully connected MLPs with 4 or hidden layers on MNIST and CIFAR- 10, using widths {128, 256, 512, 1024, 2048). For CIFAR-10, additionally eval- uated convolutional neural networks (CNNs) with widths w E (128, 256, 512, 1024). On MNIST, considered Heaviside-activation MIPs examine whether the observed scaling behaviour tends to discontinuous score functions.
All MLP models use ReLU activations (or Heaviside activations where specified) and batch normal- ization. Optimization was performed with Adam (Kingma & Ba 2013) for embedding and output layers and Muon (Jordan et al., (024) for hidden layers, using a batch size of 256 and learning rate 10-3, Training continued until at least 99% training accuracy was achieved, yielding near- interpolating solutions.
Additional MNIST protocols. For 8-layer MLPs on MNIST, we additionally performed two con- trolled variations: (i) extended-widie experiments with w up to 16384, and (ii) fixed-epoch training runs in which all widths were trained for seven epochs, independent of when 99% training accuracy was first reached (all models attained 99% within this budget). These experiments isolate the effect of overparameterization from heterogeneous training durations.
26

---

Published as a conference paper at ICLR 2026
Parameter counts and normalization. For each model, recorded the total number of trainable parameters input dimension d, and total number of training samples n.
Stability estimation. Class stability S(f) is estimated via &g adversarial perturbations us- ing Foolbox (Rauber et al. 2017). We apply collection of lg attacks (including Deep- Fool and 22-PGD (Moosavi-Deztoolii et al. 2016, [adry et al., 2018)) over an E-grid {0.01, 0.05, 0.1, 0.2, 0.5, 1.0,2.0; For each input x, we record the minimum achieved perturbation norm min a| æ=I2 across all attacks and E values. If no attack succeeds within the maximum E, we set the perturbation norm to max(s). For the chosen s grid, attack success rates exceed 90% across model sizes, and are typically higher for smaller widths. Failures occur primarily for the largest models, where no adversarial example is found within the maximal radius. In these cases, the assigned value max(e) induces a downward bias, so the reported stability values are conservative lower bounds.
Normalized Co-Stability estimation. The empirical co-stability (g) is computed via the multi- class margin
9, (x) m 1
j == arg max (z))..
averaged over the dataset. method (Xu & Sivaranjani 2024), and report the normalized ratio (g) a function of model size.
We estimate the Lipschitz constant L(g) using the efficient ECLIPSE
Implementation.
Training and evaluation code is implemented in PyTorch (Paskee et al. 2019). For MLPs, images were flattened to vectors, Attack evaluations were conducted over the test dataset.
Reproducibility. All experiments were run with multiple random seeds 1,, 4J. and mean with standard deviation are reported.
H ADDITIONAL EXPERIMENTS
We report additional experiments for MLPs trained on MNIST and CIFAR-10 with varying depths. Unless stated otherwise, MLP widths are E {128, 256, 512, 1024, 2048J. Each figure shows class stability (left) and normalized co-stability (right) as a function of width.
H.1 CIFAR 10
Figure illustrates the width-dependent scaling of 4-layer MLPs CIFAR-10. The observed in- crease in stability aligns with the qualitative trend indicated by our theoretical analysis and is com- parable to the behaviour of the 8-layer models.
CIFAR10 MLP, depth
CIFAR10
depth
0.3b
54
0.10
0.30
52
0.08
52
500
0.25
(g)
51
0.06
50
-99
49
48
0.04
48
0.15
S'tg)
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
Parameters
Parameters
Figure 5: 4-layer MLPs on CIFAR10.
27

---

Published as a conference paper at ICLR 2026
H.2 MNIST
Figure [ indicates a monotonic increase in stability with width for 4-layer MLPs, in line with the qualitative behaviour suggested by our theory. In contrast, the 8-layer models in Figure display initial decrease in stability for small widths.
We attribute this effect heterogeneous training durations. To reach 99% training accuracy, narrow models required to seven epochs, whereas the widest models required only two, with a monotonic trend across widths. Since cross-entropy training continues increase margins even after achieving correct/perfect classification, training duration, especially in the low epoch regime, induces system- atically smaller stability values.
We test this hypothesis in two ways. First, we extend the width range up to w 16384 (Figure 8 For sufficiently large widths (with inherently similar/equal number of epochs), the predicted mono- tonic relation between model size and stability is recovered. Second, we fix the training duration to seven epochs for all widths (Figure 9 Under uniform training, the expected scaling behaviour is restored across the full width range.
The same effects are observed for normalized co-stability,
MNIST
MLP, depth
MNIST MLP, depth
98.4
98.4
1.10
0.31
1.05
98.2
0.30
98.2
0.29
0.95
Aecuras
Accuracy
0.90
97.8
0.27
97.8
97.6
0.26
97.6
0.80
0.25
Sin
97.4
97.4
Acc (eat))
0.24
Ace (beet)
0.75
0.00
0.25
0.50
0.75
1.00
1.25
0.00
0.25
0.50
0.75
1.00
1.25
Parameters
1e7
Parameters
Figure 6: 4-layer MLPs on MNIST.
MNIST
MLP, depph
MNIST depth
0.056
0.90
0.88
0.054
0.36
97.7
97.6
0.053
97.6
0.84
97.5
0.052
97.5
0.82
97.4
97.4
97.3
97.3
0.050
Tig)
97.2
97.2
0.5
1.0
2.0
2.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Parameters
167
Parameters
Figure 7: 8-layer MLPs MNIST.
28

---

Published as a conference paper at ICLR 2026
MNIST
MLP, depth
MNIST MLP, depth
1.10
98.0
98.0
1.05
97.9
0.0650
97.9
97.8
0.0625
97.8
1.00
97.7 3
97.7
Accura 96
0.0600
97.6
97.6
0.90
97.5
97.5
97.4
0.0550
97.4
0.85
97.3
0.0525
97.3
0.80
Acc (ast)
0.0500
Acc (osst)
97.2
0.5
0.0
0.5
1.5
Parameters
1e9
Parameters
1e9
Figure 8: 8-layer MLPs on MNIST with extended widths up to w 16384.
MNIST
MLP, depth 8
MNIST
MLP, depth
1.02
0.625
1.00
0.600
97.8
97.8
Accuracy [%6]
0.575
Accuracy 199]
0.96
97.6
0.550
97.6
0.94
0.92
0.500
0.90
Acc Dostt
-97.2
Acc trestt
-97.2
1.0
2.0
2.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Parameters
1e7
Parameters
1e7
Figure 8-layer MLPs on MNIST trained for epochs.
29


Reviews:
[{"review_id": "8jfmS1gu4t", "reviewer": "Reviewer_mVwX", "summary": "The paper extends results on isoperimetry and robustness to discontinuous classifiers, instead of the regression setup from Bubeck & Sellke.\nTo this end the authors define a notion of class stability that measures the expected distance to the decision boundary within each class, and serves as a type of stability criterion in the classification case.\nFor a finite hypothesis class, a bound is derived for the Rademacher complexity that depends on the minimum class stability, the isoperimetry of the data distribution and of course the sizes of the class and dataset. The main conclusion from the bound is that the size of the hypothesis class needs to grow much larger than the size of the dataset in order to produce a good upper bound on the generalization error.\n\nThe results are extended to non-finite hypothesis classes using some additional conditions, and simulations are performed on MNIST and CIFAR10 to demonstrate the theory.", "questions": "No immediate questions come to mind, as the paper is written quite clearly. I will read the other reviews and see if questions come up from them.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides a nice addition to the literature on stability and interpolation. While it gives results that are in similar flavor to existing results, there are still original developments that can be of interest to the community.\nTo achieve their generalization, the authors discuss several notions of stability and how they are combined with assumptions on the hypothesis class, in order to obtain meaningful results. I think these derivations are easy-to-understand and clearly written, and so is the rest of the paper.", "weaknesses": "The most apparent weakness of the paper is that it is somewhat incremental, and proves results that are in the spirit of Bubeck and Sellke. Since the technical tools developed in the paper are novel, I think that this is not a major drawback.\n\nSmall comment: the authors mention generalization also in the context of out-of-distribution generalization and refer to a few results on this problem (e.g. Zou et al. 24). Since the paper refers to these topics and mentions generalization as a whole and not just in-distribution (or adversarially robust) generalization, I think it should also make a distinction between this setting and the setting of robustness to other distribution shifts (like spurious correlations, covariate shift etc.). The settings are rather different, but there were works discussing overparameterization in the context of distribution shifts, giving both negative and positive results [1,2,3]. Since the two lines of work share some terminology, I think it'd be useful to shortly clarify the distinction.\n\n[1] Wald, Y., Yona, G., Shalit, U., & Carmon, Y. Malign Overfitting: Interpolation Can Provably Preclude Invariance. In The Eleventh International Conference on Learning Representations.\n\n[2] Hao, Y., Lin, Y., Zou, D., & Zhang, T. (2024). On the benefits of over-parameterization for out-of-distribution generalization. arXiv preprint arXiv:2403.17592.\n\n[3] Sagawa, S., Raghunathan, A., Koh, P. W., & Liang, P. (2020, November). An investigation of why overparameterization exacerbates spurious correlations. In International Conference on Machine Learning (pp. 8346-8356). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "D4BsjgANnz", "reviewer": "Reviewer_WFc2", "summary": "This paper extends the \"universal law of robustness,\" which analyzes the relationship between overparameterization, stability, and generalization, to the domain of discontinuous classifiers. The authors prove that for any discontinuous classifier, overparametrization is necessary if one wants to robustly interpolate the data. The prior work by Bubeck and Selke (2021) established this law for high-dimensional Lipschitz functions, but their reliance on the Lipschitz constant is problematic for discontinuous classifiers. To address this, the authors leverage alternative stability measures: the input-space margin concept of \"class stability\" and a newly introduced output-space metric called \"normalized co-stability.\" By employing these two measures, they successfully extend the theoretical framework to the discontinuous case, providing a compelling explanation for why modern, heavily overparameterized models can achieve robust generalization.", "questions": "Q1.  About $\\mathrm{sgn}\\circ \\mathcal{G}$. While it clearly covers classical models like SVMs, its application to modern deep learning architectures merits further clarification. Could you provide examples of overparameterized deep learning models that fit the definition of a discontinuous classifier in this paper, and perhaps more importantly, any that might not fit this structure?\n\nQ2. The original Bubeck & Selke (2021) paper required a lower bound on the data dimension $d$ relative to the level of robustness $\\varepsilon$ (Assumption 4 in their paper). This assumption appears to be absent in your work. Could you highlight why this dimensional lower bound is no longer necessary in your proof for discontinuous classifiers?\n\nQ3. The theoretical bounds you derive depend on the true data distribution, which is unknown in practice, raising the possibility that the bounds could be vacuous. While the experiments effectively show a correlation between the proposed stability measures and test performance, could you compute the actual upper bounds derived in the paper using empirical estimates? How do these computed bound values compare to the observed generalization error?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "A major strength of this paper lies in its successful extension of the theoretical framework beyond the original Lipschitz assumption to the more challenging domain of discontinuous classifiers. While the work is theoretical in nature, its findings have practical implications explaining why heavily overparameterized models, which are common in modern machine learning, can achieve robust generalization. Furthermore, the paper is well-written and organized.", "weaknesses": "Its novelty feels somewhat incremental. At a high level, the core idea mirrors that of Bubeck and Selke (2021): the original work used the Lipschitz constant to ensure that for different inputs $x_i$ and $x_j$, the distance $\\|| x_i - x_j\\||$ is non-trivial (i.e., $\\Omega(1)$); this paper adopts a similar underlying principle.\n\nFor finite function classes, the authors use the \"class stability\" proposed by Liu and Hansen (2024) to derive an upper bound on the Rademacher complexity. However, as noted in Remark 5, this bound introduces an undesirable additional factor in certain regimes, which requires further assumptions to mitigate.\n\nFor the infinite function class case, the analysis is restricted to a specific function class of the form $\\mathrm{sgn}\\circ \\mathcal{G}$, where $\\mathcal{G}$ is Lipschitz. This raises questions about how broadly the results can be generalized to all discontinuous classifiers. The newly proposed \"co-stability\" measure, used to derive Theorem 13 and Corollary 15, is defined in terms of this Lipschitz constant of $\\mathcal{G}$. Consequently, the results feel analogous to the original idea by Bubeck and Selke, with the main difference being the consideration of a composed function class $\\mathrm{sgn}\\circ\\mathcal{G}$ rather than a fundamentally new approach.​​\n\nTypo:\npage 4: The first bullet in thm4: empirical Rademacher complexity -> Rademacher complexity", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zGrz6FmXDr", "reviewer": "Reviewer_qsC1", "summary": "The paper defines two robustness/stability surrogates for discontinuous classifiers and proves data‑dependent generalization bounds that tighten as stability increases: class stability $S(f)$ and normalized co‑stability $\\bar{S}^*$. Under a c-isoperimetry assumption on the data distribution (Def. 3, p. 4), the authors prove a Rademacher complexity bound for finite classifier classes, and an extension to infinite, parameterized classes via normalized co‑stability and parameter‑Lipschitz score maps. Experiments are conducted On MNIST and CIFAR‑10 with fully‑connected MLPs.", "questions": "- Assumption stress‑test. Can you empirically probe the isoperimetry assumption (e.g., concentration of Lipschitz functions) on MNIST/CIFAR embeddings, or supply a synthetic non‑isoperimetric counterexample where your bound degrades?\n- Is the theoretical claim / empirical phenomena general enough, to hold on other classifiers, such as SVM, random forest classifiers, etc (other than MLP)? Will one obtain similar experiment results with different network architectures?\n- typos: “Selke” should be “Sellke”", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Framing of robustness for discontinuous classifiers. Replacing Lipschitzness of $f$ with expected input‑margin and codomain margin is sensible and bridges a known gap in extending the Bubeck–Sellke robustness law to classification. The formalization via signed‑distance representation is clean.\n- The finite‑class bound (Theorem 4) uses a careful Lipschitz surrogate + isoperimetry argument, then sharpens by invoking the signed‑distance representation. The infinite‑class extension cleanly separates the roles of average confidence and smoothness.", "weaknesses": "- Assumptions vs. practice gap. The isoperimetry requirement on $\\mu_X$ is strong and not stress‑tested. The paper states a manifold‑dimension interpretation, but no empirical probes of isoperimetry or concentration are provided, even in toy data. The external validity of the law depends on this.\n- Overparameterization claim feels over‑indexed to $nd$. The corollaries argue a necessity of $p≈nd$, but the experiments do not stress this scaling (e.g., sweeping $n$ and $d$ while reading off the stability needed), nor do they test architectures beyond MLPs. As written, the claim risks overreach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)