On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Bounds
Authors: Matteo Vilucchio
Nikolaos Tsilivis
Bruno Loureiro
Julia Kempe
Venue: Accepted by TMLR ()

Abstract: Regularization, whether explicit in terms of a penalty in the loss or implicit in the choice of algorithm, is a cornerstone of modern machine learning. Indeed, controlling the complexity of the model class is particularly important when data is scarce, noisy or contaminated, as it translates a statistical belief on the underlying structure of the data. This work investigates the question of how to choose the regularization norm $\lVert \cdot \rVert$ in the context of high-dimensional adversarial training for binary classification. To this end, we first derive an exact asymptotic description of the robust, regularized empirical risk minimizer for various types of adversarial attacks and regularization norms (including non-$\ell_p$ norms). We complement this analysis with a uniform convergence analysis, deriving bounds on the Rademacher Complexity for this class of problems. Leveraging our theoretical results, we quantitatively characterize the relationship between perturbation size and the optimal choice of $\lVert \cdot \rVert$, confirming the intuition that, in the data scarce regime,  the type of regularization becomes increasingly important for adversarial training as perturbations grow in size.

Published in Transactions on Machine Learning Research (04/2026)
On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Bounds
Matteo Vilucchio
matteo siuccccooscchhheepp..cco
Information. Learning and Physics Laboratory, Ecole Polytechnique Fédérale de Lausanne (EPFL)
Nikolaos Tsilivis
md.2331 Emyu..ddu
Center for Data Science, New York University
Bruno Loureiro
brloureino@gmaailcoom com
Déportement d' d'Informatique, École Normale Supérieure PSL 8 CNRS, France
Julia Kempe
kempe @nyu. edu
Center for Data Science, New York University
Courant Institute of Muthematical Sciences, New York University
FAIR, META
Reviewed on OpenReview: https: // optp//ieeprrvvew...mmmmm net/ hl//fforur forum? id= vkmvuranbm
Abstract
Regularization, whether explicit in terms of a penalty the loss or implicit. the choice of algorithm, is a cornerstone of modern machine learning. Indeed, controlling the complexity of the model class is particularly important when data is scarce, noisy contaminated, as translates statistical belief on the underlying structure of the data. This work investigates the question of how to choose the regularization norm ||-|| in the context of high-dimensional adversarial training for binary classification. To this end, we first derive an exact asymptotic description of the robust, regularized empirical risk minimizer for various lypes of adversarial attacks and regularization norms (including non-lp norms). We complement this analysis with uniform convergence analysis, deriving bounds on the Rademacher Complexity for this class of problems. Leveraging our theoretical results, we quantitatively characterize the relationship between perturbation size and the optimal choice of ||-||, confirming the intuition that, in the data scarce regime, the type of regularization becomes increasingly important for adversarial training as perturbations grow in size.
1 Introduction
Despite all its successes, deep learning still underperforms spectacularly in worst-case situations, when models face innocent-looking data which are adversarially crafted for eliciting erroneous or undesired outputs. Since the discovery of these failure modes in computer vision (Szegedy et al.) 2014) and their re-discovery, more recently, in other modalities including text. (Zou et al. 2023), considerable effort has been put designing algorithms for training models which are robust against these adversarial attacks.
In the context of supervised learning problems, principled approach consists of appropriately modifying standard empirical risk minimization: parametric model is fit by minimizing worst-case empirical risk, where "worst-case" refers to an assumed threat model. For example, in computer vision, a threat model of lxc: perturbations translates the assumption that images whose pixels only diller by little should share the same label. Despite its conceptual clarity and proven ability to return robust models, a major drawback of this method, known as robust empirical risk minimization (RERM) or adversarial training (Goodfellow et al., 2015a; Madry et al. 2018), is that often comes with a performance tradeoff, besides being computationally more intensive than standard ERM. Indeed, has been observed that model accuracy is often compromised

---

Published in Transactions on Machine Learning Research (04/2026)
for better robustness [Tippaa et al., 2019 Zhang al.) 2019). To make matters worse, neural networks often exhibit large gap between their robust train and test performances in standard computer vision benchmarks (Rice et al. 2020).
Many empirical efforts in addressing these statistical limitations of RERM have focused on either increasing the amount of labeled (Wang al.
2023 or unlabeled (Carmon et al. 2019 Zhai et al. 2019) data, or on painstakingly re-imagining several of the design choices of deep learning (such at the loss function (Zhai et al,
2019), model averaging (Chen et al., 2021 Rebuffi et al., 2021] and more). Despite the apparent empirical
challenges, simple guidelines how different choices affect the statistical efficiency of RERM are clearly missing, even in simple models.
In this work, we make a step lowards theoretically filing this gap by invesligating model selection in RERM, and how it relates to robust and standard generalization error. In particular, we focus on the oldest model selection method: (weight.) regularization. Following large body of work originating in high-dimensional statisties (Krogh & Hertz 1991 Seung et al. 1992 [ean et al., 2013a Thrampoulidis et. al. 2018 Aubin et al. 2020 Vilucchio et al.) 2024 2025), we study this fundamental question asymptotically, when both the input dimension and the number of training samples grow to infinity while keeping their ratio constant, and under a Gaussian setting. While it is customary in this literature to study which values of regularization coefficients yield the best test errors (balancing empirical fitness with model complexity), we instead analyze the optimality of a type of regularization. A motivation for this comes from a separate line of work in uniform convergence bounds that stresses the importance of the type of regularization for robust generalization (Yin) et al. 2019 Awasthi al. 2020 Tsilivis et al., 2024). Borrowing from this line of work, which mainly offers qualitative bounds, and reinforcing it with new findings, we demonstrate, via sharp asymptotic descriptions of the errors in (regularized) RERM for variety of different perturbation and regularization norms, that regularization becomes increasingly important in RERM as the perturbation strength grows in size. This allows us to get an exact description of the relationship between optimal type of regularization and strength of perturbation, and discuss how regularization affects the tradcoff between robustness and accuracy.
To summarize, our main contributions in this work are the following:
1. We derive an exact asymptotic description of the performance of regularized RERMs for variety of perturbation and regularization norms. In addition to the usually studied lp. we consider I|-1|x: norms (induced by a positive symmetric matrix 2), which allow us to separate the effect perturbation on different features of the input.
2. We show uniform convergence bounds for this class of problems (i.e., |I-I|x regularized), by establishing new results on the Rademacher complexities for several classes of linear hypothesis classes under adversarial perturbations.
Leveraging the thcoretical results above, we show that regularizing with the dual norm of the perturbation can yield benefits in terms of robustness and accuracy, compared other regularization choices. In particular, our analysis permits precise characterization of the relationship between the perturbation geometry and the optimal type of regularization, It further allows decomposition of the contribution of regularization in terms of standard and robust (test) error.
Our results can be seen as positive news. Indcod, the main implication of our work for robust machine learning practice is that model selection, in the form of either explicil implicit regularization, plays more important role in robust ERM than in standard ERM. In the context of robust deep learning practice, model selection is often implicit in the choice of architecture, learning algorithm, stopping time, hyperparameters, etc. Our theoretical analysis in the context of simple adversarial tasks highlights the importance of these choices, as they can be crucial to the outcome in terms of robustness and performance.
Finally, while typical-case and worst-case analyses usually appear as opposites in the statistical lcarning literature, we believe our work nicely illustrates how these two approaches to studying generalization can be combined in complementary way to yield precise answers with both explanatory and predictive powers.
2

---

Published in Transactions on Machine Learning Research (04/2026)
1.1 Related work
We discuss here two recent related works, while defer more extensive discussion to Appendix A Recently, [Tannrr et al. (2025) derived high dimensional asymptoties for robust binary classification with l regularization, considering perturbations in general |1-1x norm. In our work, we study the effect of regularization, providing exact asymptolics for any combination of lp perturbation and regularization norm, while extending (Tanner et al. 2025) for various IIl|a regularization norms (where A is a positive symmetric matrix). From the perspective of learning thcory, Tsilivis et al. (2024) recently highlighted the importance of the (implicit) regularization in RERM with linear models, by showing the effect of the learning algorithm and the architecture on the robustness of the final predictor. Tn our work, consider, instead, explicit. regularization and more general perturbation (and regularization) geometries.
In Section 3 we present the technical theorems about the exact asymptotics. In Section ! we present the uniform convergence bounds. In Section 5 using the technical tools developed in the previous two sections, we investigate what regularisation geometry is optimal for robust generalization error.
2 Setting Specification
We consider a binary classification task with training data S {( 9:) where æ; E Rd and yi E {-1,+1} are sampled independently from a distribution D of the following form:
P(x,y) v) [ dur,, Pout (ul (uu 2t)
Pin Pun
(1)
where Pin is probability density function over IE& and Pout : IR + [0, 1] encodes our assumption that the label is (potentially non-deterministic) linear function of the input with teacher weights w. Rd. Here, we denote z = (w., / /Vd as the (normalized) pro-activation. For example, noiseless problem corresponds to Pout (v|z) 6(y =)), while we can incorporale noise by using the probil model: (y]z)) = e/2 (-w=/V2r), where 7 > 0 controls the label noise. We assume that w. E Rdd is drawn from a prior distribution Pw-
Given the training data S, our objective is to investigate the robustness and accuracy of linear classifiers f(w, z) sign((w, x)/ /Vd, where w (S)) are learned from the training data.
We define the robust generalization error as
max 1 + Φ(0, + +6) [|8||s
Erob (w) E Emn
(2)
where the pair (x. v) comes from the same distribution as the training data, and E bounds the magnitude of adversarial perturbations under a specific choice of norm. The (slandard) generulizalion ervor is defined as the rate of misclassification of the learnt predictor
Egen (v) = E(a.g)=D([( + ((w,)))).
3
Notice that for = 0: Erob( Egen ( for all is E Rdd. We will frequently use the following decomposition of the robust generalization error into (standard) generalization error and boundary error Ebnd:
Frob Fegen (fr) Pbon((1))
(4)
where Eond is defined as follows
Ebnd ( = ED 1(y = (((): max 1 * س(w x + 61) [|
(5)
As its name suggests, Ebnd is the probability of sample lying on (or near) the docision boundary, i.c., the probability that a sample is correctly classified without perturbation but incorrectly classified with it.
3

---

Published in Transactions on Machine Learning Research (04/2026)
2.1 Robust Regularized Empirical Risk Minimization
Direct minimization of the robust generalization error of eq. ( presents two main challenges: first, the objective function is non-convex due to the indicator function, and second, we only have access to a finite dataset rather than the full data-generating distribution. To address these issues, & widely adopted approach, introduced for the first time by Goodfellow et al. (2015b), is to optimise the robust empirical (regularized) risk, defined as
max 9 1/1 (w, Le + ++))) XF(ur) [(w) Σ
(6)
Vd
where g: IR + R4 is non-increasing convex loss function that serves surrogate for the 0-1 loss, i(w) is a convex regularization term, and À 2 0 is regularization parameter. The inner maximization over ò; models the worst-case perturbation for each data point, constrained by the attack budget & during training. Given the dataset S, we estimate the parameters of our model as
W E arg min L(w).
wER"
The choice of loss function g, regularization 7, and parameters and can significantly impact the model's accuracy and robustness.
In practice, eq. (7) is often solved with first-order optimization method, such gradient descent. Prior work (Soudry et al. 2018) has shown that optimizing the unregularized loss without any adversarial perturba-
tions (eq. 7 for x = 0) with gradient descent is equivalent to eq. 7 with the euclidean norm squared as a regularizer, where the free regularizer strength corresponds to the time duration of the algorithm (A 0 as the number of iterations goes xo). Similar results can be obtained for different first-order algorithms (Gunasekar et al., 2018) (in particular, when F(w) = | -u this corresponds to the family of steepest descent algorithms) as well as in the adversarial case (e 0) (Tsllivis et al. 2024). Therefore, studying egs. 6 and is equivalent to studying the solutions returned by first-order optimization algorithm.
3 Exact Asymptotics of Robust ERM
Our first technical result an asymptotic description of the properties of the solution of eqs. (6) and in the proportional high-dimensional limit, under the assumption of isotropic Gaussian distribution. While restrictive, this assumption is supported by recent theoretical advances showing that many learning problems exhibit universality: their asymptotic behavior matches Gaussian predictions even with non- non-Gaussian data
(Goldt et al. 2022b: Loureiro el al. 2021 Hu & Lu 2023 Montanari & Saeed 2022 Dandi et al. 2023 Wei
et al. 2022 Pesce et al. 2023 Gerace et al.] 2024]. ). While proving such correspondence for our setting is
outside the scope this work, this suggests our analysis of the Gaussian case can provide valuable insights into practical adversarial training.
3.1 Results for l norms
First, we consider the setting where the perturbations ions in eqs. (2) and 16 are constrained in their l, norm for p e oo). More precisely, we make the following assumptions:
Assumption 3.1 (Hiig--Dimensional Limit). We consider the proportional high-dimensional regime where both the number of training data n and input dimension diverge to infinily simultaneously at the same rate, while maintaining a fixed ratio a := n/a.
Assumption 3.2 (4, Norms). Let = |x, |x 1/2 denote the lp norm for p E (1,,,), with p being its dual exponent (1/++1/p- 1). The adversarial perturbations are constrained by an lp norm with parameter p. while for regularization we consider the function f(w) ||lle"" where E [1, oo) parameter that can differ from p.
Assumption 3.3 (Scaling of Adversarial Norm Constraint). We suppose that the value of scales with the dimension d such that e/d /Vd) Oa(1).
4

---

Published in Transactions on Machine Learning Research (04/2026)
Assumption 3.4 (Data Distribution). For each E [n], the covariates 2; E R are drawn i.d. from the data distribution (x) = Na (0, Ida). Then the corresponding yi is sampled independently from the conditional distribution Pout defined in eq. [ The target weight vector w. E Rd is drawn from a prior probability distribution Pw which is separable, ie. (w(w)= I Pu(ws) for distribution P. in R with finite variance Var(Pw) = co.
Under these assumptions, our first result states that in the high-dimensional limit, the robust generalization error associated with the RERM solution in eq. 77) asymptotically depends only on a few deterministic variables, known as the summary statistics, which can be computed by solving a set of low-dimensional self-consistent equations.
Theorem 3.5 (Limiting errors for Lp norm). Let ((() Rd denote solution of the RERM problem in eq. 7 Then, under Assumptions 3.1 to 3.4 the standard, robust and boundary generalization error of w converge in distribution to the following deterministic quantities
Eegen(i)) π
arccos
In'/V(p +2)
Ebud = / p'rpI
Vor erfe
J
e 2 dv 2n
22pp+ 2/9))
Frab((0) Eegen (it) + Frand (i))
where mč, , p are the values to which the following summary statistics converge in probabiliby to, i.e. 1/ (w,, w)) + m 211:0112 + -"" 2ll@@pp - P* P",
Remark 3.6. An immodiate observation from the above equations is that Egen is monotonically increasing as a function of the cosine of the angle between teacher and student (m" \/m²)) while Fbnd is decreasing. This has been observed before for boundary based classifiers (Tanay & Griffin 2016 Tanner et al. 2025
Theorem 3.5 therefore states that in order to characterize the robust generalization error in the high- dimensional limit, it is enough to compute three low-dimensional statistics of the RERM solution. Our next result shows that these quantities can be asymptotically computed without having to actually solve the high-dimensional minimization problem in eq. 7
Theorem 3.7 (Self-consistent equations for lp norms). Under the same assumptions as Theorem 3.5 the summary statistics (m" ,9", PP) are the unéque solution of the following set of self-consistent equations:
in = aB [R dy 2o. P)]
m Rg
O 2 Zw Jm WT. P.A)]
i = =a [s dy 20 (VTE, P)]
9 RS
Zn (7T. P, PA))2]
V- aB [. dy ZoOw., S, (VTE, Pi]
Z (VQE. P.A)]
(9)
V Ee
P EapT P 3 Eg J/ dy Zoyfol (VT
P = E& 2m0 + f1ppp ( (Vie)
(8)
where Zne- = Z (me// / // / 2o = Zoly. me/ /a P -- m²//)) and & ~ (O, 1), and:
Zoly. w. V) = =E,-No.0 (Pou(1) VV2 vV=+w)l
An( = EwnP,
B (-bAvo+tww
(10)
-w -w -w)/ lsww, P) (P (Pvolu--ge "/a (ww)-wwik
1,,,, = -P PH
(11)
where indicate the prorimal of function f R + as Pvs((()) and its Moreau envelope with (y)()
Two remarks on these two results are in order.
Remark 3.8. Both results hold for any separable convex regularizer in the definition of the empirical risk in eq. G This is in contrast to many prior works in this field, which primarily consider &g regularizations. Remark 3.9. The first four equations (eq. (8)) depend only on the noise distribution and the loss function, while the second set (eq. (9)) depends the regularization function and the dual norm of the perturbation.
5

---

Published in Transactions on Machine Learning Research (04/2026)
3.2 Results for Mahalanobis norms
While the lp norm is the most frequently discussed in the robust learning literature, L perturbations are isotropic, treating all covariates equally. Under the isotropic Gaussian Assumption 3.4 this is justified. However, it can be limiting under more realistic scenarios where the covariates are structured, and for instance some features are more relevant. than others. Recently, Tanner el al. (2025) introduced a model for studying adversarial training under structured covariates which considers perturbations under a Mahalanobis norm, allowing to weight the perturbation along different directions. However, the discussion that work focused only on &g regularization.
Since our goal in this work is to study what is the best regularization choice for given perturbation geometry, now derive asymptotic results akin to the ones of Section 3.1 under any combination of Mahalanobis perturbation and regularization norm. As before, we start by introducing our assumptions.
Assumption 3.10 (Mahalanobis norms). Given positive definite matrix Σs, we consider perturbations under a Mahalanobis norm | | - V Esæ. Additionally, we consider the regularization function to be F(w) = 1/2 u² Ew ur for positive definite matrix Ew.
Assumption 3.11 (Structured data). For each E [m], the covariates æ; Rd are drawn i.idd from the data distribution Pin(x) (O, (0, Ex). Then the corresponding Wi is sampled independently from the conditional distribution Pout defined in eq.
(1) The target weight vector E IR is drawn from a prior probability distribution w, ~ Pw = Nw. (0, Me), which we assume has limiting Mahalanobis norm given by p -= lim w. E. Assumption 3.12 (Scaling of Adversarial Norm Constraint). The value of & does not scales with the dimension d such that & = O2(1.
Assumption 3.13 (Convergence of spectra). We suppose that Ex, Es, Eg, E. are simultaneously diagonal- isable. We call Σx = T diag(w))S, Eg S diag(S:)S and Ew S diag(w,)S, We define O SE w w. //pp. We assume that the empirical distributions of cigenvalues and the entries of jointly converge to probability distribution μ as
5 8) 0(w w) - ()0(w; - w) n.
(12)
Remark 3.14. The simultaneous diagonalizability assumption is equivalent to the matrices having common principal components (Flury 1984 1988), a common framework in multivariate statistics where multiple
covariance matrices share eigenvectors but may have group-specific eigenvalues. This structure arises naturally
in signal processing applications such as blind source separation (Belouchrani et al. 1997 Cardoso &
Souloumiac 1996) and independent component analysis (Comon 1994 Hyvärinen & Oja 2000
As in Section 3.1 our first result concerns the limiting robust error.
Thcorem 3.15 (Limiting errors for Mahalanobis norm). Let i () Rdd denote the unique solution of the
RERM problem in eq. 7 Then, under Assumptions 3.1 and 3.10 to 3.13 the slandard, robust and boundary
generolization error of converge in distribution to the following deterministic quantities
Pggn(1D) = arccos m² /Vpp++++)>*
E Vo-
m 12(tt2-mmsp
Eond (10) =
erfe
du
22
Erob( ()) Egen (w)) + Fbnd(w))
where m²,q", g", P are the values to which the following summary statistics converge in probability to, L.e.
w Ee
m
de
En d
Es
PA
As in Soction 3.1 our next result shows that the summary statistics characterizing the limiting errors can be obtained from of set of self-consistent equations.

---

Published in Transactions on Machine Learning Research (04/2026)
Theorem 3.16 (Self- Celf-Consistent equations for Mahalanobis norm). Under the same assumptions Theo- rem 3. 15 the summary statistics (m", q², Pr) are the unique solution of the following set of self-consistent
equations:
m = E
m- aBg [ dy Zo VTE 117,1-11)ffll 1)) P)]
Awtt W
m
Bn
i = a [sR dy Zo VMc, 1 - (1) P)]
(Aw+
(14)
(13)
V aB Le dy Zoly: VTS, -1)0 P)]
V By
Aw+ Vw++P tha 0 +-4W"
P = 2Eap [Je dy Zu 1/f.1-1)ufg(
P Eu
(Aw Vor P8y2
where is the joint limiting distribution for the spectrum of all the matrices from Assumption 3.13
Remark 3.17. Notice that the first set of equations is the same as Theorem 3.7 as they depend only on the marginal distribution Pout and the loss function.
Remark 3.18 (Interpretation of the sell-consistent equations). The self-consistenl equations in Theorems 3.7 reduce
and reduee the high-dimensional optimization problem in eq. (7) to tracking only three scalar statistics (m*, -4" P*). These equations, derived via Gordon's Min-Max theorem, fully characterize the asymptotic behavior of regularized RERM through the interaction of these quantities at optimality.
While the self-consistent equations in Theorem 3.7 and Theorem 3. 1616 do not admit closed-form solution, they be efficiently solved using an iteration scheme (Appendix E Solving them yields precise curves for the generalization errors of the final predictor function of the sample complexity a and regularization geometry, allowing us to draw conclusions for the interplay between the regularization and perturbation see simulations in Section
The details of the proofs of Theorems 3.5
3.7
3.15 and 3.16 are discussed Appendix B
They are based on
an adaptation of Gordon's Min-Max Theorem for convex empirical risk minimization problems (Thrampoulddis
al. 2014
Lourciro al. 2021).
4
Which Regularization to Choose?
Our results in the previous section provide tight. predictions on the robust and standard generalization error of the set of minimizers of the robust (regularized) empirical risk. However, since the self-consistent equations describing the robust errors are not closed, it is not straightforward to read why some regularizers might produce better results than others. In this section, we derive complementary uniform convergence bounds based on the Rademacher Complezity for linear predictors under various geometries. While these bounds might not be mumerically tight, they are distribution-agnostte and provide a a-priori guarantees for the error of a predictor which are qualitatively useful. We start by introducing concepts in a general way, before deriving guarantees for the case considered in Section 3.2
Let H- be hypothesis class of linear predictors of restricted complexity, captured by function F: Rd - R.
This function plays the role of regularizer, as in Section 3 We define:
Hr (x (w, x): F(w) S W
(15)
where W 0 is arbitrary upper bound.
Central to the analysis of the generalization error uniformly inside the hypothesis class Hz is the notion of the (empirical) Rademacher Complerity (Koltchinskii 2001 of Hz
Rg (H,)) E,
sup wwr(w) ww2 1=1
0 (w, xi))
(16)
7

---

Published in Transactions on Machine Learning Research (04/2026)
where the os's are either -1 1 with equal probability. In the case of robust generalization with respect to Il [|-limited perturbations, it suffices to analyse the worst-case Rademacher Complexity of Hy=
a oi min (w, a4 + 8:) |6:
Er
sup ( SWW
71
With these ingredients in place, we can state the following bound on the robust generalization gap of any predictor in H7.-
Theorem 4.1 (Mohri et al. 20012; ; Awasthi et al. (2020 For any δ > 0, with probability at least 1 ô over the draw of the dataset S, for all w E R2 such that r(w)
S W (eq. 15
it holds that
log 2/8
(no)(w) & Erob(w)) + 2 (H,) + 3
(17)
2n
where
Brob = Σ
max (1,ū(w 0,) s 1=1 Se
(18)
is a robust empirical error.
Theorem promises that a tight bound on the worst-case Rademacher complexity of HH can bound the (robust) generalization gap of any predictor in Hr. The next proposition realises this goal for the general class of strongly conver functions This will permit the study of the cases of Scction 3.2
Proposition 4.2. Let e, > O. Consider sample S = ((I1.V))..- (I vn)}, and let Ht be the hypothesis where F is strongly conver with respect to norm .Il-11. Then, it holds:
class defined in eq. 15
Rig (H²) max,
W |xs] W.
2
E
sup W
[
(19)
vE[n]
on 2/n
where -.I.-l+=11-11
II-II+ denote the dual norms of 11l-11, I1-11, respectively.
The proof (Appendix C leverages a fundamental result on (standard) Rademacher complexities for strongly convex functions due to Kakade et al. (2008) and a symmetrization argument. This result informs us that the worst-case Rademacher complexity can decompose into two terms: one which characterizes the standard error and one that scales with the magnitude of perturbation and depends on the dual norm of the perturbation. Thus, expect that regularization which promotes small second term in the RHS of eq- (19) will likely mean smaller robust generalization gap, increases. This can be further elucidated in the following subcases (proofs appear in Appendix C for which already derived exact asymptotics in Section 3.2
|| = I|,,,,, and F(w) = || this corresponds to perturbations with respect to a a symmetric positive definite matrix Eg E IBdxd, while we regularize in the Euclidean norm. In this case, obtain:
Corollary 4.3. Let e > 0 and symmetric positive definite Eg E 12dxd, Then:
As(H))11)) < maxie[m]
||x EW2 2/n Amin (Es). (Es)
12
Vn
|||1=, and F(w)) = // this corresponds to perturbations with respect to a symmetric positive definite matrix Eg E ddd and regularization with respect to a norm induced by another matrix
En E Idddd We will analyze the special case where Σg and En share the same set of eigenvectors.
Corollary 4.4. Let > 0. Let En = Eie L.vV and Eg orthonormal. Then:
Eie A.V,V,, with v, E Rdd being
WA maxigjn
||x 1-11x=11
eWE... 2/n
1
Rg (H
(1a) )
+
max (E
(20)
Vn
XçO
8

---

Published in Transactions on Machine Learning Research (04/2026)
Erob (r =2] Erob (r =1
Eyohy E
0.5
0.5
0.8
0.1
0.4
Egan
Bxab
0.6
10-1
0.3
0.2
Ebad
0.2
0.0
10-2
-0.2
0.4
10
10
100
n/d
n/d
Figure 1: (Left) Goneralization error RERMs in the low sample complexity regime under &o perturbations for various choices of regularization. The edge & over other methods stems from the boundary error (Enna) which goes to zero as + 0t. Setting: & 0.2 with optimally tuned X. Bullet points with error bars are RERM simulations for 1000 (10 seeds). (Right) Difference between robust generalization errors for and as function of and for loo attacks. Green zones correspond to areas where the dual norm regularizatioe (e1) performs better than l2.
0.15
0.60
0.60
0.40
0.40
Exob
0.35
0.20
0.50
0.30
6
Σ
0.45
0.01
0.2
8
10
10
10
100
1.0
1.5
2.0
2.5
3.0
a an//d
Figure 2: (Left) Difference between robust generalization error for Es perturbations. We see that a regularization with the dual norm has the best adversarial error for different choices of The points with the error bars (std) are RERM simulations for d 1000 (10 random seeds), while the solid lines correspond to the theoretical predictions. (Right) Robust generalization error of the solution of regularized RERM a function of the regularization order i.e. F(w) = w|] for various perturbations strengths s. Sample complexity a = 1.0. Rogularization cocfficients are optimally tuned. The inside figure shows how the optimal value of scales with
Hence, we deduce that regularizing the class of linear predictors with Ew, = ΣT where Eg is the matrix of the perturbation bation norm, can more effectively control the robust generalization error. See Remark C.4 for more details.
Similar results can be derived in the context of bp perturbations see Yin et al. 2019 Awasthi al. 2020 and Appendix C In fact, mirroring analysis, the robust generalization error there is controlled by the I| norm of the weights. We explore the effect of the regularizer numerically with simulations next.
5 Experiments
Leveraging our exact results from Section 3 and guided by the predictions of Section 4 in this Section we numerically investigate the role of the regularization geometry in the robustness and accuracy robust empirical risk minimizers. Experimental details and further ablation studics are presented Appendix [ where we consider experiments on the MNIST dataset [Deng 2012) and additional ablations for choice of E,, in the Mahalanobis norms' case.
9

---

Published in Transactions on Machine Learning Research (04/2026)
5.1 Importance of Regularization in the Scarce Data Regime
First, we consider the setling of Section 3.1 with perlurbations constrained in their t norms, for three different regularizers (f1. &2 and f3 norms). Figure (Left) compares the generalization errors of the solutions in eq. 7 for the various regularizers and plots them as a function of the sample complexity a. Note that when a is small (scarce data), the l regularized solution (dual norm of (x) provides better defense against es perturbations. Interestingly, this due to the fact that the boundary error approaches zero as a - 0+, only the case when r = (same figure, bottom). We analytically explore this phenomenon further in Appendix [B8 where we analyze the boundary error from Theorem 3.5 and probe its dependence the overlap parameters (m" "n",,"" P.).
The phase diagram of Figure | (Right) further elucidates the difference of the methods as a function of e. We display the difference in robust generalization error between & and & regularized solutions versus attack budget and sample complexity a, with optimally tuned regularization coefficient A. We observe that 4 outperforms lz regularization regions of high and low a.
where the perturbations are constrained in Mahalanobis norm |1-1|es. We observe that regularizing the weights of the solution with the dual norm of the perturbation (11-1lz71) yields better robustness, while the gap between the various methods increases grows.
Figure 2 (Left) demonstrates Eroh in the structured
of Section 3.2
5.2 Optimal Regularization Geometry as Function of
While the previous figures compared the various regularizers F(w) as grows, it is not clear what exactly the relationship is between optimal F(w) and perturbation strength. In particular, we expect when & = 0, lz-regularized solutions to achieve better accuracy, due to the fact that the data are Gaussian. However, it is not clear how the transition to the dual norm happens.
We examine this relationship in Figure 2 (Right), where we plot the robust generalization error for various values of perturbation e and regularization order for a fixed value of sample complexity a. We observe that, the attack strength increases, the order of the optimal regularization smoothly transitions from 2 to 1. Hence, there is regime of perturbation scale where neither 2 nor 1 is optimal, but an order of r E (1, achieves the least robust test error.
6 Conclusion
We studied the role of regularization in robust empirical risk minimization (adversarial training) for a variety of perturbation and regularization norms. We derived an exact asymptotic description of the robust and standard generalization error in the high-dimensional proportional limit, and we showed results for the (worst-case) Rademacher Complexity of linear predictors in the case of structured perturbations. Phase diagrams and exact scaling laws, afforded by our analysis, suggest. that choosing the right regularization becomes increasingly important as grows, and, in fact, this optimal regularization often corresponds to the dual norm of the perturbation. Furthermore, our results reveal a curious, smooth, transition between different optimal regularizations (&2 to &i with increasing perturbation strength; a phenomenon that has not yet been captured by any other theoretical work.
It would be interesting for future works to investigate the interplay between regularization and perturbation geometry in non-linent models, such as the random features model (Mei & Montanari 2022 Gerace et al.
2021 Hassani & Javanmard 2024h.
References
Urte Adomaityte, Leonardo Defilippis, Bruno Loureiro, and Gabriele Sicuro. High-dimensional robust regression under heavy-tailed data: Asymptotics and universality. arXio preprint arXiv:2309.16: 2023.
Urte Adomaityte, Gabriele Sicuro, and Picrpaolo Vivo. Classification of heavy-tailed features in high dimensions: superstatistical approach. Advances in Newral Information Processing Systems, 36, 2024.
10

---

Published in Transactions on Machine Learning Research (04/2026)
Benjamin Aubin, Florent Krzakala, Yue Lu, and Lenka Zdeborová. Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 12199-12210. Curran Associates, Inc., 2020.
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pp. 431-44111111 441. PMLR, 2020.
Derek Bean, Peter Bickel, Noureddine El Karoui, and Bin Yu. Optimal m-estimation in high-dimensional regression. Proceedings of the National Academy of Sciences, 110(36):14563 14568, 2013a.
Derek Bean, Peter J. Bickel, Noureddine El Karoui, and Bin Yu. Optimal m-ostimation in high-dimensional regression. Proceedings of the National Academy of Sciences, 110(36):14563 14568, 2013b. doi: 10.1073/ pnas. p378.43074 URL https://www pnas org/doi//an aaooi//ass/00// 10. 1073 pnas 1307845110
Adel Belouchrani, Karim Abed-Meraim, Jean-François Cardoso, and Eric Moulines. A blind source separation technique using second-order statistics. IEEE Transactions on Signal Processing, 45(2):434 444, 1997.
Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds on adversarial robust from optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Reseavch, pp. 1024 1034. PMLR, 13 18 Jul 2020.
Stephen Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2004. doi: 10.0017/600978051880444
Jean-François Cardoso and Antoine Souloumiac. Jacobi angles for simultancous diagonalization. SIAM Journal on Malris Analysis and Applications, 17(1):161 164, 1996.
Yair Carmon, Aditi Raghmmathan, Ludwig Schmidt, John C. Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Newral Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canado, pp. 11190 -1201, 2019.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Pierre Comon. Independent component analysis, new concept? Signal Processing, 36(3):287 314, 1994.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, (0(3):273 297, 1995.
Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially robust gaussian classification. In International Conference on Machine Learning, pp. 2345 2355. PMLR, 2020.
Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Lourciro, and Lenka Zdeborová. Universality laws for gaussian mixtures in generalized linear models. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 54754-54768. Curran Associates, Inc., 2023.
Li Deng. The mnist database of handwritten digit images for machine learning rescarch. IEEE Signal Processing Magazine, 29(6):141 142, 2012.
Elvis Dohmatob and Meyer Scetbon. Precise accuracy accuracy/robustiin /robustnessssss tradeoffs in regression: Case of general norms. In Forty-fost International Conference Machine Learning, 2024.
11

---

Published in Transactions on Machine Learning Research (04/2026)
David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensiooall geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, (676666)):4273 4293, 2009.
Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen. Universality of approximate message passing with semirandom matrices. The Annals of Probability, 51(5):1616-1683 2023.
Bernhard Flury. Common principal components and related multivariate models. Wiley, 1988.
Bernhard N Flury. Common principal components groups. Journal of the Ameriaan Stalistionl Associalion, 79(388):892 898, 1984.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model*. Journel of Statistical Mechanics: Theory and Experiment, 2021((2):124013, dec 2021. doi: 10.1088 11/11/12222558/888 1412-546//ccaae. /ac3ae6. 00114442-468//c33
URL https://dd
doi orgoo/g//// 10.
Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, and Lenka Zdeborová. Gaussian universality of perceptrons with random labels. Phys. Rev. E, 109:034305, Mar 2024. doi: 10.1103/ 1hysSeevE.109.044300 URL https: www.app/.......p....t........ btgg/di/11..oo 1ttp//00..10///haaeee.... 109. 034305
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. The gaussian equivalence of generative models for learning with shallow neural networks. In Joan Bruna, Jan Hesthaven, and Lenka Zdeborova (eds.), Proceedings of the 2nd Mathematical and Scientifie Machine Learning Conference, volume 145 of Proceedings of Machine Learning Research, pp. 426 471. PMLR, 16 19 html
Aug 2022a. URL https::/procceedingg http:iisss.......esseeeeees
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. The gaussian equivalence of generative models for learning with shallow neural networks. Tn Joan Bruna, Jan Hesthaven, and Lenka Zdeborova (ods.), Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, volune 145 of Proceedings of Machine Learning Research, pp. 426 471. PMLR, 16 Aug 2022b.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, Sun Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015a.
Tan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015b. URL http: //axxiv. org.:/orrror.......ooo.eooooo..e www.obgg//////ooooo/oo..oooeeese hats///11..5..5 6572
Y. Gordon. On milman's inequality and random subspaces which escape through mesh in R Joram Lindenstrauss and Vitali D. Milman (eds.), Geometric Aspects of Punctional Analysis, pp. 84 106, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. ISBN 978-3-540-39235-4.
Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1827 1836. PMLR, 2018
Hamed Hassani and Adel Javanmard. The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression. The Annals of Statistics, 52(2))441 14444,165,, 2024.
Hong Hu and Yue M. Lu. Universality laws for high-dimensional learning with random features. IEEE Transactions Information Theory, 69(3):1932-18) 1964, 2023. doi: 10.1109/TIT.2000 211.22222..276000
12

---

Published in Transactions on Machine Learning Research (04/2026)
Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Newral Networks, 13(4-5):411443) 2000.
Leon Isserlis. On a formula for the product- moment coefficient of any order of normal frequency distribution in any number of variables. Biometrika, 12(1 (2(1/2):33-133) 1918.
Adel Javanmard and Mahdi Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50(4):2127 2156, 2022.
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou (eds.), Advances in Neural Information Processing Systems 21, Proceedings of the Twenly-Second Annual Conference on Neural Information Processing Systems, Vancoweer British Columbia, Canada, December 8-11, 2008, pp. 793-800. Curran Associates, Inc., 2008.
Vladimir Koltchinskii. Rademacher penaltics and structural risk minimization. IEEE Trans. Inf. Theory, 47 (5):1902 1914, 2001.
Anders Krogh and John Hertz. A simple weight decay can improve generalization. Advances in newral information processing systems, 4, 1991.
Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advonces in Neural Information Pro- cessing Systems, volume 33, pp. 13939-13950. Curran Associates, Inc., 2020. URL https//prrooooeeiinng 10f 10
neurips.cc/pappe httpa///////p////00/////////////
pdd
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations, 2018.
Xiaoyi Mai, Zhenyu Liao, and Romain Couillet. A large scale analysis of logistic regression: Asymptotic performance and new insights. In ICASSP 2019 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3357-3361, 2019. doi:
201..883777...
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667 766, 2022.
Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova. The role of regularization in classification of high-dimensional noisy gaussian mixture. In International conference machine learning, pp.
PMTR, 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. ISBN 978-0-262-01822-8.
Andrea Montanari and Basil N. Saeed. Universality of empirical risk minimization. Tn Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4310-4312. PMLR, 02-05 Jul 2022. URL https: : 7ppoccedings. mlr,
html
Koki Okajima, Xiangming Meng, Takashi Takahashi, and Yoshiyuki Kabashima. Average case analysis lasso under ultra sparse conditions. In Francisco Ruiz, Jennifer Dy, and Jan Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 11317-11330. PMLR, 25-27 Apr 2023. URL https::/pprccediinnet mlr. ptwppp//0e/ www/20/kkaaamm22.... html
13

---

Published in Transactions on Machine Learning Research (04/2026)
Neal Parikh and Stephen Boyd. Proximal algorithms. Found. Trends Optim., 1(3))127-239, jan 2014. ISSN 2167-3888. doi: 10. 10.1551//00 /24000000300 URL
Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan. Are Gaussian data all you need? The extents and limits of universality in high-dimensional generalized lincar estimation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 27680 27708. PMLR, 23 29 Jul 2023. URL https::/ppooceddaiiin mml press/v202/peecc2233 html
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. arXiv preprint orXw:20002.07166, 2020.
relvestre-Allise Rebulli, Sven Gowal, Dan A. Calian, Florian Stimberg, Olivia Wiles, and Timothy A. Mann. Fixing data augmentation to improve adversarial robustness. CoRR, abs/2103.000 210321013, 2021. URL 01946
Leslic Rice, Eric Wong, and J. Zico Kolter. Overfitting in adversarially robust deep learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Evenl, volume 119 of Proceedings of Machine Learning Research, pp. 8093 8104. PMLR, 2020.
Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro. Deterministic equivalent and error universality of deep random features learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 30285 30320. PMLR, 23 23-29 Jul 2023. URL
.mlr. www.r.pres//eee www.pppwwsseeeeeeee v202/ http://hhhrorr2aaaaaahee html
H. S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Phys. Rev. A, 45:6056 6091, Apr 1992.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-But Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Newral Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancowver, BC, Canada, pp. 3353-3364, 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. J. Mach. Learn. Res., 19:70:1-70:57, 2018
Christian Szegedy, Wojciech Zaremba, Πlya Sutskever, Joan Bruna, Dumitru Erhan, Tan J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Bonfl, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http://arxiv, httpaaarwiv...ora/a.a. org/ hts///bb//133/ /tt///11....1.. 6199
Hugo Tabanelli, Pierre Mergny, Lenka Zdeborova, and Florent Krzakala. Computational thresholds in multi-modal learning via the spiked matrix-tensor model. arXiv preprint ar arXic:2506.02665 2025.
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Asymptotic behavior of adversarial training in binary lincar classification. IEEE Trans. Neural Netw. Learn. Syst., PP, July 2023.
Thomas Tanay and Lewis Griffin. A boundary tilting persepective on the phenomenon of adversarial examples. arXiv preprint XrX:::1608.0700 2016.
Kasimir Tanner, Matteo Vilucchio, Bruno Loureiro, and Florent Krzakala. A high dimensional statistical model for adversarial training: Geometry and trade-offs. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statisties, volume 258 of Proceedings of Machine Learning Research, pp. 1530-2536 PMLR, 03 05 May 2025. URT. htttps://proceedings. mlr. preass/225//aamer55555 http://oceednn.......eeeeeeee//e
14

---

Published in Transactions on Machine Learning Research (04/2026)
Terence Tao and Van Vu. Random matrices: Universality of local eigenvalue statistics up to the edge. Communications in Mathematical Physics, 298:549-5777 572, 2010.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. The gaussian min-max theorem in the presence of convexity, arXiv preprint arXio:1408.44883 2014.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized Linear Regression: A precise analysis of the estimation error. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Reseorch, pp. 1683 1709, Paris, France, 03-06 Jul 2015. PMLR.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions Information Theory, 64(8):5592 5628, 2018.
A.N. Tikhonov. On the solution of ill-posed problems and the method of regularization. Doklady Akademéi Nauk USSR, pp. 201-504, 1963.
Nikolaos Tsilivis, Natalie Frank, Nathan Srebro, and Julia Kempe. The price of implicit bias in adversarially robust generalization. arXiv preprint arXiv:2406. 04981, 2024.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probubility & Its Applications, 16(2):264 280, 1971.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-171-03003-4.
Matteo Vilucchio, Emanuele Troiani, Vittorio Erba, and Florent Krzakala. Asymptotic characterisation of the performance of robust linear regression in the presence of outliers. In International Conference on Artificial Intelligence and Statistics, pp. 811 819. PMLR, 2024.
Matteo Viluechio, Yatin Dandi, Matéo Pirio Rossignol, Cedric Gerbelot, and Florent Krzakala. Asymptotics non-convex generalized linear models in high-dimensions: proof of the replica formula. arXiv preprint arXiv:2502.28 20003, 2025.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, Πhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, lan Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and han Scarlett (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 36246 36263. PMLR, 2023.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a loy: Random malrix models predict how real-world neural representations generalize. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (ods.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 17-23 Jul 2022. URL htR..httss:/// htttss:/prroceedingg mlr. wwtps//ww.w..ee/e//e/eeeeeeeeeee ptwps//162/eeii22222 html
PMLR,
15

---

Published in Transactions on Machine Learning Research (04/2026)
Jiancong Xiao, Ruoyu Sun, Qi Long, and Weijie Su. Bridging the gap: Rademacher complexity in robust and standard generalization. In Shipra Agrawal and Aaron Roth (eds.), The Thirly Seventh Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pp. 5074-5075. PMLR, 2024.
Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and higher-order scalings for dot-product kernel regression. Advances in Newral Information Processing Systems, 35:4558 4570, 2022.
Dong Yin, Kannan Ramchandran, and Peter L. Bartlett. Rademacher complexity for adversarially robust. generalization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (cds.), Proceedings of the 36th Inter- national Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Reseorch, pp. 7085-7094, PMLR, 2019.
Runtian Zhai, Tianle Cai, Di He, Chen Dan, Kun He, John Hoperoft, and Liwei Wang. Adversarially robust. generalization just requires more unlabeled data. arXiv preprint Xr: 1906.00555 2019.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp- 7472 7482. PMLR, 2019.
Andy Zou, Zifan Wang, J. Zico Kolter, and Matt Fredrikson. Universal and transferable adversarial attacks on aligned language models. CoRR, abs/2307.15043 2023.
16

---

Published in Transactions on Machine Learning Research (04/2026)
A Further related Work
Exact asymptotics:
Our results on the exact asymptotics of adversarial training build on an established
body of literalure that spans high-dimensional probability (Thrampoulidis el al. 2014
2015 Taheri et al.
2023), statistical physics (Mignacco et al. 2020
Gerace et al.) 2021 Bordelon et al.) 2020 Loureiro et al. 2021
Okafima ct al. 2023
Adomaityte ct al. 2024
2023; Tabanelli ct al.
2025 and random matrix theory [Bean
ct al. 2013b Mai et al. 2019: Liao et al. 2020;
Mei & Montanari 2022 Xiao et al., 2022 Schröder et al.
2.23). Our study is also motivated by recent efforts to understand Gaussian universality (Goldt et al. 2022a
Montanari & Saeed 2022: Dandi et al.) 2023). These works suggest that simple models for the covariates have broad scope in the context of high-dimenssonall linear estimation, often mirroring real-world datasets. From technical perspective, this phenomenon arises due to strong concentration properties in the high-dimensional regime, which imply certain universality propertics of the generalization error with respect
to the covariate distribution (Tao & Vu 2010 Donoho & Tanner 2009
Wei et al. 2022 Dudeja et al. 2023
Adversarial training: Robust empirical risk minimization, i.c. adversarial training, was first introducod
for computer vision applications [Goodfellow et al.) 2015a Madry et al. 2018). A large body of work is
devoted to the study of applied methods for improving its computational (Shafahi et al.) 2019 Rice et al.j 2020) and statistical (Zhai et al.) 2019 Chen et al.) 2021 Wang et al.) 2023) properties. Theoretically, robust
training has been considered before in both the case of Gaussian mixture models (Bhagoji et al.) 2019 Dan
et al. 2020 Javanmard & Soltanolkotabi 2022) and linear regression (Raghunathan et al.) 2020 Taheri et al.
2023
Dohmatob & Scetbon 2024).
Statistical learning theory: The role of regularization in statistical inference traces back to the work of Tikhonovv (1963) and plays central role in statistical learning theory, directly inspiring general inductive principles such as Structural Risk Minimization [Vapnik] 1998) and practical methods that realize this principle, such as SVMs (Cortes & Vapuik 1995). Uniform convergence bounds, quantities that upper bound the difference between empirical and expected risk of any predictor uniformly inside a hypothesis class, were originally stated as a function of the VC dimension of the class (Vapnik & Chervonenkis 1971). The Rademacher complexity of the class (Koltchinskii (2001) is known to typically provide finer guarantees (Kkkade et al. 2008). Several recent papers derive such results in the context of adversarially robust classification for
linear predictors and neural networks (Yin et al. 2019 Awasthi et al. 2020 Xiao et al. 2024
B Sharp High-Dimensional Asymptotics
3.7 3. 15 and 3.16 we provide in Table D comprehensive overview of the notation used throughout the paper and particularly in these proofs. The table includes both the basic notation for the problem setup and the more specialized symbols that appear in the asymptotic analysis. We have organized the symbols thematically, starting from the fundamental quantities (n, d, a) and progressing to the more complex asymptotic statistics (m", 9", P*). This reference should help readers track the various quantities as they appear in the detailed derivations that follow.
Before delving into the technical proofs of Theorems 3.5
We now proceed with the proofs. The first theorem that will be crucial in our subsequent analysis is the Convex Gaussian MinMax Theorem (CGMT), a powerful tool in high-dimensional probability theory. The CGMT provides a connection between two seemingly unrelated optimization problems under Gaussian conditioning. Essentially, it allows us to study the properties of a complex primary optimization problem (PO) by examining a simpler auxiliary optimization problem (AO). This theorem is particularly valuable in our context as it enables us to transform intricate high-dimensional problems into more tractable lower-dimensional equivalents,
significantly simplifying analysis and leading to Theorems 3.7 and 3.16
The CGMT states that under certain conditions, the probabilistic behavior of the primary optimization problem involving a Gaussian matrix is upper and lower bounded by the behavior of an auxiliary problem involving only Gaussian vectors. This powerful result allows us to derive tight probability bounds and asymptotic predictions for the high-dimensional estimation problems considered in this manuscript.
We state the theorem in full generality.
17

---

Published in Transactions on Machine Learning Research (04/2026)
Symbol
Description
Number of training samples
d
Input dimension
a n/d
Sample complexity (ratio of samples to dimension)
E Rd
Input features for sample
9: E {-1, +1}
Binary label for sample i Teacher (true) weight vector Learned weight vector (student)) Adversarial perturbation budget
w. E Rd
á Rd
|l llp
l norm, defined as | = ( |2,11,1 1/)p/// Dual exponent of p, satisfying 1/p 1/p" Robust generalization error Standard generalization error
p
Grob((i)
E Egen (10)
Eudd (w)
Boundary error (difference between robust and standard error) Regularization strength parameter Regularization function
A
F(w)
g(-)
Surrogate loss function
P Pout
Output channel (conditional probability of labels) Input distribution
Pin
P
Prior distribution on teacher weights
Es
Matrix defiming Mahalanobis norm for perturbations
En
Matrix defining Mahalanobis norm for regularization
m"
Asymptotic overlap between teacher and student weights Asymptotic squared l norm of student weights Asymptotic dual norm of student weights
q''
p*
Table 1: Notation Table
Theorem B.1 (CGMT Gordon (1988): Thrampoulidis
(2014)). Let GE Rmxx be an i.i.d. standard normal matriz and g E R. h R" two i.i.d. standard normal vectors independent of another. Let Sw, Sn be two compact sets such that S C Rhn and Sn C R Consider the two following oplimization problems for any continuous vp on Sw x Su
C(G)
min max u Gw + ((w, u)
(21)
weSw WESn
C(g. h) == min max |/l|2g T u + ||u||2hh T w + (hw, u)
(22)
weS. WES,
Then the following hold
1. For all c R we have
P(C(G) <) S 2)(C(g, s)
(23)
2. Further assume that Sw and Su are conver sets, v conver-concase on Sw x Su. Then for all c E R
P(C(G) > c) 2F c)
(24)
In porlicular for all E R 1> 0 we have P[[[([G) - n > 1) < 2P((C(g h) /1200 1).
In our analysis, we will employ version of the CGMT applicd to general class of generalizod linear models, as proved by Loureiro et al. (2021).
B.1 Notations and Definitions
In this paper, we extensively employ the concepts of Moreau envelopes and proximal operators, pivotal elements in convex analysis frequently encountered in recent. works high-dimensional asymptotic of convex
18

---

Published in Transactions on Machine Learning Research (04/2026)
problems (Boyd & Vandenberghe 2004 Parikh & Boyd 2014]. For in-depth analysis of their properties, we refer the reader to the cited literature. Here, we briefly outline their definition and the main properties for context.
Definition B.2 (Moreau Envelope). Given a convex function f :: - IR we define its Moreau envelope as being
(Vsc)(w min
2V - w112 f(xx)
(25)
where the Moreau envelope can be seen as a function Mvs() R -
Definition B.3 (Proximal Operator). Given a convex function f : - R we define its Proximal operator 88 being
Prsc)(w) = arg min
| wl12 + f(z) 2V
(26)
where the Proximal operator can be seen as function Pv R R
Thcorem B.4 (Gradient of Morcau Envelope (Thrampoulidis al. 2018). Lemma D1). Given a conver
function f : R - R, we denote its Moreau envelope by (v)()()) and its Prozimal operator Pv)o())
Then, have:
VuMys((()) 1 - (W-Prrss
(27)
Additionally we will use the following two properties
(w)(+ = MM - u), Pvs(+t)(W) u + Prscs(w++ + u)
(28)
which are easy to show from change of variables inside the minimization.
Definition B.5 (Dual of Number). We define the the dual of number 2 0 as being at the only number such that 1/4 1/4" 1.
B.2 Assumptions and Preliminary Discussion
We restate here all the assumptions that we make for the problem. Assumption B.6 (Estimation from the dataset). Given a dataset D made of pairs of input outputs [( (.)) where æ, Rd and y: IR estimate the vector w as being
y1 w (xt + o.)
E arg min weRd
max |6
+ AF(w),
(29)
Vd
where g IR + R a convex non-increasing function, À E oo) and F: Rd + R a convex regularization function.
Assumption B.7 (Higg--Dimensional Limit). We consider the proportional high-dimenniooall regime where both the number of training data and input dimension n, d + a fixed ratio == n/a.
Assumption B.8 (Regularization functions and Attack Norms considered). We consider consider two scttings for the perturbation norm |I.| and the regularization function For the first one, the regularization function and the atlack norm ép norms, defined
1/p
|
Σ
(30)
for p o0). We will refer the index of the regularization function as r and to the index of the norm inside the inner maximization as p and define p* the dual number of p (definition B.5).
For the second case, both the regularization function and the attack norm Mahalanobis norms, defined
||
Var Ex.
(31)
19

---

Published in Transactions on Machine Learning Research (04/2026)
for positive definite matrix E. We refer to the index of the matrix of the regularization function Ew and to the matrix of the norm inside the inner maximization as Eg. In this case, we define r=== = 2 (in order to unify notations) and we will thus talk about p* = r
This setting considers most of the losses used in machine learning setups for binary classification, e.g. logistic, hinge, exponential losses. We additionally remark that with the given choice of regularization the whole cost. function coercive.
Assumption B.9 (Scaling of Adversarial Norm Constraint). We suppose that the value of scales with the dimension d such that <Vd) Oa(1).
Assumption B.10 (Data Distribution). We consider two cases of data distribution. Both of them will rely on the following general generative process. For each i E [n], the covariates æ, E R are drawn i.i.d from a data distribution (z) Then, the corresponding Yi is sampled independently from the conditional distribution Pout More succinetly, one can write the data distribution for a given pair (æz, y) as
(w) (W... (w..2) x) Vd
P(x, u) = / doou J
Pm (..
(32)
The target weight vector w, E Rd is drawn from a prior probability distribution Pw.
Our two cases differentiate in the following way. For the first case, we consider Pm(()) (0, Ida) and Pw which is separable, ic. (ww() I Pw (w;) for a distribution Pw in R with finite variance Var(P.)) - p p co.
For the second case, we consider Pn(()) 2N Ex) and (w) (O,
Assumption B.11 (Limiting Convergence of Spectral Values). We suppose that Σ. Es. Eg. To.20 En are
simultaneously diagonalisable. We call Σg = S diag(w;)S, Eg = S diag(G.SS and En = S diag(w,)S. We define f = SE, w./vP We assume that the empirical distributions of eigenvalues and the entries of jointly converge to a probability distribution μ as
5 -0) w)D(s= - 5) - ww) + p.
(33)
B.3 Problem Simplification
Recall that we start from the following oplimization problem:
w T (xx + 6.) + \F(wn)
Φ = min
max 11
(34)
weRd
Vd
where F(-) is convex regularization function and 9(-) is non-increasing loss function. The non-increasing property of allows us to simplify the inner maximization, leading to equivalent formulat
T. = min
Eg
Cow U1
az - w
vā
E (llllll)) + AF(wr)
(35)
weRd
To facilitate our analysis, we introduce auxiliary variables p= || /d and P (the Lagrange parameter relative to this variable), which allow us to decouple the norm constraints. This leads to min-max formulation
T x;
t = min max Eg
0 1=1
y1
w
E
./P) + xF(w) + P|| apP,
(36)
WERd
Vd
V
where we switched the value of s for its value without the scaling in d. This reformulation is what will allow us to apply the CGMT in subsequent steps.
It's worth noting the significance of the scaling for e as detailed in Assumption B.9 In the high-dimensional limit d oo, it's essential that all terms in & exhibit the same scaling with respect to d. This careful scaling ensures that asymptotic analysis remains well-behaved and meaningful in the high-dimensional regime.
20

---

Published in Transactions on Machine Learning Research (04/2026)
B.4 Scalarization and Application of CGMT
To facilitate our analysis, we further introduce effective regularization and loss functions, and g. respectively. These functions are defined
& k/P). F(w) = F(w) + Plwllp- gly. 2) = Σ 9 Uizi - Vdd
(37)
A crucial step in analysis involves inverting the order of the min-max optimization. We can justify this operation by considering the minimization with respect to w R& at fixed values of P and P. This reordering is valid due to the convexity of our original problem. Specifically, the objective function is convex in w and concave in P and P, and the constraiin sets are convex. Under these conditions, we apply Sion's minimax theorem, which guarantees the existence of a saddle point and allows us to interchange the order of minimization and maximization without affecting the optimal value.
This reformulation enables us to directly apply (Loureiro et al., 2021 Lemma 11). This lemma represents a meticulous application of Theorem B.1 to scenarios involving non-separable convex regularization and loss functions. The result is lower-dinensional equivalent of our original high-dimensional minimization problem that represent the limiting behavior of the solution of the high-dimensional problem.
Consoquently, our analysis now focuses on a low-dimensional functional, which takes the form
max P. P.N.T..
min
KTI
aCy- 11 "1"p+
1172
L-
PP
(38)
2
2T2
2
where we have restored the min max order of the problem.
In this expression, 9 and h are independent Gaussian vectors with i.i.d. standard normal components, The terms Lg and C. represent the scaled averages of Morcau Envelopes (eq. (25)
Lg
E M
+ 1/h)
(39)
n
Vp
7 [(g + vw.)
C, E
M
(40)
(()
The extremization problem in eq. (38 is related to the original optimization problem eq. 134 as it can be
thought as the leading part in the limit n, - oc.
This dimensional reduction is the step that allows to study the asymptotic propertics of our original high-dimensional problem through more tractable low-dimensional optimization and thus have in the end a low dimensional set of equations to study.
It's important to note that the optimization problem o is still implicitly defined in terms the dimension d and, consequently, as function of the sample size n. We introduce two variables
Weg = P ,
(v't k (v*t+**))
Zeq = P Piol.n)
m ( # 1/
(41)
(()
3 r()
where (n",, T3, p* P* frr
x* D² m Ti
are the extremizer points of +.
Building upon (Loureiro et al.
2021
Theorem 5), we establish convergence result. Let t be optimal
solution of the problem defined in eq. (34h, and let = 1/2 _Xxx For any Lipschitz function yP Rd - R, and
any separable, pseudo-Lipschitz function 122 R" R, there exist constants e, C, >>00 0 such that
P
Φ
w
E
Φ1
Wea
2 6
< e
C
ene
2
(42)
à
Zeq
-enet
d2
E
Φ2
2
5
Vn
Vn
2
21

---

Published in Transactions on Machine Learning Research (04/2026)
It demonstrates that the limiting values of any function depending w and can be computed by taking the expectation of the same function evaluated at Weq Zeq, respectively. This convergence property allows us to translate results from our low-dimensional proxy problem back to the original high-dimensional setting with high probability.
B.5 Derivation of Saddle Point equations
We now want to show that extrenniigg the values of m, 1J, TI, P. P, M, 72, K. lead to the optimal value & of eq. (88 We are going to directly derive the saddle point equations and then argue that in the high-dinensional limit they become exactly the ones reported the main text.
We obtain the first set of derivatives that depend only the loss function and the channel part by taking the derivatives with respect to m, 77 Tı, to obatin
0
m h
$ )
(yp (vpstna))
V/
E
dm
nT1
npp
vp
0
(vps ( mbab
h TT P (
72
1)
Ōh
T1
T1
(43)
0
T1
a
E
S + 1/h P p=)(:0)
+ 1/
2
2
n
vP
vP
0
P
PpE
M M
m
1
0P
By taking the derivatives with respect to the remaining variables K, T2, P we obtain a set of equations depending on regularization and prior over the teacher weights
0
E
g
P
(vw, + kg)
0x
r()
72
0
w W.P.
!] (ww + kg))
Ov
T2
1 "g
11 (DW, + kg) - P
(vW + rg
)
"
(v2p - my KT. +
1JT2
+
T2 m
0r
2d 17
((-)
2T²
2
2n p
d p
M r())
7 (ng + vvc.)
ap
(44)
The rewriting of these equations the desired form in Theorems 3.7 and 3.16 follows from the same considerations as in (Loureiro et al. 2021 Appendix C.2).
To perform this rewriting the first ingredient we need is the following change of variables
m²
m. +- m,
-- 17
V
P+P. P,
(45)
V. 72
2
V.
P+P.
ant the use of Isscrlis' theorem Isscrlis present.
1918 to simplify the expectation where Gaussian 9, vectors are
B.5.1 Rewriting of the Channel Saddle Points
To obtain specifically the form implied in the main text we introduce
Zoly, w, V) =
dx
( 6 (x-))(x))
(e-w))
(46)
V
22

---

Published in Transactions on Machine Learning Research (04/2026)
where this definition is equivalent the one presented in eq. (10.. The function Zu can be interpreted as partition function of the conditional distribution Pout and contains all of the information about the label generating process.
B.5.2 Specialization of Prior Saddle Points for lp norms
In the case lp norms, we can leverage the separable nature of the regularization to simplify our equations. The key insight here is that the proximal operator of separable regularization is itself separable. This property allows us to treat each dimension independently, leading to significant simplification of our high-dimensional problem.
First, due to the separability, all terms depending on the proximal of either 9 simplify the n d at the denominator. This cancellation is crucial it eliminates the explicit dependence on the problem dimension, allowing us to derive dimension-independene equations.
Next, we introduce
Aw( dw Pw (w)e 2
(47)
which, in turn, leads in the form shown in eq. (9).
B.5.3 Specialization of Prior Saddle Points for Mahalanobis norms
In the case of Mahalanobis norm, the form of the proximal of the effective regularization function is specifically
1 1= w112
1
2PE5 22E + +
Vr(-) (w) arg min A= Ew Pz
Esz
(48)
2V
By substituting this explicit form into the equations from eq. that still depends on the dimension
44). we obtain a set of simplified equations
m
tr
D 000,
Ex (EEw PES V.E)
1
m i 0,0 E. + + Ex NEw PPE + V22) -2
(49)
1
V
tr
En N.W +ES VE
P ( 000
1
En + + Es (EE PE5 + VE
The final step involves taking the high-dimensional limit of these equations. Here, we leverage our assumptions about the trace of the relevant matrices to further simplify the expressions that they only depend on the limiting distribution from Assumption B.11
Specifically, the assumptions on the trace allow us to replace certain higl-dimensional operations with scalar quantities, effectively reducing the dimensionality our problem. This dimensionality reduction is crucial for obtaining tractable equations the high-dimensional limit. Tn the end we obtain the equations in eq. 114
B.6 Different channels and Prior functions
We want to show how the different functions 2o, Zn look like for some choices of output channel and prior in the data model. For the case of a probit output channel, we have by direct calculation
Zo(y,w, w. V) = erfe (-V 22VV + +22)
(-V
w
(50)
23

---

Published in Transactions on Machine Learning Research (04/2026)
For the case of channel of the form y sign(z) v Ar one has that
+ +, (-1, 1 ( (1- erf
Zo(y, = Nr (1,A4) [+ erf
(51)
V2VV
V2V
For the choices of the prior over the teacher weights, we have for Gaussian prior that
e /2(411)
Zw( VA+1
(52)
or for sparse binary weights
Aw) p - (1-p) cosh(>)
(53)
B.7 Error Metrics
To derive the form of the generalization the procedure the same detailed in Aubin et al.
20200)
in Mignacco et al. 2020 Appendix A). We report here the final form being
E Egen
1
arccos
m
(54)
V(- T3)g
To derive the form for the boundary proceed in the same way (Geaace et al. and obtain
2021
Appendix D)
"VPiva
e 222
m
Ennd
erfe
dA
(55)
2(p +
v V2xx
We also interested in the average teacher margin defined
E y æ
(56)
which can be expressed as a function of the solutions of the saddle point equations as follows:
(57)
B.8 Asymptotic in the low sample complexity regime
This section examines the asymptotic behavior of our model in the regime of low sample complexity, Our analysis is motivated by numerical observations of the overlaps m, q: P, V in the small regime, illustrated in Figure 3
Based on these observations, we propose a general scaling ansatz for the overlap parameters (solutions of the equations presented in Theorems 3.7 and 3.16 as functions of the sample complexity a
m mga 6m
q" %
V
V
p P
(58)
where the values with zero subscript do not depend on and the exponents are all positive. We focus the noiseless case = 0.
We are interested in the expansion of the generalization error and the boundary error, keeping only the most relovant terms in the limit a + 0+. For the generalization error we have
E7 Fyen
1
arccos
my
Am
#g + of a BB12)
(59)
Vpq
24

---

Published in Transactions on Machine Learning Research (04/2026)
7
r=
3
10a
aaa 1.01
10a
0 0.34
9 1.01
① ~ 0.80
P ~ 0.08
P ~
P ~ a.
10a
V 0.47
V
V
Ovorlaps
mg vi ~ 0.01
v7 0-50
VT 0.50
m0
10a
100
10
10-2
10-2
100
10-2
100
10
Figure 3: Scaling of the overlap parameters in the low sample complexity regime for p 0o, 6 0.3, p
and À 10 The numbers presented in the legends are the linear fit in log-log scale of the dashed part.
and for the boundary error a similar expansion leads to
P
Endd
erfc
V/a"
dv
(60)
22(p (m )2²))//²)
2
Eg VP a /p/D" -bul2
Oo
+
a
20p/0 Am 28 + o(a")
(61)
2x
where x -, 20p + 8m 25,)
Numerical simulations reveal clear distinction in the low regime between cases where the regularization parameter r r= p' and r r p". Figure illustrates this difference for a fixed regularization paramcter X. We identify two scenarios that characterize the behavior of the leading term in the boundary error expansion
When 6p/p² > 2 This occurs when p² =r= = 1. In this case, the leading term has positive exponent, causing it to vanish as a + 0.
When óp/p' = 6,/2 This scenario arises when r # p' = 1. Here, the exponent of the leading term becomos zero, resulting a constant term independent of a.
Notably, in all cases we've examined, the second terms in both the generalization error and boundary error expansions consistently approach zero the limit of low sample complexity.
C Rademacher Complexity Analysis
This appendix contains detailed proofs of the remaining results presented in the paper. For the reader's convenience, we restate each statement before its proof.
Proposition C.1. Let Lete, O. Consider a sample S {(21 81), .... (In, vn)), and let H. be the hypothesis
class defined in eq. 15
Then, it holds:
As (Tb.) < max
|x, S.sll-Wp.
+
E
sup
w
(62)
vE[n]
on
2/n
WW
where -11-11+:1 +1+ denote the dual norm of 11-11 respectively.
25

---

Published in Transactions on Machine Learning Research (04/2026)
Proof. We have:
(g{)))) = Eg
sup
0i
min
(x1((x)
ni bEH
|
n
Eg
sup
J.lii (w, x2a - =1|20|1+
(Def. of dual norm)
1i hEH- i=1
(63)
a
n1 Eo, 1|0||-
< Eg
sup n he
Jilii (w, x²)
Egg
sup
(Subadditivity of supremum)
n2 heH
= (H+)
Eg
0
sup
[
(Symmetry of σ))
n
wor( (
For the first term, i.e. the "clean" Radenacher Complexity, plug in (Kkkade et al. 2008 Theorem 1). By Jensen's 's inequality, we have for the second term:
1
1
Eg
E,
(64)
Vn
i=1
which concludes the proof.
Corollary C.2. Let 0. Then:
max ||x:||212
EW/ +
Rs (P(p--))) (g)
Amil (Es).
(65)
2/n
Proof. Leveraging Proposition 4.2 the first term the RHS follows from the fact that the squared le norm is 1-strongly convex (w.r.l itself). For the second term, we have that the dual norm of ||-1| given by
|1: 1|1 =Vw0, 'o))) Then, holds:
sup
|1lm
sup wil w w
|w Σ,
W2
sup
||20 ||
(66)
W2y Amax 1)
where the last equality follows from Courant Fischer Weyl's max principle.
Corollary C.3. Let En. = Ed avv. and Es = Ed A.V,V,, with v; E TRdd being orthonormal. Then:
WA maXie(n)
|
x
EWA
Rs 13)
+
max (E(d] X
(67)
Vn
2/n
26

---

Published in Transactions on Machine Learning Research (04/2026)
Proof. For the worst-case part, have:
sup willw|ls... SW
||
WA
sup
V (w0, 2z' w0)
w:||w||E
WA
sup
A (w, vs)2
w:|l E.
WA
sup w: Ew
ai (w, vi)²
(68)
WA A
sup
max rE(d]
ai (w, vz)²
ur: we|| [||l Fell
X
A,
WA
sup wi|lw||AS1
max kEld]
20 -لاا
Way
max rE|d] ag
max
a
On the other hand, for w yay v where j E arg max
it | = and also ||
|maxieed] A-1 so the above bound is tight. a; Remark C.4. Note that the previous result, and in particular inequality 68 implies that in order most effectively control the robust error, we better select Ew Σ3¹ To see this, consider particular ground truth w* E Rdd and let H be the smallest hypothesis class that contains hypothesis w for a given geomelry Ew, that is: H = fx + (w.x) ||w//E.. I
||| ||}- Then, from 68
we have:
< !| |ل
1 Xja;
2/
max
&E|d]
2/n
E
(69)
where equality holds for all w if and only if Ew x Σz¹ In particular, if Ew = Σz¹ then the above term becomes 2 || ||ll" ر and cannot be improved further without excluding from the class H.
C.1 Worst-case Rademacher complexity for é, norms
Awasthi et al. 2020) provides the following bound on the worst-case Rademacher complexity of linear hypothesis classes constrained in their L, norm.
Theorem C.5. Theorem 4 in Awasthi et al. 2020 Let e > and p,r 2 1. Define Hi = {x + (w,x) :
||w/|r 1). Then, it holds:
Rs s Rs(H) + max(d" 1- - 1)
(70)
2/n
The bound above suggests regularizing the weights in the l, norm, r= _ for effectively controlling the estimation error of the class.
D Parameter Exploration
This section presents the experimental details for all the figures in the main text and explore the model parameters greater detail. For implementation details of our numerical procedures, plcase refer Appendix
D.1 Settings for Main Text Figures
All figures the main text utilize the logistic loss function, defined as g(x) log(1 + exp(-x)). Below, we detail the specific parameters for each figure.
27

---

Published in Transactions on Machine Learning Research (04/2026)
p
2
3
0.40
0.550
== 0.30
0.0
0.525
225
== 0.20
Ereb
Egob
0.500
== 0.20
0.475
0.10
0.45
0.450
0.01
0.01
0.425
1.0 1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
r
T
Figure 4: Robust error as a function of the regularization order r for two different p". By increasing the value of & we have that the optimal value r*t gets close to p".
= 0.1
E = 0.3
Exoby Egen
0.6
Egen
Eyob
Frob/ Egen
0.6
Eggn
Froh
0.4
0.4
10-1-
10
r=1
Ebad
Ebnd
10
==3
10
10
10a
10
10"
a=n/d
Q= n/d
Figure Robust error, gencralization error and boundary error for different choices regularization geometry as function of the sample complexity a. We see that the value of the errors increases with
Figure (Left) We optimize the regularization parameter À for each curve. Parameters: = 0.2, noiseless regime (r 0). Data points represent averages over 10 distinct data realizations with dimension d = 1000, varying sample size n to adjust a. Error bars indicate one standard deviation from the mean.
Figure
(Right) Generated in the noiseless case (7 0) with optimal regularization parameter A. We optimize robust error for regularizations 2 and independently, then compute their difference.
Figure
(Left) We employ a Strong Weak Feature Model (SWFM) as defined in Tanner et al. 2025 This model implements block structure on covariances (Ex; Es, Eg. and Ew,, with block sizes relative dimension denoted by Φ; for block i. We use equal-sized feature blocks, totaling d 1000. All matrices are block diagonal, with each block being diagonal. The values for each matrix are follows
Σx
Σg
Case En Es
Case lg
Case Enp Eg
First Block
1
1
2.5
Second Block
1
2.5
2.5
1
All matrices are trace-normalized, with E values as specified in the figure. Again error bars indicate the deviation from the mean.
Figure (Right) We optimize the regularization parameter À in the noiseless case (T = 0), with = 1. The inset is generated by conducting r sweeps for 10 distinct & values. Each sweep compriscs 50 points, with the minimum determined using argmnn...
28

---

Published in Transactions on Machine Learning Research (04/2026)
Optimized X
A 10
0.52
2-m 0:30
0.325
L15
0:31
0.500
Eyeb
0.20
Erob
0.475
0.48
0,450
0.05
0.46
0.01
0.425
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
Figure 6: Robust gencralization error as a function of regularization order r for fixed versus optimized regularization strength A. The comparison illustrates that the impact of optimization does not change qualitatively the behavior of the optimal regularization geometry r" as increases.
MNIST Ovsl, 1.0, x 10-3
MNIST Ovsl, & = 2.0, X = 10-3
Egen
0.0125
Egon
Eyab
Ero
0.0100
r
0.008
r =
0.0075
7=
0.006
r=
0.0050
0.004
0.002
0.0025
10
10P
10a
n/d
n/d
Figure 7: Generalization error and robust generalization error as function of sample complexity a for MNTST binary classification (0 vs 1) with for adversarial training. The optimal regularization is = (matching the attack norm), consistent with theoretical predictions from Section 5 Despite the non- non-Gaussian data distribution, the empirical results align closely with high-dimenssonal asymptotic theory.
D.2 Additional Parameter Exploration and Dataset Choice
We now present some additional exploration of the model in some different regimes.
Figure
These figures display thcoretical results for attack perturbations constrained by l (Left) and 6a/2 (Right) norms. We vary e as shown and use the noiseless regime (r = 0). Parameters: a = 0.1, optimal A. Each sweep comprises 50 points, with minima determined using np. argmin. Points on the curves indicate the minimum for each value.
Figure
This figure illustrates generalization metrics as function of a for various regularization geometrics. We present results for two allack strengths: & = 0.1 (Left) and e = 0.3 (Right). Both use optimal X values. This figure can be compared to Figure (Left)..
Figure Both panels show robust generalization error versus regularization geometry r, with a 0.1. The right panel optimizes regularization strength X, while the left uses fixed value À 14
Figure Empirical validation on MNIST binary classification (digits 0 vs 1). We train a lincar classifier via too adversarial training eqs. 6 and 7 where MNIST images are flattened to 2p E 784 and normalized element-wise wise to [0, 1 (.c. xe x,,/255). Labels are mapped to ya E (=1}. The ridge 10-3 across all experiments. We evaluate the population adversarial error eq. 2 and standard generalization error eq. 3 via the empirical version of the expectation
parameter fixed
with Dhest 1000 samples from the test. set.. Results are shown function of the sample complexity
29

---

Published in Transactions on Machine Learning Research (04/2026)
0.54
a 1,00
d = 1,
0.52
o = 1,
6 1,0
Brub
0.50
d 1, d = 2,
0.48
o = 3,00 0 =
4,0
0.46
5,0
10-3
a = n/d
Figure 8: Robust generalization error function of sample complexity for the Mahalanobis model defined in Section 3.2 and sweep in different regularization matrices. We see that interpolating from the value of Ew = Eg to Ew Eg² decreases the value of the error.
ratio a = n/d where d = 784 kept fixed. Two atlack budgets are considered: & = 1.0 (Left) and E = 2.0 (Right). We compare different regularization norms {1, oo) to identify the optimal choice matching the attack geometry.
Figure
We study the behaviour of the robust generalization error for more choices of regularization matrix Ew for the model defined in Section 3.2 This model implements a block structure on all covariances (Ez, Eg: Eg, and Ew.) We use two equal-sized feature blocks. All matrices are block diagonal, with each block being diagonal. The values for each matrix are as follows
Σx
Σ8
Eg
First Block
1
1
Second Block
1
5
All matrices are trace-normalized, with e values as specified the figure. We vary the values of af and au and keep À -1033, 0.1 fixed.
E Numerical Details
The self-consistent equations from Theorems 3.7 and 3.16 are wrilten in a way amenable to be solved via fixed-point iteration. Starting from random initialization, iterate through both the hat and non-hat variable equations until the maximum absolute difference between the order parameters in two successive iterations falls below tolerance of 10-5.
To speed-up convergence we use a damping scheme, updating each order parameter at iteration i, designated as Fj, using x; == z,μ + -; -), with as the damping parameter.
Once convergence achieved for fixed X, hyper-parameters are optimized using a gradient-free numerical minimization procedure for a one dimensional minimization.
For each iteration, evaluate the proximal operator numerically using SciPy's (Virtanen et al. 2020 Brent's algorithm for root finding (scipy optimize www.miieeeeeeeeeeeeeemme sanimize_scalarr. The numerical integration is handled with SciPy's quad method (scipy. inr.iiatttetee quad), which provides adaptive quadrature of a given function over specified interval. These numerical techniques allow us to evaluate the equations and perform the necessary integrations with the desired accuracy.
Rogarding the computer hardware all the experiments have been run on consumer grade hardware, specifically MacStudio M2 Ultra 2022, and none of the run took more than I day of CPU time.
30


Reviews:
[{"review_id": "QpEUgKNfUO", "reviewer": "Reviewer_jnAD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript studies the binary classification problem under Robust ERM, with a particular focus on the effect of regularization. The authors consider two approaches: (i) under Gaussian covariates and a generative assumption, they derive precise standard and robust generalization risk curves for $L_p$ and Mahalanobis norm perturbations; (ii) they derive robust generalization bounds using uniform convergence argument and Rademacher complexity analysis for different norm geometries. They also conduct experiments to validate their theoretical results.\n\n**Strengths:**\n\n* The precise derivations in the Gaussian setting provide insight into the effect of regularization, which may generalize to a broader class of distributions via universality. In this sense, the results are interesting.\n\n**Weaknesses:**\n\n* Although the use of Gaussian data is justified in the paper through universality results from the literature, I could not find experiments beyond the Gaussian case for the asymptotic risk (please let me know if I am missing something). The authors could study more general sub-Gaussian covariates to empirically assess when universality holds or fails.\n* The precise results, as they stand in the manuscript, are difficult to interpret: the effect of the regularization norm and strength is not clearly visible, and this aspect is not analyzed by the authors either. For example, For example, can the behavior observed in Figure 2 (right) be derived from the self-consistent equations?\n* The precise asymptotic analysis and the Rademacher complexity–based bounds feel more complementary than connected. What is the conceptual connection between these two sections? For example, can we show (or disprove) the tightness of the uniform convergence bound through the precise asymptotic analysis?", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is primarily theoretical, and the theorems are consistent with the experimental results. I partially reviewed the proofs, and the results appear to be correct.", "audience_yn": "Yes", "audience_explanation": "See the \"Strengths\" part above", "requested_changes": "Please address the Weaknesses part above.", "broader_impact_concerns": "NA", "additional_comments": "Some minor comments:\n* Page 5, third line from the end: convariates -> covariates.\n* Page 8, second line: Proposition -> proposition.\n\n*As a final question*, what happens if the perturbations at training and test time are different? Does the analysis in the paper provide insight into how a mismatch between perturbations affects robust generalization? I would appreciate further comments on this.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RrsdC9cWyc", "reviewer": "Reviewer_513z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a theoretical analysis of the statistical learning error of adversarial empirical risk minimization for high-dimensional linear classification problems. The authors mainly consider robust empirical risk minimization (RERM) under the proportional limit regime. They first derive the PDEs satisfied by the exact asymptotics under both the $L_p$ norm and the Mahalanobis norm. Then, using Rademacher complexity, they derive analytic formulas for upper bounds on the generalization error. Based on these upper bounds, they propose using the inverse of the variance of the predictor in the Mahalanobis norm. They further provide experiments to justify the theoretical claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical results are presented clearly without significant issues. All bounds are stated with explicit coefficient factors, making the claims trustworthy. The experimental settings are well designed, with complete details provided in the appendix.", "audience_yn": "Yes", "audience_explanation": "On the theory side, it gives an attempt to derive the exact asymptotic characterization of the RERM across several attack and regularization norms, together with a complementary uniform-convergence/Rademacher-complexity analysis. Although the current results do not fully close the story, the framework feels like a clean base for researchers who want to push this direction further. Overall, it is written clearly and reads as an incremental but useful contribution that can support future extensions and discussion.", "requested_changes": "I suggest that the authors reconsider the role of the exact asymptotics results in the paper. As they stand, the results are incomplete, and most of the intuitive insights of choice of regularizations come from the Rademacher-complexity–based upper bounds. The authors should rethink and position the exact asymptotic analysis in a more appropriate way. At present, these results appear distracting from the main story. It may be worth adding more discussion of the Rademacher-complexity bounds or including additional experimental settings. Alternatively, is it possible that the exact asymptotics provide additional information that would be missed if one focuses only on Rademacher complexity?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6yi0xivQh4", "reviewer": "Reviewer_rjdr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary** \n\nThis paper provides an analysis of how different regularization schemes in adversarial training impact both standard and robust generalization. Specifically, for model selection via regularization in Robust Empirical Risk Minimization (RERM), this work investigates how the geometries of the regularization (defined by the norm $||\\cdot||$) and admissible perturbations interact to determine the robust generalization error. \n\nThe theoretical analysis is done in the high-dimensional proportional limit, i.e., when both the input dimension ($d$) and the number of training samples ($n$) diverge to infinity while maintaining a fixed ratio $\\alpha = n/d$. Within this regime, the authors focus on binary classification using generalized linear models. They get an exact asymptotic characterization of the RERM estimator in two settings: isotropic gaussian input and $l_p$ norm geometry, and correlated gaussian input and Mahalanobis norm, with the latter considered under simultaneous diagonalizability. These high-dimensional characterizations are then reduced to low-dimensional summary statistics, determined as solutions to a set of self-consistent equations, which are solved via an iteration scheme and validated against numerical evidence. Additionally, the authors complement this asymptotic analysis by establishing uniform convergence bounds based on Rademacher Complexity. Lastly, both approaches suggest an insight that in certain cases choosing a regularization norm that corresponds to the dual norm of the perturbation (e.g., using $l_1$ regularization to defend against $l_\\infty$ attacks) could be beneficial.\n\n\n\n\n**Strengths**\n- *Sound Theoretical Foundation*: The work has a rigorous theoretical analysis .\n- *Tractable Characterization*: The authors provide a characterization of the problem, which is complemented by a numerically tractable procedure that gives predictions aligning with empirical results.\n- *Extension to Structured Covariates*: The work explores beyond isotropic Gaussian distributions.\n- *Novel Insights*: The theoretical results suggest interesting insights, i.e., suggesting benefits of using one regularization norm over the other depending on the perturbation geometry, attack budget and sample complexity.\n\n**Weakness**\n\n- *Gaussian Assumption*: The characterized asymptotics rely strictly on Gaussian covariates. The authors assume, but do not prove, that these results transfer to real-world distributions via universality, leaving a gap between theory and practice .\n- *Model simplicity*: The analysis is restricted to linear binary classification. This simplifies the complex, non-convex optimization landscape of the deep neural networks that practitioners actually use for adversarial training.\n- *Qualitative bound*: The derived Rademacher complexity bounds are acknowledged to be numerically loose. They function as a qualitative confirmation of the \"dual norm\" principle rather than offering tight, quantitative guarantees.", "claims_and_evidence_yn": "Yes", "claims_explanation": "For the most part the claims made in the submission are supported by accurate convincing and clear evidence. The authors accurately support the first two main contributions outlined in the introduction, i.e., the exact asymptotic characterizations of the standard and robust generalization error, and uniform convergence bound. However, I have a reservation regarding Contribution 3, which claims that regularizing with the dual norm can yield \"**significant** benefits\". Even though this claim is technically true, in order to have any practical implications I believe that presented evidence to support it should be more robust. For example, while Figure 2 (Left) does show the dual norm ($\\Sigma_\\delta^{-1}$) outperforms both the perturbation norm ($\\Sigma_\\delta$) and the standard Euclidean norm ($l_2$), the empirical evidence is somewhat limited to this specific matrix setup. To fully support such a claim, it would be beneficial to see comparisons across a wider variety of matrix structures or regularization geometries beyond these specific cases. Furthermore, while the authors use Rademacher complexity bounds to theoretically motivate the dual norm choice, they acknowledge these bounds are not numerically tight, meaning they should be viewed as qualitative intuition rather than definitive proof of the claim.", "audience_yn": "Yes", "audience_explanation": "Yes, I believe that these findings can be of interest to the TMLR audience. In general, this work tackles a relevant question, as adversarial robustness remains an unsolved challenge in modern machine learning. This work addresses the need for simple, principled guidelines on how design choices, specifically regularization, affect statistical efficiency in robust learning. Moreover, the precise asymptotic characterization in the high dimensional limit as well as Rademacher uniform convergence bound can be valuable to the learning theory community. This is supported by the fact that this work offers a complementary theoretical picture to recent work by (Tanner et. al. 2025) by extending their analysis of structured covariates to Mahalonobis regularization norms. Lastly, even though these findings are made for linear models, they could still inform model selection in practice. For example the finding in Figure 1 (Right) that optimal regularization transitions smoothly (e.g., from $l_2$ to $l_1$) as the attack budget $\\epsilon$ grows offers a specific, testable insight for hyperparameter tuning. This could provide a geometric justification for choosing sparsity-inducing norms in high-perturbation regimes.", "requested_changes": "**Proposed changes** (would help supporting recommendation of acceptance)\n- It would be good to see more evidence to support the claim that dual norm of the perturbation can yield **significant** benefits, or to make the claim weaker. The former can be done by e.g. analyzing a wider variety of matrix structures or regularization geometries beyond analyzed specific cases.\n-  Give support to the claim that optimizing the robust empirical risk as defined in (6) is a widely adopted approach.\n\n**Typos encountered & notation change suggestions** (none of them are critical for recommendation of acceptance):\n- Page 3 (top): $z$ is used, but there is no definition of what z is. Even though it is clear from the context, I think it should be defined.\n- Pages 3 (bot), 19 (bottom): Both $r$ and $\\tilde{r}$ show up throughout the paper. I think this is a typo, and only $\\tilde{r}$ should be used. \n- Pages 4,5, etc.: Throughout the paper equation (6) is referred to as the definition of the RERM problem, whereas (6) is the definition of the empirical regularized risk and (7) is closer to the actual definition of the RERM problem. Therefore, I think that when referring to the RERM problem, one should refer to the equation (7), or if referring to equation (6) to be more precise. \n- Pages 5 and 6 (mid): Make precise what are the variables from the 8 equations that the solution $(m*,q*,P^*)$ should correspond to, as it is not uniquely determined just from the statement.\n- Pages 5 and 6 (mid): Specify what type of convergences are used in Theorems 3.5 and 3.14.\n- Page 6 (top): I think it's not clear what perturbations under a Mahalanobis norm mean, since the subscript in $\\Sigma_\\delta$ is $\\delta$ which is used as a variable. This suggests that $\\Sigma_\\delta$ also changes with $\\delta$. I suppose this should not be the case, and thus It would be worth it to clear up this ambiguity.\n- Page 6 (mid): The notation of $\\omega_i$ and $w_i$ can be confused. I would propose to use something else instead of $\\omega_i$.\n- Pages 8 and 24-26 (mid): I think $m$ is a typo and should be substituted by $n$.\n- Pages 8 and 24-26: There is matrix $A$ that shows up in notation that probably should be matrix $\\Sigma_{w}$.\n- Pages 24-26: As the statements of propositions in Appendix C are the same as in the main body,  it would be good to acknowledge that they are indeed just restatements.\n- Page 26 (top): I think $\\Sigma^{-1}$ should be $\\Sigma_{\\delta}^{-1}$.", "broader_impact_concerns": "I have no broader impact concern.", "additional_comments": "**Questions**\n- Can some theoretical insights be gathered from the summary statistics formulas obtained in Theorem 3.7. And Theorem 3.15. without running the numerical iteration scheme. If not, what would be a roadblock? \n- On page 8, below Corollary 4.4 can you give a precise mathematical statement from which we can deduce that choosing $\\Sigma_{\\delta}^{-1}$ can more effectively control the robust generalization error?\n- What would be required to move away from the simultaneous diagonalizability assumption used in Section 3.2.?\n- What is the main technical difference in the proofs of the results in this work in section 3.1. and 3.2. and (Tanner et. al. 2025)?\n\n\nTanner, Kasimir, Matteo Vilucchio, Bruno Loureiro, and Florent Krzakala. \"*A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offs.*\" In The 28th International Conference on Artificial Intelligence and Statistics.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)