Paper deep dive
Does Order Matter : Connecting The Law of Robustness to Robust Generalization
Mihir More, Aritra Das, Jaee Ponde, Himadri Mandal, Vishnu Varadarajan, Debayan Gupta
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/20/2026, 1:36:13 PM
Summary
This paper connects the Law of Robustness, which posits that overparameterization is necessary for robust interpolation (Lipschitz continuity), to robust generalization, defined as the gap between robust training and test loss. Using Rademacher complexity, the authors prove that for global complexity, the Lipschitz bound order remains $\Omega(n^{1/d})$. However, for local complexity (small empirical error), the bound changes depending on the perturbation radius $\rho$ and the localized concentration term $\sqrt{r/n}$.
Entities (8)
Relation Signals (6)
Law of Robustness → implies → Lipschitz continuity
confidence 95% · The Law of Robustness states that overparameterization is necessary for models to interpolate robustly, i.e., the interpolating function is required to be Lipschitz.
Law of Robustness → requires → Overparameterization
confidence 95% · The Law of Robustness states that overparameterization is necessary for models to interpolate robustly
Rademacher Complexity → analyzes → Robust Generalization
confidence 93% · This can be studied using statistical learning techniques such as Rademacher complexities
Rademacher Complexity → bounds → Lipschitz Constant
confidence 93% · a bound on the Rademacher complexity of the robust loss class implies a bound on the Lipschitzness of the function class.
Wu et al. → proved → Lipschitz Constant Bound
confidence 92% · Wu et al. (2023) extend this law to arbitrary data distributions, proving that the Lipschitz constant satisfies $L = \Omega(n^{1/d})$.
Local Rademacher Complexity → dependson → Perturbation Radius
confidence 90% · At the local scale... the order of the Lipschitz bound changes with the perturbation radius $\rho$
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Bubeck and Selke (2021) propose the connection between the Law of Robustness and robust generalization error as an open problem. The Law of Robustness states that overparameterization is necessary for models to interpolate robustly, i.e., the interpolating function is required to be Lipschitz. Wu et al. (2023) extend this law to arbitrary data distributions, proving that the Lipschitz constant satisfies $L = \Omega(n^{1/d})$. Robust generalization, on the other hand, asks whether small robust training loss implies small robust test loss. This can be studied using statistical learning techniques such as Rademacher complexities, where a bound on the Rademacher complexity of the robust loss class implies a bound on the Lipschitzness of the function class. We use this connection to explicitly link the two for arbitrary data distributions. (i) We prove that the order of the Lipschitz bound remains the same when considering the global Rademacher complexity of robust loss classes. (ii) At the local scale, i.e., for subsets of functions with small empirical error, the order of the Lipschitz bound changes with the perturbation radius $\rho$ and the localized concentration term $\sqrt{r/n}$.
Tags
Links
- Source: https://arxiv.org/abs/2602.20971v3
- Canonical: https://arxiv.org/abs/2602.20971v3
Trouble viewing inline? Open PDF directly →
Full Text
70,232 characters extracted from source content.
Expand or collapse full text
Does Order Matter: Connecting the Law of Robustness to Robust Generalization Mihir More Ashoka University, Sonepat, Haryana &Aritra Das Ashoka University, Sonepat, Haryana Truth Audit Labs &Jaee Ponde Ashoka University, Sonepat, Haryana &Himadri Mandal Indian Statistical Institute, Kolkata &Vishnu Varadarajan Ashoka University, Sonepat, Haryana &Debayan Gupta Ashoka University, Sonepat, Haryana Truth Audit Labs Abstract Bubek and Selke [3] propose the connection between the law of robustness and robust generalization error as a fantastic open problem. The Law of Robustness states that overparameterization is necessary for models to interpolate robustly, i.e., the function is required to be Lipschitz. Wu et al. [30] extend this law for arbitrary data distributions, proving L = Ω(n1/d) (n^1/d). Robust generalization, on the other hand, asks if small robust training loss implies small robust test loss. This can be studied using statistical learning techniques like Rademacher complexities. Accordingly, a bound on the Rademacher complexitiy of the robust loss class implies a bound on the Lipschitzness of the function class. We use this to explicitly connect the two for arbitrary data distributions. i) We prove that the order of the Lipschitz bound remains the same when considering global Rademacher complexity of robust loss classes. i) At the local scale, that is, for subsets of functions with small empirical error, the order of the Lipschitz bound changes with the perturbation radius ρ and localized concentration term r/n r/n. 1 Introduction Deep neural networks have demonstrated exceptional performance across different machine learning applications [16]. One of the fundamental methodologies of deep learning involves overparameterized models. These networks are highly expressive and are often easy to optimize to (near) zero training error with SGD. [21] In many settings, making the model even larger can improve test performance beyond the interpolation threshold, a phenomenon also known as double descent [22]. Bubek et al. [2] provide a theoretical explanation for why overparameterization is necessary: they introduce a sharp law of robustness for two layer neural networks showing that achieving robust interpolation characterized by a small Lipschitz constant requires more parameters than interpolation alone. Bubek and Selke [3] then prove a universal version under isoperimetric covariate distributions, showing that smooth interpolation for O(1)O(1) Lipschitz requires p≫ndp nd parameters. Furthermore, Wu et al. [30] extend the theory beyond isoperimetry, providing robust-interpolation lower bounds for arbitrary bounded-support distribution. Despite their remarkable success, deep networks remain vulnerable to subtle perturbations, as revealed through the existence of adversarial samples [12]. The most common mitigation strategy is adversarial training, where models are trained on adversarially perturbed examples to improve robustness [26]. Other methods such as margin-based measures, flatness-based measures, and gradient-based measures have also been utilized to improve adverserial robustness [24]. Another line of work pursues certified robustness by constraining the Lipschitz constant of the model, which provides formal guarantees on the maximum possible perturbation impact [14]. However, none of these methods explicitly connect these two different notions of robustness, i.e., the Law of Robustness to robust generalization. Bubek and Selke [3] refer to this connection as a “fantastic open problem.” We study this problem through the lens of Rademacher complexity, which provides distribution-dependent uniform bounds on the deviations of the induced loss class. We first show that, under the assumption of overfitting, we can bound the robust generalization error. We then apply global Rademacher bounds to obtain upper and lower bounds on the complexity of the loss class. This allows us to derive a bound on the Lipschitz constant of the robust loss, which we observe does not change its order and remains Ω(n1/d) (n^1/d), consistent with the distribution-free setting in [30]. However, global Rademacher complexity is too coarse for interpolation and low-error regimes, because it measures the complexity over the entire loss class rather than the small-risk region selected by the learning process [1, 15]. Local Rademacher complexity allows us to compute the complexity of subclasses with small empirical risk, thus providing tighter bounds. Covering numbers can be used to relate metric entropy estimates to local Rademacher complexity bounds [17]. Motivated by this, we polynomially bound the metric entropy of Lipschitz function classes using covering numbers and graph theory. We use this result to bound the metric entropy of the robust square loss, and then prove that polynomial entropy implies a local bound on the Rademacher complexity. We extend our previously obtained lower bounds on the Robust Generalization gap in the global setting (where we showed that the order of the Lipschitz constant does not change), to the local setting. We now find that the bound on the Lipschitz constant of the robust loss is dependent upon the perturbation radius ρ and localized concentration term r/n r/n. So we answer the titular question, does order matter? It turns out this depends on how closely one looks! 2 Related Work 2.1 Adversarial robustness, adversarial training, and Lipschitz Modern neural networks are vulnerable to adversarial examples, a phenomenon first identified by [27, 11]. The most widely used defense is adversarial training, which minimizes a worst-case objective over bounded perturbations [20], with principled variants such as TRADES making explicit the trade-off between standard and robust accuracy [35]. Furthermore, parameter-free evaluation suites such as AutoAttack are commonly used for reliable comparison due to robustness being highly sensitive to the threat model [8]. Another line of work deals certified robustness by controlling (global or local) Lipschitz. Bounding a model’s Lipschitz constant yields worst-case guarantees on output variation under input perturbations, motivating Lipschitz regularization and Lipschitz-constrained architectures. Examples such as Parseval networks [7], Lipschitz-margin training for scalable certification [28], and more recent work emphasizing expressive Lipschitz networks for improved certified robustness [34]. However, computing tight global Lipschitz constants for deep neural networks is difficult, so much work has focused on computable bounds and approximations. CLEVER relates robustness evaluation to local Lipschitz estimation [29], while optimization-based methods provide tighter upper bounds for neural networks [10]. Zuhlke and Kudenko [38] provide a comprehensive survey unifying Lipschitz constants, adversarial attacks, robustness guarantees, and estimation methods. 2.2 Overparameterization and laws of robustness Recent theory connects model size and smooth interpolation through lower bounds on the Lipschitz constant of interpolating predictors. Bubek et al. [2] formulate and prove a sharp trade-off for two-layer networks, suggesting that overparameterization is necessary to achieve small Lipschitz constant while fitting the data. Bubek and Selke [3] establish a universal version under isoperimetric-type covariate distributions, showing that smooth interpolation can require substantially more parameters than interpolation alone. Wu et al. [30] extend this direction beyond isoperimetry and derive distribution-free robust-interpolation lower bounds, including an Ω(n1/d) (n^1/d) regime for general bounded-support distributions. More recently, Das et al. [9] generalize universal-law-type results beyond squared loss to a broad family of Bregman divergence losses (covering common classification losses), and related work also studies robustness laws under weight-bounded classes [13]. 2.3 Robust generalization and robust overfitting A persistent challenge in adversarial robustness is robust generalization, where robust training error can be low while test error remains high. It is known that robust learning can require significantly more labeled data than standard learning, even in simple data models [25, 4, 33]. It has also been shown by [31] that robust generalization bounds exhibit unavoidable dimension dependence unless additional structure is imposed. A closely related phenomenon is robust overfitting: continued adversarial training can improve robust training loss while degrading robust test performance [23]. Subsequent work proposes mechanisms to mitigate robust overfitting via learned smoothing regularization [5] or by analyzing which subsets of adversarial examples drive overfitting and modifying training to counteract it [32]. Moreover, it has recently been shown why why robust generalization is intrinsically challenging from an expressive power perspective [18]. Finally, several recent papers develop stability-based and training-dynamics-based explanations for robust generalization behavior [36, 6, 37]. Additionally, recent work further formalizes the clean-generalization vs. robust-overfitting dichotomy through representation complexity and phase-transition analyses [19]. 3 Law of Robustness and Robust Generalization 3.1 Notation All random variables are defined on a common probability space. The data-generating distribution is denoted by P, and a generic sample is written as Z=(X,Y)∼PZ=(X,Y) P, where (X,Y)(X,Y) takes values in ×⊆ℝd×[−1,1]X×Y ^d×[-1,1]. Let σ2=[Var(Y∣X)]σ^2=E[Var(Y X)] be the irreducible noise level. The training sample is written as S=Zi=(Xi,Yi)i=1n∼PnS=\Z_i=(X_i,Y_i)\_i=1^n P^n. PnP_n denotes the empirical measure associated with S. Thus, for any measurable function g:×→ℝg:X×Y , we write Pg=[g(X,Y)]andPng=1n∑i=1ng(Xi,Yi).Pg=E[g(X,Y)] P_ng= 1n _i=1^ng(X_i,Y_i). For ρ≥0ρ≥ 0, let Bρ(x)=B_ρ(x)= denote the closed Euclidean ball of radius ρ centered at x. We also define the ρ-enlargement of the input space by ρ=x+u:x∈,‖u‖2≤ρ.X_ρ=\x+u:x ,\ \|u\|_2≤ρ\. For L≥0L≥ 0, let ℱL=f:ρ→[−1,1]:|f(x)−f(x′)|≤L‖x−x′‖2for all x,x′∈ρF_L= \f:X_ρ→[-1,1]:|f(x)-f(x )|≤ L\|x-x \|_2\ for all x,x _ρ \ be the class of bounded L-Lipschitz functions. When the perturbation radius is clear from context, we suppress the dependence of ℱLF_L on ρX_ρ. For f∈ℱLf _L, the clean squared loss and the adversarial squared loss at radius ρ are ℓ0,f(x,y)=(f(x)−y)2 _0,f(x,y)=(f(x)-y)^2 and ℓρ,f(x,y)=supx~∈Bρ(x)(f(x~)−y)2 _ρ,f(x,y)= _ x∈ B_ρ(x)(f( x)-y)^2. When ρ=0ρ=0, this reduces to the clean loss. The corresponding clean population and empirical risks are R0(f)=Pℓ0,fR_0(f)=P _0,f and R^0(f)=Pnℓ0,f R_0(f)=P_n _0,f, while the robust population risks and empirical risks are Rρ(f)=Pℓρ,fandR^ρ(f)=Pnℓρ,fR_ρ(f)=P _ρ,f R_ρ(f)=P_n _ρ,f. The robust generalization gap is denoted by Gapρ(f)=Rρ(f)−R^ρ(f)Gap_ρ(f)=R_ρ(f)- R_ρ(f). The clean and robust loss classes induced by ℱLF_L are ℒ0(ℱL)=ℓ0,f:f∈ℱL,ℒρ(ℱL)=ℓρ,f:f∈ℱL.L_0(F_L)=\ _0,f:f _L\, _ρ(F_L)=\ _ρ,f:f _L\. When the underlying predictor class is clear, we abbreviate these by ℒ0L_0 and ℒρL_ρ. Finally, when (T,dT)(T,d_T) is a metric space and η>0η>0, the covering number (η,T,dT)N(η,T,d_T) is the smallest integer N for which there exist t1,…,tN∈Tt_1,…,t_N∈ T such that T⊆⋃j=1Nt∈T:dT(t,tj)≤ηT _j=1^N\t∈ T:d_T(t,t_j)≤η\. If no such finite cover exists, we set (η,T,dT)=∞N(η,T,d_T)=∞. For a class G of functions and a probability measure Q, we write ‖g−h‖L2(Q)=(Q(g−h)2)1/2\|g-h\|_L_2(Q)= (Q(g-h)^2 )^1/2. Thus (η,,L2(Q))N(η,G,L_2(Q)) denotes the covering number of G under the L2(Q)L_2(Q)-metric. We first show that clean overfitting creates a robust train–test gap. Furthermore, we use Rademacher generalization bounds to obtain a lower bound on the complexity of the robust loss class. Lemma 1 (Robust generalization gap and overfitting). For any f∈ℱLf _L, R^ρ(f)≤(R^0(f)+Lρ)2, R_ρ(f)≤ ( R_0(f)+Lρ )^2, and hence Gapρ(f)≥σ2−(R^0(f)+Lρ)2Gap_ρ(f)≥σ^2- ( R_0(f)+Lρ )^2. Proof. For each (Xi,Yi)∈S(X_i,Y_i)∈ S and every X~i∈Bρ(Xi) X_i∈ B_ρ(X_i), |f(X~i)−Yi|≤|f(Xi)−Yi|+|f(X~i)−f(Xi)|≤|f(Xi)−Yi|+Lρ|f( X_i)-Y_i|≤|f(X_i)-Y_i|+|f( X_i)-f(X_i)|≤|f(X_i)-Y_i|+Lρ. Taking the supremum over X~i∈Bρ(Xi) X_i∈ B_ρ(X_i), squaring, and averaging gives R^ρ(f)≤1n∑i=1n(|f(Xi)−Yi|+Lρ)2 R_ρ(f)≤ 1n _i=1^n (|f(X_i)-Y_i|+Lρ )^2. By Cauchy–Schwarz, 1n∑i=1n|f(Xi)−Yi|≤R^0(f). 1n _i=1^n|f(X_i)-Y_i|≤ R_0(f). Therefore R^ρ(f)≤R^0(f)+2LρR^0(f)+L2ρ2=(R^0(f)+Lρ)2. R_ρ(f)≤ R_0(f)+2Lρ R_0(f)+L^2ρ^2= ( R_0(f)+Lρ )^2. Finally, Rρ(f)≥R0(f)≥σ2R_ρ(f)≥ R_0(f)≥σ^2, where the last inequality follows from the squared-loss variance decomposition. This proves the claim. ∎ Corollary 1 (Overfitting implies a robust gap). If 0<ε<σ20< <σ^2 and R^0(f)≤σ2−ε, R_0(f)≤σ^2- , then Gapρ(f)≥Γρ(ε,L)Gap_ρ(f)≥ _ρ( ,L) where Γρ(ϵ,L):=σ2−(σ2−ε+Lρ)2=ε−2Lρσ2−ε−L2ρ2 _ρ(ε,L):=σ^2- ( σ^2- +Lρ )^2= -2Lρ σ^2- -L^2ρ^2. In particular, the lower bound is positive whenever Lρ<σ−σ2−εLρ<σ- σ^2- . Proof. The assumption gives R^0(f)≤σ2−ε R_0(f)≤ σ^2- ; substituting in Theorem 1 proves the result. ∎ We now convert the robust gap into a lower bound on the complexity of the robust loss class. Since Y∈[−1,1]Y∈[-1,1], every robust squared loss satisfies 0≤ℓρ,f≤4.0≤ _ρ,f≤ 4. Definition 1 (Rademacher complexities). Let S=Zii=1nS=\Z_i\_i=1^n be a sample, and let ξ1,…,ξn _1,…, _n be independent Rademacher random variables, independent of S, with ℙ(ξi=1)=ℙ(ξi=−1)=12.P( _i=1)=P( _i=-1)= 12. For a class G of real-valued functions on ×X×Y, the empirical and expected Rademacher complexity is ℜ^S()=ξ[supg∈1n∑i=1nξig(Zi)]andℜn()=Sℜ^S(). R_S(G)=E_ξ [ _g 1n _i=1^n _ig(Z_i) ] R_n(G)=E_S R_S(G). Lemma 2 (Complexity forced by a robust gap). With probability at least 1−δ1-δ over S, simultaneously for all f∈ℱLf _L, ℜn(ℒρ)≥12[σ2−(R^0(f)+Lρ)2−4log(1/δ)2n]. R_n(L_ρ)≥ 12 [σ^2- ( R_0(f)+Lρ )^2-4 (1/δ)2n ]. Consequently, if R^0(f)≤σ2−ε R_0(f)≤σ^2- , then ℜn(ℒρ)≥12[Γρ(ε,L)−4log(1/δ)2n]. R_n(L_ρ)≥ 12 [ _ρ( ,L)-4 (1/δ)2n ]. Proof. By the standard Rademacher generalization bound for classes bounded in [0,4][0,4], with probability at least 1−δ1-δ, every g∈ℒρg _ρ satisfies Pg−Png≤2ℜn(ℒρ)+4log(1/δ)2n.Pg-P_ng≤ 2 R_n(L_ρ)+4 (1/δ)2n. Applying this to g=ℓρ,fg= _ρ,f gives, uniformly over f∈ℱLf _L, Gapρ(f)≤2ℜn(ℒρ)+4log(1/δ)2n.Gap_ρ(f)≤ 2 R_n(L_ρ)+4 (1/δ)2n. Combining this upper bound with Lemma 1 yields σ2−(R^0(f)+Lρ)2≤2ℜn(ℒρ)+4log(1/δ)2n.σ^2- ( R_0(f)+Lρ )^2≤ 2 R_n(L_ρ)+4 (1/δ)2n. Rearranging proves the first inequality. The below-noise version follows from Corollary 1. ∎ We now compare robust and clean squared-loss classes. Lemma 3 (Extremal envelopes). For f∈ℱLf _L, define fρ+(x)=supx~∈Bρ(x)f(x~)f_ρ^+(x)= _ x∈ B_ρ(x)f( x) and fρ−(x)=infx~∈Bρ(x)f(x~)f_ρ^-(x)= _ x∈ B_ρ(x)f( x). Both fρ+f_ρ^+ and fρ−f_ρ^- are bounded in [−1,1][-1,1] and L-Lipschitz on X. Moreover, for every (x,y)∈×[−1,1](x,y) ×[-1,1], ℓρ,f(x,y)=max(fρ+(x)−y)2,(fρ−(x)−y)2 _ρ,f(x,y)= \(f_ρ^+(x)-y)^2,\,(f_ρ^-(x)-y)^2 \. See Appendix A-8 for the proof. Corollary 2 (Squared-loss contraction). Let y1,…,yn∈[−1,1]y_1,…,y_n∈[-1,1], and let A⊆[−1,1]nA [-1,1]^n. Then ℜ^(((ai−yi)2)i=1n:a∈A)≤4ℜ^(A). R ( \ ((a_i-y_i)^2 )_i=1^n:a∈ A \ )≤ 4\, R(A). Proof. Set ϕi(t)=(t−yi)2−yi2 _i(t)=(t-y_i)^2-y_i^2. Then ϕi(0)=0 _i(0)=0, and ϕi _i is 44-Lipschitz on [−1,1][-1,1]. Extend ϕi _i to a 44-Lipschitz function on ℝR. We use the local contraction Lemma 9 (Appendix A) gives ℜ^(((ai−yi)2−yi2)i=1n:a∈A)≤4ℜ^(A). R ( \ ((a_i-y_i)^2-y_i^2 )_i=1^n:a∈ A \ )≤ 4\, R(A). Adding the fixed vector (yi2)i=1n(y_i^2)_i=1^n does not change Rademacher complexity. ∎ Lemma 4 (Coordinatewise maxima). Let A,B⊆ℝnA,B ^n, and define A∨B=(a1∨b1,…,an∨bn):a∈A,b∈BA B=\(a_1 b_1,…,a_n b_n):a∈ A,\ b∈ B\. Then ℜ^(A∨B)≤ℜ^(A)+ℜ^(B) R(A B)≤ R(A)+ R(B). Proof. Using u∨v=(u+v+|u−v|)/2u v=(u+v+|u-v|)/2, ℜ^(A∨B)≤12ℜ^(A)+12ℜ^(B)+12ξ[supa∈A,b∈B1n∑i=1nξi|ai−bi|]. R(A B)≤ 12 R(A)+ 12 R(B)+ 12E_ξ [ _a∈ A,b∈ B 1n _i=1^n _i|a_i-b_i| ]. Apply Lemma 9 to the class a−b:a∈A,b∈B\a-b:a∈ A,\ b∈ B\ and to t↦|t|t |t|. The last expectation is at most ξ[supa∈A,b∈B1n∑i=1nξi(ai−bi)]≤ℜ^(A)+ℜ^(−B).E_ξ [ _a∈ A,b∈ B 1n _i=1^n _i(a_i-b_i) ]≤ R(A)+ R(-B). Since ℜ^(−B)=ℜ^(B) R(-B)= R(B), the claim follows. ∎ Theorem 1 (Local robust-to-clean reduction). Fix a sample S=(Xi,Yi)i=1nS=\(X_i,Y_i)\_i=1^n. Let ℱL()=h:→[−1,1]:|h(x)−h(x′)|≤L‖x−x′‖2 for all x,x′∈.F_L(X)=\h:X→[-1,1]:|h(x)-h(x )|≤ L\|x-x \|_2 for all x,x \. Then ℜ^S(ℒρ(ℱL))≤2ℜ^S(ℒ0(ℱL()))≤8ℜ^X1n(ℱL()) R_S (L_ρ(F_L) )≤ 2\, R_S (L_0(F_L(X)) )≤ 8\, R_X_1^n (F_L(X) ). Proof. By Lemma 3, every robust-loss vector (ℓρ,f(Xi,Yi))i=1n ( _ρ,f(X_i,Y_i) )_i=1^n is the coordinatewise maximum of two clean squared-loss vectors induced by fρ+f_ρ^+ and fρ−f_ρ^-. Since both envelopes belong to ℱL()F_L(X), the set of robust-loss vectors is contained in A∨A A, where A=((h(Xi)−Yi)2)i=1n:h∈ℱL().A= \ ((h(X_i)-Y_i)^2 )_i=1^n:h _L(X) \. By monotonicity of Rademacher complexity and Lemma 4, ℜ^S(ℒρ(ℱL))≤ℜ^(A∨A)≤2ℜ^(A)=2ℜ^S(ℒ0(ℱL())). R_S (L_ρ(F_L) )≤ R(A A)≤ 2\, R(A)=2\, R_S (L_0(F_L(X)) ). The second inequality follows from Corollary 2, because h(Xi)∈[−1,1]h(X_i)∈[-1,1] and Yi∈[−1,1]Y_i∈[-1,1]: ℜ^S(ℒ0(ℱL()))≤4ℜ^X1n(ℱL()). R_S (L_0(F_L(X)) )≤ 4\, R_X_1^n (F_L(X) ). Combining the two bounds proves the claim. Using Lemma 3.8 in [30], L = Ω(n1/d) (n^1/d) ∎ 4 Local Rademacher complexity and Robust Generalization We now localize the robust loss class by its true L2(P)L_2(P)-radius. For r≥0r≥ 0, define ℒρ(r)=ℓρ,f:f∈ℱL,Pℓρ,f2≤rL_ρ(r)= \ _ρ,f:f _L,\;P _ρ,f^2≤ r \. Throughout this section, let ⊂ℝdX ^d be nonempty, compact, and connected, with D:=diam()<∞D:=diam(X)<∞. Because the robust loss evaluates f on the enlarged set ρX_ρ, while samples lie in X, we first record a simple extension lemma. It shows that any Lipschitz function defined on X can be extended to ρX_ρ without increasing its Lipschitz constant or leaving the range [−1,1][-1,1]. This allows us to treat covers of restrictions to X as covers induced by functions in the original class on ρX_ρ. For purposes of bounding the empirical metric entropy on samples from X, it is enough to construct covers of Lipschitz functions on X. Any such approximant may be extended back to ρX_ρ while remaining in ℬLB_L. This can be proved using McShane’s Theorem (Appendix A).We next prove a covering bound for bounded Lipschitz functions on X. Theorem 2 (Metric entropy of bounded Lipschitz predictors). Let ℱL()F_L(X) be as defined above. There is a constant cd>0c_d>0, depending only on d, such that for every 0<η≤10<η≤ 1, log(η,ℱL(),∥⋅∥∞)≤cd(1+LDη)d. (η,F_L(X),\|·\|_∞ )≤ c_d ( 1+LDη )^d. Proof. The case L=0L=0 is immediate. Assume L>0L>0 and set δ=η/(8L)δ=η/(8L). Let x1,…,xmx_1,…,x_m be a maximal δ-separated subset of X. Then it is a δ-net, and the standard packing bound gives m≤(1+2Dδ)d=(1+16LDη)d.m≤ (1+ 2Dδ )^d= (1+ 16LDη )^d. Connect i and j if B¯(xi,δ)∩B¯(xj,δ)≠∅ B(x_i,δ)∩ B(x_j,δ)≠ . This graph is connected; otherwise the corresponding unions of δ-balls over two graph components would separate the connected set X. Fix a spanning tree rooted at an arbitrary vertex. Let h=η/4h=η/4 and Gη=hℤ∩[−1−h/2,1+h/2]G_η=hZ∩[-1-h/2,1+h/2]. Choose πη(t)∈Gη _η(t)∈ G_η with |t−πη(t)|≤h/2=η/8|t- _η(t)|≤ h/2=η/8, t∈[−1,1]t∈[-1,1]. Then |Gη|≤2+8/η|G_η|≤ 2+8/η. For f∈ℱL()f _L(X), define its quantized net-value vector by q(f)=(q1(f),…,qm(f)),qj(f)=πη(f(xj)).q(f)=(q_1(f),…,q_m(f)), q_j(f)= _η(f(x_j)). The root coordinate has at most 2+8/η2+8/η choices. If p(j)p(j) is the parent of j in the spanning tree, then ‖xj−xp(j)‖2≤2δ\|x_j-x_p(j)\|_2≤ 2δ, and hence |f(xj)−f(xp(j))|≤2Lδ=η/4|f(x_j)-f(x_p(j))|≤ 2Lδ=η/4. Therefore |qj(f)−qp(j)(f)|≤η/8+η/4+η/8=η/2|q_j(f)-q_p(j)(f)|≤η/8+η/4+η/8=η/2. Since the grid spacing is η/4η/4, each non-root coordinate has at most five possible values once its parent value is fixed. Thus the number of admissible quantized net-value vectors is at most (2+8η)5m−1 (2+ 8η )5^m-1. If f,g∈ℱL()f,g _L(X) have the same quantized net-value vector, then for any x∈x , choosing xjx_j with ‖x−xj‖2≤δ\|x-x_j\|_2≤δ gives |f(x)−g(x)|≤Lδ+η/8+η/8+Lδ=η/2|f(x)-g(x)|≤ Lδ+η/8+η/8+Lδ=η/2. Hence each nonempty fiber of the quantization map has ∥⋅∥∞\|·\|_∞-diameter at most η. Taking one representative from each nonempty fiber yields an η-cover, so log(η,ℱL(),∥⋅∥∞)≤log(2+8η)+(log5)(1+16LDη)d. (η,F_L(X),\|·\|_∞ )≤ (2+ 8η )+( 5) (1+ 16LDη )^d. Let A=(1+LD)/ηA=(1+LD)/η. Since 0<η≤10<η≤ 1, A≥1A≥ 1, and log(2+8η)≤10η≤10Ad. (2+ 8η )≤ 10η≤ 10A^d. Also, 1+16LDη≤17A1+ 16LDη≤ 17A Hence log(η,ℱL(),∥⋅∥∞)≤(10+17dlog5)Ad (η,F_L(X),\|·\|_∞ )≤ (10+17^d 5 )A^d. Absorbing the constant into cdc_d gives log(η,ℱL(),∥⋅∥∞)≤cd(1+LDη)d. (η,F_L(X),\|·\|_∞ )≤ c_d ( 1+LDη )^d. ∎ Lemma 5 (Metric entropy of robust squared losses). There is a constant Cd>0C_d>0, depending only on d, such that for every 0<η≤40<η≤ 4, log(η,ℒρ(ℱL),∥⋅∥∞)≤Cd(1+LDη)d. (η,L_ρ(F_L),\|·\|_∞ )≤ C_d ( 1+LDη )^d. See Appendix A-12 for the proofs. Lemma 6 (Polynomial entropy implies a local bound). Let G be a measurable class of functions bounded in [0,b][0,b], where b>0b>0. Assume that for some p>2p>2 and A>0A>0, supQlog(η,,L2(Q))≤Aη−pfor all 0<η≤b, _Q (η,G,L_2(Q) )≤ Aη^-p all 0<η≤ b, where the supremum is over all finitely supported probability measures Q. For r≥0r≥ 0, define (r)=g∈:Pg2≤r.G(r)=\g :Pg^2≤ r\. Let A¯:=1∨A A:=1 A. Then there is a constant Cp,b>0C_p,b>0, depending only on p and b, such that ℜn((r))≤Cp,b(A¯1/pn−1/p+rn). R_n(G(r))≤ C_p,b ( A^1/pn^-1/p+ rn ). In particular, if A≥1A≥ 1, then ℜn((r))≤Cp,b(A1/pn−1/p+rn). R_n(G(r))≤ C_p,b (A^1/pn^-1/p+ rn ). See Appendix A-13 for the proofs. Theorem 3 (Localized robust Rademacher upper bound). Assume d≥3d≥ 3. There is a constant Cd>0C_d>0, depending only on d, such that for every r∈[0,16]r∈[0,16], ℜn(ℒρ(r))≤Cd((1+LD)n−1/d+rn). R_n (L_ρ(r) )≤ C_d ((1+LD)n^-1/d+ rn ). Proof. Since f:ρ→[−1,1]f:X_ρ→[-1,1] and Y∈[−1,1]Y∈[-1,1], every robust squared loss satisfies 0≤ℓρ,f≤4.0≤ _ρ,f≤ 4. By Lemma 5, and since ∥⋅∥L2(Q)≤∥⋅∥∞\|·\|_L_2(Q)≤\|·\|_∞, supQlog(η,ℒρ(ℱL),L2(Q))≤Cd(1+LDη)d. _Q (η,L_ρ(F_L),L_2(Q) )≤ C_d ( 1+LDη )^d. Apply Lemma 6 with =ℒρ(ℱL)G=L_ρ(F_L), p=dp=d, b=4b=4, and A=Cd(1+LD)dA=C_d(1+LD)^d. This gives ℜn(ℒρ(r))≤Cd((1+LD)n−1/d+rn), R_n (L_ρ(r) )≤ C_d ((1+LD)n^-1/d+ rn ), after absorbing constants depending only on d. ∎ Lemma 7 (Localized robust gap forces localized complexity). Fix r∈[0,16]r∈[0,16] and δ∈(0,1)δ∈(0,1). With probability at least 1−δ1-δ over S, every f∈ℱLf _L satisfying Pℓρ,f2≤randR^0(f)≤σ2−εP _ρ,f^2≤ r R_0(f)≤σ^2- also satisfies ℜn(ℒρ(r))≥12[Γρ(ε,L)−4log(1/δ)2n]. R_n (L_ρ(r) )≥ 12 [ _ρ( ,L)-4 (1/δ)2n ]. This can be proved using standard McDiarmid’s inequality. The detailed proof is in Appendix A. Corollary 3 (Localized compatibility condition). Under the assumptions of Theorem 3, fix r∈[0,16]r∈[0,16] and δ∈(0,1)δ∈(0,1). With probability at least 1−δ1-δ, every f∈ℱLf _L satisfying Pℓρ,f2≤randR^0(f)≤σ2−εP _ρ,f^2≤ r R_0(f)≤σ^2- must obey Γρ(ε,L)≤2Cd((1+LD)n−1/d+rn)+4log(1/δ)2n. _ρ( ,L)≤ 2C_d ((1+LD)n^-1/d+ rn )+4 (1/δ)2n. Equivalently, ε−2Lρσ2−ε−L2ρ2≤2Cd((1+LD)n−1/d+rn)+4log(1/δ)2n. -2Lρ σ^2- -L^2ρ^2≤ 2C_d ((1+LD)n^-1/d+ rn )+4 (1/δ)2n. Proof. Combine Corollary 11 with Theorem 3. ∎ 5 Local Lipschitz Scaling from Localized Robust Rademacher Bounds We now rewrite the localized compatibility condition as a lower bound on the Lipschitz scale L. Throughout this section, assume d≥3d≥ 3, D=diam()<∞D=diam(X)<∞, 0<ε<σ20< <σ^2, r∈[0,16]r∈[0,16], δ∈(0,1)δ∈(0,1), and ρ≥0ρ≥ 0. Define sε:=σ2−εs_ := σ^2- . By Corollary 3, with probability at least 1−δ1-δ, every f∈ℱLf _L satisfying Pℓρ,f2≤rP _ρ,f^2≤ r and R^0(f)≤σ2−ε R_0(f)≤σ^2- must obey ε−2Lρsε−L2ρ2≤2Cd((1+LD)n−1/d+rn)+4log(1/δ)2n. -2Lρ s_ -L^2ρ^2≤ 2C_d ((1+LD)n^-1/d+ rn )+4 (1/δ)2n. (1) Define the localized excess margin Δn,r,δ:=ε−2Cdn−1/d−2Cdrn−4log(1/δ)2n. _n,r,δ:= -2C_dn^-1/d-2C_d rn-4 (1/δ)2n. (2) Then (1) implies Δn,r,δ≤ρ2L2+(2ρsε+2CdDn−1/d)L. _n,r,δ≤ρ^2L^2+ (2ρ s_ +2C_dDn^-1/d )L. (3) Thus a nontrivial lower bound on L is obtained precisely in the regime Δn,r,δ>0. _n,r,δ>0. Corollary 4 (Local Lipschitz scaling). On the event of probability at least 1−δ1-δ from Corollary 3, suppose that Δn,r,δ>0 _n,r,δ>0. Then every f∈ℱLf _L satisfying Pℓρ,f2≤rP _ρ,f^2≤ r and R^0(f)≤σ2−ε R_0(f)≤σ^2- must satisfy the following lower bounds. If ρ>0ρ>0, then L≥−Bn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ2ρ2,L≥ -B_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ2ρ^2, (4) where Bn,ρ,ε:=2ρσ2−ε+2CdDn−1/d.B_n,ρ, :=2ρ σ^2- +2C_dDn^-1/d. (5) Equivalently, L≥2Δn,r,δBn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ.L≥ 2 _n,r,δB_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ. (6) In particular, L≥Δn,r,δ2ρσ2−ε+2CdDn−1/d+ρΔn,r,δ.L≥ _n,r,δ2ρ σ^2- +2C_dDn^-1/d+ρ _n,r,δ. (7) Consequently, up to constants depending only on d, L=Ω(Δn,r,δρσ2−ε+Dn−1/d+ρΔn,r,δ).L= ( _n,r,δρ σ^2- +Dn^-1/d+ρ _n,r,δ ). (8) See Appendix A-5 for the proofs. Remark 1 (A weaker form using σ). Since σ2−ε≤σ σ^2- ≤σ, one may replace Bn,ρ,εB_n,ρ, by the larger quantity B¯n,ρ:=2ρσ+2CdDn−1/d B_n,ρ:=2ρσ+2C_dDn^-1/d. This gives the weaker but sometimes simpler valid lower bound, for ρ>0ρ>0, L≥−B¯n,ρ+B¯n,ρ2+4ρ2Δn,r,δ2ρ2,L≥ - B_n,ρ+ B_n,ρ^2+4ρ^2 _n,r,δ2ρ^2, and hence L=Ω(Δn,r,δρσ+Dn−1/d+ρΔn,r,δ),L= ( _n,r,δρσ+Dn^-1/d+ρ _n,r,δ ), whenever Δn,r,δ>0 _n,r,δ>0. This is a relaxation of the exact bound, not the exact compatibility condition. Ignoring only constants depending on d, the confidence term, and the displayed lower-order localization terms, the exact nonvacuous regime can be summarized as L=Ω(ε−n−1/d−r/nρσ2−ε+Dn−1/d+ρε−n−1/d−r/n),L= ( -n^-1/d- r/nρ σ^2- +Dn^-1/d+ρ -n^-1/d- r/n ), provided the numerator is positive. Dependence on the number of parameters. The localized Rademacher argument above is geometric: it applies to the bounded Lipschitz class on a d-dimensional domain and therefore depends on n,d,D,r,ρ,σ,εn,d,D,r,ρ,σ, , and δ, but not directly on the number of network parameters p. A parameter-count dependence enters only after imposing an additional assumptions on the distribuion like the Isoperimteric distribution [3]. 6 Discussion This work takes a step towards unifying worst-case robustness and robust generalization, as posed by [3]. In the global setting, our analysis connects robust generalization gaps to the global Rademacher complexity of the induced robust loss class, finding that the Lipschitz constant remains of the order Ω(n1/d) (n^1/d). Interestingly, when using local notions of Rademacher complexity, we find a contrary outcome: the order of the Lipschitz constant changes with ρ and the concentration term r/n r/n. We surmise that this is because, in the global setting, the number of functions is huge: in this massive ocean of functions, perturbations are imperceptible in terms of order. However, when we zoom in and look at the functions which might actually be reached by the optimizing algorithm, the changes suddenly become visible: the order of the Lipschitz constant is now directly affected! There are several natural directions for future work. First, there needs to be experimental exploration of the significance of this concentration term. Next, our theoretical results are stated for square-loss, whereas Robust Generalization is usually in the classification setting using cross-entropy loss; extending the analysis to Bregmann divergence losses would close this gap. Further, distributional robustness may provide another route to connect robust generalization with worst-case robustness. References [1] P. L. Bartlett, O. Bousquet, and S. Mendelson (2005) Local rademacher complexities. The Annals of Statistics 33 (4), p. 1497–1537. External Links: Document Cited by: §1. [2] S. Bubeck, Y. Li, and D. M. Nagaraj (2021) A law of robustness for two-layer neural networks. In Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 134, p. 804–820. External Links: Link Cited by: §1, §2.2. [3] S. Bubeck and M. Sellke (2021) A universal law of robustness via isoperimetry. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §1, §1, §2.2, §5, §6. [4] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and P. Liang (2019) Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.3. [5] T. Chen, Z. Zhang, S. Liu, S. Chang, and Z. Wang (2021) Robust overfitting may be mitigated by properly learned smoothening. In International Conference on Learning Representations, External Links: Link Cited by: §2.3. [6] X. Cheng, K. Fu, and F. Farnia (2024) Stability and generalization in free adversarial training. Transactions on Machine Learning Research. External Links: Link Cited by: §2.3. [7] M. Cissé, P. Bojanowski, E. Grave, Y. N. Dauphin, and N. Usunier (2017) Parseval networks: improving robustness to adversarial examples. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, p. 854–863. External Links: Link Cited by: §2.1. [8] F. Croce and M. Hein (2020) Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 2206–2216. External Links: Link Cited by: §2.1. [9] S. Das, J. Batra, and P. Srivastava (2025) A direct proof of a unified law of robustness for bregman divergence losses. IEEE Transactions on Information Theory 71 (8), p. 6340–6352. External Links: Link Cited by: §2.2. [10] M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. J. Pappas (2019) Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.1. [11] I. J. Goodfellow, J. Shlens, and C. Szegedy (2014) Explaining and harnessing adversarial examples. Note: ICLR 2015 External Links: Link Cited by: §2.1. [12] I. J. Goodfellow, J. Shlens, and C. Szegedy (2015) Explaining and harnessing adversarial examples. External Links: Link Cited by: §1. [13] H. Husain and B. Balle (2021) A law of robustness for weight-bounded neural networks. External Links: Link Cited by: §2.2. [14] H. Kim, J. Park, Y. Choi, and J. Lee (2023) Fantastic robustness measures: the secrets of robust generalization. In Advances in Neural Information Processing Systems, Vol. 36, p. 48793–48818. External Links: Link Cited by: §1. [15] V. Koltchinskii (2006) Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics 34 (6), p. 2593–2656. External Links: Document Cited by: §1. [16] Y. LeCun, Y. Bengio, and G. Hinton (2015) Deep learning. Nature 521 (7553), p. 436–444. External Links: Document Cited by: §1. [17] Y. Lei, K. Ding, and J. Bi (2015) Local rademacher complexity bounds based on covering numbers. External Links: Link Cited by: Appendix A, Appendix A, Appendix A, §1. [18] B. Li, J. Jin, H. Zhong, J. E. Hopcroft, and L. Wang (2022) Why robust generalization in deep learning is difficult: perspective of expressive power. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.3. [19] B. Li and Y. Li (2025) On the clean generalization and robust overfitting in adversarial training from two theoretical views: representation complexity and training dynamics. In International Conference on Machine Learning, External Links: Link Cited by: §2.3. [20] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu (2018) Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, External Links: Link Cited by: §2.1. [21] C. Mingard, H. Rees, G. Valle-Pérez, and A. A. Louis (2025) Deep neural networks have an inbuilt occam’s razor. Nature Communications 16 (1). External Links: Document, Link Cited by: §1. [22] P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever (2019) Deep double descent: where bigger models and more data hurt. External Links: Link Cited by: §1. [23] L. Rice, E. Wong, and J. Z. Kolter (2020) Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 8093–8104. External Links: Link Cited by: §2.3. [24] K. Scaman and A. Virmaux (2019) Lipschitz regularity of deep neural networks: analysis and efficient estimation. External Links: Link Cited by: §1. [25] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry (2018) Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.3. [26] A. Shafahi, M. Najibi, A. Ghiasi, Z. Xu, J. Dickerson, C. Studer, L. S. Davis, G. Taylor, and T. Goldstein (2019) Adversarial training for free!. External Links: Link Cited by: §1. [27] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus (2013) Intriguing properties of neural networks. External Links: Link Cited by: §2.1. [28] Y. Tsuzuku, I. Sato, and M. Sugiyama (2018) Lipschitz-margin training: scalable certification of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.1. [29] T. Weng, H. Zhang, P. Chen, J. Yi, D. Su, Y. Gao, C. Hsieh, and L. Daniel (2018) Evaluating the robustness of neural networks: an extreme value theory approach. In International Conference on Learning Representations, External Links: Link Cited by: §2.1. [30] Y. Wu, H. Huang, and H. Zhang (2023) A law of robustness beyond isoperimetry. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 37439–37455. External Links: Link Cited by: §1, §1, §2.2, §3.1. [31] D. Yin, K. Ramchandran, and P. Bartlett (2019) Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 7085–7094. External Links: Link Cited by: §2.3. [32] C. Yu, B. Han, L. Shen, J. Yu, C. Gong, M. Gong, and T. Liu (2022) Understanding robust overfitting of adversarial training and beyond. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 162. External Links: Link Cited by: §2.3. [33] R. Zhai, T. Cai, D. He, and L. Wang (2019) Adversarially robust generalization just requires more unlabeled data. In International Conference on Learning Representations, External Links: Link Cited by: §2.3. [34] B. Zhang, D. Jiang, D. He, and L. Wang (2022) Rethinking lipschitz neural networks and certified robustness: a boolean function perspective. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.1. [35] H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. El Ghaoui, and M. I. Jordan (2019) Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, External Links: Link Cited by: §2.1. [36] K. Zhang, Y. Wang, and R. Arora (2024) Stability and generalization of adversarial training for shallow neural networks with smooth activation. In Advances in Neural Information Processing Systems, External Links: Link Cited by: §2.3. [37] Z. Zhang, M. Backes, and Y. Zhang (2024) Generating less certain adversarial examples improves robust generalization. Transactions on Machine Learning Research. External Links: Link Cited by: §2.3. [38] M. Zühlke and D. Kudenko (2025) Adversarial robustness of neural networks from the perspective of lipschitz calculus: a survey. ACM Computing Surveys. External Links: Document, Link Cited by: §2.1. Appendix A Technical appendices and supplementary material Lemma 8 (Extremal envelopes). For f∈ℱLf _L, define fρ+(x)=supx~∈Bρ(x)f(x~),fρ−(x)=infx~∈Bρ(x)f(x~).f_ρ^+(x)= _ x∈ B_ρ(x)f( x), f_ρ^-(x)= _ x∈ B_ρ(x)f( x). Both fρ+f_ρ^+ and fρ−f_ρ^- are bounded in [−1,1][-1,1] and L-Lipschitz on X. Moreover, for every (x,y)∈×[−1,1](x,y) ×[-1,1], ℓρ,f(x,y)=max(fρ+(x)−y)2,(fρ−(x)−y)2. _ρ,f(x,y)= \(f_ρ^+(x)-y)^2,\,(f_ρ^-(x)-y)^2 \. Proof. Since Bρ(x)⊆ρB_ρ(x) _ρ, the envelopes are well-defined and bounded in [−1,1][-1,1]. For x,x′∈x,x and ‖u‖2≤ρ\|u\|_2≤ρ, f(x+u)≤f(x′+u)+L‖x−x′‖2.f(x+u)≤ f(x +u)+L\|x-x \|_2. Taking the supremum over u gives fρ+(x)≤fρ+(x′)+L‖x−x′‖2.f_ρ^+(x)≤ f_ρ^+(x )+L\|x-x \|_2. Exchanging x,x′x,x proves that fρ+f_ρ^+ is L-Lipschitz. Since fρ−=−(−f)ρ+f_ρ^-=-(-f)_ρ^+, the same holds for fρ−f_ρ^-. Fix (x,y)(x,y). Let Ax=f(x~):x~∈Bρ(x),M=supAx,m=infAx.A_x=\f( x): x∈ B_ρ(x)\, M= A_x, m= A_x. Since Ax⊆[m,M]A_x [m,M], supz∈Ax(z−y)2≤max(M−y)2,(m−y)2. _z∈ A_x(z-y)^2≤ \(M-y)^2,(m-y)^2\. The reverse inequality follows by approximating M and m with sequences in AxA_x. Hence supz∈Ax(z−y)2=max(M−y)2,(m−y)2, _z∈ A_x(z-y)^2= \(M-y)^2,(m-y)^2\, which gives the claimed identity. ∎ Lemma 9 (Local contraction). Let A⊆ℝnA ^n. For each i, let ϕi:ℝ→ℝ _i:R be C-Lipschitz and satisfy ϕi(0)=0 _i(0)=0. Then ℜ^((ϕ1(a1),…,ϕn(an)):a∈A)≤Cℜ^(A). R (\( _1(a_1),…, _n(a_n)):a∈ A\ )≤ C\, R(A). Lemma 10 (Range-preserving Lipschitz extension). Let g:→[−1,1]g:X→[-1,1] be L-Lipschitz. Then there exists an L-Lipschitz function g~:ρ→[−1,1] g:X_ρ→[-1,1] such that g~=g g=g on X. Proof. By the McShane extension theorem, the function g~0(z):=infx∈g(x)+L‖z−x‖,z∈ρ, g_0(z):= _x \g(x)+L z-x \, z _ρ, is an L-Lipschitz extension of g from X to ρX_ρ. The metric projection Π[−1,1](t):=max−1,mint,1 _[-1,1](t):= \-1, \t,1\\ is 11-Lipschitz on ℝR, so g~:=Π[−1,1]∘g~0 g:= _[-1,1] g_0 is still L-Lipschitz, takes values in [−1,1][-1,1], and agrees with g on X because g()⊂[−1,1]g(X)⊂[-1,1]. ∎ Lemma 11 (Localized robust gap forces localized complexity). Fix r∈[0,16]r∈[0,16] and δ∈(0,1)δ∈(0,1). With probability at least 1−δ1-δ over S, every f∈ℱLf _L satisfying Pℓρ,f2≤randR^0(f)≤σ2−εP _ρ,f^2≤ r R_0(f)≤σ^2- also satisfies ℜn(ℒρ(r))≥12[Γρ(ε,L)−4log(1/δ)2n]. R_n (L_ρ(r) )≥ 12 [ _ρ( ,L)-4 (1/δ)2n ]. Proof. Let Φ(S):=supg∈ℒρ(r)(Pg−Png). (S):= _g _ρ(r)(Pg-P_ng). Since 0≤g≤40≤ g≤ 4 for all g∈ℒρ(r)g _ρ(r), McDiarmid’s inequality gives, with probability at least 1−δ1-δ, Φ(S)≤SΦ(S)+4log(1/δ)2n. (S) _S (S)+4 (1/δ)2n. By the usual ghost-sample symmetrization, SΦ(S)≤S,S′supg∈ℒρ(r)1n∑i=1n(g(Zi′)−g(Zi))≤2ℜn(ℒρ(r)).E_S (S) _S,S _g _ρ(r) 1n _i=1^n (g(Z_i )-g(Z_i) )≤ 2\, R_n (L_ρ(r) ). Hence, on the same event, supg∈ℒρ(r)(Pg−Png)≤2ℜn(ℒρ(r))+4log(1/δ)2n. _g _ρ(r)(Pg-P_ng)≤ 2\, R_n (L_ρ(r) )+4 (1/δ)2n. Now let f satisfy Pℓρ,f2≤rP _ρ,f^2≤ r. Then ℓρ,f∈ℒρ(r) _ρ,f _ρ(r), so Rρ(f)−R^ρ(f)≤2ℜn(ℒρ(r))+4log(1/δ)2n.R_ρ(f)- R_ρ(f)≤ 2\, R_n (L_ρ(r) )+4 (1/δ)2n. If also R^0(f)≤σ2−ε R_0(f)≤σ^2- , then Corollary 1 gives Rρ(f)−R^ρ(f)≥Γρ(ε,L).R_ρ(f)- R_ρ(f)≥ _ρ( ,L). Combining the last two displays and rearranging proves the claim. ∎ Lemma 12 (Metric entropy of robust squared losses). There is a constant Cd>0C_d>0, depending only on d, such that for every 0<η≤40<η≤ 4, log(η,ℒρ(ℱL),∥⋅∥∞)≤Cd(1+LDη)d. (η,L_ρ(F_L),\|·\|_∞ )≤ C_d ( 1+LDη )^d. Proof. By Lemma 3, for every f∈ℱLf _L, ℓρ,f(x,y)=max(fρ+(x)−y)2,(fρ−(x)−y)2, _ρ,f(x,y)= \(f_ρ^+(x)-y)^2,\,(f_ρ^-(x)-y)^2 \, where fρ+,fρ−∈ℱL()f_ρ^+,f_ρ^- _L(X). Define the auxiliary class ℳρ:=mh+,h−:(x,y)↦max(h+(x)−y)2,(h−(x)−y)2:h+,h−∈ℱL().M_ρ:= \m_h_+,h_-:(x,y) \(h_+(x)-y)^2,\,(h_-(x)-y)^2 \:h_+,h_- _L(X) \. Then ℒρ(ℱL)⊆ℳρ.L_ρ(F_L) _ρ. We first convert covers of the larger class ℳρM_ρ into proper covers of the subclass ℒρ(ℱL)L_ρ(F_L). Let α>0α>0, and let m1,…,mN∈ℳρm_1,…,m_N _ρ be an α-cover of ℳρM_ρ in ∥⋅∥∞\|·\|_∞, where N=(α,ℳρ,∥⋅∥∞).N=N (α,M_ρ,\|·\|_∞ ). For each index j such that B∞(mj,α)∩ℒρ(ℱL)≠∅,B_∞(m_j,α) _ρ(F_L)≠ , choose one element gj∈B∞(mj,α)∩ℒρ(ℱL).g_j∈ B_∞(m_j,α) _ρ(F_L). Discard the remaining indices. We claim that the selected functions gj⊆ℒρ(ℱL)\g_j\ _ρ(F_L) form a 2α2α-cover of ℒρ(ℱL)L_ρ(F_L). Indeed, for any g∈ℒρ(ℱL)g _ρ(F_L), since ℒρ(ℱL)⊆ℳρL_ρ(F_L) _ρ, there exists j such that ‖g−mj‖∞≤α.\|g-m_j\|_∞≤α. For this index j, the ball B∞(mj,α)B_∞(m_j,α) intersects ℒρ(ℱL)L_ρ(F_L), so a corresponding gjg_j was selected and satisfies ‖gj−mj‖∞≤α.\|g_j-m_j\|_∞≤α. Therefore, by the triangle inequality, ‖g−gj‖∞≤‖g−mj‖∞+‖mj−gj‖∞≤2α.\|g-g_j\|_∞≤\|g-m_j\|_∞+\|m_j-g_j\|_∞≤ 2α. Thus (2α,ℒρ(ℱL),∥⋅∥∞)≤(α,ℳρ,∥⋅∥∞).N (2α,L_ρ(F_L),\|·\|_∞ ) (α,M_ρ,\|·\|_∞ ). Taking α=η/2α=η/2, we obtain (η,ℒρ(ℱL),∥⋅∥∞)≤(η2,ℳρ,∥⋅∥∞).N (η,L_ρ(F_L),\|·\|_∞ ) ( η2,M_ρ,\|·\|_∞ ). It remains to bound the covering number of ℳρM_ρ. Set β:=η8.β:= η8. Since 0<η≤40<η≤ 4, we have 0<β≤1/20<β≤ 1/2, so Lemma 2 applies at scale β. Let h1,…,hM∈ℱL()h_1,…,h_M _L(X) be a proper β-cover of ℱL()F_L(X) in ∥⋅∥∞\|·\|_∞, with M=(β,ℱL(),∥⋅∥∞).M=N (β,F_L(X),\|·\|_∞ ). For each pair 1≤j,k≤M1≤ j,k≤ M, define mjk(x,y):=max(hj(x)−y)2,(hk(x)−y)2.m_jk(x,y):= \(h_j(x)-y)^2,\,(h_k(x)-y)^2 \. By construction, mjk∈ℳρm_jk _ρ. We claim that the functions mjk:1≤j,k≤M\m_jk:1≤ j,k≤ M\ form an η/2η/2-cover of ℳρM_ρ. Fix mh+,h−∈ℳρm_h_+,h_- _ρ. Choose j,kj,k such that ‖h+−hj‖∞≤β,‖h−hk‖∞≤β.\|h_+-h_j\|_∞≤β, \|h_--h_k\|_∞≤β. For all (x,y)∈×(x,y) ×Y, |(h+(x)−y)2−(hj(x)−y)2| |(h_+(x)-y)^2-(h_j(x)-y)^2 | =|h+(x)−hj(x)||h+(x)+hj(x)−2y| =|h_+(x)-h_j(x)|\,|h_+(x)+h_j(x)-2y| ≤4‖h+−hj‖∞≤4β. ≤ 4\|h_+-h_j\|_∞≤ 4β. Here we used h+(x),hj(x),y∈[−1,1]h_+(x),h_j(x),y∈[-1,1]. Similarly, |(h−(x)−y)2−(hk(x)−y)2|≤4β. |(h_-(x)-y)^2-(h_k(x)-y)^2 |≤ 4β. Since the maximum map is 11-Lipschitz with respect to the sup norm on ℝ2R^2, we have |mh+,h−(x,y)−mjk(x,y)| |m_h_+,h_-(x,y)-m_jk(x,y) | ≤max|(h+(x)−y)2−(hj(x)−y)2|,|(h−(x)−y)2−(hk(x)−y)2| ≤ \ |(h_+(x)-y)^2-(h_j(x)-y)^2 |, |(h_-(x)-y)^2-(h_k(x)-y)^2 | \ ≤4β=η2. ≤ 4β= η2. Taking the supremum over (x,y)(x,y) gives ‖mh+,h−mjk‖∞≤η2.\|m_h_+,h_--m_jk\|_∞≤ η2. Therefore (η2,ℳρ,∥⋅∥∞)≤(η8,ℱL(),∥⋅∥∞)2.N ( η2,M_ρ,\|·\|_∞ ) ( η8,F_L(X),\|·\|_∞ )^2. Combining the preceding bounds yields (η,ℒρ(ℱL),∥⋅∥∞)≤(η8,ℱL(),∥⋅∥∞)2.N (η,L_ρ(F_L),\|·\|_∞ ) ( η8,F_L(X),\|·\|_∞ )^2. Taking logarithms and applying Lemma 2, log(η,ℒρ(ℱL),∥⋅∥∞) (η,L_ρ(F_L),\|·\|_∞ ) ≤2log(η8,ℱL(),∥⋅∥∞) ≤ 2 ( η8,F_L(X),\|·\|_∞ ) ≤2cd(1+LDη/8)d ≤ 2c_d ( 1+LDη/8 )^d =2⋅8dcd(1+LDη)d. =2· 8^dc_d ( 1+LDη )^d. Thus the claim holds with Cd:=2⋅8dcd.C_d:=2· 8^dc_d. ∎ Lemma 13 (Polynomial entropy implies a local bound). Let G be a measurable class of functions bounded in [0,b][0,b], where b>0b>0. Assume that for some p>2p>2 and A>0A>0, supQlog(η,,L2(Q))≤Aη−pfor all 0<η≤b, _Q (η,G,L_2(Q) )≤ Aη^-p all 0<η≤ b, where the supremum is over all finitely supported probability measures Q. For r≥0r≥ 0, define (r)=g∈:Pg2≤r.G(r)=\g :Pg^2≤ r\. Let A¯:=1∨A. A:=1 A. Then there is a constant Cp,b>0C_p,b>0, depending only on p and b, such that ℜn((r))≤Cp,b(A¯1/pn−1/p+rn). R_n(G(r))≤ C_p,b ( A^1/pn^-1/p+ rn ). In particular, if A≥1A≥ 1, then ℜn((r))≤Cp,b(A1/pn−1/p+rn). R_n(G(r))≤ C_p,b (A^1/pn^-1/p+ rn ). Proof. If (r)=∅G(r)= , the claim is trivial. We therefore assume (r)≠∅G(r)≠ . Define H(η):=supQlog(η,,L2(Q)),H_G(η):= _Q (η,G,L_2(Q) ), where the supremum is over finitely supported probability measures Q. Since every function in G takes values in [0,b][0,b], the L2(Q)L_2(Q)-diameter of G is at most b. Hence, for η≥bη≥ b, (η,,L2(Q))≤1for every finitely supported Q.N(η,G,L_2(Q))≤ 1 every finitely supported Q. Consequently, H(η)≤Aη−pfor every η>0.H_G(η)≤ Aη^-p every η>0. Indeed, for 0<η≤b0<η≤ b this is the entropy assumption, while for η>bη>b the left-hand side is zero. Let ~:=g−g′:g,g′∈. G:=\g-g :g,g \. We first bound the entropy of ~ G. Fix a finitely supported probability measure Q. If g1,…,gN\g_1,…,g_N\ is an (η/2)(η/2)-cover of G in L2(Q)L_2(Q), then the functions gj−gk,1≤j,k≤N,g_j-g_k, 1≤ j,k≤ N, belong to ~ G and form an η-cover of ~ G in L2(Q)L_2(Q). Therefore (η,~,L2(Q))≤(η2,,L2(Q))2.N (η, G,L_2(Q) ) ( η2,G,L_2(Q) )^2. Taking logarithms and the supremum over Q gives H~(η):=supQlog(η,~,L2(Q))≤2H(η/2)≤2p+1Aη−pfor all η>0.H_ G(η):= _Q (η, G,L_2(Q) )≤ 2H_G(η/2)≤ 2^p+1Aη^-p all η>0. For a sample S=(Z1,…,Zn)S=(Z_1,…,Z_n), write PnP_n for the empirical measure and define Ψ(ε):=Sℜ^S(h∈~:Pnh2≤ε2). ( ):=E_S R_S ( \h∈ G:P_nh^2≤ ^2 \ ). We use Theorem 2 of Lei et al. [17], which gives ℜn((r))≤infε>0[2Ψ(ε)+8bH(ε/2)n+2rH(ε/2)n]. R_n(G(r))≤ _ >0 [2 ( )+ 8b\,H_G( /2)n+ 2r\,H_G( /2)n ]. It remains to bound Ψ(ε) ( ). Fix a sample S and set dn(h,h′):=(Pn(h−h′)2)1/2.d_n(h,h ):= (P_n(h-h )^2 )^1/2. For a fixed ε>0 >0, define the empirical localized difference class ~n,ε:=h∈~:Pnh2≤ε2. G_n, := \h∈ G:P_nh^2≤ ^2 \. We need to be careful because covering numbers are proper in our convention. We claim that for every α>0α>0, (2α,~n,ε,dn)≤(α,~,dn).N (2α, G_n, ,d_n ) (α, G,d_n ). Indeed, let u1,…,uM∈~u_1,…,u_M∈ G be an α-cover of ~ G in dnd_n. For each j such that Bdn(uj,α)∩~n,ε≠∅,B_d_n(u_j,α)∩ G_n, ≠ , choose one element vj∈Bdn(uj,α)∩~n,ε.v_j∈ B_d_n(u_j,α)∩ G_n, . Discard the remaining indices. Then the selected vjv_j’s lie inside ~n,ε G_n, . Moreover, for every h∈~n,εh∈ G_n, , there exists j such that dn(h,uj)≤αd_n(h,u_j)≤α, and for that same j, dn(vj,uj)≤αd_n(v_j,u_j)≤α. Hence dn(h,vj)≤dn(h,uj)+dn(uj,vj)≤2α.d_n(h,v_j)≤ d_n(h,u_j)+d_n(u_j,v_j)≤ 2α. Thus the selected elements form a proper 2α2α-cover of ~n,ε G_n, . Now apply Lemma A.5 of Lei et al. [17] to ~n,ε G_n, . Let εk:=2−kε, _k:=2^-k , k≥0.k≥ 0. For every integer N≥1N≥ 1, ℜ^S(~n,ε)≤4∑k=1Nεk−1log(εk,~n,ε,dn)n+εN. R_S ( G_n, )≤ 4 _k=1^N _k-1 ( _k, G_n, ,d_n )n+ _N. By the proper-subclass covering argument above, log(εk,~n,ε,dn)≤log(εk2,~,dn). ( _k, G_n, ,d_n )≤ ( _k2, G,d_n ). Since PnP_n is finitely supported, the entropy bound for ~ G applies with Q=PnQ=P_n. Therefore log(εk2,~,dn)≤H~(εk/2)≤22p+1Aεk−p. ( _k2, G,d_n )≤ H_ G( _k/2)≤ 2^2p+1A _k^-p. Thus, for a constant Cp>0C_p>0 depending only on p, ℜ^S(~n,ε)≤CpAn∑k=1Nεk−1εk−p/2+εN. R_S ( G_n, )≤ C_p An _k=1^N _k-1 _k^-p/2+ _N. Since εk−1=2εk _k-1=2 _k, εk−1εk−p/2=2εk1−p/2=2ε1−p/22k(p/2−1). _k-1 _k^-p/2=2 _k^1-p/2=2 ^1-p/22^k(p/2-1). Hence ℜ^S(~n,ε)≤CpAnε1−p/2∑k=1N2k(p/2−1)+2−Nε. R_S ( G_n, )≤ C_p An\, ^1-p/2 _k=1^N2^k(p/2-1)+2^-N . Taking expectation over S, the same bound holds for Ψ(ε) ( ): Ψ(ε)≤CpAnε1−p/2∑k=1N2k(p/2−1)+2−Nε. ( )≤ C_p An\, ^1-p/2 _k=1^N2^k(p/2-1)+2^-N . Now choose ε0:=A¯1/p, _0:= A^1/p,N:=max1,⌈log2np⌉.N:= \1, _2np \. Since p>2p>2, ∑k=1N2k(p/2−1)≤Cpn1/2−1/p, _k=1^N2^k(p/2-1)≤ C_pn^1/2-1/p,2−N≤n−1/p.2^-N≤ n^-1/p. Therefore Ψ(ε0)≤CpAε01−p/2n−1/p+ε0n−1/p. ( _0)≤ C_p A\, _0^1-p/2n^-1/p+ _0n^-1/p. Because ε0p=A¯=1∨A _0^p= A=1 A, we have Aε01−p/2≤ε0. A\, _0^1-p/2≤ _0. Indeed, if A≥1A≥ 1, then Aε01−p/2=A1/2A(1−p/2)/p=A1/p=ε0, A\, _0^1-p/2=A^1/2A^(1-p/2)/p=A^1/p= _0, while if A<1A<1, then ε0=1 _0=1 and Aε01−p/2=A≤1=ε0. A\, _0^1-p/2= A≤ 1= _0. Thus Ψ(ε0)≤CpA¯1/pn−1/p. ( _0)≤ C_p A^1/pn^-1/p. We next bound the entropy terms in Theorem 2 of Lei et al. [17] at ε0 _0. Since the entropy bound has been extended above to all positive scales, H(ε0/2)≤A(ε0/2)−p=2pAε0−p=2pA¯≤2p.H_G( _0/2)≤ A( _0/2)^-p=2^pA _0^-p=2^p A A≤ 2^p. Substituting ε=ε0 = _0 into the local Rademacher bound gives ℜn((r))≤CpA¯1/pn−1/p+Cp,bn+Cprn. R_n(G(r))≤ C_p A^1/pn^-1/p+ C_p,bn+C_p rn. Since n≥1n≥ 1, p>2p>2, and A¯1/p≥1 A^1/p≥ 1, 1n≤A¯1/pn−1/p. 1n≤ A^1/pn^-1/p. Absorbing constants depending only on p and b, we obtain ℜn((r))≤Cp,b(A¯1/pn−1/p+rn). R_n(G(r))≤ C_p,b ( A^1/pn^-1/p+ rn ). This proves the claim. ∎ Corollary 5 (Local Lipschitz scaling). On the event of probability at least 1−δ1-δ from Corollary 3, suppose that Δn,r,δ>0. _n,r,δ>0. Then every f∈ℱLf _L satisfying Pℓρ,f2≤randR^0(f)≤σ2−εP _ρ,f^2≤ r R_0(f)≤σ^2- must satisfy the following lower bounds. If ρ>0ρ>0, then L≥−Bn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ2ρ2,L≥ -B_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ2ρ^2, (9) where Bn,ρ,ε:=2ρσ2−ε+2CdDn−1/d.B_n,ρ, :=2ρ σ^2- +2C_dDn^-1/d. (10) Equivalently, L≥2Δn,r,δBn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ.L≥ 2 _n,r,δB_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ. (11) In particular, L≥Δn,r,δ2ρσ2−ε+2CdDn−1/d+ρΔn,r,δ.L≥ _n,r,δ2ρ σ^2- +2C_dDn^-1/d+ρ _n,r,δ. (12) Consequently, up to constants depending only on d, L=Ω(Δn,r,δρσ2−ε+Dn−1/d+ρΔn,r,δ).L= ( _n,r,δρ σ^2- +Dn^-1/d+ρ _n,r,δ ). (13) If ρ=0ρ=0 and D>0D>0, then L≥Δn,r,δ2CdDn−1/d=Ω(Δn,r,δn1/dD).L≥ _n,r,δ2C_dDn^-1/d= ( _n,r,δn^1/dD ). (14) If ρ=0ρ=0, D=0D=0, and Δn,r,δ>0 _n,r,δ>0, then no such f can satisfy the two assumptions above on the event of Corollary 3. Proof. Starting from (3), set Bn,ρ,ε=2ρσ2−ε+2CdDn−1/d.B_n,ρ, =2ρ σ^2- +2C_dDn^-1/d. Then every admissible f must satisfy ρ2L2+Bn,ρ,εL−Δn,r,δ≥0.ρ^2L^2+B_n,ρ, L- _n,r,δ≥ 0. First suppose ρ>0ρ>0. The quadratic q(L):=ρ2L2+Bn,ρ,εL−Δn,r,δq(L):=ρ^2L^2+B_n,ρ, L- _n,r,δ has one negative root and one positive root because Δn,r,δ>0 _n,r,δ>0 and Bn,ρ,ε≥0B_n,ρ, ≥ 0. Since L≥0L≥ 0, the condition q(L)≥0q(L)≥ 0 forces L to be at least the positive root. Therefore L≥−Bn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ2ρ2,L≥ -B_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ2ρ^2, which proves (4). Rationalizing the numerator gives −Bn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ2ρ2=2Δn,r,δBn,ρ,ε+Bn,ρ,ε2+4ρ2Δn,r,δ, -B_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ2ρ^2= 2 _n,r,δB_n,ρ, + B_n,ρ, ^2+4ρ^2 _n,r,δ, which proves (6). Moreover, Bn,ρ,ε2+4ρ2Δn,r,δ≤Bn,ρ,ε+2ρΔn,r,δ. B_n,ρ, ^2+4ρ^2 _n,r,δ≤ B_n,ρ, +2ρ _n,r,δ. Hence L≥2Δn,r,δ2Bn,ρ,ε+2ρΔn,r,δ=Δn,r,δBn,ρ,ε+ρΔn,r,δ.L≥ 2 _n,r,δ2B_n,ρ, +2ρ _n,r,δ= _n,r,δB_n,ρ, +ρ _n,r,δ. Substituting the definition of Bn,ρ,εB_n,ρ, gives (7), and the order form (8) follows immediately. Now suppose ρ=0ρ=0. Then (3) reduces to Δn,r,δ≤2CdDLn−1/d. _n,r,δ≤ 2C_dDLn^-1/d. If D>0D>0, rearranging gives L≥Δn,r,δ2CdDn−1/d,L≥ _n,r,δ2C_dDn^-1/d, which proves (14). If D=0D=0, the right-hand side of the reduced compatibility condition is zero, contradicting Δn,r,δ>0 _n,r,δ>0. Hence no admissible f can exist in that case. ∎ NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and introduction state the theoretical goal of connecting law-of-robustness bounds to robust generalization. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The Discussion section states that the current theory is for squared loss while the experiments use cross-entropy, and it identifies extensions to Bregmann losses, local Lipschitz notions, distributional robustness, etc. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete proof? Answer: [Yes] 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper, regardless of whether the code and data are provided? Answer: [N/A] 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [N/A] 6. Experimental setting/details Question: Does the paper specify all the training and test details, e.g., data splits, hyperparameters, how they were chosen, type of optimizer, necessary to understand the results? Answer: [N/A] 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [N/A] 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources, type of compute workers, memory, and time of execution needed to reproduce the experiments? Answer: [N/A] 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics? Answer: [Yes] 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [N/A] 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse, e.g., pre-trained language models, image generators, or scraped datasets? Answer: [N/A] 12. Licenses for existing assets Question: Are the creators or original owners of assets, e.g., code, data, models, used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [N/A] 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [N/A] 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation? Answer: [N/A] 15. Institutional review board approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board approvals or an equivalent approval/review based on the requirements of the authors’ country or institution were obtained? Answer: [N/A] 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [N/A]