Adversarial Vulnerability from On-Manifold Inseparability and Poor Off-Manifold Convergence
Authors: Rajdeep Haldar
Yue Xing
Qifan Song
Guang Lin
Venue: Accepted by TMLR ()

Abstract: We introduce a new perspective on adversarial vulnerability in image classification: fragility can arise from poor convergence in off-manifold directions. We model data as lying on low-dimensional manifolds, where on-manifold directions correspond to high-variance, data-aligned features and off-manifold directions capture low-variance, nuanced features. Standard first-order optimizers, such as gradient descent, are inherently ill-conditioned, leading to slow or incomplete convergence in off-manifold directions. When data is inseparable along the on-manifold direction, robustness depends on learning these subtle off-manifold features, and failure to converge leaves models exposed to adversarial perturbations.

On the theoretical side, we formalize this mechanism through convergence analyses of logistic regression and two-layer linear networks under first-order methods. These results highlight how ill-conditioning slows or prevents convergence in off-manifold directions, thereby motivating the use of second-order methods which mitigate ill-conditioning and achieve convergence across all directions. Empirically, we demonstrate that even without adversarial training, robustness improves significantly with extended training or second-order optimization, underscoring convergence as a central factor.

As an auxiliary empirical finding, we observe that batch normalization suppresses these robustness gains, consistent with its implicit bias toward uniform-margin rather than max-margin solutions.

By introducing the notions of on- and off-manifold convergence, this work provides a novel theoretical explanation for adversarial vulnerability.

Published in Transactions on Machine Learning Research (12/2025)
Adversarial Vulnerability from On-Manifold Inseparability and Poor
Convergence
Rajdeep Haldar
rhaldar edu
Deportment of Statistics, Purdue University
Yue Xing
ringyuel &msu. edu
Department of Statistics and Probabiliby, Michigan State University
Qifan Song
gfsong edu
Deportment of Statistics, Purdue University
Guang Ling
quanglin&purduer edu
Department of Statistics, Purdue University
Reviewed on OpenReview: https: // openrevvee. net/ forum? id- pa90uRZA7F
Abstract
We introduce new perspective on adversarial vulnerability in image classification: fragility can arise from poor convergence in off-manifold directions. We model data as lying on low-dimensional manifolds, where on-manifold directions correspond to high-variance, data- aligned features and off-manilold directions caplure low-variance, nuanced features. Standard first-order optimizers, such as gradient descent, are inherently ill-conditioned, leading to slow or incomplete convergence off-manifold directions. When data is inseparable along the on-manifold direction, robustness depends on learning these subtle off-manifold features, and failure to converge leaves models exposed to adversarial perturbations.
On the theoretical side, we formalize this mechanism through convergence analyses of logistic regression and two-layer linear networks under first-order methods. These results highlight how ill-conditioning slows or prevents convergence in off-manifold directions, thereby motivating the of second-order methods which mitigate ill-conditioning and achieve convergence across all directions. Empirically, we demonstrate that even without adversarial training, robustness improves significantly with extended training or second-order optimization, underscoring convergence as central factor.
As an auxiliary empirical finding, we observe that batch normalization suppressos these robustness gains, consistent with its implicit bias toward uniform-margin rather than max- margin solutions.
By introducing the notions of on- and off off-manifold convergence, this work provides novel theoretical explanation for adversarial vulnerability.
1 Introduction
Neural networks achieve high classification accuracy and generalize well to unseen examples drawn from the training distribution (Liu et al. 2020). Yet, they exhibit a striking vulnerability: small, imperceptible perturbations can drastically alter predictions (Szegedy al., 2013) Goodfellow al. 2014 Madry et al., 2017 Carlini & Wagner 2017). These perturbed inputs, known as adversorial examples, highlight fundamental flaws in modern training and raise questions about the reliability of neural networks in safety-critical applications.

---

Published in Transactions on Machine Learning Research (12/2025)
While empirical progress has been rapid, yielding strong attacks and defenses, the theoretical foundations for why adversarial examples exist have advanced more slowly. A principled understanding is critical for developing models that are inherently robust and aligned with human perception.
The manifold hypothesis. One of the most compelling explanations is the manifold hypothesis, which posits that real-world data lies on low-dinensional manifold embedded in higl-dimensional space. Recent works [Melamed et al. 2024 Haldar et al. 2024] show that redundant dimensions (e.g., background pixels in images) make it possible to generate adversarial perturbations of arbitrarily small magnitude. This suggests that robustness may be attainable if learning is confined to the manifold.
Implicit bias and robustness expectations. The implicit bias literature (Wei et al. 2019 Lyu &
Li 2019: Lyu et al.) 2021: Nacson et al. 2022) demonstrates that standard training often yields solutions corresponding to KarushKuhn Tucker (KKT) points of the mazimum-margin problem. More generally, Rosset eet al. (2003) established that losses like logistic regression are inherently margin-maxiimiiing a property extending deep networks. These results suggest that in the absence of redundant dimensions, clean training is expected to yield max-margin classifiers that possess reasonable robustness.
The puzzle. In practice, however, this expectation is not realized. Dimensionality reduction methods such as PCA do not lead to the anticipated robustness gains (Alemany & Pissinou 2020: Aparne et al.) 2022). while adding redundant dimensions consistently amplifies vulnerability. This raises fundamental questions: Is clean training alone sufficient for robustness? And are there overlooked mechanisms that undermine the robustness promised by implicit bias?
Our perspective. In this work, we identify such a mochanism. We argue that poor convergence in off-manifold directions, caused by ill-conditioning of first-order optimization, an additional and overlooked source of adversarial vulnerability. Our theoretical framework is summarized in Figure 1 High-variance features define on-manifold directions, while low-variance features define off-manifold directions, First-order methods converge quickly in on-manifold directions but slowly off-manifold, lcading to suboptimal boundaries w when separability relies on off-manifold features. This convergence gap explains why robustness does nol. follow automatically from implicit bias, even in the absence of redundant dimensions.
Separable
Dimeraiorrality of Data charectarized by ratio of varfancee feature directions
Model Learning
meeredetiinn repi ineres based as the mosthil direction.
High frmernlonaitty
Low Oimmeddonallyy
(1 اlll - Vo Pasl Orta www.cookkaaandeeee
diveiiv
LAW VOTTATC Fasture PeoouurRuu
vurfone lantaa off-enniia
inseparabie
Clus
The modilt riddy lears hevesiize ee- mortfed direction making
vastance Nesture On Mo- directio
Figure! 1: Theoretical framework for adversarial vulnerability from a convergence perspective. (Left) Data dimensionality can be characterized by the ratio of variances in feature directions: high-variance features define on-manifold directions, while low-variance features define off-manifold directions. (Middle) First-order methods suffer from ill-conditioning in aff-manifold directions, leading to slow convergence. (Right) When data is separable along the on-manifold direction, models quickly learn robust boundaries. When inseparable, however, convergence failure in off-manifold directions causes suboptimal boundaries and increased adversarial vulnerability.
2

---

Published in Transactions on Machine Learning Research (12/2025)
Mathematical intuition for dimensionality in terms of variance. We view variance ratios across feature directions a surrogate for the elfective dimensionality of the data manifold. Intuitively, directions with high variance capture the dominant structure of the data (on-manifold), while directions with very low variance contribute little and can be regarded as off-manifold. As the variance in certain directions vanishes relative to others, the data distribution effectively collapses to a lower-dimensional set. This provides a natural way formalize dimensionality beyond earlier notions based only on redundant versus useful features (Haldar et al., 2024 Melamed al., 2024). Our definition extends these ideas by characterizing on- and off-manifold directions explicitly through variance ratios.
Illustrative examples. Figure 2 provides intuition for our framework. In birdinsect classification task (Fig. 2)), wing length serves as a high-variance, n--manifold feature that separates most birds from insects. A classifier trained on this feature alone will perform well on the majority of examples, and thus naturally favors it. However, overlap occurs: certain insects, such moths, may have wings longer than some small birds, such as hummingbirds. In this overlapped region, robustness requires exploiting low-variance, off- mt-imafioold featuresuch as the presence of a beak. Because off manifold features are harder to learn due to slower convergence, models that fail to capture them remain fragile.
This phenomenon retenstraaed a synthetic experiment (Fig. pp). When the data is separable along the on-manifold direction, neural networks rapidly learn stable, robust decision boundaries. In contrast, when the data is inseparable on-manifold, distinguishing classes requires reliance off-manifold dircctions. Here, convergence is markedly slower, and the learned boundaries remain suboptinal for many training epochs despite high classification accuracy. Together, these examples highlight why models often default to on-manifold features, yet robustness in overlapping regions critically depends on off-manifold learning, which is preciscly where first-order methods struggle.
Birds
(00))
Peleeer But fur
(Humming Bird)
Beak
(Ant)
(Atlas Moth)
(Albatross)
No-Beak
(((On)
Wing Length
T= P2
T-a0
Te 10
(a) Real-world example. Binary classification between birds and insects. The purple region shows overlap in the on-manifold feature, where only the off-manifold feature (beak vs. no-beak) separates the classes.
(b) Synthetic example. Neural network decision bound- aries after T training epachs. Data distribution is (top) inseparable on-manifold and (bottom) separable. Clean accuracy is 100% for all T > 102, yet convergence is fast and slow across on- and off-manifold directions respec- lively, which may lead to suboptinal decision boundary.
Figure 2: Illustrations of adversarial vulnerability arising from off manifold convergence. (a) A real-world case where overlap in the on-manifold feature requires reliance on off-manifold features. (b) synthetic example showing how first-order methods converge differently along on- vs. off-manifold directions.
Our contributions. We formalize the ideas described in Figs. and 2 through parameter and loss convergence results:
Thcorem 1.1 (Informal version of Theorem 4.2 Convergence faster and independent of dimensionality in on-manifold directions, but slower in mffifolffold directions. As dimensionality reduces, off- iffmmanifold convergence becomes even slower.
3

---

Published in Transactions on Machine Learning Research (12/2025)
There crists ervor threshold, determined by on-manifold separability, that is quickly reached. Reducing ervor further depends on off- all-/on-manifold vorionce ralios and is substantially slower.
Theorem 1.2 (Informal version of Theorem 4.3).
Implications. These results clarify why clean training may give the illusion of convergence: models can achieve high training accuracy after finite iterations, yet incomplete convergence across all directions leaves them vulnerable to adversarial perturbations. Addressing convergence in off-manifold directions leads to substantial robustness improvements, even without adversarial training. While this does not eliminate adversarial vulnerability entirely, the gains are significant. Furthermore, second-order optimization methods, which are immune to ill-conditioning, realize these improvements far more efficiently (Section 5), , a finding validated by our experiments (Section 6.2
2 Related Works
Adversarial Vulnerability Explained via Manifold Hypothesis: Stutz et al. (2019) introduces the distinction between on/off-manifol adversarial eramples and their role in robustness and generalization.
Shamir et al. (2021) shows empirically that clean-trained classifiers align with a low-dimensional dimple- manifold around the data, making them vulnorable to impercoptible perturbations. Zhang et al. (2022) decomposes the adversarial risk into geometric components motivated by manifold structure. |Haldrr el al. (2024) Melamed al. (2024) theoretically establish relationship between the dimension gap (induced by low-dimension data manifold) and adversarial vulncrability.
Attacc/ Sttack/Defense systems based on manifold hypothesis: Xiao et al. (2022) uses a generative model to learn the manifold and create on on- attacks. Jha et al. (2018): Lindqvist et al. (2018); Lin et al. (2020) have tried to learn the underlying manifold to detect and defend adversarial examples outside the data manifold.
Implicit Bias and Robustness Frei et al. (2024) shows that the max-margin implicit bias of neural networks isn't the most robust model. However, the attack strength in this work comparable to the signal strength, and reduces to natural/on-manine
attack scenario mentioned in Haldar et al. (2024). These attacks are perceptible by humans and of relatively large magnitude. We still expect natural robustness against imperceptible small-magee magnituee attacks in the absence of redundant dimensions, as discussed previously. Min & Vidal 2024 shows that under poly-RelU activation, implicit bias is robust to larger attacks.
growing body of work studies how training dynamics influence robustness. Kalimeris et al. 2019 showes that SGD learns low-complexity functions before more complex ones, while Tlyas et al. (2019). Hermann et al. argue that adversarial vulnerability arises due to shorteut learning of more accessible non-robust features. Tsilivis & Kempel (2022) analyzes adversarial robustness through the NTK spectrum, showing that robust features correspond to dominant eigen-directions learned early in training. |Rice et al. (2020) further demonstrates that adversarial training can overfit due to optimization dynamics. [Tnaa & Griffin (2016) attribute adversarial examples to decision boundaries lying close to the data manifold. Our framework offers complementary explanation via convergence: even when robust features are lincarly separable and accessible, first-order methods converge slowly along low-variance (off-manifold) directions due to ill-conditioning, thereby delaying robust solutions when the data isn't separable in the fost-converging manifold direction. Additionally, Tanner et al (025) and Javanmard & Soltanolkotabi (2022) also provide data geometric arguments in studying robustness for adversarial training. In contrast, our work strictly focuses on standard training and how the lack of convergence due to data geometry can inherently limit robustness, despite the existence of a robust solution.
Optimization Dynamics and feature learning
To the best of our knowledge, our work is the first to extend the notion of on/off manifold dimensions terms of feature variances rather than utility, and draw connections between on- m--manifold separability, ill-conditioning and adversarial vulnerability.
4

---

Published in Transactions on Machine Learning Research (12/2025)
3
Problem Setup
This section describes the technical setting and assumptions used for our main results in section 4.2
3.1 Notation
Throughout this paper, we will use the subscripts L to denote mathematical objects corresponding to on-manifold and off manifold, respectively. The notation 1a denotes the concatenated vector of ones of length d. For any two vectors u, such that 0, Σ i Vi, we can define a hypercube [u, such that if 2 E [u, v] then for cach i, 2 E [u, vy]. Denote Ia as the identity matrix of d dimensions. Notation 22(-) is the usual asymptotic lower bound notation. For a, b E R, a < a S b.c c for some e > O. Note that the notation implies |b| N |a] when a and b are negative). Denote
3 also works for negative sequences a and (i.e.,
@ as the Hadamard product.
3.2 Assumption on Data Distribution
We denote the underlying signal of the data with x E IR and its corresponding label as E { [-1,+1]. Wo study a binary classification problem with the data pair (2,, y).
Our signal can be decomposed as x = (1), where x, R2 and x1 E R2 are the on/off manifold components respectively. Corresponding to each class, define d-dimensional hypercubes of side as I, (-1) = (1- (1--))-aa 1a, k- La] and Z, (+1) I-k- 1a, (1- La]. The parameter & controls the overlap between the two hyper-cubes in the on-manifold direction. We assume that conditioned on the label the on-manifold signal is uniformly drawn from
12 Ia respectively. such hyper-cubes fn ~ (I, with means ( y(!-2k) 2k) La and covariance of Ia (v)
1²
Similarly, define non-overlapping symmetric hyper-cubes I, (v) = [m'() - /3o. 1, #1 + / - such that I_ (-) TIn (+1) 0, and zily (I[ (1) with means ( and covariance of Ig. The class probabilities themselves are binomial with probability x i.e. Ply 1) and P(y 1) = Also, || and 0L/o. < 1.
To explain the above assumption, the data is essentially uniformly distributed over two high-dimensional rectangles corresponding to each class. Due to the non-overlapping off-manifold distributions, the two rectangles are linearly separable in the ambient D-dimensional space. However, there an overlap in the on-manifold distribution controlled by k. The x and æ1 distributions are linearly separable, but x, is not for k + 0. The ratio of the variances of oi// < characterizes the low-dimensional manifold structure. Our data model is high dimensional hetaaicl represenlation of Figures 1 (middle) and 2b
Overlapping coefficient In order to formulate the extent of non-separability in the on- mn-manifold distribution we borrow the concept of overlapping coefficient (OVL) from traditional statistics. For any two probability densities fi()), fz( the overlapping coefficient is defined as v' y= So min (f)), dx where D is the support. Note that u E [0, 1], and essentially represents the probability of being drawn from the minority distribution. In the context of a naive Bayes classifier, V represents the probability of misclassification area of conflict. We can quantify non-separability for the on-manifold distribution by computing f min (-I), (1) dx = (t/1). As k increases, geometrically, our on-manifold hypercubes overlap more, which is consistent with v. Later, we will see how the non-scparability of the on-manifold component. affects our classifier learning.
3.3 Models
For our binary classification problem, we work with the logistic loss {(2) = In(1+e))). We will denote f(z, 7) with real output as the score predicted by our classifier for a particular data point x and parameter vector yy The expected loss of the classifier over the data distribution is L(>) = E fly f(z, 7)). The clean training
is the optimization problem min L(7) where I is a compact parameter space. Let 7* = arg min C(7), then 7Er
gEr
5

---

Published in Transactions on Machine Learning Research (12/2025)
working with compact space ensures Iy'| is finite and makes analysis tractable. This work considers the linear model and the two-layer linear network.
3.3.1 Logistic Regression
In the linear sctup, ? 8 where 0 E RP is the cocfficient vector of logistic regrossion, f(x, 0) 0T We implement a first-order gradient descent optimization scheme with step size to obtain the minimizer in this scenario. The tt iteration step is as follows:
0 =000 (VL((()))
(1)
Parameter components Corresponding to 2,,, 21 have 8,, such that 0T 6. + +0TIL. Naturally, the notion of on/off manifold components translates to 0 (0.:
3.3.2 Two-layer linear network
For the linear network, we over-parametrize the logistic regression case with 0 A Aw where A R is a matrix representing the weights of the first. layer with m-neurons, and R represents the weights of the output layer. ? (vec A, w) and the model is f(r,7) w" Az. The parameter space is the product space I' = A x W of the first and second layers. As we are working with compact spaces, minimization over the product space is equivalent to sequential minimization over the first and second layer, i.e.
min [()) min min C())
7EAXW
wEW voc AEA
Consoquently, we can implement an alternating gradient descent (AGD) algorithm with stop sizes an 0r to obtain the minimizer. The 4 step of AGD involves the following two gradient descent steps:
w-step: (++1) (1) an V. (1()) (0)
(2)
A-step: A (++1) A (t) 02 VAC
(w(++)) A (t)
(3)
Identifiability issue For the two-layer model, the optimal parameter 7 = (vec A", w²) isn't unique, however the corresponding logistic regression coefficient 6* - =" is unique and identifiable. The AGD steps in equations
2 3) induce a sequence in 9 as well, with @(2)) = A (1) w((t) and g(2r+ = A (0) (t+1), In the subsequent section, we can use this identification to tackle convergence rates of AGD in terms of 0 and the loss [(0)= = L (w, A). Furthermore, the notion of on/off manifold parameters can be extended in the two-layer settings in terms of A w = O1.,
Orthogonalization For technical simplicity, consider orthogonalization step in addition to the and A-sleps That is, before the (th iteration, (t) is hoomm-orthhooonliieee such that A (0) A = Ip, and (1()) recalibrated to preserve (t9), i.e., (4) (t()) keeps the same after orthogonalization. However, this assumption is practical, as orthogonality improves generalizability and curbs vanishing gradient issues Li
et al. 2019 Achour et al. 2022)
4
Main Results
4.1
Motivation
Consider the expected gradient and Hcssian of the loss w.r.t. the identifiable parameter 0. Denote the score as = f(x, 7) and ovv) = (1 +1+00 exp(-u)) as the standard sigmoid function.
Vol(T) = ~a.y
(4)
VOC(T) = xz n 022)0(-2)
(5)
wa.y

---

Published in Transactions on Machine Learning Research (12/2025)
Eq. (4) is the gradient over the distribution over z. Thus, for z, belonging to the well-separated region, the gradients are accumulated constructively; in contrast, for all En belonging to the overlapping region, gradients from each class cancel out and accumulate destructively. This implies that as the overlapping or v increases, we expect weaker gradients for learning II direction.
Furthermore, Eq. (5) showcases the messian/curvature of the loss w.r.t. Notice that the curvature implicitly depends on Exx which essentially captures the covariance structure of the data. The variance in the direction is controlled by oi inducing larger curvature, compared the variance in the 1 direction which induces a small flatter curvature. When implementing first-order gradient methods, the step size is bounded by the inverse of the largest curvature a,,²; As we want to change the parameters carefully, if the loss is sensitive in certain directions. However, this leads to slower learning in the flatter region, in this case, I direction. Consequently, we expect faster convergence in the direction and slower convergence in the 1 direction, leading to a suboptimal solution with poor margins that is vulnerable to adversarial examples. Technically, at very high level, we bound the loss Hessian based on variance matrices derived from the data structure. Subsequently, we use Taylor expansions of the loss, Lipschitz smoothness, strong convexity and PL-inequality--bie based arguments to derive parameter /loss convergence rates. We formalize the prior intuitions in the following subsection with our main theorems.
4.2 Theorems
For both the logistic regression and two-layer lincar network case, denote the change in loss from lf - 0 as: AC(() ((0(++1))- L()(9). Furthermore, the change in loss contributed by the on/off manifold direction is denoted by A,,(()= = L(g((+1), (0))- ((B()) and A (()(t) L(e , [(((t)) respectively.
Thcorem 4.1 (Progressive bounds). Suppose (a, v) follows data distribution described in Section 3.2 then
for the th iterate of 0 induced by GD (Eq. ( w-step (Eq. ( or A-step of AGD (Eq. 3) we have:
Vo, (((()) -(1 - vi @ 1. k/2 + vcs C la 8/2
(6)
Vo, ((((0) = =- ( @ (P) + (1 - x) ((1, 2 の 11
(7)
- -(a + d5) 2 4g 01/2
Furthermore, for appropriate choice of step sizes a, a1 a2 3 o 2
we have:
A() 3 - Vo. (()(t)) )|2 -
(8)
AIC()) -l (()(() .
AC(() = - -1Vo .-.-
(9)
where oi are vectors dependent on t with all their elements positive and- 1;
As gradient norms and the variances are positive, Fq. { and Eq. 9 imply that at each step of GD or AGD, the overall loss strictly decreases. In particular, the loss improves strictly in both I, directions.
Effect of v Eq. (6) decomposes the gradient in the on- manifold direction into two components corresponding to the well-separated and overlapping regions of the on-manifold distribution, respectively. Notice that the two terms are competing with each other, and as v (overlapping coefficient) initially increases, V (((()) || tends to decrease due to cancellation. Hence, the loss improvement. With the extreme increase in и even if ,| [((()) is large, the classifier becomes agnostic of the original class direction, due to shift in the gradient direction favoring the overlapping component.
direction also diminishes (Fq.
Theorem 4.2 (Parameter Convergence). Suppose (z. v) follows data distribution described in Section 3.2
then for both the logistic regression and bwo-layer linear network, let T be the number of ilerations w.r. 0
induced by GD (Eg. 1),, or w-step (Eq. 2) and A-step of AGD (Eq. 3 with appropriate a, a1 02 1 o then:
1. [| 01 < 6, when T 2(log([ - 0711 -- -8-1)).
2. ||0
0 || $ 8, when T = 0((0)/o1)2 log([ - 001 [| (8))).
7

---

Published in Transactions on Machine Learning Research (12/2025)
Theorem 4.2 provides the convergence rate in terms of the identifiable parameter 0 in both 1, directions. The convergence rate in the n-direction is independent of the dimensionality, whereas for I-direction the rate depends on (=1/o.) Note that as /1/0. + 0 or To = 0 (x1 follows a discrete distribution), the data distribution of x bocomes a d-dimensional manifold immersed in D-dimension space and the time required for convergence in i-direction blows to co.
Theorem 4.3 (Loss Convergence). Suppose (z. y) follows data distribution described in Section 3.2 then for both the logistic regression and two-layer linear network, let T be the number of iterations w.r.t induued by GD (Eq. ( or w-step (Eq. ( and A-step of AGD (Eq. (3) with appropriate a, 01, 02 3 o, 2 If 0" is the optimal solution, then target error (C(O(T))- - [(0))) < can be achieved, when:
1. T min(r1,72) if C;
2. T i C,
where = ([loo((((((()))) ((0 "10a://0__a_//////--oo/100000000
and C' = (D(vlog 2).
Theorem 4.3 provides the convergence rates in terms of the loss. Additionally, it states that if the error tolerance 5 >>>> C, we can have fast, convergence rate ri independent of dimensionality (o.). However, for an arbitrarily small < C, the convergence rate r2 can be significantly slower, controlled by the dimensionality (o1/a.) of the data. The threshold C Q2 log 2) is essentially the minimum loss that can be attained by only training 0, A.5 As 8 C, the rate r2 depended on dimensionality takes over.
Well separated on-manifold distribution Suppose there is no overlap, i..,, v =0 0, then Theorem 4.3 tells that can always have fast convergence rate independent of dimensionality for any arbitrary crror-tolerance 5. The on-manifold coefficients are sufficient for perfect classification, corrosponding to faster convergence. In this scenario, as long as convergence in и direction is attained, the data is perfectly classifiable. Hence, the classifier can achieve robustness just based on the on-manifold direction (Fig. 2bb.
Illusion of convergence When v is small, the model can attain fast convergence to a small loss value; however, perfectly classify the data distribution, convergence in both 1 and direction is still required 0 (Fig. 2b))). The model in this scenario will face adversarial vulnerability due to the poor convergence in the 1 direction, even though the loss value is small.
5 Second-order optimization to address ill-conditioning
Our results in Section 4.2 show that slow convergence in clean training arises from the use of a step size uniformly bounded by o across both the ıI (on-manifold) and 1 (off-manifold) directions. A small step size is necessary in the i direction, where curvature is large, to avoid overshooting, However, applying this same bound to the 1 direction, where curvature is much smaller, Icads to overly conservative updates and hence slow convergence.
To eliminate this imbalance, the step size should adapt to the local curvature: in off-manifold directions, it should scale with o while in on-manifold directions it remains limited by -. Such -urvature-deeendent (variable) step-size limits yield convergence rales that are independent of the variance ratio "1/a, (Remark A.1
However, first-order methods cannot automatically adjust step sizes based on curvature and remain bounded by a global Lipschitz constant of the overall gradienta well-known result in the optimization literature. Even so-called adaptive first-order algorithms such as Adam or AdaGrad, which perform coordinate-wis scaling, lack true curvature awareness: their effective step size is still constrained by this global constant (Barakat & Bianchi 2020 Theorem 2). Consequently, all first-order methods suffer from the same ill-conditioning, where off-manifold updates remain limited by o,, (Global Lipschitz constant in our framework). Now to actually employ curvature-dependent step-size limits, we consider replacing the gradient descent step in Eq. {1) with a Newton step: g(++1) = git) (V)C()()) -1 VVL(((()) Here, the inverse Hessian plays the role of an adaptive step size: sharp directions (large curvature) are traversed cautiously, while flat directions (small curvature) are traversed liberally. Sedond-order methods therefore automatically induce auraauure-depnden variable step sizes, addressing ill-conditioning.
8

---

Published in Transactions on Machine Learning Research (12/2025)
baaet Stopo Reach Accurany Thresbold y 0.55
KPM (odons)
Alaxsileat bdeast
Steps to Reach Threshold, p
50
290
40
200
30-
000
20
50
Wall-Clok Time, y- 0.25
Wall-Clock Time, u-D
10
0.10 0.20
0.35
0./0)
Figure Effect of dimensionality 01/o., on convergence. Number of optimization steps (vop) and wall-clock time (boltom) required to reach 100% clean accuracy (dashed) and 95% PGD-& robust accuracy (solid) as the dimensionality varies. Left: data with on-manifold overlap (v = 0.25). Right: no-overlap case (v = 0). Adam's robust convergence (surrogate for optimality) becomes slow as "1/o. - 0 in the overlap regime due to ill-conditioning, whereas K-FAC mitigates this effect. In the v == 0 setting, both optimizers converge rapidly and show no dependence on dimensionality, since off-manifold convergence is unnecessary for achieving the optimal boundary.
Practical approximations. Computing the inverse Hessian in the Newton update computationally prohibitive. In practice, one uses preconditioning matrices that approximate the inverse Hessian. Our experiments employ Kronecker-Facte Factored Approximate Curvature (KFAC) (Martens & Grosse 2015) scalable natural-gradicnt method that approximates the Fisher information layerwise block matrix, and further factorizes each block into a Kronecker product of two smaller matrices. KFAC is computationally efficient, scales to large models, and well-suited for distributed training.
Convergence guarantees. A natural question is whether second-order methods converge to the same optima first-order methods. Recent theoretical advances suggest they do. Du et al. (2019) showed that gradient descent reliably finds global minima in sufficiently wide overparameterized networks. ZZhan et al.) (2019a) extended this line, proving that natural gradient descent methods (a class of second-order methods) converge to global minima as well, often with faster rates under reasonable assumptions. Moreover, they show that KFAC, as an efficient approximation, retains these convergence guarantees. These results justify our use KFAC as representative socond-order method in our experiments.
6 Experiments
6.1 Simulation results
We empirically validate the consequences of Theorems
4.2 4.3 and the effect of second-order KFAC optimiza-
tion, using models trained on the synthetic rectangular data distribution defined in Section 3.2 Fig. 2bb. We consider two regimes: (i) a on-manifold overlap setting with v = 0.25, and (ii) a no-overlap setting with 0, and train using both Adam (first-order) and K-FAC (second-order) optimization.
(visualized
For cach configuration, mcasure the number of optimization steps and wall-clock time required to reach 100% clean accuracy and 95% robust accuracy under E2 Projected gradient descent (PGD)-altacks (Madry ct al. 2017) of strength |p(") --(11) 2/301, which corresponds to the effective scparation between the two class clusters in the off-manifold direction. this setting, robust accuracy serves as proxy for proximity to the optimal decision boundary, achieving robustness requires accurate alignment. in the 1-direction.

---

Published in Transactions on Machine Learning Research (12/2025)
Theorem 4.2 predicts that convergence in the L-direction becomes increasingly slow 01/011 0, while
Theorem 4.3 implies that this slow direction aflects overall loss convergence only when * 0. Consequently, in
the // = 0.25 regime, first-order optimization requires substantially more iterations to reach a robust solution as the dimensionality ratio decreases, since robust convergence necessitates precise off-manifold learning. contrast, K-FAC mitigates this slowdown by incorporating curvature information. 100% Clean accuracy,
however, is attained rapidly, reflecting fast convergence to a coarse loss level (Section 4.2 paragraph Iluusion of Convergence) dependent on the extend of overlap.
In the no-overlap case 0, both clean and robust accuracy converge rapidly and remain insensitive a oi/ous as the optimal classifier depends solely on the on-manifold component and does not require convergence in the i-direction. Figure 3 confirms these predictions: robust convergence under Adain deteriorates sharply as ol/o,, + the overlap regime, while K-FAC remains stable, whereas no such degradation appears when = With this motivation, we will move on to real-life experiments, where we show that just by long first-order training or second-order optimization we can significantly boost adversarial robustness in vision datasets without any adversarial training.
6.2 Computer vision datasets
NNIST robustness
Fashon I. robustness
0.8
0.8
22
5.00
39
055
Fportss
Facme
Frorts
Foath
(a) PGD, MNIST: Adam vs. KFAC.
(b) PGD, FMNIST: Adam vs. KFAC.
HWST_adam CE. LifT
DechIOnNNEST APGD-CE,
FashIMMMSST KIAE ARGDCCT Lnd
3.0
0.0
406
0.5
00-
8.59
622
0.4
0.
0.2
02
02-
0.
00
200
022
800
apc22
opoda
spocha
(c) APGD, MNIST, Adam. (d) APGD, MNIST, KFAC. (e) APGD, FMNIST Adam.(f) APGD, FMNIST, KFAC.
BatchWorm robustress
NNIST
04
202
200
1200
300
650
220
1003
Eascte
Epocts
(g) PGD, NorchNorm: MNIST (left) and FMNIST (right).
Figure 4: Robustness to fxr atlacks over training. Top: PGD robust where long training increases robustness for first-order Adam and second-order KFAC reaches comparable or higher robustness much faster. Middle: APGD robustness confirms the same trend for MNIST and Fashion-MNIST, with markedly quicker gains under KFAC. Bottom: PGD robustness for BatchNorm models, where the robustness gains observed in standard networks do not appear.
10

---

Published in Transactions on Machine Learning Research (12/2025)
Most computer vision datasets can be attributed to having a low-dimensional manifold structure (Pope et al. 2021: Osher et al., 2017]. According to our framework, if there is an overlap in the manifold dimensions, the clean training is subjected to ill-conditioning, requiring considerable time to converge. Consequently, if a lack of convergence leads to adversarial vulnerability, the robust accuracy should increase with enough training. Our discussions in Section 5 imply that with a second-order optimization scheme like KFAC, this robustness improvement should be much faster, and we could attain much more robust classifiers by just using clean training. We use the cross-entropy loss in our experiments, which is multiclass generalization of the logistic loss we used in our theoretical setup.
We perform clean training on popular computer vision datasets MNIST (LeCun et al. 2010 and MNSHIonMNIST (Xiao et al. 2017) with a convolution neural network models (Tables 1 2015 under two different optimization schemes first order and second order. We use the ADAM optimizer Kingma & Ba 2014), which is considered one of the fastest first-order methods. We incorporate KFAC preconditioned matrices for our second-order optimization inlo the existing ADAM update. We use pytorch implementations (Pauloski et al. 2020 2021 to compute the KFAC preconditioning.
3 LeCun et al.
At each training epoch, we subject the model to adversarial attacks to keep track of the model's robustness. We use fxr Projected gradient descent (PGD)-attacks of strength e to attack the models (Madry et al. 2017 We choose very small step sizes to get best approximation of PGD attacks as possible. The robust accuracy is evaluated on the test data unbeknownst to training for various choices of attack strength e, where e = 0 corresponds to the clean test accuracy. We also conduct A-PGD attacks that automatically choose the best step-sizes of PGD adaptively, and we get similar results regardless, consistent with the story line. The total training is limited to 1000 epochs for illustrative purposes. We implement 10 runs for each model to get the avg and std dev. After ~ 10 epochs, the clean training loss is ~ O in all scenarios. (For additional details see appendix C Code
Figure | exhibits the results of our experiments described above for the MNIST and FMNIST datasets, respectively. is evident that irrespective of the order of optimization, the robustness of the clean-trained model does increase with time under all attack strengths (E) with time, as suggested by our theory. Even though the clean test accuracy is stagnant around (c= 0) is ~ 100, ~ 95% (MNIST, FMNIST resp.) for the majority of the training, the adversarial robust ness increases throughout. This validates our theory, suggesting a lack of convergence in 1 direction leading to suboptimal classifiers that aren't large margin. Attaining, ~ clean loss value and almost perfect test accuracy yet showcasing improvement in robustness throughout excessive training aligns with our discussions in section 4.2 (Illusion of Convergence) and the motivating illustration Fig tom right where the classifier is good enough on the data distribution, however, hasn't attained convergence to optimal classifer and exhibits vulnerability. Additionally, the rate of robustness improvement for the second-order optimization is much faster, for the same amount of training epochs.
Ofhr10 ADAM i, rebustness
(With Natm) Cher10 10 ADAM L. rebustmess
(W0 BatchMermi mn AON-ARDD-CE CE rebostress
0.8
5055
3.4
14-
2030
02-
2035
62
02
0:
4233
00
2000
1000
1803 2000
2000 2500 4300 beem
250
600
2003 1200
Eaochs
Spochs
(a) PGD, Standard.
(b) PGD, BatchNorm.
(c) APGD, Standard.
(d) APGD, BatchNorm.
Figure 5: CIFAR-10 lx robustness over training for first-order optimization. PGD (left two) and APGD (right two). Standard networks (no BatchNorm) show robustness gains with longer training, while BatchNorm networks fail to exhibit similar improvements.
11

---

Published in Transactions on Machine Learning Research (12/2025)
Moreover, we conduct similar robustness experiment on the CIFAR10 dataset Krizhevsky al. 2009 with ADAM training (Figure 5a and 5cp. KFAC is designed to scale up in distributed setting for larger models. Although we couldnt provide the KFAC version for CIFARIO due to limited access to a single GPU, we conducted the first-order training for larger epochs to illustrate robustness improvement. We expect a second-order optimization scheme would yield similar results but with much smaller training epochs, as observed in the MNIST and FashionMNIST cases.
Unparalleled clean training performance Attaining 80 and 40% robust accuracy for 0.3 (ADAM+KFAC in Fig 4 in MNIST and FMNIST datasets respectively just by clean training is unprecedented. = 0.3 is a very large attack strength for these datasets, for context [Mdry et al. (2017) reports a robust accuracy of only 3.5% for MNIST dataset undergoing clean training with the same attack strength. Similarly, for CIFAR10 Fig 5a we attain ~ 60% robust accuracy for c = =/2555 just using clean training. Traditional literature reports 0% robust accuracy for clean-trained model and 47.04% accuracy for the PGD-based adversarially trained model (Zhang el. al. 2019b).
6.3 Vulnerability of Batch Normalization
Figures 5b 5d and ig present experiments with architectures that include batch normalization (see Tables 2
in the Appendix). Unlike standard networks, these models show no robustness improvement with extended training, oven when convergence is reachod. These results suggest that batch-normalized networks do not
benefit from the convergence-driven robustness gains identified in Section 5
This observation is consistent with the different implicit biases of the two architectures. Traditional ReLU networks exhibit a bias toward marimum-margin classifiers, which naturally promotes robustness. By contrast, batch-normalizzd networks have been shown to favor uniform-maryin classifiers (Cao et al. 2023) which lack the same robustness properties. Within our framework, this helps explain why the convergence benefits we obscrve in standard models do not extend to batch-normalized ones.
Importantly, the vulnerability of batch normalization has also been noted in prior work, though from different. perspectives. Galloway al. (0019) reported reduced robustness, attributing it to mean-field effects. Wang et al. (022) and Muhammad et al. (2023) showed that removing batch normalization improves robustness even under adversarial training, suggesting the effect is intrinsic to BN rather than training specifics.
Taken together, these findings indicate that the lack of robustness gains in batch-normalized models is not unique to our experiments, but part of a broader phenomenon. Our contribution is to situate this behavior within a convergence- based framework, complementing earlier explanations and raising caution about the default use of batch normalization in robustness-crttiaal settings.
7 Discussion and Conclusion
We extend the notion of on and off-manifold dimensions to high and low-variance features. We explore framework where inseparability in the on-manifold direction between data classes causes adversarial vulnerability due to slow learning in off-manifold direction from ill-conditioning. We present theoretical results supporting this hypothesis for a binary classification problem on a toy data distribution motivated by this concept. The theoretical analysis is done for the logistic regression case and 2-layer linear network for mathematical tractability. We validate the implications of our framework via simulations and real life experiments on MNIST, FMNIST, and CIFAR10 datasets with CNNs under cross-cntropy loss. Furthermore, we advocate using second-order methods that inherently circunvent ill- illccondiioo and accelerate convergence continual long training for first-order method to reach closer to optimality, significantly boosting robust. accuracy just by clean training.
Adversarial Training. We also provide a convergence-based interpretation of adversarial training within our framework and discuss how it implicitly mitigates off- ill-conditioning by inflating variance in low-variance directions. For clarity and space, we defer this discussion to Appendix
12

---

Published in Transactions on Machine Learning Research (12/2025)
References
El Mehdi Achour, François Malgouyres, and Franck Mamalet. Existence, stability and scalability of orthogonal convolutional neural networks. Journal of Machine Learning Research, 23(44)): 2022.
Sheila Alemany and Niki Pissinou. The dilemmna between data transformations and adversarial robustness for time series application systems. arXiv preprint vrXiv:2006.1088: 2020.
Gupta Aparne, Andrzej Banburski, and Tomaso Poggio. Pca as a defense against some adversaries. Technical report, Center for Brains, Minds and Machines (CBMM), 2022.
Anas Barakat and Pascal Bianchi. Convergence rates of momentum algorithm with bounded adaptive step size for nonconvex optimization. In Sinno Jialin Pan and Masashi Sugiyama (eds.), Proceedings of The 12th Asian Conference on Machine Learning, volume 129 of Proceedings of Machine Learning Research, pp. 225 240. PMLR, 18 28-0 Nov 2020. URL https::t//// http:///pooeeeiggs.. mlr www.sppees/vvlvv wttesss/v119/// 122/b//a/battaaa..... html
Yuan Cao, Difan Zou, Yuanzhi Li, and Quanquan Gu. The implicit bias of batch normalization linear models and two-layer linear convolutional neural networks, 2023.
Nicholas Carlini and David Wagner. Towards evaluating the robust of neural networks. In 2017 iece symposium on security and privacy (sp), pp. 39 57. leee, 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1675-16855 PMLR, 09-15 Jun 2019. URL httpp::/ mwa.inngss..r...... www.r..prees//////111ee httpss//ppooeeelggg...a.e//s///p html
Spencer Frei, Gal Vardi, Peter Bartlett, and Nati Srebro. The double-edged sword of implicit bias: Gen- cralization vs. robustness in relu networks. Advances in Neural Information Processing Systems, 36, 2024.
Angus Galloway, Anna Golubeva, Thomas Tanay, Medhat Moussa, and Graham W Taylor. Batch normaliza- tion is a cause of adversarial vulnerability. In ICML 2019 Workshop on Identifying and Understanding Deep Learning Phenomena, 2019.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arviv preprint ar Xiv: 10l::4122, 6572, 2014.
Rajdeep Haldar, Yue Xing, and Qifan Song. Effect of ambient-intrinsic dimension gap on adversarial vulnerability. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1090-1098. PMLR, 02-04 May 2024. URL ptttps://proceediine mlr. .pres// v238 w238/haldar24a html.
Katherine Hermann, Hossein Mobahi, Michael Curtis Mozer, et al. On the foundations of shortcut learning. In The Twelfth International Conference on Learning Representations.
Andrew Tlys, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'AchéeBue,, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpa////ee..aaaaaaa.oo.o.....a.
Adel Javanmard and Mahdi Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50(4):2127-2156, 2022.
Susmit Jha, Uycong Jang, Somesh Jha, and Brian Jalaian. Detecting adversarial examples using data manifolds. In MILCOM 2018-20 2018-2018 IEEE Militory Communications Conference (MILCOM), pp. 547-552. TERE, 2018.
13

---

Published in Transactions on Machine Learning Research (12/2025)
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. In H. Wallach, Н. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httts:://rrccedding .pff
neurips.. Beurips.cc/paper__rr. wttpc/pper.lleeeeepeeeeeeeeeeeee Stapeerffllleeeepe//////e
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprinl
4rXiu:1412.6988 2014.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Lobs [Onlinej. Available: http://yann. lecun. com/erdb /mnist, 2, 2010.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, (7553) ::36 444, 2015.
Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE transactions on pattern analysis and machine intelligence, (34):11352-1388 13688 2019.
Wei-An Lin, Chun Pong Lau, Alexander Levine, Rama Chellappa, and Soheil Feizi. Dual manifold adversarial robustness: Defense against Ip and non-lp advensarial attacks. Advances in Newral Information Processing Systems, 03:3487-3499) 2020.
Blerta Lindqvist, Shridatt Sugrim, and Rauf Izmailov. Aulogan: Robust classifier against adversarial attacks. arXiv preprint XrX:::1812.00./ 2018
Jinlong Liu, Guoqing Jiang, Yunzhi Bai, Ting Chen, and Huayan Wang. Understanding why neural networks generalize well through gsnr of parameters. arXiv preprint arXiv:200100338, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint Xrx: 05890, 2019.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 170x 06083, 2017.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factonn factored approximate curvature. Tn International conference on machine learning, pp. 2408 2417. PMTR, 2015.
Odelia Melamed, Gilad Yehudai,, and Gal Vardi. Adversarial examples exist in two-layer relu networks for low dimensional linear subspaces. Advances in Neural Information Processing Systems, 36, 2024.
Hancheng Min and René Vidal. Can implicit bias imply adversarial robustness? arXiv:2405.159.3 15942, 2024.
arXiv preprint
Awais Muhammad, Fahad Shamshad, and Sung-Ho Bae. Adversarial attacks and batch normalization: A batch statistics perspective. IEEE Access, 11:96449-964555 2023. doi: ALLL00//ACCESS.222...2.2
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate, 2022.
Stanley Osher, Zuoqiang Shi, and Wei Zhu. Low dimensional manifold model for image processing. SIAM Journal Imaging Sciences, 10(4):1669 1116669999,,,,,-111111 2017.
J. Gregory Pauloski, Zhao Zhang, Lei Huang, Weijia Xu, and Ian T. Foster. Convolutional Neural Network Training with Distributed K-FAC. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 220. IEEE Press, 2020. ISBN 9781728199986. doi: 00.5555/343377 33386333333700.333886.
14

---

Published in Transactions on Machine Learning Research (12/2025)
J. Gregory Pauloski, Qi Huang, Lei Huang, Shivaram Venkataraman, Kyle Chard, Ian Foster, and Zhao Zhang. Kaisa: An Adaptive Second-Order Optimizer Framework for Deep Neural Networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 221, New York, NY, USA, 2021. Association for Computing Machinery. ISEN 9781450384421. doi: 00.1146/8458817.34476553
URL /ttp::////oo..r//1.... 1144//445/441111 /1/.////8.0///1001111/////888771 3476152
Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. arXiv preprint arXiv:2104.0888 08894, 2021.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In Hal Dauné III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8093 8104. PMLR, 13 18 Jul 2020. URL https: //proceedings.. . mlr. pptpss/v19//rreeeeeeeeo html
Saharon Rosset, Ji Zhu, and Trevor Hastic. Margin maximizing loss functions. Advances in neural information processing systems, 16, 2003.
Adi Shamir, Odelia Melamed, and Oriel BenShmuel. The dimpled manifold model of adversarial examples in machine learning. arXiv preprint ar Wriv:2106.10151. 2021.
David Stutz, Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1976-6987, 2019.
Christian Szegedy, Wojciech Zaremba, lya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 6199 2013.
Thomas Tanay and Lewis Grilfin. A boundary tilting persepective on the phenomenon of adversarial examples. arXiv preprint arXiv:1600 100.006609, 2016.
Kasimir Tanner, Matteo Vilucchio, Bruno Loureiro, and Florent Krzakala. A high dimensional statistical model for adversarial training: Geometry and trade-offs. In International Conference on Artificial Intelligence and Statistics, pp. 2530 2538. PMLR, 2025.
Nikolaos Tsilivis and Julia Kempe. What can the neural tangent kernel tell us about adversarial robustness? Advances in Neural Information Processing Systems, 35:18116-18130, 2022.
Haotao Wang, Aston Zhang, Shuai Zheng, Xingjian Shi, Mu Li, and Zhangyang Wang. Removing batch nor- malization boosts adversarial training. In International Conference on Mochine Learning, pp. 23433 23445. PMLR, 2022.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image datasct for benchmarking machine learning algorithms, 2017.
Jiancong Xiao, Liusha Yang, Yanbo Fan, Jue Wang, and Zhi-Quan Luo. Understanding adversarial robustness against on-manifold adversarial examples. arXiv preprint arXiv:2210.004.0 2022.
Guodong Zhang, James Martens, and Roger B Grosse. Fast convergence of natural gradient descent for over-parametterieel neural networks. Advances in Newral Information Processing Systems, 32, 2019a.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoni, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp-
PMLR, 2019b.
Wenjia Zhang, Yikai Zhang, Xiaoling Hu, Mayank Goswami, Chao Chen, and Dimitris N Metaxas. A manifold view of adversarial risk. In International Conference on Artificial Intelligence and Statistics, pp. 11598 11614. PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (12/2025)
A
Proofs
In all our proofs, we assume that Rank(A) = D, as when Rank(A) < D, we can just work with a block of A that is full rank. The gradient of w corresponding the co-kernel A will always be zero, and doesn't 't. affect any of the gradient descent steps pertaining to our analysis.
A.1 Reparametrization
Lemma A.1.1 (Reparametrizationn). For the thh iterate of w-step Eg. ( and A-step of AGD Eq.
3
there exist reparametrizations w((t) and ( such that ((2++1) = (0(2++1) , (( = (a a((i) and (( (0(2t) 0 (w ..f).. Where i (m L1, (x)), vec (ā,, "G,, __. a-) and VL.. 0m-D. D. VLa--
O.
Proof. Recall that, for the two-layer linear network, Y = (vec A, w) and = ATw, with VeC(n)
E yxr 2) (Eq. (4)). Our reparametriaationccaang of basis will help us separate the components of wazyy the first and second layer into +,ト directions corresponding to the identifiable parameter 0 = (6., 01). H components correspond to redundant directions that don't undergo any change in the AGD step.
A.1.1 w-step
In this stop of AGD, the second layer is fixed to A Given A A the gradient w.r.t. the first layer parameter w is:
Vw((220)) Ba A)yAr
(10)
A rectangular matrix (m D;m D). Rank(A) S D. Hence there exists change of basis B mmx such that A B(ei../.. eD] where e; is the standard basis in R" with 7th coordinate being 1, and rest 0. This choice of standard basis for the Tm(A) loses generality the basis in such way so that the transformation adheres to the choice of subset of the standard basis. In general B = A c] has to take this kind of form, for any choice of C E Rmxm- Hence, the gradient w.I.t.can be expressed as:
we can always have B = BP which permutes
V V= = = -oo(-y z)yB
(11)
0m-D)
We choose appropriate full rank C outside the span of B to get inverse transformation B-1 Note in the case that Rank(A)= < D just work with block inverse of the full rank part in B; as the gradient of w corresponding to the co-kernel of A will always be zero, so it isn't of interest. Consider the reparametrization (+)) = (?) with gradients:
V C(B(20) = B V. C= - -Eo(-y A) = -Eo( z)y
x Om-D)
(12)
Note that, ((2)) = A (t)) = (B(c "ol)" w(()) = -...... -.l.elTTTee. Therefore, it follows that there exists Wn, w components corresponding to 0,, 0, al every L. Note that the remaining components wh are redundant. and have zero gradients.
a (() Fo(-y yg. 2)y
x (nnDD)
(13)
V. w. C(0) = -Eo(-y -y z)yz
(14)
((0) -Eo(-W z 2)y01
(15)
my (()) Omn-D
(16)
16

---

Published in Transactions on Machine Learning Research (12/2025)
A.1.2 A-step
In this step, the first layer is fixed to w((+1), Given w = w((+1), the gradient w.r.t. the second layer parameters
A is:
VAC -Eo(-y (0):2))uuu =)ywax
(17)
V vec Al -Eo( 2)
(18)
T
11
Consider the reparametrization À such that A (1)
Å.
The columns are chosen using
Um
Gram-Schmidt such that, u1 w/1l/// and (uy w) 0, |uylIl re-parametrized space is then:
for all j * The gradient in the
VAC = -Eoo
2) 2)y Eo(-y 2)ye,
(19)
A - z)ye1 o
(20)
Note that,
((2++1) A (0) ((++1) = (U (0) wt = ( Uw = AA00
Therefore, it follows that there exists au an components for vec À corresponding O,,, 01 at every t. Hence, vec Å a a.) with:
a. ((0) [oolyy 2)yx,
(21)
V a, [()) -Eo(-- 2)yx
(22)
V [(0) = 00.D-D
(23)
7
A.2 Hessian
Lemma A.2.1 (Lipschitz smoothness and Strong Couvexity). For any value o in both logistic and two-layer-linear setting. The loss Hessians w.r.t. identifiable parameter 0 can be bounded as follows:
La
o
< vic()) < <a.
(24)
0
o I
0
o
qoi
1
Vi [(7) coiL,
(25)
q V2, (()) <,,
(26)
Here C1 Cn > are constants. Consequently, L(7) conner in 0, 0,, 01.
Proof. The Hessian of the loss w.r.t. the identifiable parameter f is ViC(?) E zr" (22)0(-2) [Eq. (5) ~x,y
As our analysis is restricted to the compact space, a2)) is strictly between 0 and 1, as (2) 1/0 if and only if to0 Let a > 0 be the lower bound of the entropy (=)) Then, using positive definiteness and integrating both sides (Here >, < between matrices corresponds to the difference being positive /negative definite):
E THT q V2L(2) NE
XT
Σx B 3 q V2 Σ, -
ESE TT -2.9 -9.9
Where Σ, 2I
the covariance matrix. The vector outer-product Ex Ex. has eigenvalues
of L
||al| = |Ex|
0.0... 0. Hence, Op & ExExTe s Ip. This implics that:
Σn ...q q v8C(n) En I
17

---

Published in Transactions on Machine Learning Research (12/2025)
For 0 |||| on < <0.. We have |||| C.O, TOTa
Vic(()) < oo
0
0 201
o i
o
+
Then there exists constants Cu = max (1 + 4: 1 + 24) such that
T
vi((()) ca of
of oil
I
III
1 Vo, f(7) cLolI
q0 V (()) C.o
As the above Hessians are positive definite, convexity follows.
Proof of Theorem 4.1
A.3 Gradient Decomposition
From Eq.
4
VoL(r)
=
E yro 22. We will tackle the " / components of the gradient separately,
~x.y
A.3.1 On Manifold
Consider V(,) = ynua(-y.3 z). Vo C can be decomposed into Vo, Vo, the gradients ~x.y
arising from overlapping non-overlapping distribution of Ia, with probabilities v, - v respectively. The distribution of æ corresponding to the non-overlapping part and overlapping part xuly.0 U[00, (1 k) y 1a] and z xulg.-0 U(-k.y la, 0) resp. One can validate this with the definition v (Section 3.2 xuly. contributes in the computation of v, while Zuly. has non-zero contribution over the support.
Vo. Vo,)(n)
E yo 1- v. 2) = -11 - v)- ~z yz V. ~x.y
E -xy
y 2)
(27)
E yo =
E
x + TT)
E
(2)
(28)
1.0
1// jo
1-k
1-k (n,o((2) (1 - 1s) ( dx iE f1.....d}
22,0(220
11
(29)
~0 111
c 2 1//12/22
(30)
Eq. 29
every integral is in a positive domain, with o(-2) E (0,1) within the compact space. < 2 k/2, component-win get Eq. (30) where ci. for i E (1..... d).
-o- x.,, Bm Fmn))
k
I (2) 11 (1-
- ())o)()) (1 k)) 4 de ii (1....,,
~ 1,0 1,0
((-A)
(1-b) (1-b)
(2) . -1 kk) -k)-4aa dr
(no(-22) (1 k) - 1 dx
Eq. 29
2 1//2
(31)
Substituting Eq.
30 and Eq-
31
in Eq. 28
have:
E
y ( 2)= = 1al-///
(32)
~a 10
E
(,,0(-2) = =1
(- k dx ,iE (1.....)) d)
(33)
18

---

Published in Transactions on Machine Learning Research (12/2025)
Using analogous arguments as in Eq.
29
02 L/.
(34)
Similarly, we have
E
-2,0(2)
-62 0 14.4/
(35)
~at 1=
Substitute Eq.
334
and Eq.
355 in
E
yoe yo ( () =
E ~
3 ((2) + -t)
1. (
E
(36)
to get
yz, u- - 1/.²/2
(37)
~x..1
Using Eq.
32
Eq.
37
in Eq.
we have:
= (1 vo.A))=--00v),0000dd-444 + +v. 2.000000 20011.1 1////
(38)
A.3.2
Off Manifold
=
E yr (-- 2) v. wx.
E
(10(-2) - (1-+) E
- - -z)
(39)
~aly
~x/ym-1
px( tv30
(1)) tv
E x x_oo(-2) =[
x1:0(-2)- (2v301) 'I ,iE {I,....g}
(40)
~a/y=1
1301
(1) -3o1
Let 1 = =11 + then
1301
(w()) (1)
+ (-))) (2233)))))33 "d
V3o
Via -Va
/30
2 11
m0((=2) (2v3o ) dn
nio ( (2v3o1)
30 "
-301
2
+ (6 + (5)
2 1g 01/4
(41)
Also,
E
o(z)
E
E
x (-2)
~
Following similar steps following Eq.
to Eq. 41
c6 11 (-1) + (a+ (5) 211 +1, 0L/4
(42)
Substituting Eq. 41 Eq.
42
in Eq. 39
we have:
Vo (()) = - c + p ()) (1 T) (-(1, -66 0 -11- (G +6) 01/1
19

---

Published in Transactions on Machine Learning Research (12/2025)
A.4
Progressive Bound
A.4.1
Loss change all directions
At()) C(o(t+1)) (()())). Using Taylor's expansion of ((o(t+1)) around g(t) with Lipschitz smoothness
Eq. 24 we have:
((B(+t1)) C(0 Vol()l))(((tt) ((0)) + Cu (0ltt)) ((t)) (ff
(10 0
(0ltt))
TTT
As 01 < un we have:
((0l+12)) < <((0()) + VoL(O -000) + Eu (0((tt)) ( 1 - 0(1)
For logistic case the gradient step g(++1) g(t) @Vo(((
Guo
((0(++2)) L(B()) aa V || + a²
V VoL()()) 1|2
2
AC(T) < V (1 cuo
2
For step-size
(43)
AC(I) <
2. For w-step Eq. 2 we have (1/2++)) = w V n L(D(0). From lemma A.1.1 section A.1.1 have reparametrization (0, 0m- = (t(2/)) = B" (t/2). Note that B = A C| for some specific choice of C. This induces a gradient descent step in T space follows (t//++1) (((l2)) - a B ((0(( or gi++1) = 0(0) - A0/2) (((00)))) Hence, the Taylor expansion can be written as:
c(g(++1)) < -((())- a1 VoL(O 0/2) A A + taj Cuo (A/22) A 2
let SA,AA be the minimum/nnxximmm eigen values of A ( Al/2)) respectively. Then
c(0(t+2)) < - ai
GuOD Xa VeL(O())
AC(t) < -0 {6
1-
For slep-size
a1 S (M -
(44)
Where 82/2a S M for all and some M < 0 (compact space).
AC(t) < -A- (2M c. -
20

---

Published in Transactions on Machine Learning Research (12/2025)
3. For A step Eq.
13 have A (111))) A (111/a) 02 V A(((()) From lemma A.1.1 section
A.1.2 vec A (t 1/2)
vec U 42) (ID 00 U2) vec A 1/2) Let K"
(ID &
Ip x
descent step in vec A 9 space follows vec A (1+1/)) 1,..,,,,.1 _ Im This induces a gradient vec A 11/122 a2KKKV A(((0) (where
Diag (Iw [ I)) as D'aa
K"K = ID @ Diag (Ilw("1/)) 1, 1,..., Im) or ((++1) = ((0) 0 a2||w 4/) (o((())) Following
analogous steps to the derivation for the logistic case (Item D with step size
02 = (W . G
(45)
where ||l ||/00+ < W for all t. We get the following:
AC(t) < - 11 (2 W
A.4.2 Loss change on- on-manifold direction
A,C(t) = C(O(+t1) 0(9) C(O(t)). Using Taylor's expansion of ((0(t41) ,00)) around 0(t) with Lipschitz
smoothness Eq. 26 we have:
((0((t1) 0l1) - 000 (0 ( +
Cu (o((+2) -00) o(0) 10 0000)
2
Logistic case: From section A.4.1 Item
remember that the gradient step for logistic case is Eq. (3)) Hence, g(t+1) 0 a ((O()))
g(t+1) g(t) (oC((0)) with step size a c.
2 o² A,C(t) aalVV, ((0()))1
Vo ((1
2
As a 5
1 coo
A,C(t) -(2cu0,) -22 )(
w-step: From section A.4.1 Item 2
remember that the gradient step induced in the identifiable parameter 0. for w-step is 01++1) g(0) a A(/2)) (1t/2 voL((()) with step size ai (M
cgo Egq 44). Due to orthogonalization of the first layer, A (t/2) A = Ip and ÂAA = with M 1. Hence, g((+1) 8000 a1 V.. (((()) and a S (c. Now, mimicking the steps in
the logistic case, we have:
C (2c.
(2cc,;)))) 1Va
3. A-Step From section
A.4. 4.
[tem 3 remember that the gradient step induced in the identifiable param-
eter 0, for A-step is 0
1+1)
(1))
o2ll (** VoL(((t) ( with step size 02 (W -,,o,)-- Eq. (45).
Hence, g(++1)_ = (!!) a2 w
V Vp (((())). Now, following identical the steps as in the logistic
case, w-step, we have:
1 <11lu((+)))))) (2 -
21

---

Published in Transactions on Machine Learning Research (12/2025)
A.4.3 Loss change fff-manifold directions
A A())) L( o((t1)) L(0(0). Using Taylor's expansion of _(0 o around 0 with Lipschitz
smoothness Eq. 25 we have:
C(0().0((+1) C( 0 Vo_ (0) 019))
-(0)) + Cu (0((+t)) 0( o² In( B
As To in have:
-0(") 010 < C(8) 819)= + Vo. ((0(0) - + Cu (o((+1)
2 6 To ID -
Follow identical steps corresponding to off-manifold direction in section A.4.2 to get:
(logistic step) (t)(() < -
(w-step) A, < - [o,
(A-step) (,t < - -1|20(+11/)11 (2 We Weooo)
Lemma A.4.1. Let 0" = (6),0] f11 be the optimal identifiable parameter minimizing [(7) and B(t) be the thh ilerate of induced by the oplimization in logislic vegression (Section 3.3.1) and L-Lnee Layer network setup (Section 8.3.2), then for t2 > b and oppropriate a, on, 01,00 02 o, we have:
[(O,,, (40,)04)))- S [(0m, 0(:1)); VO,. ((0((t) ,01) S ((0) , 01
(46)
(47)
In particular, we have component-ure wise progressive bounds as such:
[(0,,, 0(t1)) - [(O., (4) - c,((2c.01= ((0(Ht2), (0)
(48)
01) - C( 01) & (2(2c,0 -
(49)
Proof. We will prove for the 1 direction; one can identically derive the result for the ı direction. Suppose we do T iteration of optimization; this induces sequence in off-manifold parameters 0 l - p())
(T)
Fixing the parameter to general 0,, apply Taylor expansion with Lipschitz smoothness (lemma A.2. to the loss C(O... o((+2) around the point (O.,, (()):
C(0,, s C(O.., 02) C(O,, (0 0(0)
Cuo?
(a++) -
0000 (00)
-oo ((((1) (Eq. 54)) for some step-size ä depending on the situation.
C(e,,, C(0,, (((+1))+)))) = L( ((0) VV L(,,, 0 " L(B(t)
+ x²
Vo. L(0(t)))2
2
(8)
$ L(O,, ((0)) à V/ ((
82 Co
Vo. _(0
2
$ C(B,,, 0 o Vo. C(0
c- 6-6Coot
2
20
S C(O,, (()) -cp (2c, (1
Cp =c when and cp 2c when
22

---

Published in Transactions on Machine Learning Research (12/2025)
(i) Vo, L(0,, (1) wxy
E ye yorio(-1) 2) -- - E y0 (1 + exp (v0Tx.) x.)) exp (uD(t) x1))-1 Let mx,y
exp f20) z,,) -exp -0(t) 2n). Then Vol Li00,,
E yr (1+rexp (vo(t)² 2 2,) exp (wol)) x1))-1 wayy
As As
E yo (1 exp (10 mn) exp (vol( x x1))) c. Vo_ L((()) for some c 0. ~z,9
(i)) If c 2 1 with á I (c Eq. 55 then (1i)
0.
If 0 < < 1. one can choose strictly
smaller step size still satisfying the upper bound of Eq. 55 á S c (cuo < (cuo which makes
(i) 00
As L(e,,, ( C(O.,, (()), for all t using induction [( o((a)) - C(0,,, when to t1. One
identically show that L(0 01) S ((0 (1).
A.5 Convergence Theorems
Proof of Theorem 4-2 We start with the proof of I. direction; one can derive the result for mimicking similar steps with minor alteration. 0== () is the optimal identifialle parameter value which minimizes the loss and takes T iteration of optimization.
Upper bound the Gradient norm by Loss difference: Using lemma A.4.1 with 2o = T,t = t + 1:
- 01) S C(O ((0"".01")))
Using lipschitz smoothness in direction we have
s <( 0(9) Vo Vo_ ((()))
co [1((tt1) - -00001
Gradient descent steps induce updates in 1 of the form, o((+1) 8(4) vvo. ((((0)
< C( ( (10) - a V 1(0 (1-a a Coo7 2
(1
Vo. c(0())))) = (c(0()))_(()" -
.81) (1- ā
Guo?
-1
(50)
2
Similarly, for the on-manifold direction
Vo, (( (c(O(0)) L(0,, -(0), (1-ai, a-a,
Cu
2
(51)
2
Also, using strong convexity Eq. 25 we have:
-( 01) 2 C(0())) + C(0(0) -0(t)
10
1
2
Vo, C(000) 01) 2 (((() - -( 01)
.00) + ao?
00- - 11
(52)
2
Similarly, for the on-manifold direction, strong convexity leads to:
2 100 0
Va. ((00))/TT 0,) 2 ((0(0)) - L(0; ((0) +
(53)
Also, from Eq.
43
Eq.
44
Eq.
45
a < ?) -1 (logistic)
a
á
01
01 (G -1 (w-step)
(54)
12
02 < (W c,0 1|/w(++//0)++ W, Vt (A-step)
23

---

Published in Transactions on Machine Learning Research (12/2025)
á S (c
(55)
The parameter difference can be expressed in terms of the difference at the previous iteration:
|ottu - 01 0i1|== [10[² ä ((0())- - 01
= =110( 0- 112 28 ((0 (0 01) + =(
Substituting Eq. 52
I |10(0) 011l" - 28 (<()()) - _(0 ,01 ++
90?
|10 01113) + VV C(0()))
2
Using Eq. 50
$ 110 - 04 28 (C(B(O) -(0((), ,01)
a
|10 07 07 112
2
(E(0l0)) - C(0 .01) (1- x1-
(1 cuo
2 à
Using Eq.
55 and 21/0. <1
Cuo )-1 -2
= =100")
- -0 (1 åqoo) (C(OL)) - -(0
(1 (1-
2
50
22
Using Eq. 55 and < Cu Eq. (24
< 110
07 112
Suppose we have T total iterations then, inductively the equations accumulate over as:
l09T 8 11 S |10(0) - 0% 11? (1 qi??
T
s |00 - 0t 11? exp ( --99
(56)
cuo
CuO
Hence, we require 7 c log
11000 -i for ( distance from 0
Similarly, one can derive the bound for the direction mimicking the exact steps direction but instead using analogous equations Eq.. (53),
Eq.
51
T cua" log 11 log [|a
[1010_0011
for O()) distance from 0",
C.o.
Remark A.1. When deriving the bounds for [10000 - 0; || es [100h) - 0 ||- the key point of difference is using the same step size à I o-- even though the strong converity constants are different, & o² for direction and x of for 1 direction. This introduces the ratio a_/a, in the 1 case, while for case the step size and strong-convertte parameter neutralize each other to Hence, if we could enforce seporate step size for 1," directions a 30 an 30,² Then, we can get equivalent rates in both directions.
Proof of Theorem 4.3 We want to minimize the loss L())
E Ely z). The minimum loss that can be ~x.9
attained has a natural lower bound min L(0) 2 (1 v) min
{(y 2) + D min
E(y 2). Suppose
~
8 or
24

---

Published in Transactions on Machine Learning Research (12/2025)
only optimize the loss w.r.t. 6n and 81 0, then perfect classifier on direction distinguish an with probability 1 or 0 loss, but only with 1/2 probability on 1 direction. In this case, min [ 2 v log 2. Tn
general, the classifier isn't perfect, and 0 can fixed at some default value. Hence, the lower bound is controlled by v log? 2 up a constant min [()) 2 (o 2). Consider two cases when the loss tolerance e
8 < or C.
Case 1: 8 C
From the progressive bounds in proof of Theorem 4.1 for any optimization iterate (logistic, w-step or A-step) induced in the identifiable paramcter 0, has decremental loss:
1(0(++1)) -((0)) S -2cc 1 ]oL((()))
(57)
-2q02 (c(0())-CC) -(0)) 2 Vo
(PL-inequality)
Proof of PT inequalily: The Eq. Pll-inequality is a consequence st strong convexity. Using strong convexity in the space of identifiable paramcter 0 Lemma A.2.1 Eq. (24] we have:
L()) 2 -(0()) + Vo o(9) + - [ - o (0))
(o)
0
) (0 - (0-00)
0
oit,/
o
[(0) 2 ((0()) VoL(O (()) +
10 1100112
2
Minimizing both sides w.r.t 0, happens for 0 = 0(0) (oL( -1
C(0') 2 ((0())) 2122000)
Hence, from the progressive bound, have Eq. 57
c(0(++1)) < ((((1)) (2c (
Subtracting ((0)) from both sides
((0(+1))- - L((0) S - - -200
Using Eq. PL-inequality
(1 (1- aof
((B(++1)) - _(0") <
Cua
Suppose have T total iterations; then, inductively, the equations accumulate over as:
(( c(0) (C(010)) 2(8)) (2()))))((0)) (<0)) 9o?
T s -C()))))(((())
exp (-r90) Cuo
c,0
(58)
Hence, we require T > statement.
co qo?
log ((C()(0) - L(8")) 8-1) for O()) error tolerance. This is rate in the thm
Case 2: C>C
The rate 72 proved in the previous case universal and holds for this case as well. However, we can obtain a better rate this scenario.
In this case, the loss can attain value 8 solely by optimizing 9,.. Therefore, we will upper bound the original gradient descent loss sequence by loss sequence solely dependant updates of 0., and will see that
25

---

Published in Transactions on Machine Learning Research (12/2025)
because convergence is better on 0, direction, can get better rates. Note that if (()) = C, then using Jensen's 's inequality for convex functions: 8 E y 2) s L()) = C. wz.y
In (1 + exp( spp(-E00' 2)) S
exp(-Ey0* x) 1 Ee -
1
Eyo* 2 In(
ec
1
By((O, xn) + (01 xn)) In(
ec
T((0,, /1 + (01 =(()) (1 (00) 111))) + (01 , m! (1-1)1) In(
1
Note that the above can always be satisfied by 0, = d' Mi d" my (11) for appropriate choice of constants d, c". Hence for a fixed 0 there always exists some O, such that L(0,,01) <C = c(O,, [()') << C.
This means fixing 0_ o initialization, there exists 0, well which satisfies:
min L(O.., 0"0 [()*) - 0(0., =()0) <
(59)
8,
Using lemma 1 we have:
((A(T)) < ((((T) )10
Subtracting [()") both sides
((A(2)) ((0") s ((((T) .6(0) ((0))
(() (1()) min L(O.., 010) + min L(O.,, 0() - L(0))
B.
6.
S C) + CC
(60)
Hence, we find a T' for which (( 0 min [(O,, _ 6 then we are done.
On
From lemma A.4.1 Eq.
49
have progressive bound the off-manifold component follows:
((0 o( s c().)) 0(m) - (2,,)2,0 Vo, C( (
(61)
26,01 ((e()) (00) min [(), 010) 2 (( 0,
(PL-inequality 8.)
Proof of PL inequalily: The Eq.
PL-inequality
consequence strong convexity. Using strong convexity
w.t.t. 8, Lemma A.2.1 Eq. (66
we have:
(00)) (0, - -0()) a. o2 C(O., (0) 2 ((. Vo. (( ","))""""""""""
100, 0000
2
Minimizing both sides w.r.t 0., happens for 0, = (()) "(0) 00 (((o)) -1
min L(e,,, ( ((0 V 0( ( 2| (2c)0 -1
8n
From arguments like (i) in proof of lemma A.4.1 know & Vo [( , )12
((,(()))) for some
proportionality constant o
min L(O,, 0 (() ,0 11vo (1(c))))))(()))))03
8,
26

---

Published in Transactions on Machine Learning Research (12/2025)
Hence, from the progressive bound, we have Eq. 61
((0 0 s C( ( - cp (2 ((
Subtracting min L(,,, ) from both sides
8n C(0(++1) ,00) - min C(o,,, ) S _(0,"000)) - min [(,,, - ((00))))
Using Eq.
PL-inequality 8,
c(0(++2), 0 min C(O,, (0) < (c(ol") ,0(0) min c(o.,, 010) (1-
Spcice
8,
0
Cu
Suppose have T total iterations; then, inductively, the equations accumulate over as:
(( ) min [(0,, (1) ((()00) min [( 0f)) ((e.. (1 Spcich T
6,
0
(() min L(o,.. 0100)
exp
-T
Cu
-T Tpac
(C(O10) [(8)) exp
Cu
Hence, we require T 2 Cig log ((C(0 ((0))) (6 - C)-1) for (( ,000) min L(O ((, < 8 C.
spere
On
Hence, validating the series of equations Eq. 60) and implying L(O(T)) C()*) S 6. This gives us the rate
in Theorem Note that the rate holds regardless of å value. The final rate is the minimum of the two rates.
B Convergence and Dimensionality Perspective on Adversarial Training
In practice, adversarial training (AT) is the dominant approach for inducing robustness in models (Goodfellow et al. 2014 Madry et al. 2017). Whereas clean training minimizes the loss on the original data distribution, AT minimizes the loss on distribution of perturbed examples. These perturbations are colleolled by a parameter e, which specifies the attack strength or radius around each training point. When e is smaller than the natural margin between classes, AT can be viewed clean training covers an e-ball around the original data.
expanded distribution that
From the perspective of our framework, this has key implication. Even if the original data lies on low- dimensional manifold, the e-ball expansion increases the effective dimensionality: off-manifold (low-variance) directions are also perturbed, eflectively inflating their variance. As a result, the variance ratio s1/a increases under AT compared clean training.
By Theorems 4.2 and 4.3 this change directly improves convergence rates in off-manifold directions, making it easier to reach solutions that depend on these features. This provides convergence-baset explanation for why adversarial training can succeed in learning robust classifiers even when clean training cannot, despite the fact that a robust classifier is also an optimal solution to the clean loss. In essence, AT alters the geometry of the training distribution a way that mitigates ill-conditioning, narrowing the gap between theoretical optima and practical convergence.
C Additional Experimental Details
A lcarning rate of 10-3 with default ADAM parameters were used for clean training. For generating PGD 2 with [c- 23 is the attack strength) attack iterations and 1 restart was used, For KFAC preconditioner, the default hyper-parameters were used.
attacks step size of 255
27

---

Published in Transactions on Machine Learning Research (12/2025)
Compute resource: A single NVIDIA V100 gpu used, requiring 2hrs, 3.5 hrs (MNIST, FMNIST 1000 epochs) per run for ADAM and ADAM+KFAC respectively. For CIFAR1O ADAM experiments it took 6 hrs per run (4000 epochs). Attack time included.
Layers
Conv2d(1, 16, 4, stride=2, padding=1), ReLU Conv2d(16, 32, 4, stride=2, padding-1), ReLU (inear(32**7,,100 ReLU Linear(100, 10)
Table 1: NN architecture FMNIST/MNISTT.
Layers
Conv2d(1, 16, 4, stride=2, padding=1), BatchNorm2d(16). ReLU Conv2d(16, 32, 4, stride=2, padding=1), (3tchNorm2d(32), ReLU Linear(32***7,100), BatchNorm22(100), ReLU Linear(100, 10)
Table 2: NN architecture FMNIST/MNIS with BN.
Layers
Conv2d(3, 128, 5, padding-2). ReLU
Conv2d(128, 128, 5, padding-2) ReLdi,, ReLU,
Max,ool2d(2,2), Conv2d(128, 256, 3, Re Conv2d(256, 256, 3, Dadding=I).ReLLU, (axPool2d(2.2), Flatten ( Linear(1024, 512) Linear(512, 10)
Table 3: NN architecture CIFAR10.
Layers
Conv2d(3, 128, 5, padding=2), ReLU (atchNorrm2d(129)
Conv2d(128, 128, 5, padding=2),ReLU, BatchhNorm2
MaxPool2d(2.2),, Conv2d(128, 256, 3, padding=1), 2atch_Norm2d(256,, Conv2d(256, 256, 3, Redl BatchhNorm22((56),,
MaxPool2d(2.2)) Flattee(() (2ttben(()Lneear22223334541.1))
BatchNormla((1044) Linear(1024, Re2)
BatchNormlld(512) L512 10)
Table 4: NN architecture CIFAR10 with BN.
28


Reviews:
[{"review_id": "xEhfLveUT3", "reviewer": "Reviewer_j4Br", "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 makes contributions to the theoretical foundation of adversarial examples. Specifically, the paper attributes the existence of adversarial examples to the poor convergence in off-manifold directions. With a specific data distribution and model architecture, the paper presents several theorems on the convergence of optimization along directions parallel (i.e., on-manifold) or perpendicular (i.e., off-manifold) to the data manifold. In particular, the convergence along the off-manifold direction was slower by a factor defined by the ratio of the on-manifold variance to the off-manifold variance. Consequently, the paper concludes that variable step sizes (across directions) are required to balance convergence speed and claims that the second-order optimization method already adjusts them. Through experiments, the paper demonstrates the robustness of a KFAC technique (which approximates Hessian computation) compared to naive first-order optimization. The experiments also show that the proposed idea does not improve robustness when the commonly used batch normalization is used.\n\n### Strengths\n1. Still, adversarial machine learning lacks theoretical explanations about why adversarial samples exist. This paper makes a valuable contribution towards them.\n2. The paper presents novel insights into the relationship between on-manifold overlapping and adversarial robustness, showing that there may be an intrinsic vulnerability factor that depends on the data distribution.\n3. The experimental results support the paper’s claim well.\n\n### Weaknesses\nI don’t find any major flaws or weaknesses in this paper. There are some questions or minor changes listed in the **Requested Changes** section.", "claims_and_evidence_yn": "Yes", "claims_explanation": "In the Appendix, the paper provides the proofs for all the theoretical results. The experiments clearly demonstrate the improved robustness achieved by employing KFAC during training.", "audience_yn": "Yes", "audience_explanation": "To the best of my knowledge, this is the first paper that theoretically investigates the overlap along the on-manifold direction as a potential reason for the adversarial vulnerability. The theoretical contribution indicates that vulnerability may be intrinsic to the data manifold geometry, and that special care may be required during training to alleviate ill-conditioning. Practitioners would be interested in this finding to improve the robustness of their training in general.", "requested_changes": "Please go through the paper once again and make sure that the formulae have no typos.\n* **Section 3.2**. Overlapping coefficient. There is a missing parenthesis in the equation for $\\nu$.\n* **Section 4.2**. Effect of $\\nu$. Eq. (4.1) should be Eq. (6) in Theorem 4.2", "broader_impact_concerns": "I don’t see a particular broader impact concern regarding this paper.", "additional_comments": "This paper contains an interesting theoretical explanation of the adversarial example vulnerability. Compared to other theory papers, this paper is of good quality and not too difficult to read. While more research would be needed in this direction, e.g., how to measure the overlap in the training data, this paper provides valuable insights into a new understanding of adversarial examples.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CeMv1rMSsP", "reviewer": "Reviewer_kj1y", "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": "No", "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 authors propose a new mechanism that could contribute to adversarial vulnerability: the slow convergence of the networks in off-manifold directions (i.e., in the directions where the data variance is low). First, they discuss how adversarial vulnerability might arise from this phenomenon. Then, they propose a theoretical models where the slow convergence could occur. Finally, the authors test their intuition empirically by demonstrating a superior adversarial vulnerability in models trained with KFAC.\n\n**Strengths**\n1. The mechanisms of adversarial vulnerability are still not fully understood. And the current paper aims to bridge this gap.\n2. Intuitively, the proposed explanation makes sense.\n3. Theoretical results seem novel.\n\n**Weaknesses**\n1. While the authors discuss how the slow convergence could cause adversarial vulnerability, they do not prove this result theoretically. Moreover, the empirical evidence for this link is only based on Figure 2, which does not constitute a thorough evaluation.\n2. While I understand the intent behind the theoretical analysis, I miss a discussion of the crucial limitations of the proposed framework. In particular, it is not clear how the absence of non-linearities affects the results.\n3. I have concerns about the correctness of Theorem 4.2 (see below).\n4. I do not clearly see the link between Section 4 and Sections 5 and 6 (see below).\n5. Additionally, I think the work would benefit from a more thorough discussion of the literature. First, I believe it is beneficial to discuss the link with the simplicity bias of SGD (e.g., Kalimeris et al., 2019), given that the current paper shows that some complex features are learned later in training. Second, I think it is important to discuss the link with the theoretical literature on shortcut learning (e.g., Hermann et al., 2024), as the outlined mechanisms are quite similar.\n\n**References**\n\nKalimeris, D., Kaplun, G., Nakkiran, P., Edelman, B., Yang, T., Barak, B., & Zhang, H. (2019). SGD on neural networks learns functions of increasing complexity.\n\nHermann, K., Mobahi, H., & Mozer, M. C. (2024). On the Foundations of Shortcut Learning.", "claims_and_evidence_yn": "No", "claims_explanation": "1. About Theorem 4.2. I do not see how Equation (55) implies the lower bound on $T$: it only implies the upper bound. Given that this is one of the main results of the paper, it is crucial to clarify this implication.\n2. (more minor) Additionally, given that the classification result does not depend on the scale of the parameters and only on direction, it would be more appropriate to discuss the directional convergence of $\\theta$. In particular, currently it is impossible to distinguish between the two mechanisms: the domination of on-manifold parameters for classification and the incorrect direction of off-manifold parameters.\n3. About Sections 5 and 6. The authors suggest that KFAC-conditioning should perform better due to the adjustment of step sizes. However, the same could be said about the Adam optimizer; in fact, the adaptivity of step-sizes to different parameters was the initial motivation behind Adam. The point of curvature conditioning is actually two-fold: choose the right learning rates for the parameters and simplify the optimization geometry. The current experiments suggest that, in fact, the geometry of the parameter space appears to play a crucial role, rather than the difference in learning speed between the parameters.", "audience_yn": "Yes", "audience_explanation": "As I outlined earlier, the underlying causes of adversarial vulnerability are still unclear. Thus, a well-supported mechanism could clarify some practically relevant questions about adversarial training of models.", "requested_changes": "1. Please clarify the link between the slow convergence of off-manifold directions and adversarial vulnerability.\n2. Please expand the discussion of the theoretical framework limitations.\n3. Please clarify the proof of Theorem 4.2, and comment on the directional convergence.\n4. Please explain the purpose and scope of Section 6. Specifically, please clarify the link between Sections 4 and 6.\n5. Please add a discussion of the literature on simplicity bias, shortcut mechanisms, and expand the discussion of different mechanisms of adversarial vulnerability.", "broader_impact_concerns": "I do not have concerns about the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sRFoIcyWBp", "reviewer": "Reviewer_kcM2", "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 explores the connection between adversarial robustness and proper model convergence. The authors define a data model that separates between in-manifold and off-manifold. The main thesis of this paper is to state that adversarial fragility corresponds to poor convergence in off-manifold directions of the data.\nThe paper extends the notion of on/off-manifold dimensions from redundant/useful features to high/low variance features, characterizing data distributions as low-dimensional manifolds embedded in higher-dimensional ambient spaces\nFor logistic regression and 2-layer linear networks on a specific uniform data distribution, the authors prove that convergence in the off-manifold is slower than the on-manifold directions causing the loss to appear to converge even if the classifier is far from optimal in the off-manifold directions.\nThe authors additionally propose second order optimisation (specifically KFAC) as a natural way to fix poor convergence in off-manifold directions.\nThey show that second order optimisation improves adversarial robustness in number of empirical settings (MNIST, FashionMNIST, and CIFAR10).", "claims_and_evidence_yn": "Yes", "claims_explanation": "The technical claims of the paper are supported by proofs in the Appendix. While I didn't reproduce the entirety of the proofs they seem to be technically correct and sound. \nThe numerical experiments are shown as the average over 10 different runs and the code used to produce the simulations is publicly available.", "audience_yn": "Yes", "audience_explanation": "I find the paper interesting as it tries to relate adversarial robustness to model convergence, implicitly proposing robustness as a property of poor model convergence. I believe that this interested is shared among other members of the adversarial/robustenss ML community.\n\nThe theoretical analysis, while limited in scope, provides rigorous convergence rates relating to data geometry.\n\nThe batch normalization findings have practical implications for model design.", "requested_changes": "[Required] The authors should explicitly discuss the limitations of extending results from 2-layer linear networks to deep CNNs. Either they could provide theoretical analysis for at least a 2-layer ReLU network showing similar convergence behavior, or more carefully qualify the empirical results as supporting evidence for a hypothesis that requires further theoretical development.\n\n[Required] Improve discussion of related works. The related work section is too brief given the extensive literature on adversarial robustness, with a focus on the theoretical part of it. The additional references that should be added are (but should not be limited to)\n\n- Rice et al., \"Overfitting in Adversarially Robust Deep Learning\" - discusses convergence phenomena in adversarial training\n- Ilyas et al., \"Adversarial examples are not bugs, they are features\" - discusses non-robust features, relevant for the paper's framework\n- Tanay and Griffin, \"A Boundary Tilting Persepective on the Phenomenon of Adversarial Examples\" - proposes that adversarial examples exist when classification boundaries lie close to the data manifold and introduces the concept of \"boundary tilting\"; directly relevant to this paper's geometric analysis of decision boundaries and manifold structure\n- Javanmard and Soltanolkotabi, \"Precise Statistical Analysis of Classification  Accuracies for Adversarial Training'' -  provides insights for a mathematical model under logistic regression\n- Zhang et al., Theoretically Principled Trade-off between Robustness and Accuracy - provides theoretical analysis of the accuracy-robustness tradeoff - \n- Tanner et al., \"A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offs\" - the authors propose a model where utility and variance of each feature are connected (third paragraph of related works)\n- Tsilivis and Kempe, \"What can the neural tangent kernel tell us about adversarial robustness?\" - uses NTK to study adversarial examples and shows robust features correspond to largest eigenvalues learned early in training\n- Tsipras et al. \"Robustness may be at odds with accuracy\" - demonstrates fundamental tension between standard and robust accuracy; relevant to understanding why convergence to different features matters\n\n[Minor] The figures should be improved and given the same sizes.\n\n[Minor] On page 6 after \"Effect of $\\nu$\" I believe it should be Theorem instead of Eq.\n\n[Minor] The equation presenting the on/off-manifold gradient in Theorem 4.1 should be put as a display and not inline.\n\n[Minor] While not always possible, it would be nice if the authors could give a simple sketch of the proof to obtain the result in Theorem 4.1 and give some intuition on what the different terms in the gradient mean\n\n[Minor] It would have been interesting to include discussion (and maybe empirical measurement) of the difference in complexity and speed of the more advanced second order methods.", "broader_impact_concerns": "The paper does not raise significant broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)