Adversarial Training with Large Step Sizes: Implicit Bias, Optimization, and Sharpness

Adversarial Training with Large Step Sizes: Implicit Bias, Optimization, and Sharpness

arXiv:2611.08457v1 [cs.LG] 5 Nov 2026

Yi Feng Aarhus University, Denmark yi.feng@cs.au.dk

Abstract Adversarial Training (AT) is an important method for improving model robustness. We study the dynamics of deterministic Gradient Descent (GD) in AT. Most existing works in this direction focus on the small or vanishing step sizes regime, where GD resembles a continuous-time flow. However, such step sizes can make training inefficient and are rarely used in practice. In this paper, we study the AT dynamics of GD with large constant step sizes. We first study GD in adversarial linear logistic regression, focusing on two aspects: where the model parameters converge (implicit bias) and how quickly the losses decrease (optimization). We then turn to neural networks training and study how the sharpness of losses evolve during AT. Our results advance the understanding of the behaviors of GD with large step sizes in AT and highlight three key differences from its behavior in Standard Training (ST): (i) the implicit bias gap between AT and ST, previously established only for small step sizes, persists for arbitrarily large constant step sizes, (ii) different from ST, there is no uniform rate of convergence for the optimization error in AT, and (iii) sharpness can exhibit two-stage dynamics that differ from the Edge-of-Stability behavior observed in ST.

1

INTRODUCTION

Adversarial training (AT) (Szegedy et al., 2014; Goodfellow et al., 2015; Madry et al., 2018) is widely regarded as the de facto approach for training models that are robust to perturbations of the input data (Athalye et al., 2018). Conceptually, adversarial training recasts empirical risk minimization as minimizing the worst-case loss over an ℓp ball around each training instance, typically choosing p = 2 or p = ∞ to bound the perturbation’s Euclidean norm or per-coordinate magnitude (Pang et al., 2021).

Andrea Paudice Aarhus University, Denmark apaudice@cs.au.dk

In practice, the AT is typically solved using stochastic firstorder methods, where the gradient calculation for the outer parameters relies on an approximate solution to the inner maximization problem (Madry et al., 2018; Wong et al., 2020). While highly effective empirically, analyzing the trajectory and convergence of these algorithms presents substantial challenges. This complexity stems from two primary sources. First, the inherent min-max nature of AT makes its optimization landscape considerably more intricate than that of Standard Training (ST) (Liu et al., 2020). Second, the stochasticity of the optimizer introduces an additional layer of complexity, compounded by the noise and approximations involved in solving the inner problem. To isolate these phenomena and gain a fundamental understanding of the unique features of AT compared to ST, recent literature (Li et al., 2020; Zhang et al., 2020, 2024b; Tsilivis et al., 2024; Lyu and Zhu, 2025) has shifted its focus toward deterministic Gradient Descent (GD), which dates back to the classical work of Cauchy (1847) and forms the foundation of all first-order methods (Nesterov, 2013). In this work, we focus on three complementary aspects of the training dynamics of AT via GD. The implicit bias describes which solutions are selected by the optimization algorithm among those compatible with minimizing the training objective. The optimization error quantifies how quickly the loss approaches its infimum. Finally, sharpness measures the local curvature of the loss landscape along the training trajectory and plays an important role in understanding the optimization dynamics of deep neural networks (Foret et al., 2020). Together, these perspectives address which predictors training selects, how efficiently it reaches low loss, and how the local geometry evolves. While these foundational questions have been extensively probed in ST, existing theoretical work on AT remains severely constrained in its algorithmic scope. Specifically, the vast majority of current literature on the dynamics of AT relies on infinitesimal learning rates, which makes the dynamics become a continuous-time gradient flow (Gu et al., 2021; Tsilivis et al., 2024), or restricts the analysis to small step sizes that are exponentially small in the dimension (Li et al., 2020; Lv and Zhu, 2022; Lyu and Zhu, 2025). Such frame-

Adversarial Training with Large Step Sizes

Figure 1: Illustrations of the main findings of this work. Left: AT and ST have different implicit bias under large constant step sizes. Middle: The ST loss decreases monotonically after a phase transition time τ , whereas the AT loss increases infinitely often. It can also be observed that the AT loss decreases very slowly. Right: ST and AT can exhibit different sharpness evolutions. In particular, ST exhibits the edge-of-stability phenomenon, in which the sharpness oscillates around 2/η, while the sharpness of AT decreases to a value much lower than 2/η.

works fail to capture the behavior of practical optimization regimes, which frequently employ large constant step sizes (Pang et al., 2021) that induce non-monotonic loss behaviors and complex sharpness behaviors like the Edge-of-Stability (EoS) phenomena (Cohen et al., 2021). In this work, we begin by studying the implicit bias and optimization of GD with arbitrary constant step sizes in adversarial linear logistic regression with separable data, whose standard training counterpart is known to exhibit new phenomena absent from the small step size analyses (Wu et al., 2023, 2024). We then turn to an empirical study of adversarial neural network training, studying how the sharpness evolves during adversarial training and comparing it with the EoS phenomena in standard training. 1.1

Our Contributions.

In this work, we focus mainly on ℓ∞ -adversarial attacks since it is the mostly used in practice, and also less theoretically understood compared with other norms (Wang et al., 2025a). Most of our results can also be extended to ℓp -attacks for p ∈ [1, ∞] using the ℓp /ℓq duality, except for the results in Section 4, which relies on properties specific to the ℓ∞ norm. We summarize our main contributions below. Implicit Bias of GD for Adversarial Logistic Regression. For adversarial logistic regression, we prove that, under standard separability assumption on the dataset, GD with arbitrary constant step size converges to a robust maxmargin direction u2,∞ (c) depending on the adversarial radius c > 0. (Theorem 3.1) This behaves differently from ST, where the implicit bias is driven toward the standard max-margin direction on the original data, see the left of Figure 1 for a comparison between these two directions. While this discrepancy was first shown by Li et al. (2020), our work extends their findings in two aspects. First, our result holds for arbitrary constant step sizes, whereas Li et al. (2020) require step sizes exponentially small with dimension. Second, we establish a rate of order ln ln T / ln T for the implicit bias, √ improving over Li et al. (2020) by a factor of order 1/ ln T . In Proposition 3.2 we also show that this rate is tight, thereby providing a comprehensive

characterization of the implicit bias for this problem.

Optimization of GD for Adversarial Logistic Regression. Recent work by Wu et al. (2024) characterizes GD for standard logistic regression with large step sizes through two phases separated by a transition time τ : the loss behaves non-monotonically before τ and monotonically afterward. They further show that this non-monotonic phase is necessary to achieve an accelerated loss convergence rate of Õ(1/T 2 ). Surprisingly, we find that both the existence of the transition time and the acceleration effect of large step size can fail for AT. In fact, the situation of AT is even worse: Theorem 4.2 shows that, for any adversarial radius c > 0 and time budget T , there exists a dataset on which GD’s optimization error is bounded below by a positive constant depending only on c. Moreover, there exist infinitely many steps t where the loss increases from t to t+1. In the middle of Figure 1, we illustrate this phenomenon. These results show that the optimization aspect of GD with large constant step sizes can behave differently in AT than in ST.

Sharpness Evolution in AT. We conduct experiments on AT with neural networks to study how sharpness evolves along the training trajectory. We observe that the sharpness initially increases monotonically and then begins to oscillate with an overall decreasing trend. This behavior remains consistent across different architectures, datasets, and adversarial attack generation approaches. It also differs from the EoS phenomenon in ST of neural network with deterministic GD (Cohen et al., 2021), where sharpness oscillates around 2/η for step size η after an initial monotone increasing stage. The right of Figure 1 present their difference. To develop theoretical understanding of this phenomenon, we analyze a min-max variant of the theoretical model proposed in Ahn et al. (2023). Our analysis shows that the sharpness of this model converges points with a sharpness level significantly below the standard sharpness level 2/η, consistent with our empirical findings. These results show that sharpness evolves very differently in standard and adversarial neural network training.

Yi Feng, Andrea Paudice

1.2

Related Works

Implicit Bias of Linear Logistic Regression. In standard training, Soudry et al. (2018) and Ji and Telgarsky (2018) showed that GD converges to the max-margin direction for linear models on separable data. Subsequent work studied other training algorithms than GD, like steepest descent Gunasekar et al. (2018), momentum methods (Wang et al., 2022; Zhang et al., 2024a), and spectral descent method like Muon (Fan et al., 2026). Most of these analyses require sufficiently small step sizes. An exception is Wu et al. (2023), who established the implicit bias of GD with any constant step size under additional assumptions. For AT, Li et al. (2020) showed that GD for separable adversarial logistic regression converges to robust max-margin direction with exponentially small step size. Subsequent work extended the results on adversarial training to other linear networks and training dynamics (Lv and Zhu, 2022; Tsilivis et al., 2024; Lyu and Zhu, 2025; Lyu et al., 2025). Wang et al. (2025a) derived faster robust margin-maximization rates for other optimization methods than GD, and their analysis does not extend to ℓ∞ adversarial attacks. Optimization with Large Step Sizes. In practice, large step sizes can lead to non-monotonic loss trajectories while preserving favorable long-term behavior. For standard logistic regression, Wu et al. (2024, 2026) showed that large step size gradient descent can accelerate the convergence rate despite oscillations. Cai et al. (2024) extends the results to nonHomogeneous two-layer neural networks. Crawshaw and Liu (2026) established tighter bounds for two-dimensional separable logistic regression. Beyond the convergence rate analysis, Andriushchenko et al. (2023b) showed that large step sizes help neural networks to learn sparse features to improve generalization. Meng et al. (2024) studied the bifurcation behaviors of gradient descent with large step sizes in logistic regression with non-separable dataset. Liang and Montufar (2026) characterized critical step sizes for scalar-vector factorization and showed that large step sizes can induce chaotic optimization dynamics.

2

PRELIMINARIES

2.1

Adversarial Linear Logistic Regression

d Given a dataset {(xi , yi )}N i=1 where (xi , yi ) ∈ R × {±1}, we consider ℓ∞ -adversarial logistic regression with adversarial radius c ≥ 0. The objective is to minimize LAdv (w) over w ∈ Rd , where

LAdv (w) :=

N X i=1

=

N X

⊤

max ln 1 + e−yi (xi +δi ) w

∥δ i ∥∞ ≤c

⊤ ln 1 + e−yi xi w+c∥w∥1 .

i=1

(ℓ∞ -adversarial logistic regression) Here the second equality follows from the duality between ℓ∞ and ℓ1 norms. When c = 0, this reduces to the standard logistic loss L(w). We consider the (sub)gradient descent (GD) dynamics: wt+1 = wt − η ∂w LAdv (wt ).

(GD)

Here η > 0 is the step size. In this work, following Wu et al. (2024), we use the term large step size to refer to any constant step size for the iteration in (GD). We also always select the minimum Euclidean-norm subgradient of ∥w∥1 , whose j-th component is zero whenever wj = 0. This choice is standard in the literature (Shalev-Shwartz and Tewari, 2011; Scetbon and Dohmatob, 2023) and is consistent with PyTorch’s autograd convention. Definition 2.1. For data set {(xi , yi )}N i=1 and adversarial radius c, we define the following notations: • Robust maximum margin: γ2,∞ (c) = max min

min yi ⟨xi + δ i , w⟩

∥w∥2 =1 i∈[N ] ∥δ i ∥∞ ≤c

• Robust max-margin direction: u2,∞ (c) := argmax min

min yi ⟨xi + δ i , w⟩

∥w∥2 =1 i∈[N ] ∥δ i ∥∞ ≤c

Sharpness & Edge-of-Stability. Sharpness plays an important role in neural network training. Cohen et al. (2021) observed the edge-of-stability (EoS) phenomenon, in which sharpness initially increases and then hovers near 2/η. Several works have developed theoretical explanations for these dynamics. For example, Damian et al. (2022) identified the self-stabilization mechanism. Cohen et al. (2025) introduced central flows to model the time-averaged trajectories of oscillatory optimizers. Ahn et al. (2023) connected EoS to generalization performance of neural networks. Another lines of work theoretically studied the EoS through a minimalist example approach (Kreisler et al., 2023; Zhu et al., 2023; Wang et al., 2025b; Liu et al., 2026). Recent works of Islamov et al. (2026) and Song et al. (2026) generalized the EoS to Riemannian and zero-th order optimization settings.

Here, γ2,∞ (c) represents the ℓ2 margin of the extended dataset: {(x′ , y ′ ) | ∃i, ∥x′ − xi ∥∞ ≤ c, y ′ = yi }, which includes all admissible perturbations of the original samples with their labels unchanged, and u2,∞ (c) is the corresponding max-margin direction. We assume that the dataset is robustly linearly separable, meaning that the extended dataset remains linearly separable. This assumption is standard in analyses of (GD) for adversarial training (Charles et al., 2019; Li et al., 2020; Lyu and Zhu, 2025). Assumption 2.2. The dataset {(xi , yi )}N i=1 is robustly linearly separable, i.e., γ2,∞ > 0.

Adversarial Training with Large Step Sizes

2.2

General Adversarial Training

Adversarial training (AT) is a widely used approach to improving the robustness of machine learning models. For ℓ∞ -adversarial attack with radius c, it minimizes LAdv (w), defined as LAdv (w) = gc (xi , w) =

N X

1 gc (xi , w) , N i=1 max ′

∥xi −xi ∥∞ ≤c

where (AT)

g(x′i , w).

Here, g is a loss function, such as mean squared error (MSE), with dependence on the label yi suppressed for simplicity. In practice, a common approximation of the inner maximization problem is the fast gradient sign method (FGSM) (Goodfellow et al., 2015): x′i = xi + c Sign(∇x g(xi , w)) .

(FGSM)

Alternatively, projected gradient descent (PGD) (Madry et al., 2018) approximately solves the inner maximization problem using T projected gradient ascent steps. Starting from xi,0 ∈ Bi , it updates xi,t = ProjBi (xi,t−1 + α Sign(∇x g(xi,t−1 , w))) , (PGD) for t = 1, . . . , T . Here α > 0 is the attack step size and Bi := {x′ : ∥x′ − xi ∥∞ ≤ c}. Then the adversarial example used in training is defined as x′i := xi,T . We define the sharpness at w as the largest eigenvalue of the parameter Hessian evaluated on fixed adversarial examples {x′i }N i=1 , namely, λmax N1

XN i=1

∇2w g(x′i , w)

(sharpness)

Following the standard practice in sharpness analyses of AT, we compute the parameter Hessian while holding the adversarial examples fixed (Yao et al., 2018; Liu et al., 2020; Sitawarin et al., 2021; Wang et al., 2023; Zhong et al., 2025; Walter et al., 2026). Computing the Hessian while accounting for the dependence of x′i on w would require differentiating through the adversarial example generation, making it computationally prohibitive. When c = 0, the notation is same as the sharpness in ST.

3

IMPLICIT BIAS OF ADVERSARIAL LOGISTIC REGRESSION

In this section, we study the implicit bias of gradient descent for ℓ∞ -adversarial logistic regression, while proofs are deferred to Appendix B. Following earlier analyses of implicit bias of standard training (Nacson et al., 2019; Ji and Telgarsky, 2021; Wu et al., 2023), we decompose each

gradient descent iterate of adversarial training into its projection onto the robust max-margin direction and its orthogonal component: wt = vt u2,∞ (c) + rt ,

(orthogonal decomposition)

where vt = ⟨wt , u2,∞ (c)⟩ is the projection of wt onto the robust max-margin direction, and rt is the orthogonal component, i.e., ⟨rt , u2,∞ (c)⟩ = 0. The ratio ∥rt ∥2 /vt determines the convergence rate of implicit bias. We present the main theorem of this section below. Theorem 3.1. Under Assumption 2.2, fix any constant step size η > 0 and let {wt }t≥0 be given by the (GD) dynamic with w0 = 01 . Then, for every t ≥ 1, we have   2 ηγ2,∞ (c) 1 t . (i) vt ≥ γ2,∞ (c) ln 1 + 2 (ii) ∃ Cr > 0, independent of t, s.t. ∥rt ∥2 ≤ Cr ln ln t.
(iii) ∥wwtt∥2 − u2,∞ (c) ≤ 2∥rt ∥2 /vt = O lnlnlnt t . 2

We make the following comments. Previous work of Li et al. (2020) established the implicit bias of (GD) toward the robust max-margin direction u2,∞ (c) under Assumption 2.2 √ and with step size at most of order e−Θ( d) . Theorem 3.1 strengthens their result in two respects. First, it allows any positive constant step size. This is practically relevant because constant step sizes are often chosen empirically, and exponentially small step sizes are rarely used in practice (Pang et al., 2021). Second, it improves the implicit bias convergence rate established by Li et al. (2020) from √ O(1/ ln t) to O(ln ln t/ ln t). The next result shows that this improved rate is tight. Proposition 3.2. The dataset x1 = (1/2, 1/4), x2 = (1/2, 1/2), y1 = y2 = 1, c = 1/4 is robustly linearly separable. The GD trajectory {wt }∞ t=1 on it satisfies lim

ln t

t→∞ ln ln t

wt − u2,∞ (c) = 1. ∥wt ∥2 2

Finally, Theorem 3.1 directly implies a convergence rate of e (1/t) , LAdv (wt ) = O

(1)

e hide the log factors and the dependence on η and where O the other parameters of the problem. Proof Overview of Theorem 3.1. Our analysis builds on the proof strategy of Wu et al. (2023) for ST with large step sizes. We handle the irregularities in adversarial training, such as nonsmoothness, through refined comparison points and tighter cumulative loss difference bounds as explained below. In the following, we illustrate our proof by 1 The zero initialization is assumed only for simplicity, and the results can be extended to any fixed w0 ∈ Rd .

Yi Feng, Andrea Paudice

√ recovering the O(1/ ln t) rate of Li et al. (2020) under arbitrary constant step sizes. We then explain how to refine this argument to obtain the full result. The complete proof is provided in Appendix B. Part (i) of Theorem 3.1 follows from the fact that, at each iteration, there exists at least one data xj whose robust margin min∥δi ∥≤c yj ⟨xj + δ i , wt ⟩ is at most γ2,∞ vt , ensuring sufficient growth of vt (see Proposition B.2, similar argument also used in Lemma B.6 of Wu et al. (2023)). In the following we focus on bounding the term ∥rt ∥2 . Let {w̃t }∞ t=1 be a series of comparison points with known bounds on its norms and loss values. The proof starts from the following comparison inequality, which holds for any η > 0 and is derived using the convexity of ℓ∞ -adversarial logistic regression: X ∥wt − w̃t ∥22 ≤ 2 η (LAdv (w̃s ) − LAdv (ws )) s<t

+

X

∥ws+1 − ws ∥22

(2)

s<t

We choose the comparison points {w̃t } according to ! 2 ηγ2,∞ (c) 1 w̃t = ln 1 + t u2,∞ (c), γ2,∞ (c) 2 whose norm and cumulative adversarial loss are both O(ln t). Intuitively, the growth of wt along u2,∞ (c), measured by vt = ⟨wt , u2,∞P (c)⟩, controls the updates of wt , allowing us to establish s<t ∥ws+1 − ws ∥22 ≤ Kvt for some constant K (see Lemma B.3). Dropping the negative loss term in (2), and using vt = ⟨wt −w̃t , u2,∞ (c)⟩+O(ln t) ≤ ∥wt −w̃t ∥2 +O(ln t), we get ∥rt ∥22 ≤ ∥wt − w̃t ∥22 ≤ O(ln t) + K∥wt − w̃t ∥2 , √ which implies ∥rt ∥2 ≤ ∥wt − w̃t ∥2 = O( ln t). Combing this with the lower √ bound of vt in Part (i) of Theorem 3.1 gives the O(1/ ln t) rate of implicit bias. Note that even in this simple setting, our analysis already differs from that of Wu et al. (2023) for standard training, where additional rank assumptions on the dataset (Assumption 2 & 3 in their work) are used to establish a uniform bound on ∥rt ∥2 . We avoid such assumption by constructing suitable comparison points, which adaptive to the adversarial training process and gives a refined growth rate of ∥rt ∥2 . To obtain the O(ln √ ln t/ ln t) rate, we sharpen the bound on ∥rt ∥2 from O( ln t) in above argument to O(ln ln t) by choosing more suitable comparison points {w̃t }∞ t=1 . The new construction includes vector directions that are orthogonal to u2,∞ (c), thus is more close to the gradient descent trajectories for adversarial logistic regression (see Proposition B.4). We also refine the analysis of the cumulative adversarial loss difference in (2) by retaining the negative

loss term (see Proposition B.6), and use the fact that the cumulative squared updates in (2) are in fact uniformly bounded (see Lemma B.3).

4

OPTIMIZATION OF ADVERSARIAL LOGISTIC REGRESSION

In this section, we study how the ℓ∞ -adversarial logistic regression evolves under GD with arbitrary constant step sizes. It is well-known that gradient descent dynamics with η > 2/L may exhibit non-monotonic loss behavior, where L is the Lipschitz constant of the gradient. Recent work of Wu et al. (2024) characterize these non-monotonic loss behavior in standard linear logistic regression (c = 0). We informally restate their main results below using our notation: Theorem 4.1 (Wu et al. (2024)). Under Assumption 2.2 with c = 0, and normalize the dataset such that ∥xi ∥ ≤ 1 for i ∈ [N ]. For standard logistic regression, gradient descent with a constant step size η > 0 satisfies: • (Phase transition time) There exists some phase transition time τ , depending on the step size η and the dataset, before which the loss can be non-monotonic and after which L(wt+1 ) ≤ L(wt ) for all t ≥ τ . • (Accelerated Convergence Rate) For a sufficiently large time budget T , an appropriate constant step size η = Θ(T ) yields a upper bound L(wT ) = Õ(1/T 2 ). The work of Ji and Telgarsky (2018) also established a Õ(1/T ) loss bound for every fixed step size η ∈ (0, 1] for ST. These results nature questions for AT: (i) does there also exist a phase transition time? (ii) can any constant step size, possibly tuned to the horizon T , that guarantees a fast vanishing loss bound? The following theorem shows that the answer is negative. Theorem 4.2. For any 0 < c < 2 and time budget T > 64/c, there exists a dataset DT whose dimension depends on T and satisfies Assumption 2.2, such that for any step size η > 0, gradient descent dynamics on DT satisfies • (Uniform Constant Lower Bound) The loss function has a uniform constant lower bound LAdv (wT ) ≥ C, where C only depends on c. • (No phase transition time) When gradient descent is run indefinitely on DT , there exist infinitely many t such that LAdv (wt+1 ) > LAdv (wt ). We have two remarks. First, for ST, Theorem 4.1 shows that an appropriately chosen large constant step size can yield a polynomial acceleration of the loss convergence rate, 2 e from the 1/T scale to O(1/T ). In contrast, Theorem 4.2 shows that the convergence is intrinsically non-uniform over the problem class: for every T , there exists a problem for

Adversarial Training with Large Step Sizes

Figure 2: Sharpness evolution across neural network architectures (MLP, CNN, ResNet, and Vision Transformer) and step sizes under standard training (ST) and ℓ∞ -adversarial training on CIFAR-10. Adversarial examples are generated using (FGSM). Except for the MLP at step size 0.005, sharpness under ST initially increases and then oscillates around 2/η, consistent with the edge-of-stability phenomenon (Cohen et al., 2021). Under AT, sharpness also initially increases, but subsequently oscillates with an overall decreasing trend. Opaque curves show smoothed trends for clarity, while semi-transparent curves show the raw values.

which the optimization error at time T is bounded below by a positive real for every constant step size. Note that there is no contradiction with eq. (1), which instead ensures an instance dependent convergence. Second, Theorem 4.1 shows that, in standard training, there exists a transition time before which the loss can be non-monotonic and after which it decreases monotonically. Moreover, Wu et al. (2024) show that this non-monotonic phase is essential for the acceleration obtained with large step sizes. In contrast, Theorem 4.2 shows that in AT such a transition time need not exist: the loss may increase infinitely often. Notably, these increases occur even between differentiable iterates, so the persistent non-monotonicity is not an artifact of evaluating subgradients at nonsmooth points.

nonsmooth ℓ1 term in the adversarial loss causes the last q 2 small coordinates of wt to oscillate around zero, which makes the gradient descent dynamics unstable since it depends on the sign of these small coordinates. Large step sizes can amplify these oscillations, whose combined contribution to the loss outweighs the improvement along the dominant coordinate. More precisely, consider the robust margin min∥δ∥∞ ≤c ⟨x + δ, wt ⟩. For sufficiently large step sizes, the first coordinate of x contributes at most 4ηT to the robust margin, whereas the remaining coordinates contribute at most −ηcT 2 /2 in total. Thus the negative contribution dominates, keeping the adversarial loss large throughout the time budget. The detailed proof of Theorem 4.2 is presented in Appendix C.

Proof Overview of Theorem 4.2. We construct a single sample dataset DT = {(x, 1)}, where

5

2

x = (2, q −1 , . . . , q −1 ) ∈ R1+q , q = 4T 2 . √ We have ∥x∥2 = 5. This data has one dominant coordinate and T 4 small coordinates whose magnitudes are below the adversarial radius. It can be seen that DT is linearly robustly separable for c < 2 with robust max-margin direction u2,∞ (c) = (1, 0, . . . , 0) and γ2,∞ (c) = 2 − c. The

EVOLUTION OF SHARPNESS IN ADVERSARIAL TRAINING

In this section, we study how the sharpness evolve along the adversarial training trajectories. Sharpness, i.e., the maximal eigenvalue of the loss Hessian, plays an important role in neural network training, from guiding the design of optimization algorithms (Foret et al., 2020) to improve under-

Yi Feng, Andrea Paudice

Figure 3: The experimental settings are identical to those in Figure 2 except that adversarial examples are generated by ℓ2 attacks, and adversarial radius is adjusted per common practice.

standing of generalization (Andriushchenko et al., 2023a). The classical descent lemma for GD in optimization problem minθ f (θ) states the loss decreases monotonically under GD if the sharpness remains below 2/η along the optimization process, where η is the step size (Nesterov, 2013). However, in neural networks training, people usually employ large step sizes in the regime where the loss exhibits non-monotonic behavior. Cohen et al. (2021) observe that sharpness can evolve in two stages during standard training of neural network with deterministic gradient descent: • Progressive Sharpening: If the sharpness is less than 2/η, it tends to increase monotonically. • Edge-of-stability: The sharpness oscillate around 2/η. It is natural to ask whether AT of neural networks exhibits a similar sharpness evolution to standard training. Our experiments reveal a different pattern: after an initial increase similar to progressive sharpening, adversarial sharpness oscillates with an overall decreasing trend. We report these experimental results in Section 5.1. In Section 5.2, we provide theoretical support by showing that adversarial training can reduce sharpness in an adversarial variant of a minimalist example introduced by Ahn et al. (2023).

5.1

Experimental Results

In Figure 2 and Figure 3, we present our experiments on the sharpness evolution of AT under MLP, CNN, ResNet and Vision Transformer (ViT) on the CIFAR-10 dataset. The training algorithm is the deterministic gradient descent on CIFAR-10. We adopt the architectures and implementation of Cohen et al. (2021), keeping our setup consistent with prior work on edge-of-stability. We also use the Mean Squared Error (MSE) loss as it can most align with the edgeof-stability phenomena in ST. The experimental details are provided in Appendix D.2. Our main observation is that the sharpness evolution of AT follows a very different two-stage dynamics as with ST: • Stage I: In this stage, sharpness tends to increase monotonically, similar to the progressive sharpening stage in standard training reported by Cohen et al. (2021). • Stage II: After Stage I, sharpness begins to oscillate. Although the oscillation patterns may vary across different settings, they share a common feature: sharpness exhibits an overall decreasing trend over longer timescales. More experiments are reported in Appendix D.3, and the experimental results are consistent with the two-stage dynamics as described above. One major property of the

Adversarial Training with Large Step Sizes

predictor fx,y (z) = y(x + z). Ahn et al. (2023) studied the following gradient descent dynamic when c = 0: (xt+1 , yt+1 ) = (xt , yt ) − η ∂Lc (xt , yt ), with p (x0 , y0 ) = (2 + δ)/η (x̃, ỹ). (EoS initialization)

Figure 4: Sharpness evolution under randomly perturbed losses resembles that of standard training.

sharpness in AT is that it tracks the curvature of a timevarying loss function, as the adversarial examples x′i change at each iteration (see Section 2.2). However, our experiments suggest that time variation alone does not explain the observed dynamics. In Figure 4, we track sharpness along standard CNN training trajectories using loss functions with small random perturbations instead of adversarial attack on the training data at each iteration. The resulting sharpness evolution remains similar to that of standard training and differs markedly from that of adversarial training. Together, these results suggest that the observed two-stage behavior stem inherently from the adversarial training dynamics and persist across different experimental settings. 5.2

Theoretical Investigation on a Minimalist Example

Due to the complexity of neural network training dynamics, theoretical studies of EoS often adopt a minimalist example approach. In the following, we study an adversarial variant of a model introduced by Ahn et al. (2023) to investigate the EoS phenomenon in standard training. Let ℓ(s) be the Huber loss function:   s2 1 1{|s|>1} , (Huber loss) ℓ(s) := 1{|s|≤1} + |s| − 2 2 which is widely used for regression (Meyer, 2021). The theoretical model proposed by Ahn et al. (2023) is the twodimensional function ℓ(xy) for (x, y) ∈ R2 . One main reason for the difference between the sharpness behavior of ST and AT is is the special min-max structure of AT. Motivated by this observation, we study the following adversarial variant of ℓ(xy) for an adversarial radius c ≥ 0, which recovers the the standard training objective of Ahn et al. (2023) when c = 0: min Lc (x, y) =

(x,y)∈R2

min max ℓ ((x + δ)y)

(x,y)∈R2 |δ|≤c

(Adversarial Huber loss) This objective can be viewed as adversarial regression on a single example with input z = 0 and target 0, using the

Here δ > 0, ỹ > x̃ > 0 and ỹ 2 − x̃2 = 1. This initialization condition distinguishes gradient descent from continuous-time gradient flow. The sharpness of (Adversarial Huber loss) at the t-th iteration of gradient descent is conventionally defined as the maximum eigenvalue
of the Hessian, given by λct := λmax ∇2 Lc (xt , yt ) . Proposition 5.1. Consider the GD with EoS initialization. There exist constants η0 > 0, depending only on δ, x̃, ỹ and c such that under mild boundary-avoidance assumption as described in Assumption D.3, for every 0 < η ≤ η0 , the limiting sharpness λc∞ := lim supt→∞ λct satisfies: • Standard training (Ahn et al., 2023, Theorem 2): if c = 0, then η2 − O(1) ≤ λ0∞ ≤ η2 . • Adversarial training: if c > 0, then λc∞ = O(η + c2 ). Proposition 5.1 reveals a transition in sharpness evolution between ℓ(xy) and its min-max variant. The adversarial dynamics converge to points with sharpness O(η + c2 ), much smaller than the edge-of-stability level 2/η for η , c ≪ 1, which is typical in practice. This is consistent with the experimental results reported in Section 5.1. The difference arises from changes in both the structure of the minimizer set and the training dynamics induced by adversarial perturbations. When c = 0, all points (x, y) satisfying xy = 0 are global minimizers, and the trajectory converges to (0, y∞ ) with y∞ ̸= 0 and sharpness close to 2/η. When c > 0, the minimizer set remains large: every point (x, 0) is a global minimizer. The sharpness at such a point is (|x|+c)2 , which can be arbitrarily large. However, the training dynamics en√ sure that the limiting point satisfies x∞ = O( η). The detailed proof is given in Appendix D.

6

CONCLUSION AND FUTURE DIRECTION

In this paper, we studied the dynamics of deterministic gradient descent with large step sizes in adversarial training, focusing on three aspects: implicit bias and optimization in adversarial logistic regression, and sharpness evolution in adversarial neural network training. Our results reveal that the effects of large step sizes in adversarial training can differ substantially from those in standard training. An interesting direction for future work is to find a general mechanism, possibly analogous to the self-stabilization mechanism in standard training (Damian et al., 2022), that explains the decreasing trend in sharpness observed in Section 5.

Yi Feng, Andrea Paudice

References Ahn, K., Bubeck, S., Chewi, S., Lee, Y. T., Suarez, F., and Zhang, Y. (2023). Learning threshold neurons via edge of stability. Advances in Neural Information Processing Systems, 36:19540–19569. Andriushchenko, M., Croce, F., Müller, M., Hein, M., and Flammarion, N. (2023a). A modern look at the relationship between sharpness and generalization. arXiv preprint arXiv:2302.07011.

Foret, P., Kleiner, A., Mobahi, H., and Neyshabur, B. (2020). Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412. Goodfellow, I. J., Shlens, J., and Szegedy, C. (2015). Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR). Gu, H., Guo, X., and Li, X. (2021). Adversarial training for gradient descent: Analysis through its continuous-time approximation. arXiv preprint arXiv:2105.08037.

Andriushchenko, M., Varre, A. V., Pillaud-Vivien, L., and Flammarion, N. (2023b). Sgd with large step sizes learns sparse features. In International Conference on Machine Learning, pages 903–925. PMLR.

Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. (2018). Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832–1841. PMLR.

Athalye, A., Carlini, N., and Wagner, D. (2018). Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning (ICML).

Islamov, R., Crawshaw, M., Cohen, J., and Gower, R. (2026). Non-euclidean gradient descent operates at the edge of stability. arXiv preprint arXiv:2603.05002.

Boyd, S. and Vandenberghe, L. (2004). Convex optimization. Cambridge university press. Cai, Y., Wu, J., Mei, S., Lindsey, M., and Bartlett, P. (2024). Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast optimization. Advances in Neural Information Processing Systems, 37:71306–71351. Cauchy, A.-L. (1847). Méthode générale pour la résolution des systèmes d’équations simultanées. Comptes Rendus de l’Académie des Sciences, 25:536–538.

Ji, Z. and Telgarsky, M. (2018). Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300. Ji, Z. and Telgarsky, M. (2021). Characterizing the implicit bias via a primal-dual analysis. In Algorithmic Learning Theory, pages 772–804. PMLR. Kreisler, I., Nacson, M. S., Soudry, D., and Carmon, Y. (2023). Gradient descent monotonically decreases the sharpness of gradient flow solutions in scalar networks and beyond. In International Conference on Machine Learning, pages 17684–17744. PMLR.

Charles, Z., Rajput, S., Wright, S., and Papailiopoulos, D. (2019). Convergence and margin of adversarial training on separable data. arXiv preprint arXiv:1905.09209.

Li, Y., Fang, E. X., Xu, H., and Zhao, T. (2020). Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations (ICLR).

Cohen, J., Damian, A., Talwalkar, A., Kolter, J. Z., and Lee, J. D. (2025). Understanding optimization in deep learning with central flows. In The Thirteenth International Conference on Learning Representations.

Liang, S. and Montufar, G. (2026). Gradient descent with large step sizes: Chaos and fractal convergence region. In The Fourteenth International Conference on Learning Representations.

Cohen, J., Kaur, S., Li, Y., Kolter, J. Z., and Talwalkar, A. (2021). Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations.

Liu, C., Salzmann, M., Lin, T., Tomioka, R., and Süsstrunk, S. (2020). On the loss landscape of adversarial training: Identifying challenges and how to overcome them. Advances in Neural Information Processing Systems, 33:21476–21487.

Crawshaw, M. and Liu, M. (2026). Tight bounds for logistic regression with large stepsize gradient descent in low dimension. In Hanneke, S. and Lattimore, T., editors, Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 1575–1610. PMLR. Damian, A., Nichani, E., and Lee, J. D. (2022). Selfstabilization: The implicit bias of gradient descent at the edge of stability. arXiv preprint arXiv:2209.15594. Fan, C., Schmidt, M., and Thrampoulidis, C. (2026). Implicit bias of spectral descent and muon on multiclass separable data. Advances in Neural Information Processing Systems, 38:39622–39669.

Liu, L., Zhang, Z., Du, S., and Zhao, T. (2026). A minimalist example of edge-of-stability and progressive sharpening. Advances in Neural Information Processing Systems, 38:14938–14975. Lv, B. and Zhu, Z. (2022). Implicit bias of adversarial training for deep neural networks. In International Conference on Learning Representations. Lyu, B., Wang, H., Wang, Z., and Zhu, Z. (2025). Effects of momentum in implicit bias of gradient flow for diagonal linear networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 19242–19250.

Adversarial Training with Large Step Sizes

Lyu, B. and Zhu, Z. (2025). Analyzing the implicit bias of adversarial training from a generalized margin perspective. IEEE Transactions on Pattern Analysis and Machine Intelligence.

Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2014). Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR).

Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018). Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations.

Tsilivis, N., Frank, N., Srebro, N., and Kempe, J. (2024). The price of implicit bias in adversarially robust generalization. Advances in Neural Information Processing Systems (NeurIPS).

Meng, S. Y., Orvieto, A., Cao, D. Y., and De Sa, C. (2024). Gradient descent on logistic regression with non-separable data and large step sizes. arXiv preprint arXiv:2406.05033.

Walter, N. P., Adilova, L., Vreeken, J., and Kamp, M. (2026). When flatness does (not) guarantee adversarial robustness. In International Conference on Learning Representations, volume 2026, pages 20330–20360.

Meyer, G. P. (2021). An alternative probabilistic interpretation of the huber loss. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 5257–5265. IEEE.

Wang, B., Meng, Q., Zhang, H., Sun, R., Chen, W., Ma, Z.-M., and Liu, T.-Y. (2022). Does momentum change the implicit regularization on separable data? Advances in Neural Information Processing Systems, 35:26764– 26776.

Nacson, M. S., Lee, J., Gunasekar, S., Savarese, P. H. P., Srebro, N., and Soudry, D. (2019). Convergence of gradient descent on separable data. In Chaudhuri, K. and Sugiyama, M., editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3420–3428. PMLR. Nesterov, Y. (2013). Introductory lectures on convex optimization: A basic course. Springer Science & Business Media. Pang, T., Yang, X., Dong, Y., Su, H., and Zhu, J. (2021). Bag of tricks for adversarial training. In International Conference on Learning Representations (ICLR). Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press. Scetbon, M. and Dohmatob, E. (2023). Robust linear regression: Gradient-descent, early-stopping, and beyond. In International Conference on Artificial Intelligence and Statistics, pages 11583–11607. PMLR. Shalev-Shwartz, S. and Tewari, A. (2011). Stochastic methods for <i>l</i>₁-regularized loss minimization. Journal of Machine Learning Research, 12(52):1865–1892. Sitawarin, C., Chakraborty, S., and Wagner, D. (2021). Sat: Improving adversarial training via curriculum-based loss smoothing. In Proceedings of the 14th ACM Workshop on Artificial Intelligence and Security, pages 25–36.

Wang, G., Hu, Z., Gentile, C., Muthukumar, V., and Abernethy, J. (2025a). Faster margin maximization rates for generic and adversarially robust optimization methods: G. wang et al. Mathematical Programming, pages 1–41. Wang, Y., Xu, Z., Zhao, T., and Tao, M. (2025b). Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult. Journal of Machine Learning Research, 26(273):1–68. Wang, Z., Ding, N., Levinboim, T., Chen, X., and Soricut, R. (2023). Improving robust generalization by direct pac-bayesian bound minimization. In 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 16458–16468. IEEE. Wong, E., Rice, L., and Kolter, J. Z. (2020). Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations (ICLR). Wu, J., Bartlett, P. L., Telgarsky, M., and Yu, B. (2024). Large stepsize gradient descent for logistic loss: Nonmonotonicity of the loss improves optimization efficiency. In The Thirty Seventh Annual Conference on Learning Theory, pages 5019–5073. PMLR. Wu, J., Braverman, V., and Lee, J. D. (2023). Implicit bias of gradient descent for logistic regression at the edge of stability. Advances in Neural Information Processing Systems, 36:74229–74256.

Song, M., Zhang, L., Li, B., He, N., Muehlebach, M., and Oh, S. (2026). Zeroth-order optimization at the edge of stability. arXiv preprint arXiv:2604.14669.

Wu, J., Marion, P., and Bartlett, P. (2026). Large stepsizes accelerate gradient descent for regularized logistic regression. Advances in Neural Information Processing Systems, 38:104485–104525.

Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. (2018). The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1–57.

Yao, Z., Gholami, A., Lei, Q., Keutzer, K., and Mahoney, M. (2018). Hessian-based analysis of large batch training and robustness to adversaries. Advances in neural information processing systems, 31.

Yi Feng, Andrea Paudice

Zhang, C., Zou, D., and Cao, Y. (2024a). The implicit bias of adam on separable data. Advances in Neural Information Processing Systems, 37:23988–24021. Zhang, K., Wang, Y., and Arora, R. (2024b). Stability and generalization of adversarial training for shallow neural networks with smooth activation. In Advances in Neural Information Processing Systems (NeurIPS). Zhang, Y., Plevrakis, O., Du, S. S., Li, X., Song, Z., and Arora, S. (2020). Over-parameterized adversarial training: An analysis overcoming the curse of dimensionality. In Advances in Neural Information Processing Systems (NeurIPS). Zhong, X., Huang, Y., and Liu, C. (2025). Understanding and improving fast adversarial training against l_0 bounded perturbations. In Belgrave, D., Zhang, C., Lin, H., Pascanu, R., Koniusz, P., Ghassemi, M., and Chen, N., editors, Advances in Neural Information Processing Systems, volume 38, Main Conference, pages 38523–38555. Curran Associates, Inc. Zhu, X., Wang, Z., Wang, X., Zhou, M., and Ge, R. (2023). Understanding edge-of-stability training dynamics with a minimalist example. In The Eleventh International Conference on Learning Representations.

Adversarial Training with Large Step Sizes: Implicit Bias, Optimization, and Sharpness Supplementary Materials

A

MORE BACKGROUNDS

In the following, without loss of generality, we assume yi = 1 for all i ∈ [N ] in what follows since if yi = −1, we can equivalently take the negative of xi as input. We introduce the following decomposition of Rd , which was motivated by Wu et al. (2023): F : Rd → Rd × Rd   x → ⟨x, u2,∞ (c)⟩u2,∞ (c), Proju⊥ (x) . (c) 2,∞

(3)

wt = vt u2,∞ (c) + rt ,

(4)

We write

where ⟨rt , u2,∞ (c)⟩ = 0. We have −∂w LAdv (wt ) = −

N X

∂w ln 1 + exp(−x⊤ i wt + c∥wt ∥1 )

i=1

=

N X

λi,t (xi − c st ) ,

i=1

where st = (st,j )di=1 ∈ ∂∥wt ∥1 ,

exp(−x⊤ 1 i wt + c∥wt ∥1 ) = > 0. ⊤ ⊤ 1 + exp(−xi wt + c∥wt ∥1 ) 1 + exp(xi wt − c∥wt ∥1 )

λi,t =

(5)

Thus the (GD) dynamics can be written as wt+1 = wt + η

N X

λi,t (xi − c st )

(6)

i=1

A.1

Some useful Lemmas

d ⊤ Lemma A.1. Assume the dataset {(xi , yi )}N i=1 is linearly separable, i.e., ∃ w ∈ R such that yi w xi > 0 for all i ∈ [N ]. If c < γ∞ , we have γ2,∞ (c) > 0. ⊤ Proof. Let u∞ = argmax∥w∥1 =1 mini∈[n] x⊤ i w. By definition, we have γ∞ = mini∈[N ] xi u∞ .

Moreover, we have γ2,∞ (c) ≥ min

⊤

min (xi + δi ) u∞

i∈[N ] ∥δi ∥∞ ≤c

= min x⊤ i u∞ − c∥u∞ ∥1 i∈[N ]

= γ∞ − c > 0. This completes the proof.

(Since min x⊤ i u∞ = γ∞ and ∥u∞ ∥1 = 1) i∈[N ]

Yi Feng, Andrea Paudice

Lemma A.2. Let D = {(x, 1)} be a one-sample dataset and let 0 ≤ c < ∥x∥∞ . Then for this data set, we have
|x| − c1 +

γ2,∞ (c) =

, 2

where the absolute value and positive part are applied coordinate wise. Proof. For every u ∈ Rd , we have

min ⟨x + δ, u⟩ = x⊤ u − c∥u∥1 ,

∥δ∥∞ ≤c

where the minimum is attained by δj = −c sign(uj ). Therefore, x⊤ u − c∥u∥1 ≤

d X

d X

(|xj | − c)|uj | ≤

j=1

(|xj | − c)+ |uj | ≤ ∥(|x| − c1)+ ∥2 ∥u∥2 ,

j=1

where the final inequality uses the Cauchy-Schwarz inequality. For ∥u∥2 = 1, the last expression equals ∥(|x| − c1)+ ∥2 . Since c < ∥x∥∞ , this quantity is positive, and equality is attained by u = u∗ , where u∗j =

A.2

sign(xj )(|xj | − c)+ , ∥(|x| − c1)+ ∥2

j ∈ [d].

ℓ∞ -Robust Support Vector Machine

The ℓ∞ -robust support vector machine (SVM) problem can be formulated as min

1

w∈Rd 2

∥w∥22 ,

such that

min ⟨xi + δ i , w⟩ ≥ 1

(ℓ∞ -Robust SVM)

∥δ i ∥∞ ≤c

Let ŵ(c) be the solution of (ℓ∞ -Robust SVM). We have u2,∞ = ŵ(c)/∥ŵ(c)∥2 , and γ2,∞ (c) = 1/∥ŵ(c)∥2 . We use zi (c) to denote the worst-case adversarial perturbation that an adversary can construct on xi against the classifier parameterized by ŵ(c): zi (c) := xi − c s∗ ,

where

s∗ ∈ ∂∥ŵ(c)∥1 .

(7)

We choose s∗ jointly with the KKT multipliers so that the representation in Proposition A.3 below holds, and fix this choice throughout the subsequent analysis. The adversarial support vectors are defined as: S(c) := {i ∈ [N ] | ⟨zi (c), u2,∞ (c)⟩ = γ2,∞ (c)}

(Adversarial Support Vectors)

∗ Proposition P A.3. [Boyd and Vandenberghe (2004)] There exists a subgradient s ∈ ∂∥ŵ(c)∥1 , such that we have ŵ(c) = i∈S(c) αi zi (c), and αi ≥ 0.

The main property we need for the (ℓ∞ -Robust SVM) is the following: Lemma A.4. For every r ⊥ u2,∞ (c), there exists a j ∈ S(c) with αj > 0 such that ⟨zj (c), r⟩ ≤ 0. Proof. For r ⊥ u2,∞ (c), we have 0=

X ⟨u2,∞ (c), r⟩ = ⟨ŵ(c), r⟩ = αi ⟨zi (c), r⟩. γ2,∞ (c) i∈S(c)

If every inner product with αi > 0 were positive, then X αi ⟨zi (c), r⟩ = i∈S(c)

X i∈S(c): αi >0

contradicting the preceding equality. This finished the proof.

αi ⟨zi (c), r⟩ > 0,

Adversarial Training with Large Step Sizes

B

PROOF OF SECTION 3

B.1

Preliminary estimate on the convergence rate of implicit bias √ Lemma B.1. Let M = maxi∈[N ] ∥xi ∥2 + c d, then we have ∥xi − cst ∥2 ≤ M.

(8)

∥wt ∥2 ≤ ηN M t.

(9)

and

Proof. Since the norm of subgradient satisfies |st,j | ≤ 1, we have √ ∥xi − cst ∥2 ≤ ∥xi ∥2 + c∥st ∥2 ≤ ∥xi ∥2 + c d ≤ M. Moreover, ∥wt ∥2 =

t−1 X (ws+1 − ws ) s=0

≤ 2

t−1 X ∥ws+1 − ws ∥2 ≤ ηN M t. s=0

Proposition B.2 (Growth of vt ). For every t ≥ 0, we have vt+1 − vt ≥ ηγ2,∞ (c)

N X i=1

λi,t ≥

ηγ2,∞ (c) −γ2,∞ (c)vt e . 2

In particular, above recursion gives vt > 0, and ! 2 ηγ2,∞ (c) ln 1 + t , vt ≥ γ2,∞ (c) 2 1

1

e−γ2,∞ (c)vt ≤

ηγ 2 (c) 1 + 2,∞ t 2

≤

C1 . t+1

(10)

n o where C1 = max 1, ηγ 2 2 (c) , which is independent of t. 2,∞

Proof. Recall in (5), we define st = (st,j )di=1 ∈ ∂∥wt ∥1 . Since |st,j | ≤ 1, we have ⟨st , u2,∞ (c)⟩ =

d X

st,j u2,∞,j (c) ≤

d X

|st,j | |u2,∞,j (c)| ≤

j=1

j=1

d X

|u2,∞,j (c)| = ∥u2,∞ (c)∥1 .

(11)

j=1

For every i, we have ⟨xi − cst , u2,∞ (c)⟩ = x⊤ i u2,∞ (c) − c⟨st , u2,∞ (c)⟩ (11)

≥ x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1

  ≥ min x⊤ k u2,∞ (c) − c∥u2,∞ (c)∥1 = γ2,∞ (c). k∈[N ]

(12)

Projecting the update into the direction of u2,∞ yields vt+1 − vt = ⟨wt+1 − wt , u2,∞ (c)⟩ =η

N X

(13)

λi,t ⟨xi − cst , u2,∞ (c)⟩

i=1 (12)

≥ η

N X i=1

λi,t γ2,∞ (c) = ηγ2,∞ (c)

N X i=1

λi,t > 0.

(14)

Yi Feng, Andrea Paudice

Since v0 = 0, (14) gives vt > 0 for t ≥ 1. Apply Lemma A.4 to rt and choose its index j according to Lemma A.4. Recall we define s∗ ∈ ∂∥ŵ(c)∥1 in (7). The same coordinatewise argument gives ∗

⟨s , wt ⟩ ≤

d X

|s∗k | |wt,k | ≤ ∥wt ∥1 .

(15)

k=1

Consequently, (15)

⊤ ∗ x⊤ j wt − c∥wt ∥1 ≤ xj wt − c⟨s , wt ⟩ = ⟨zj (c), wt ⟩

= vt ⟨zj (c), u2,∞ (c)⟩ + ⟨zj (c), rt ⟩ = γ2,∞ (c)vt + ⟨zj (c), rt ⟩ ≤ γ2,∞ (c)vt .

(Since Lemma (A.4))

(16)

Hence 1 + exp(x⊤ j wt − c∥wt ∥1 ) ≤ 1 + exp(γ2,∞ (c)vt ), 1 1 λj,t = . ≥ ⊤ 1 + exp(γ2,∞ (c)vt ) 1 + exp(xj wt − c∥wt ∥1 )

(17)

Since γ2,∞ (c)vt ≥ 0, we have 1 exp(−γ2,∞ (c)vt ) 1 = ≥ exp(−γ2,∞ (c)vt ), 1 + exp(γ2,∞ (c)vt ) 1 + exp(−γ2,∞ (c)vt ) 2 (14)

vt+1 − vt ≥ ηγ2,∞ (c)

N X

λi,t ≥ ηγ2,∞ (c)λj,t

(17),(18) ηγ 2,∞ (c)

≥

i=1

2

(18)

exp(−γ2,∞ (c)vt ).

(19)

For x ≥ 0, we have the following general inequality: ex − 1 ≥ x.

(20)

Applying this with x = γ2,∞ (c)(vt+1 − vt ) ≥ 0 gives h i eγ2,∞ (c)vt+1 − eγ2,∞ (c)vt = eγ2,∞ (c)vt eγ2,∞ (c)(vt+1 −vt ) − 1 (20)

≥ eγ2,∞ (c)vt γ2,∞ (c)(vt+1 − vt )

(19)

≥ eγ2,∞ (c)vt γ2,∞ (c)

2 ηγ2,∞ (c) ηγ2,∞ (c) −γ2,∞ (c)vt e . = 2 2

(21)

Summing the increments from s = 0 to s = t − 1 gives eγ2,∞ (c)vt = eγ2,∞ (c)v0 +

t−1 h 2 i (21) X (c) ηγ2,∞ eγ2,∞ (c)vs+1 − eγ2,∞ (c)vs ≥ 1 + t, 2 s=0

(22) (23)

which implies ! 2 ηγ2,∞ (c) vt ≥ ln 1 + t , γ2,∞ (c) 2 1

e−γ2,∞ (c)vt ≤

1 ηγ 2 (c) 1 + 2,∞ t 2

Finally, we have ( ) 2 2 ηγ2,∞ (c) ηγ2,∞ (c) t+1 1+ t ≥ min 1, (t + 1) = . 2 2 C1 This proves all the stated bounds.

.

Adversarial Training with Large Step Sizes

Lemma B.3 (Preliminary estimates). Let ! 2 ηγ2,∞ (c) w̃t = ŵ(c) ln 1 + t . 2

(24)

There are fixed C2 , C3 , C4 > 0 such that, for all t ≥ 0, ∥rt ∥2 ≤ C2

p

ln(t + 2),

N X

∞ X ∥ws+1 − ws ∥22 ≤ C4 .

λi,t ≤ C3 (t + 1)−3/4 ,

s=0

i=1

Moreover, LAdv (wt ) → 0 as t → ∞. Proof. Since ŵ(c) = u2,∞ (c)/γ2,∞ (c), we have ! 2 ηγ2,∞ (c) 1 vt+1 ln 1 + − 2 (t + 1) ⟨wt+1 − w̃t+1 , ŵ(c)⟩ = (c) γ2,∞ (c) γ2,∞ 2 " !# 2 (10) ηγ2,∞ (c) 1 1 vt+1 − ≥ 0. ln 1 + (t + 1) = γ2,∞ (c) γ2,∞ (c) 2

(25)

Moreover, we have  w̃t+1 − w̃t = ŵ(c) ln 



2 ηγ2,∞ (c) (t + 1) 2 , 2 ηγ2,∞ (c) 1+ t 2

1+

which implies  ⟨wt+1 − w̃t+1 , w̃t+1 − w̃t ⟩ = ln 



2 ηγ2,∞ (c) (25) (t + 1) 2  ⟨wt+1 − w̃t+1 , ŵ(c)⟩ ≥ 0. 2 ηγ2,∞ (c) 1+ t 2

1+

(26)

Expanding the square, we have 2

∥wt+1 − w̃t ∥22 = ∥(wt+1 − w̃t+1 ) + (w̃t+1 − w̃t )∥2 = ∥wt+1 − w̃t+1 ∥22 + 2⟨wt+1 − w̃t+1 , w̃t+1 − w̃t ⟩ + ∥w̃t+1 − w̃t ∥22 (26)

≥ ∥wt+1 − w̃t+1 ∥22 .

(27)

Since (ℓ∞ -adversarial logistic regression) is convex and (wt − wt+1 )/η is a subgradient at wt , we have 1 LAdv (w̃t ) ≥ LAdv (wt ) + ⟨wt − w̃t , wt+1 − wt ⟩. η Rearranging and multiplying by η > 0 yields   ⟨wt − w̃t , wt+1 − wt ⟩ ≤ η LAdv (w̃t ) − LAdv (wt ) .

(28)

Combining this with the preceding square expansion, (27)

2

∥wt+1 − w̃t+1 ∥22 ≤ ∥wt+1 − w̃t ∥22 = ∥(wt − w̃t ) + (wt+1 − wt )∥2 = ∥wt − w̃t ∥22 + 2⟨wt − w̃t , wt+1 − wt ⟩ + ∥wt+1 − wt ∥22 (28)   ≤ ∥wt − w̃t ∥22 + 2η LAdv (w̃t ) − LAdv (wt ) + ∥wt+1 − wt ∥22 . Since the scalar multiplying ŵ(c) in w̃t is nonnegative, we have ! ! 2 2  ηγ2,∞ (c)  ⊤ ηγ2,∞ (c) (24) ⊤ xi w̃t − c∥w̃t ∥1 = ln 1 + t xi ŵ(c) − c∥ŵ(c)∥1 ≥ ln 1 + t , 2 2

(29)

(30)

Yi Feng, Andrea Paudice

where the last inequality comes from ŵ(c) is a solution of (ℓ∞ -Robust SVM). Moreover, we have LAdv (w̃t ) =

N X

N N 2  X  ηγ2,∞ (c) (30) X ⊤ ⊤ e− ln(1+ 2 t) ln 1 + e−xi w̃t +c∥w̃t ∥1 ≤ e−xi w̃t +c∥w̃t ∥1 ≤

i=1

i=1

i=1

N

= 1+

2 ηγ2,∞ (c) t 2

,

(31)

where the second inequality used ln(1 + x) ≤ x, x ≥ 0. Also, since 0 < λi,t < 1 and w0 = 0, we have N X

∥wt+1 − wt ∥2 = η

i=1

Then

N X

≤η

λi,t (xi − cst ) 2

i=1

N X

!2

λi,t ∥xi − cst ∥2 ≤ ηM

N X

λi,t .

(32)

i=1

P

i λi,t ≤ N implies

∥wt+1 − wt ∥22 ≤ η 2 M 2

≤ η2 N M 2

λi,t

i=1

N X

λi,t .

(33)

i=1

Summing the recursion inequality of vt in (14) and using v0 = 0 gives ηγ2,∞ (c)

t−1 X N X

t−1 (14) X

λi,s ≤

s=0 i=1

(vs+1 − vs ) = vt ,

and

s=0 t−1 X

(33)

∥ws+1 − ws ∥22 ≤ η 2 N M 2

s=0

t−1 X N X

λi,s ≤

s=0 i=1

ηN M 2 vt . γ2,∞ (c)

(34)

Now sum the squared-distance recursion. Since w0 = w̃0 = 0 and the loss is nonnegative, ∥wt − w̃t ∥22 =

t−1 X

∥ws+1 − w̃s+1 ∥22 − ∥ws − w̃s ∥22

s=0 (29)

≤ 2η

t−1 X

LAdv (w̃s ) − 2η

s=0 (31),(34)

≤

2ηN

t−1 X

LAdv (ws ) +

s=0 t−1 X

s=0 2

1

2 ηγ2,∞ (c) s s=0 1 + 2

here we use a rather loss bound by ignoring the effect of the 2η

t−1 X ∥ws+1 − ws ∥22

+

ηN M vt , γ2,∞ (c)

(35)

Pt−1

s=0 LAdv (ws ) term.

For t ≥ 1, we have t−1 X

1

2 ηγ2,∞ (c) s s=0 1 + 2

=1+

t−1 X

1

2 ηγ2,∞ (c) s s=1 1 + 2

Z t ≤1+

dx

2 ηγ2,∞ (c) 0 1+ x 2

! 2 ηγ2,∞ (c) =1+ 2 ln 1 + t . ηγ2,∞ (c) 2 2

(36)

It follows that ∥wt − w̃t ∥22

(35),(36)

≤

! 2 ηγ2,∞ (c) 4N ηN M 2 2ηN + 2 ln 1 + t + vt . γ2,∞ (c) 2 γ2,∞ (c)

(37)

Adversarial Training with Large Step Sizes

The right side also bounds the zero initial distance at t = 0. To eliminate vt , apply Cauchy–Schwarz and ∥u2,∞ (c)∥2 = 1, we get vt = ⟨wt − w̃t , u2,∞ (c)⟩ + ⟨w̃t , u2,∞ (c)⟩ ! 2 (c) ηγ2,∞ ln 1 + t . ≤ ∥wt − w̃t ∥2 + γ2,∞ (c) 2 1

(24)

(38)

Substitution gives ∥wt − w̃t ∥22

(37),(38)

≤

+

! 2 ηγ2,∞ (c) 4N + ηN M 2 ln 1 + t 2ηN + 2 (c) γ2,∞ 2

ηN M 2 ∥wt − w̃t ∥2 . γ2,∞ (c)

(39)

The inequality 2ab ≤ a2 + b2 gives ηN M 2 1 1 ∥wt − w̃t ∥2 ≤ ∥wt − w̃t ∥22 + γ2,∞ (c) 2 2



ηN M 2 γ2,∞ (c)

2 .

(40)

Subtracting the 21 ∥wt − w̃t ∥22 term from both sides and multiplying by two yields ∥wt − w̃t ∥22



(39),(40)

≤

4ηN +

ηN M 2 γ2,∞ (c)

2

! 2 ηγ2,∞ (c) 2(4N + ηN M 2 ) + t . ln 1 + 2 (c) γ2,∞ 2

(41)

In the following, we want to rewrite (41) in the form ∥wt − w̃t ∥22 ≤ C22 ln(t + 2), with C2 be some constant independent of t. For brevity, set  2 2 ηγ2,∞ (c) ηN M 2 2(4N + ηN M 2 ) a := , A := 4ηN + . , B := 2 (c) 2 γ2,∞ (c) γ2,∞ Then (41) reads ∥wt − w̃t ∥22 ≤ A + B ln(1 + at). For every t ≥ 0, we have 1 + at ≤ max{1, a}(t + 2) and ln(t + 2) ≥ ln 2. Consequently,   A + B ln (max{1, a}) A + B ln(1 + at) ≤ B ln(t + 2) + A + B ln max{1, a} ≤ B + ln(t + 2). ln 2 Thus, defining the positive constant C2 by C22 := B +

A + B ln (max{1, a}) , ln 2

(42)

we obtain ∥wt − w̃t ∥22 ≤ C22 ln(t + 2),

t ≥ 0.

(43)

Since w̃t is parallel to u2,∞ (c), we have 

wt − w̃t

ηγ 2

ln(1 + 2,∞ 2 = vt − γ2,∞ (c)

(4),(24)

(c)

t)

  u2,∞ (c) + rt .

(44)

Taking the square of both side on (44), the cross term in its squared norm vanishes because ⟨u2,∞ (c), rt ⟩ = 0. Therefore we get  2 2 ηγ2,∞ (c) ln(1 + t) (44) 2  ∥u2,∞ (c)∥22 + ∥rt ∥22 ≥ ∥rt ∥22 , ∥wt − w̃t ∥22 = vt − γ2,∞ (c)

Yi Feng, Andrea Paudice

which implies (43)

∥rt ∥2 ≤ ∥wt − w̃t ∥2 ≤ C2

p

ln(t + 2).

(45)

The triangle inequality and Cauchy–Schwarz give √

⊤ x⊤ i wt − c∥wt ∥1 − xi w̃t − c∥w̃t ∥1 ≥ −∥xi ∥2 ∥wt − w̃t ∥2 − c d ∥wt −w̃t ∥2 ≥ −M ∥wt − w̃t ∥2 .

(46)

Combining above bounds, we get x⊤ i wt − c∥wt ∥1

(46),(30) (45)

≥

! 2 p ηγ2,∞ (c) ln 1 + t − M C2 ln(t + 2), 2

(47)

which gives LAdv (wt ) ≤

N X

e

−x⊤ i wt +c∥wt ∥1

(47) N exp(M C2

≤

λi,t ≤

i=1

N X

(47) N exp(M C2

⊤

ln(t + 2))

ηγ 2 (c) 1 + 2,∞ t 2

i=1 N X

p

e−xi wt +c∥wt ∥1 ≤

p

ln(t + 2))

ηγ 2 (c) t 1 + 2,∞ 2

i=1

,

.

(48)

2 Now we want to bound the right hand side term of (48) more explicit in terms of t. Since C1 = max{1, 2/(ηγ2,∞ (c))}, we have 2 (1 + ηγ2,∞ (c)t/2)−1 ≤ C1 /(t + 1). √ √ Moreover, the inequality ( x/2 − M C2 )2 ≥ 0 gives M C2 x ≤ x/4 + M 2 C22 for every x ≥ 0. Applying this with x = ln(t + 2) yields

N exp(M C2

p

ln(t + 2)) (10) N C1 ≤ exp 2 ηγ2,∞ (c) t+1 1+ t



1 ln(t + 2) + M 2 C22 4



2

2

2

2

2

21/4 N C1 eM C2 C3 N C1 eM C2 (t + 2)1/4 ≤ = , = 3/4 t+1 (t + 1) (t + 1)3/4

(49)

where C3 = 21/4 N C1 exp(M 2 C22 ) is independent of t. In particular, we get 0 ≤ LAdv (wt ) ≤

N X

C3 , (t + 1)3/4

λi,t ≤

i=1

C3 . (t + 1)3/4

(50)

Finally, since ∞ X

(t + 1)

−3/2

=1+

t=0

∞ X

k

−3/2

Z ∞ ≤1+

x−3/2 dx = 3,

1

k=2

we get ∞ ∞ N X X X (32) ∥wt+1 − wt ∥22 ≤ η 2 M 2 λi,t t=0

t=0

i=1

where c4 = 3η 2 M 2 C32 . This finished the proof of Lemma B.3.

!2

(50)

≤ η 2 M 2 C32

∞ X (t + 1)−3/2 ≤ C4 , t=0

(51)

Adversarial Training with Large Step Sizes

Lemma B.3 already implies a preliminary convergence rate for implicit bias. Indeed, recalling wt = vt u2,∞ (c) + rt with rt ⊥ u2,∞ (c), we have ∥wt ∥2 ≥ vt > 0 for t ≥ 1. The triangle inequality also gives ∥wt ∥2 − vt ≤ ∥rt ∥2 . Hence, ∥rt ∥2 wt ∥wt ∥2 − vt 2∥rt ∥2 − u2,∞ (c) ≤ + ≤ ∥wt ∥2 ∥wt ∥2 ∥wt ∥2 vt 2

≤

p   2γ2,∞ (c)C2 ln(t + 2) 1   √ = O , ηγ 2 (c) ln t t ln 1 + 2,∞ 2

t → ∞.

This convergence rate proved above is the same as that of Theorem 3.4 in Li et al. (2020). In the following, we will improve this bound by choosing more suitable comparing points than w̃t . B.2

Contraction of comparison point

For r ⊥ u2,∞ (c), define X

pi (r) = ⟨xi , r⟩ − c

X

Sign(u2,∞,j (c))rj − c

j: u2,∞,j (c)̸=0

|rj |.

(52)

j: u2,∞,j (c)=0

The quantity pi (r) represents the change in the robust margin of xi induced by adding the orthogonal component r to vu2,∞ (c), provided that the signs on the nonzero coordinates of u2,∞ (c). Specifically, if v > 0 and
this addition preserves
Sign vu2,∞,j (c) + rj = Sign u2,∞,j (c) for every j with u2,∞,j (c) ̸= 0, then i h i h

⊤ pi (r) = x⊤ i vu2,∞ (c) + r − c vu2,∞ (c) + r 1 − xi vu2,∞ (c) − c vu2,∞ (c) 1 . We define F (r) =

X

e−pi (r) .

i∈S(c)

For each fixed r ⊥ u2,∞ (c), the sign preservation condition above holds for all sufficiently large v, which will be the case of (GD) dynamics as shown by Proposition B.2. The contribution of the robust support vectors to the adversarial logistic loss then satisfies   X ln 1 + e−γ2,∞ (c)v−pi (r) ≈ e−γ2,∞ (c)v F (r), for sufficient large v. i∈S(c)

Thus, for fixed r and sufficiently large v, F (r) captures the contribution of the component r of parameter w = vu2,∞ (c) + r to the adversarial logistic loss. Moreover, It can also be seen that (52)

|pi (r)| ≤ |⟨xi , r⟩| + c

X

|rj | + c

j: u2,∞,j (c)̸=0

X

|rj |

≤ ∥xi ∥2 ∥r∥2 + c∥r∥1 ≤ M ∥r∥2 .

(53)

j: u2,∞,j (c)=0

The following Propoaition is an extension of Lemma 3.3 in Ji and Telgarsky (2018) to the adversarial loss. Proposition B.4 (Adversarial version of Ji and Telgarsky (2018, Lemma 3.3)). There are fixed r̄, v ⊥ u2,∞ (c) and C5 , C6 ≥ 1, independent of t, such that qε = r̄ + v ln(C5 /ε) satisfies, for 0 < ε ≤ 1,
F (qε ) ≤ inf F (r) + ε, ∥qε ∥2 ≤ C6 1 + ln(1/ε) . (54) r⊥u2,∞ (c)

Let H := {r : ⟨r, u2,∞ (c)⟩ = 0},

F∗ := inf F (r). r∈H

To specify what r̄ and v must accomplish, choose a sequence r(n) ∈ H such that F (r(n) ) → F∗ ,

as

n → ∞,

and

F (r(n) ) ≤ N + 1.

Yi Feng, Andrea Paudice

Such a sequence exists because F∗ ≤ F (0) = |S(c)| ≤ N . Each term e−pi (r subsequence, all these terms have limits: e−pi (r

(n)

)

→ ℓi ,

(n)

)

belongs to [0, N + 1]. After passing to a

i ∈ S(c).

Let I := {i ∈ S(c) : ℓi > 0}, bi := − ln ℓi for i ∈ I. Then as n → ∞, we have pi (r(n) ) → bi ∈ R which also implies F∗ = that

P

i∈I e

−bi

for

pj (r(n) ) → +∞

i ∈ I,

for

j ∈ S(c) \ I,

. We will construct a convex polyhedral cone K ⊆ H and two vectors r̄, v ∈ K such

(1). each pi (r) is linear on K, (2). pi (r̄) = bi for i ∈ I, (3). pi (v) = 0 for i ∈ I and pj (v) ≥ 1 for j ∈ S(c) \ I. Condition (2) ensures that r̄ realizes the finite limiting values bi for i ∈ I. Together with linearity in (1), condition (3) ensures that moving from r̄ along v preserves these values while increasing pj for every j ∈ S(c) \ I. If S(c) \ I ̸= ∅, then F (r̄) > F∗ because the corresponding exponential terms are still positive at r̄; moving along v makes these terms tend to zero. We first establish the claimed bounds assuming this construction, and then prove that such K, r̄, and v exist. Proof of Proposition B.4 assuming conditions (1)-(3). Since K is a convex cone, r̄ + τ v ∈ K for every τ ≥ 0. Since p(r) is linear on K, we have i ∈ I,

and

pj (r̄ + τ v) = pj (r̄) + τ pj (v)

F (r̄ + τ v) − F∗ =

X

e−pj (r̄)−τ pj (v) ≤ e−τ

pi (r̄ + τ v) = bi

for

for

j ∈ S(c) \ I.

Consequently,

j∈S(c)\I

X

e−pj (r̄) ,

j∈S(c)\I

where the last inequality used condition (3). For 0 < ε ≤ 1, consider qε = r̄ + v ln(C5 /ε), where C5 ≥ 1 will be determined below. Since ln(C5 /ε) ≥ 0, the preceding estimate gives F (qε ) − F∗ ≤

ε C5

X

e−pj (r̄) .

(55)

j∈S(c)\I

Moreover, the triangle inequality yields  
∥qε ∥2 ≤ ∥r̄∥2 + ∥v∥2 ln C5 + ∥v∥2 ln(1/ε) ≤ ∥r̄∥2 + (1 + ln C5 )∥v∥2 1 + ln(1/ε) . Thus by choosing

C5 := max

  

X

1,

e−pj (r̄)

j∈S(c)\I

 

,

and

C6 := ∥r̄∥2 + (1 + ln C5 )∥v∥2 ,



and take them into (55) and (56), we get F (qε ) − F∗ ≤ ϵ,

and

∥qε ∥2 ≤ C6 (1 + ln(1/ϵ)),

which finished the proof. Lemma B.5. The required construction of K, r̄ and v in conditions (1)-(3) exists.

(56)

Adversarial Training with Large Step Sizes

Proof. First, we select a region where the absolute values in pi (r) can be replaced by linear expressions. There are finitely many sign choices for the coordinates rj with uj = 0. Hence a further subsequence of r(n) lies in one fixed convex polyhedral cone K := {r ∈ H : σj rj ≥ 0 for every j with uj = 0} , σj ∈ {−1, 1}. In particular, inf r∈K F (r) = F∗ . Indeed, since F (r(n) ) → F∗ , the function values along any subsequence converge to the same limit. For r ∈ K, we have X X pi (r) = x⊤ Sign(u2,∞,j )rj − c σj rj , i r−c j:u2,∞,j ̸=0

j:u2,∞,j =0

which is a linear function of r. In the following, we will use the elementary fact that a linear image of a polyhedron is a polyhedron and hence is closed, e.g., Rockafellar (1970, Theorem 19.3). We first show the existence of r̄. If I = ∅, take r̄ = 0. Otherwise, the set {(pi (r))i∈I : r ∈ K} is a closed polyhedral image. Since it contains the sequence (pi (r(n) ))i∈I → (bi )i∈I , it also contains the limit. Therefore some r̄ ∈ K satisfies pi (r̄) = bi for i ∈ I. We then show the existence of v̄. If I = S(c), take v = 0. Otherwise, all pj (r(n) ) with j ∈ S(c) \ I tend to +∞. Passing to a further subsequence and relabeling, arrange that pj (r(n) ) ≥ n

for j ∈ S(c) \ I.

Set d(n) := r(n) /n. The cone property and linearity on K give d(n) ∈ K,

pi (d(n) ) → 0

for

i ∈ I,

pj (d(n) ) ≥ 1

for j ∈ S(c) \ I.

Thus {d(n) } make all pi , i ∈ I, arbitrarily close to zero, while keeping pj ≥ 1 for every j ∈ S(c) \ I. To find a vector v ∈ K satisfying pi (v) = 0 for every i ∈ I while retaining pj (v) ≥ 1 for every j ∈ S(c) \ I, consider the polyhedron D := {r ∈ K : pj (r) ≥ 1 for every j ∈ S(c) \ I} . If I ̸= ∅, the image {(pi (r))i∈I : r ∈ D} is closed. It contains (pi (d(n) ))i∈I → 0, so it contains 0. Hence there exist some v ∈ D satisfies pi (v) = 0 for every i ∈ I. If I = ∅, any d(n) serves as v. In both cases, pi (v) = 0

for

i ∈ I,

pj (v) ≥ 1

for j ∈ S(c) \ I.

This proves the required existence. B.3

Cumulative loss comparison

For T ≥ 3, fix the vectors from Lemma B.4 and set
qT = r̄ + v ln C5 ln(T + 2) , l m 2 tT = e(ln ln(T +2)) .

(57) (58)

Proposition B.6. There exist an integer T0 ≥ 3 and nonnegative constants C̃, which is independent of T , such that, for every integer T ≥ T0 , we have tT < T and T −1 X t=tT

  LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) ≤ C̃.

(59)

Yi Feng, Andrea Paudice

Lemma B.7 (Loss decomposition). For every integer T ≥ 3 and t ≥ 0, define
E1,t,T = e−γ2,∞ (c)vt F (qT ) − F (rt ) , X 1 e−2pi (rt ) , E2,t = e−2γ2,∞ (c)vt 2 i∈S(c) X 
 E3,t,T = exp −vt x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1 − pi (qT ) .

(60) (61) (62)

i∈S(c) /

There exists an integer T0 ≥ 3, independent of T , such that tT < T for every integer T ≥ T0 and, for tT ≤ t < T , LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) ≤ E1,t,T + E2,t + E3,t,T .

(63)

Proof. For T ≥ 3, 0 < 1/ ln(T + 2) < 1. Substituting ε = 1/ ln(T + 2) into the construction in Proposition B.4 gives   C5 (57) = r̄ + v ln(C5 ln(T + 2)) = qT , qε = r̄ + v ln 1/ ln(T + 2) (54) 1 F (qT ) ≤ inf F (r) + , ln(T + 2) r⊥u2,∞ (c)   (54) 1 ∥qT ∥2 ≤ C6 1 + ln = C6 (1 + ln ln(T + 2)). (64) 1/ ln(T + 2) For every r ⊥ u2,∞ (c), we have F (qT ) − F (r) ≤ F (qT ) −

(64)

F (s) ≤

inf s⊥u2,∞ (c)

1 . ln(T + 2)

(65)

By the definition of tT , we have 2

(58)

2

2

e(ln ln(T +2)) ≤ tT < e(ln ln(T +2)) + 1,

2

tT + 2 < e(ln ln(T +2)) + 3 ≤ 4e(ln ln(T +2)) .

(66)

The preliminary bound in Proposition B.3 for rT gives (45)

∥rtT ∥2 ≤ C2

p

(66)

ln(tT + 2) ≤ C2

p

(ln ln(T + 2))2 + ln 4.

(67)

For the component along the u2,∞ (c) direction, we have 2 ηγ2,∞ (c) vtT ≥ ln 1 + tT γ2,∞ (c) 2 (10)

1

!

2 (66) (ln ln(T + 2))2 + ln(ηγ2,∞ (c)/2)

≥

γ2,∞ (c)

.

(68)

Once the last numerator is positive, these inequalities imply ∥qT ∥2 (64),(68) γ2,∞ (c)C6 (1 + ln ln(T + 2)) ≤ 2 (c)/2) → 0, vtT (ln ln(T + 2))2 + ln(ηγ2,∞

as

T → ∞.

(69)

Since ∥u2,∞ (c)∥2 = 1, the vector u2,∞ (c) has at least one nonzero coordinate. Consequently, min j: u2,∞,j (c)̸=0

|u2,∞,j (c)| > 0.

Thus we can choose a fixed integer T0 ≥ 3 such that, for every integer T ≥ T0 , we have tT < T and ! 2 ηγ2,∞ (c) γ2,∞ (c)C6 (1 + ln ln(T + 2)) 2 (ln ln(T + 2)) + ln > 0, min |u2,∞,j (c)|. 2 (c)/2) < 2 (ln ln(T + 2))2 + ln(ηγ2,∞ j: u2,∞,j (c)̸=0

(70)

Adversarial Training with Large Step Sizes

Moreover, since we have proved vt is an increasing function in Proposition B.2, thus for t ≥ tT , we have vt ≥ vtT . Hence, at each such nonzero coordinate of u2,∞ (c), we have Sign(u2,∞,j (c))(vt u2,∞,j (c) + qT,j ) = vt |u2,∞,j (c)| + Sign(u2,∞,j (c))qT,j ≥ vtT |u2,∞,j (c)| − ∥qT ∥2

(69),(70)

>

0.

It follows that Sign(vt u2,∞,j (c) + qT,j ) = Sign(u2,∞,j (c))

if u2,∞,j (c) ̸= 0.

(71)

For the actual iterate, |a| ≥ Sign(u2,∞,j (c))a at each nonzero coordinate of the direction. Thus X X ∥wt ∥1 = |vt u2,∞,j (c) + rt,j | + |rt,j | j: u2,∞,j (c)̸=0

j: u2,∞,j (c)=0

X

≥ vt ∥u2,∞ (c)∥1 +

X

Sign(u2,∞,j (c))rt,j +

j: u2,∞,j (c)̸=0

|rt,j |.

(72)

j: u2,∞,j (c)=0

For the comparison point, the sign equality makes the corresponding bound an equality: X (71) ∥vt u2,∞ (c) + qT ∥1 = vt ∥u2,∞ (c)∥1 + Sign(u2,∞,j (c))qT,j + j: u2,∞,j (c)̸=0

X

|qT,j |.

(73)

j: u2,∞,j (c)=0

Combining above estimate on the ℓ1 norm of wt and comparison point vt u2,∞ (c) + qT , we get (72)

⊤ ⊤ x⊤ i wt − c∥wt ∥1 ≤ vt xi u2,∞ (c) + xi rt − cvt ∥u2,∞ (c)∥1 X −c Sign(u2,∞,j (c))rt,j − c j: u2,∞,j (c)̸=0

X

|rt,j |

j: u2,∞,j (c)=0

(52)

= vt x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1 + pi (rt ),

(74)

and x⊤ i (vt u2,∞ (c) + qT ) − c∥vt u2,∞ (c) + qT ∥1

(73),(52)

=

vt x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1 + pi (qT ).

(75)

By the definition of the support set S(c), for every i ∈ S(c), we have x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1 = γ2,∞ (c). Since the logistic loss is decreasing in the margin, we get   (74)   ⊤ ln 1 + e−xi wt +c∥wt ∥1 ≥ ln 1 + e−γ2,∞ (c)vt −pi (rt ) 1 ≥ e−γ2,∞ (c)vt −pi (rt ) − e−2γ2,∞ (c)vt −2pi (rt ) , 2

(76)

where the last inequality used ln(1 + x) ≥ x − x2 /2 for x > 0. Discarding the adversarial losses contributed by data points not in S(c) gives   X ⊤ LAdv (wt ) ≥ ln 1 + e−xi wt +c∥wt ∥1 i∈S(c) (76)

≥

 X  1 e−γ2,∞ (c)vt −pi (rt ) − e−2γ2,∞ (c)vt −2pi (rt ) 2

i∈S(c)

= e−γ2,∞ (c)vt F (rt ) − E2,t

(77)

For the adversarial loss at the comparison point, use ln(1 + x) < x for x > 0, we get N (75) X

LAdv (vt u2,∞ (c) + qT ) ≤


 exp −vt x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1 − pi (qT )

i=1

= e−γ2,∞ (c)vt F (qT ) + E3,t,T .

(78)

Yi Feng, Andrea Paudice

Combining the two bounds in (78) and (77) gives     LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) ≤ e−γ2,∞ (c)vt F (qT ) + E3,t,T − e−γ2,∞ (c)vt F (rt ) − E2,t   = e−γ2,∞ (c)vt F (qT ) − F (rt ) + E2,t + E3,t,T = E1,t,T + E2,t + E3,t,T .

In the following Lemma B.8 to Lemma B.10, we will bound the E1,t,T , E2,t and E3,t,T terms by some absolute constant separately. Lemma B.8. Let T0 be as in Lemma B.7. There is a constant C7 ≥ 0, independent of T , such that, for every T ≥ T0 , we have T −1 X E1,t,T ≤ C7 . t=tT

Proof. Since rt ⊥ u2,∞ (c),
(65) e−γ2,∞ (c)vt (10) C1 e−γ2,∞ (c)vt F (qT ) − F (rt ) ≤ ≤ . ln(T + 2) (t + 1) ln(T + 2)

(79)

Consequently, we have T −1 X

E1,t,T =

t=tT

T −1 X

(79) e−γ2,∞ (c)vt F (qT ) − F (rt ) ≤

t=tT

T −1 X C1 1 ln(T + 2) t=t t + 1 T

C1 (1 + ln T ) ≤ ln(T + 2) ≤ 2C1 = C7 , where the second inequality used

(80)

PT −1

1 t=0 t+1 ≤ 1 + ln T .

Lemma B.9. Let T0 be as in Lemma B.7. There is a constant C8 ≥ 0, independent of T , such that, for every T ≥ T0 , we have T −1 X E2,t ≤ C8 . t=tT

Proof. By Proposition B.3, we have √ (53) (45) e−2pi (rt ) ≤ e2|pi (rt )| ≤ e2M ∥rt ∥2 ≤ e2M C2 ln(t+2) . p √ √ The inequality ( x/2 − 2M C2 )2 ≥ 0 gives 2M C2 x ≤ x/2 + 2M 2 C22 . Therefore 1 −2γ2,∞ (c)vt X −2pi (rt ) (10),(81) N C12 2M C2 √ln(t+2) e e ≤ e 2 2(t + 1)2

(81)

i∈S(c)

2

2

N C12 e2M C2 (t + 2)1/2 ≤ 2(t + 1)2 C8 = , 3(t + 1)3/2 2

(82)

2

where C8 = N C12 e2M C2 . Summing the above bound yields T −1 X t=tT

E2,t =

T −1 X

T −1 1 −2γ2,∞ (c)vt X −2pi (rt ) (82) C8 X e e ≤ (t + 1)−3/2 2 3 t=tT t=tT i∈S(c)   Z ∞ C8 C8 x−3/2 dx = (1 + 2) = C8 . ≤ 1+ 3 3 1

(83)

Adversarial Training with Large Step Sizes

Lemma B.10. Let T0 be as in Lemma B.7. There is a constant C9 ≥ 0, independent of T , such that, for every T ≥ T0 , T −1 X

E3,t,T ≤ C9 .

t=tT

Proof. If [N ] \ S(c) = ∅, then E3,t,T = 0 and we take C9 = 0. For the remaining case, define   ⊤ xi u2,∞ (c) − c∥u2,∞ (c)∥1 − 1 > 0. δ = min γ2,∞ (c) i∈S(c) /

(84)

For such an index in [N ] \ S(c), we have 
 (84),(53) −(1+δ)γ2,∞ (c)vt M ∥qT ∥2 exp −vt x⊤ e ≤ e i u2,∞ (c) − c∥u2,∞ (c)∥1 − pi (qT ) = e−γ2,∞ (c)vt

≤

C11+δ eM ∥qT ∥2 . (t + 1)1+δ

Moreover, we have the following bound: Z ∞ ∞ ∞ Z t+1 X X t−δ −1−δ −1−δ (t + 1) ≤ x dx = x−1−δ dx = T δ t tT t=t t=t T

1+δ M ∥qT ∥2 (10) e

(85)

(66) 1

≤

δ

2

e−δ(ln ln(T +2)) .

(86)

T

It follows that T −1 X

T −1 X

E3,t,T =

t=tT

X


 exp −vt x⊤ i u2,∞ (c) − c∥u2,∞ (c)∥1 − pi (qT )

t=tT i∈S(c) / (85)

≤ N C11+δ eM ∥qT ∥2

∞ X

(t + 1)−1−δ

t=tT (86),(64) N C 1+δ 1

≤

δ

  exp M C6 (1 + ln ln(T + 2)) − δ(ln ln(T + 2))2 .

(87)

Completing the square in the exponent gives M C6 (1 + ln ln(T + 2)) − δ(ln ln(T + 2))2  2 M C6 M 2 C62 M 2 C62 − δ ln ln(T + 2) − ≤ M C6 + . = M C6 + 4δ 2δ 4δ

(88)

Thus we can choose C9 as    1+δ M 2 C62  N C1 exp M C6 + , [N ] \ S(c) ̸= ∅, C9 = δ 4δ  0, [N ] \ S(c) = ∅.

(89)

Now we can prove Proposition B.6. Proof of Proposition B.6. Take T0 from Lemma B.7. Then tT < T and (63) holds for every T ≥ T0 and tT ≤ t < T . Summing this inequality and applying Lemmas B.8, B.9, and B.10 gives T −1 X

  LAdv (vt u2,∞ (c) + qT ) − LAdv (wt )

t=tT

≤

T −1 X t=tT

E1,t,T +

T −1 X t=tT

E2,t +

T −1 X t=tT

E3,t,T ≤ C7 + C8 + C9 .

Yi Feng, Andrea Paudice

The constants are independent of T , as required. B.4

Refined estimate on ∥rt ∥2

In the following, we provide a refined estimate of ∥rt ∥p 2 based on the estimates established in Section B.3. In particular, we show that the preliminary estimates of ∥rt ∥2 with O( ln(t + 2)) can be improved to O(ln ln t) Proposition B.11. There is a fixed Cr > 0 which is independent of t, such that ∥rt ∥2 ≤ Cr ln ln t,

t ≥ 3.

(90)

Proof. Fix T0 , C7 , C8 , C9 from Proposition B.6, and let T ≥ T0 . Let the vector qT be the same as (57). Subtracting the decompositions at two consecutive times gives (4)

rt+1 − rt = wt+1 − wt − (vt+1 − vt )u2,∞ (c), ⟨rt − qT , u2,∞ (c)⟩ = ⟨rt , u2,∞ (c)⟩ − ⟨qT , u2,∞ (c)⟩ = 0,

(91)

where the second equality comes from both rt and qT are orthogonal to u2,∞ (c). Thus, we have ⟨rt − qT , rt+1 − rt ⟩ = ⟨rt − qT , wt+1 − wt ⟩ − (vt+1 − vt )⟨rt − qT , u2,∞ (c)⟩ = ⟨rt − qT , wt+1 − wt ⟩.

(92)

The comparison point vt u2,∞ (c) + qT differs from the trajectories of {wt } generated by (GD) in that (4)

vt u2,∞ (c) + qT − wt = vt u2,∞ (c) + qT − (vt u2,∞ (c) + rt ) = qT − rt .

(93)

Consequently, the subgradient inequality reads  LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) ≥ =

wt − wt+1 , vt u2,∞ (c) + qT − wt η

1 ⟨rt − qT , wt+1 − wt ⟩, η

(94)

where the first inequality used the fact that LAdv is a convex function. Combining the two identities in (92) and (94), and multiplying by η yields   ⟨rt − qT , rt+1 − rt ⟩ ≤ η LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) .

(95)

Since rt+1 − rt ⊥ u2,∞ (c), we get (91)

2

∥wt+1 − wt ∥22 = ∥(vt+1 − vt )u2,∞ (c) + (rt+1 − rt )∥2 = (vt+1 − vt )2 + ∥rt+1 − rt ∥22 ≥ ∥rt+1 − rt ∥22 .

(96)

Expanding the distance to the fixed qT gives 2

∥rt+1 − qT ∥22 = ∥(rt − qT ) + (rt+1 − rt )∥2 = ∥rt − qT ∥22 + 2⟨rt − qT , rt+1 − rt ⟩ + ∥rt+1 − rt ∥22 (95),(96)   ≤ ∥rt − qT ∥22 + 2η LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) + ∥wt+1 − wt ∥22 .

(97)

Adversarial Training with Large Step Sizes

Summing (97) from t = tT to T − 1 gives: ∥rT − qT ∥22 − ∥rtT − qT ∥22 =

T −1 X



∥rt+1 − qT ∥22 − ∥rt − qT ∥22



t=tT (97)

≤ 2η

T −1 X

−1   TX LAdv (vt u2,∞ (c) + qT ) − LAdv (wt ) + ∥wt+1 − wt ∥22

t=tT

t=tT

(59)

≤ 2η(C7 + C8 + C9 ) +

∞ X

∥wt+1 − wt ∥22

t=0 (51)

≤ 2η(C7 + C8 + C9 ) + C4 := C10 .

(98)

∥rT ∥2 ≤ ∥rT − qT ∥2 + ∥qT ∥2 (98) q ≤ ∥rtT − qT ∥22 + C10 + ∥qT ∥2 p ≤ ∥rtT − qT ∥2 + C10 + ∥qT ∥2 p ≤ ∥rtT ∥2 + 2∥qT ∥2 + C10 p p (67),(64) ≤ C2 (ln ln(T + 2))2 + ln 4 + 2C6 (1 + ln ln(T + 2)) + C10 .

(99)

Then the triangle inequality gives

Since ln ln(T + 2) > 0, we have p √ √ (ln ln(T + 2))2 + ln 4 ≤ ln ln(T + 2) + ln 4 ≤ (1 + ln 4)(1 + ln ln(T + 2)),

which gives p √ (99)   ∥rT ∥2 ≤ C2 (1 + ln 4) + 2C6 + C10 (1 + ln ln(T + 2))   p √   1 + ln 2 ln ln(T + 2) ≤ C2 (1 + ln 4) + 2C6 + C10 1 + ln ln 3 = C11 (1 + ln ln(T + 2)) ≤ C̃r ln ln(T )

for

T ≥ T0 .

(100)

For the remaining integers 3 ≤ t < T0 , orthogonality and the initial update bound give q (9) ηN M T0 ∥rt ∥2 ≤ vt2 + ∥rt ∥22 = ∥wt ∥2 ≤ ηN M t ≤ ηN M T0 ≤ ln ln t ≤ Ĉr ln ln t. ln ln 3 Then we can choose Cr = max{C̃r , Ĉr }, this proves the bound for every t ≥ 3. B.5

Proof of Theorem 3.1

Proof of Theorem 3.1. According to Lemma B.3, we have LAdv (wt ) → 0 as t → ∞. We also have q vt ≤ ∥wt ∥2 = vt2 + ∥rt ∥22 ≤ vt + ∥rt ∥2 . Here vt > 0. Subtracting vt yields 0 ≤ ∥wt ∥2 − vt ≤ ∥rt ∥2 . The normalized difference is   wt vt rt (4) − u2,∞ (c) = − 1 u2,∞ (c) + . ∥wt ∥2 ∥wt ∥2 ∥wt ∥2

(101)

(102)

Yi Feng, Andrea Paudice

Applying the triangle inequality and then the two lemmas, (102) vt ∥rt ∥2 wt ≤ − u2,∞ (c) − 1 ∥u2,∞ (c)∥2 + ∥wt ∥2 ∥w ∥ ∥w t 2 t ∥2 2 ∥wt ∥2 − vt + ∥rt ∥2 = ∥wt ∥2 (101) 2∥rt ∥2 ≤ vt 2γ2,∞ (c)Cr ln ln t ≤ , ηγ 2 (c) ln(1 + 2,∞ t) 2

(103)

where the last inequality comes from Proposition B.2 and Proposition B.11. Moreover, we have 2 ηγ2,∞ (c) t ln 1 + 2

!

(

2 ηγ2,∞ (c) ≥ min 1, 2

) ln(1 + t) =

ln(1 + t) ln t ≥ . C1 C1

(104)

Since the denominator is positive, we have (103),(104) ln ln t wt ≤ 2γ2,∞ (c)C1 Cr − u2,∞ (c) =O ∥wt ∥2 ln t 2



ln ln t ln t

 .

This finished the proof. B.6

Proof of Proposition 3.2

Proposition B.12. Let d = N = 2, y1 = y2 = 1, and 

1 c= , 4

x1 =

1 1 , 2 4



 ,

x2 =

1 1 , 2 2

 .

This dataset is robustly linearly separable, with ŵ(c) = (4, 0), u2,∞ (c) = (1, 0), and γ2,∞ (c) = 1/4. For every fixed η > 0, the iteration from w0 = 0 satisfies lim

ln t

t→∞ ln ln t

wt − u2,∞ (c) = 1. ∥wt ∥2 2

Proof. Recall that γ∞ = max∥w∥1 =1 mini=1,2 x⊤ i w. For any w = (w1 , w2 ) with ∥w∥1 = 1, we have ⊤ min x⊤ i w ≤ x1 w =

i=1,2

1 1 1 1 1 1 w1 + w2 ≤ |w1 | + |w2 | ≤ (|w1 | + |w2 |) = . 2 4 2 4 2 2

Taking the maximum over all such w gives γ∞ ≤ 1/2. Conversely, the vector w = (1, 0) satisfies ∥w∥1 = 1 and we have ⊤ x⊤ 1 w = x2 w =

1 , 2

hence γ∞ ≥ 1/2. Combining the two bounds yields γ∞ = 1/2 > c = 1/4, thus according to Lemma A.1, we have the proposed data set is robustly linearly separable. According to the definition, every solution of (ℓ∞ -Robust SVM) satisfies 1≤

min ⟨xi + δ i , w⟩ = ⟨xi , w⟩ − c∥w∥1 ,

∥δ i ∥∞ ≤c

take x1 into above, we get 1≤

1 1 1 1 1 1 1 w1 + w2 − (|w1 | + |w2 |) = w1 + (w1 − |w1 |) + (w2 − |w2 |) ≤ w1 . 2 4 4 4 4 4 4

Adversarial Training with Large Step Sizes

Hence, for any solution w of (ℓ∞ -Robust SVM), we need w1 ≥ 4 and ∥w∥22 = w12 + w22 ≥ 16. On the otherside, for the vector w = (4, 0), we have:    1 1 1 ⟨x1 , w⟩ − c∥w∥1 = , , (4, 0) − ∥(4, 0)∥1 = 1, 2 4 4    1 1 1 ⟨x2 , w⟩ − c∥w∥1 = , , (4, 0) − ∥(4, 0)∥1 = 1. 2 2 4 Thus for this data set, the solution of (ℓ∞ -Robust SVM) is unique, and we have ŵ(c) = (4, 0),

u2,∞ (c) =

(4, 0) = (1, 0), 4

γ2,∞ (c) =

1 , 4

S(c) = {1, 2}.

Let s∗ = (s∗1 , s∗2 ) ∈ ∂∥ŵ(c)∥1 . By Proposition A.3, there exist α1 , α2 ≥ 0 and s∗ ∈ ∂∥ŵ(c)∥1 such that ŵ(c) = α1 (x1 − cs∗ ) + α2 (x2 − cs∗ ). Since ŵ(c) = (4, 0), we have s∗1 = 1 and s∗2 ∈ [−1, 1], which gives     1 1 1 1 1 − + α2 − = (α1 + α2 ), 4 = α1 2 4 2 4 4     1 1 1 1 ∗ 1 − s∗2 1 1 ∗ 0 = α1 − s2 + α2 − s2 = (α1 + α2 ) + α2 ≥ α2 ≥ 0. 4 4 2 4 4 4 4

(105)

It follows that α1 = 16,

α2 = 0,

and

s∗2 = 1.

Consequently, we have z1 (c) = x1 − cs∗ =



1 1 , 2 4



1 − (1, 1) = 4



 1 ,0 , 4

z2 (c) = x2 − cs∗ =



1 1 , 2 2



1 − (1, 1) = 4



1 1 , 4 4

 .

(106)

At w0 = 0, recall from the definition of λi,t in (5), we have λ1,0 = λ2,0 = 1/2. We choose s0 = 0, which belongs to ∂∥w0 ∥1 = [−1, 1]2 . The first update is then     η η 3 η 3η w1 = (x1 + x2 ) = 1, = , . 2 2 4 2 8 Both coordinates are positive. Whenever wt has positive coordinates, its norm subgradient is (1, 1), and the update adds positive multiples of (1/4, 0) and (1/4, 1/4). Induction shows that both coordinates remain positive for all t ≥ 1. Therefore vt = wt,1 , rt = (0, wt,2 ), and 1 1 1 vt vt + wt,2 − (vt + wt,2 ) = , 2 4 4 4 1 1 1 vt + wt,2 ⊤ x2 wt − c∥wt ∥1 = vt + wt,2 − (vt + wt,2 ) = . 2 2 4 4 x⊤ 1 wt − c∥wt ∥1 =

(107)

Substitution into the update gives, for t ≥ 1, we get λ1,t =

1 , 1 + evt /4

λ2,t =

1 , 1 + e(vt +wt,2 )/4

vt+1 − vt =

η (λ1,t + λ2,t ), 4

wt+1,2 − wt,2 =

η λ2,t . 4

(108)

For x ≥ 0, 0 < e−x ≤ 1 implies 1 −x 1 e ≤ ≤ e−x , 2 1 + ex

and

1 1 ≤ . 1 + ex 2

(109)

(109) η vt+1 − vt η ≤ (2λ1,t ) ≤ e−vt /4 , 4 16 8

(110)

Since wt,2 > 0, we have 0 < λ2,t ≤ λ1,t ≤ 1/2. It follows that (109) η vt+1 − vt (108) η η (λ1,t + λ2,t ) ≥ λ1,t ≥ e−vt /4 , = 4 16 16 32

Yi Feng, Andrea Paudice

and 0<

vt+1 − vt (109) η ≤ 4 16



1 1 + 2 2

 =

η . 16

(111)

Using the fact that xex > x for x > 0, we have     vt+1 − vt (110) η (vt+1 −vt )/4 vt /4 e −1 ≥e e −e =e ≥ , 4 32   (110) η vt+1 − vt evt+1 /4 − evt /4 ≤ evt /4 e(vt+1 −vt )/4 ≤ eη/16 . 4 8 vt+1 /4

vt /4

vt /4

(112) (113)

Since v1 = η/2, we have evt /4 = ev1 /4 +

t−1  X

 evs+1 /4 − evs /4 ,

eη/8 +

s=1

(112) (113) η η (t − 1) ≤ evt /4 ≤ eη/8 + eη/16 (t − 1). 32 8

(114)

Let C12 = min{eη/8 , η/32} and C13 = max{eη/8 , (η/8)eη/16 }, then we have eη/8 +

η (t − 1) ≥ C12 t, 32

η eη/8 + eη/16 (t − 1) ≤ C13 t. 8

(115)

Thus we have C12 t ≤ evt /4 ≤ C13 t,

ln C12 + ln t ≤

vt ≤ ln C13 + ln t, 4

4 ln C12 ≤ vt − 4 ln t ≤ 4 ln C13 .

(116)

Reciprocation of the first inequality in (116) gives 1 1 ≤ e−vt /4 ≤ . C13 t C12 t

(117)

For the second coordinate, we have (109) η wt+1,2 − wt,2 (108) η = λ2,t ≥ e−(vt +wt,2 )/4 , 4 16 32 wt+1,2 − wt,2 (109) η −(vt +wt,2 )/4 wt+1,2 − wt,2 (109) η ≤ e , 0< ≤ . 4 16 4 32

(118)

Applying x ≤ ex − 1 ≤ xex , we get   wt+1,2 − wt,2 (118) η −vt /4 ewt+1,2 /4 − ewt,2 /4 = ewt,2 /4 e(wt+1,2 −wt,2 )/4 − 1 ≥ ewt,2 /4 ≥ e , 4 32 wt+1,2 − wt,2 (wt+1,2 −wt,2 )/4 (118) η η/32 −vt /4 ewt+1,2 /4 − ewt,2 /4 ≤ ewt,2 /4 e ≤ e e . 4 16

(119) (120)

The reciprocal bounds therefore imply (117) η (119) (120) η (117) ηeη/32 η ≤ e−vt /4 ≤ ewt+1,2 /4 − ewt,2 /4 ≤ eη/32 e−vt /4 ≤ . 32C13 t 32 16 16C12 t

(121)

Summing from s = 1 to t − 1, and using w1,2 = 3η/8, ewt,2 /4 − e3η/32 =

t−1  X

 ews+1,2 /4 − ews,2 /4 ,

which implies

s=1 t−1 t−1 (121) ηeη/32 X 1 η X 1 (121) wt,2 /4 − e3η/32 ≤ ≤ e . 32C13 s=1 s 16C12 s=1 s

(122)

Adversarial Training with Large Step Sizes

For t ≥ 2, using the inequality ln t ≤

Pt−1

s=1 1/s ≤ 1 + ln t, we get

(122) (122) ηeη/32 η ln t ≤ ewt,2 /4 − e3η/32 ≤ (1 + ln t). 32C13 16C12

(123)

Define e3η/32 ηeη/32 C15 = + ln 2 16C12

η C14 = , 32C13



1 1+ ln 2

 .

(124)

We have C14 ln t ≤ e

wt,2 /4

 3η/32   e ηeη/32 1 (124) ≤ + + 1 ln t = C15 ln t. ln 2 16C12 ln 2

(125)

Taking logarithms of above, we get 4 ln C14 ≤ wt,2 − 4 ln ln t ≤ 4 ln C15 .

(126)

Since these constants depend only on η, in conclusion, we get (116)

(126)

vt = 4 ln t + Oη (1),

∥rt ∥2 = wt,2 = 4 ln ln t + Oη (1).

(127)

Finally, compute the implicit bias error explicitly gives  2 2  2 v 2 w wt t t,2  =2− p . − (1, 0) =  q − 1 +  q ∥wt ∥2 1 + (wt,2 /vt )2 2 v 2 + w2 v 2 + w2 t

t

t,2

t,2

Taking (128) into the calculation, we get ln t wt − (1, 0) ln ln t ∥wt ∥2 2 as t → ∞. This finished the proof.

=

∥wt /∥wt ∥2 − (1, 0)∥2 wt,2 / ln ln t → 1, wt,2 /vt vt / ln t

(128)

Yi Feng, Andrea Paudice

C

PROOFS IN SECTION 4

C.1

Proof of Theorem 4.2

We first prove the no acceleration by large step sizes part of Theorem 4.2. Proof. We establish the lower bound for gradient descent with w0 = 0 , which already suffices to rule out a general acceleration guarantee. For an integer time budget T , let q = 4T 2 and dT = q 2 + 1 = 16T 4 + 1. Define the one-sample data set     x = 2, q −1 , . . . , q −1  ∈ RdT . | {z }

DT = {(x, 1)},

q 2 coordinates

√ Note that this data set depends only on T , and we have ∥x∥2 = 5. Fix any adversarial radius 0 < c < 2 such that T > 64/c, and any η > 0. Since cq = 4cT 2 > 256T , we have q −1 < c. Lemma A.2 therefore gives γ2,∞ (c) = 2 − c > 0

and

u2,∞ (c) = (1, 0, . . . , 0).

In particular, DT is robustly separable under ℓ∞ adversarial attack with radius c. For data set DT , write the robust margin of x with respect to w as Mt := x⊤ wt − c∥wt ∥1 ,

(129)

which gives LAdv (wt ) = ln (1 + exp(−Mt )). The (GD) dynamics can be written as wt+1 = wt − η ∂w LAdv (wt ) = wt + ηλt (x − c Sign(wt )) ,

where

λt =

1 < 1. 1 + exp(Mt )

(130)

Since the last q 2 coordinates of x and w0 are the same, we have the last q 2 coordinates of wt are also the same. Denote wt = (vt , ηcrt , . . . , ηcrt ) ,

(131)

where vt = ⟨wt , u2,∞ (c)⟩. According to (130), the first update gives v1 = v0 + ηλ0 (2 − c · 0) = η,

and

r1 = ηcr0 + ηλ0 (q −1 − c · 0) /(ηc) = β/2,

(132)

where β = (cq)−1 < 1. Through explicitly writing down (130) with the data in DT , we have vt+1 = vt + η(2 − c)λt , rt+1 = rt + λt (β − Sign(rt ))

for

t ≥ 1.

(133)

Since 2 − c > 0, this implies vt > 0 for every t ≥ 1. Consequently, under above notation, we have Mt = x⊤ wt − c∥wt ∥1 = (2 − c)vt + ηc2 q 2 (βrt − |rt |) .

(134)

For the first term in (134), by using the recursion formula in (133), we have ! t−1 X 2 (2 − c)vt = (2 − c)v1 + η(2 − c) λt s=1

(130),(131)

≤

(2 − c)η + η(2 − c)2 (t − 1) ≤ 4ηt,

t ≥ 1.

(135)

Adversarial Training with Large Step Sizes

Let A := ln(8cqT ) and H := (ηcq)/16. The assumptions on c and T give cq = 4cT 2 > 256T,

βT <

1 , 256

0 < A ≤ ln(64T 3 ) ≤ 4 ln(3T ).

(136)

We consider the following two cases: (1). H < A, i.e., small step size η < 16A/cq is used. Since β < 1, the second term in (134) is nonpositive. Hence, we have (134),(135)

≤

MT

4ηT <

64AT 16A 64 ln(3T ) = ≤ . cq cT cT

Since the function u → ln(3u)/u is decreasing for u > e/3. As T > 64/c > 32, we have MT < Consequently, we have

64 ln(3(64/c)) 192 = ln . c 64/c c

 c  . LAdv (wT ) = ln(1 + e−MT ) > ln 1 + 192

(2). H ≥ A, which is the regime where a rather large step size can be used. To facilitate the analysis, we compare the recursion for rt in (133) with an auxiliary sequence obtained by replacing λt in (133) with 1, which gives the following sequence {r̄t }: r̄1 =

β , 2

r̄t+1 = r̄t + β − Sign(r̄t ).

(137)

Since β < 1/(256 T ), direct induction gives r̄2k−1 =

4k − 3 β > 0, 2

r̄2k = −1 +

4k − 1 β < 0, 2

whenever the corresponding index is at most T . In particular, we have |r̄t | ≥ β/2 for 1 ≤ t ≤ T . We first show that the error between rt and r̄t belongs to O(β) under the current regime. In fact, we have: |rt − r̄t | ≤ 2(t − 1) exp(−H) ≤

β , 4

1 ≤ t ≤ T.

(138)

The second inequality follows from 2T exp(−H) ≤ 2T exp(−A) =

1 β = . 4cq 4

The first inequality of (138) can be proved by induction on t. It holds at t = 1 because r1 = r̄1 from (132) and (137). Suppose it holds at some t < T . Then rt and r̄t have the same sign, and |rt | ≥ β/4, which is because r̄t ≥ β/2. Since β ≤ 1/2, we obtain ηc2 q 2 (βrt − |rt |) ≤ −ηc2 q 2 (1 − β)|rt |

≤−

(Since βrt − |rt | < (β − 1)|rt |)

ηcq ηc2 q 2 β =− = −2H. 8 8

Combining this with (134) and (135), and using 4ηT ≤ H, yields Mt ≤ 4ηt − 2H ≤ −H,

1 − λt =

exp(Mt ) ≤ exp(−H). 1 + exp(Mt )

Subtracting the two recursions and using Sign(rt ) = Sign(r̄t ), we conclude that |rt+1 − r̄t+1 | ≤ |rt − r̄t | + (1 − λ1,t )|β − Sign(rt )| ≤ 2(t − 1) exp(−H) + 2 exp(−H) = 2t exp(−H).

Yi Feng, Andrea Paudice

This proves (138) by induction. In particular, |rT | ≥ β/4, so the same estimate in (134) gives MT ≤ −H. Therefore,  c  . LAdv (wT ) = ln (1 + exp(−MT )) ≥ −MT ≥ H ≥ A > ln 1 + 192 This completes the proof. We then prove the no phase transition time part of Theorem (4.2) in the following. Proof. We use the same data set DT and the same initialization and subgradient choice as above. Fix any admissible T, c and any η > 0. In the following, T and q = 4T 2 remain fixed. Recall from (136) that 0<β<

1 , 2

cq − 1 > (2 − c)2 .

Moreover, (133) gives    rt − λt (1 − β), rt > 0, rt+1 = λt β, rt = 0,   rt + λt (β + 1), rt < 0. Combining with 0 < λt < 1 and 0 < β < 1/2, this implies |rt+1 | ≤ max{|rt |, 1 + β} by using the inequality |a − b| ≤ max{a, b}. Since |r1 | = β/2 < 1 + β, |rt+1 | ≤ max{|rt |, 1 + β} yields |rt | ≤ 1 + β,

t ≥ 1.

(139)

Moreover, vt is increasing and must tend to infinity. Indeed, suppose that vt ≤ V for all t. Then Mt ≤ (2 − c)V by (134), and hence 1 λt ≥ =: δ > 0. 1 + exp((2 − c)V ) By (133), a positive lower bound of vt implies vt ≥ v1 + η(2 − c)δ(t − 1) → ∞,

t → ∞,

(140)

which contradicts the boundedness of vt . Combining vt → ∞ with (134) and (139), we obtain Mt ≥ (2 − c)vt − ηc2 q 2 (1 + β)2 → ∞,

t → ∞.

Consequently, as t → ∞, we have LAdv (wt ) → 0,

λt → 0,

∞ X

and

λt = ∞,

t=1

where the last assertion follows from the recursion for vt and vt → ∞ by (140). Since the function f (r) = βr − |r| is (1 + β)-Lipschitz, (133) and (134) imply |Mt+1 − Mt | ≤ (2 − c) vt+1 − vt + η 2 cq f (rt+1 ) − f (rt ) ≤ η(2 − c)2 λt + (1 + β) rt+1 − rt

(Since (133) and Lipschit property of f (r))

= η(2 − c)2 λt + (1 + β)λt |β − Sign(tt )|
≤ η (2 − c)2 + c2 q 2 (1 + β)2 λt → 0.

(From (133)) (Since |β − Sign(tt )| ≤ 1 + β)

(141)

Adversarial Training with Large Step Sizes

Together with Mt → ∞, this gives λt+1 /λt =

1 + exp(Mt ) → 1, 1 + exp(Mt+1 )

t → ∞.

(142)

We now show that there are infinitely many indices t such that rt > 0 and rt+1 < 0. The sequence rt cannot be Peventually strictly positive. Otherwise, (133) would give rt+1 = rt −(1−β)λt for all sufficiently large t, which contradicts t λt = ∞ as shown in (141). The same argument shows that rt cannot be eventually strictly negative. Moreover, if rt = 0, then rt+2 = βλt − (1 − β)λt+1 < 0

rt+1 = βλt > 0,

for all sufficiently large t, by (142) and β < 1/2. Thus, whether rt equals zero finitely or infinitely often, there are infinitely many indices t such that rt > 0 and rt+1 < 0. For each sufficiently large index τ such that rτ > 0 and rτ +1 < 0, we also have rτ +2 > 0. This is because, rτ +1 = rτ − (1 − β)λτ > −(1 − β)λτ , and therefore rτ +2 = rτ +1 + (1 + β)λτ +1 > −(1 − β)λτ + (1 + β)λτ +1 > 0, where the last inequality follows from (142). Hence, there are infinitely many indices satisfying rτ > 0,

rτ +1 < 0,

rτ +2 > 0.

(143)

For any index τ satisfying (143), the recursions in (133) give vτ +2 − vτ = η(2 − c)(λτ + λτ +1 ), rτ +2 − rτ = −(1 − β)λτ + (1 + β)λτ +1 . Since rτ , rτ +2 > 0, it follows from (134) that Mτ +2 − Mτ = (2 − c)(vτ +2 − vτ ) − ηc2 q 2 (1 − β)(rτ +2 − rτ ). Substituting the two identities above, we obtain     Mτ +2 − Mτ λτ +1 λτ +1 = (2 − c)2 1 + + c2 q 2 (1 − β) (1 − β) − (1 + β) . ηλτ λτ λτ By (142) and recall that we have β = 1/cq, the right-hand side converges to
2(2 − c)2 − 2c2 q 2 β(1 − β) = 2 (2 − c)2 − (cq − 1) < 0. Since ηλt > 0, we have Mτ +2 < Mτ for infinitely many τ . Therefore, LAdv (wτ +2 ) > LAdv (wτ ) for infinitely many τ . For each such τ , at least one of the two updates from τ to τ +2 strictly increases the loss. Consequently, ∀s ∈ N,

∃τ ≥ s :

LAdv (wτ +1 ) > LAdv (wτ ).

Thus, no finite time exists after which the loss remains non-increasing. This completes the proof.

Yi Feng, Andrea Paudice

D

APPENDIX OF SECTION 5.1

D.1

Proof of Proposition 5.1

High-Level Overview of the Proof. We will analysis the dynamics given by Lemma (D.1), which is the explicit form of the adversarial training dynamics for (xt , yt ). To study this dynamics, we first introduce the following time horizon, which is motivated by Lemma 6 in Ahn et al. (2023): s := inf{t ≥ 0 | xt < 0 or qt yt ≤ 1}

(144)

The definition of qt is presented in (147). In other worlds, for all t ≤ s, the trajectories (xt , yt ) lies in the linear region, and xt ≥ 0. Moreover, for small η, the initialization given by (EoS initialization) must lies in the linear region, thus s > 0 and is well-defined. It turns out that in the region t ≤ s, the following value Dt := yt2 − qt2

(145)

is nearly conversed. Since the initialization given by (EoS initialization) makes D0 = Ω(1/η), thus for t < s, yt keeps a √ magnitude of O(1/ η), which result in xt significantly decreases in each iteration according to (148). In Lemma D.4, we will prove s = O(1/η). This results in the training trajectories enter a small tube with |xs | = O(η) as shown in Lemma D.5. Moreover, in Lemma D.6, we prove that once the trajectory enters this tube, it will remain in this tube for the rest of the training time. After the trajectory enter the tube, we will show the y-coordinate of the trajectory gradually be compressed to zero and the trajectory future enter the quadratic region, then we use Lemma D.2 to prove the upper bound on the sharpness when t tends to infinity. We first note that as in (ℓ∞ -adversarial logistic regression), the inner max problem of (Adversarial Huber loss) has an explicit solution: max ℓ ((x + δ)y) = ℓ ((x + c Sign(x)) y) . |δ|≤c

Thus (ℓ∞ -adversarial logistic regression) has an explicit formula: 
2  (x + c Sign(x)) y   ,
2 max ℓ (x + δ)y =  |δ|≤c   (x + c Sign(x))y − 1 , 2

(146)

(x + c Sign(x))y ≤ 1, (x + c Sign(x)) y > 1.

In the following, we define the region where (x + c Sign(x))y ≤ 1 holds as the quadratic region, and the region where (x + c Sign(x))y > 1 holds as the linear region. To simplify the notation, we will also denote qt := |x + c Sign(x)| = |xt | + c.

(147)

Lemma D.1. If yt > 0, then in the linear region, the gradient descent dynamic can be written as: xt+1 = xt − η Sign(xt ) yt , yt+1 = yt − ηqt .

(148)

While in the quadratic region, the gradient descent dynamic can be written as: xt+1 = (1 − η yt2 )xt − η Sign(xt ) c yt2 , yt+1 = (1 − η qt2 )yt . Proof. Since we assume yt > 0, we have (xt + c Sign(xt ))yt = xt + c Sign(xt ) yt = qt yt .

(149)

Adversarial Training with Large Step Sizes

We first consider the linear region (xt + c Sign(xt ))yt > 1. In this case we have max ℓ ((x + δ)y) = (x + c Sign(x))y − |δ|≤c

1 1 = qt yt − , 2 2

and yt+1 = yt − η ∂y max ℓ ((xt + δ)yt ) = yt − ηqt , |δ|≤c

this finished the y-part in (148). For the x-part, we have xt+1 = xt − η ∂x max ℓ ((xt + δ)yt ) = xt − η (∂x qt ) yt |δ|≤c

= xt − η Sign(xt ) yt , and this finished the x-part of the (148). Next we consider the quadratic region (xt + c Sign(x))yt ≤ 1. In this case, we have (xt + c Sign(xt )) yt max ℓ ((xt + δ)yt ) = 2 |δ|≤c

2 =

qt2 yt2 , 2

and
yt+1 = yt − η ∂y max ℓ ((xt + δ)yt ) = 1 − η qt2 yt , |δ|≤c

this finished the y-part in (149). For the x-part, we have xt+1 = xt − η ∂x max ℓ ((xt + δ)yt ) = xt − η (∂x qt2 ) yt2 /2. |δ|≤c

Note that ∂x qt2 /2 = qt ∂x qt = Sign(xt ) qt = Sign(xt ) (|xt | + c) = xt + Sign(xt ) c, thus xt+1 = xt − η (∂x qt2 ) yt /2 = xt − η (xt + Sign(xt ) c) yt2
= 1 − η yt2 xt − η Sign(xt ) c yt2 , this finished the the x-part of the (149). Lemma D.2. If (xy , yt ) lies in the quadratic region, we have 2

λct ≤ (|yt | + qt ) .
Proof. We first calculate the Hessian matrix ∇2 Lc (xt , yt ) = ∇2 max|δ|≤c ℓ ((xt + δ)yt ) in the quadratic region. We have
2 !  2 2   (x + c Sign(x )) y qt yt t t t 2 2 2 ∇ max ℓ ((xt + δ)yt ) = ∇ =∇ 2 2 |δ|≤c Note that we have  2 2 qt yt • ∇xx = ∇xx (qt2 /2) · yt2 = yt2 2  2 2 qt yt • ∇yy = qt2 /2 · ∇yy (yt2 ) = qt2 2

Yi Feng, Andrea Paudice

• ∇xy

 2 2
qt yt = ∂x qt2 yt = 2 Sign(xt ) qt yt 2

Combining above, we get 

Ht := ∇2 max ℓ ((xt + δ)yt ) |δ|≤c

yt2





2 Sign(xt ) qt yt

= 2 Sign(xt ) qt yt

qt2

 .

Moreover, since λct ≤ ∥Ht ∥∞ := max{yt2 + 2 qt yt , qt2 + 2 qt yt } ≤ (|yt | + qt )2 , this finished the proof. Assumption D.3. We assume the following assumptions hold in the training process: • (Boundary-avoidance) The training trajectories do not hit the non-smooth set xt = 0, (|xt | + c) yt = 1 • (Magnitudes of Adversarial Radius) We assume c is fixed and c ̸= 0. Note that the boundary-avoidance part of Assumption D.3 is to avoid the cases where the solution of inner-max problem of (Adversarial Huber loss) is not unique when x = 0, and the Hessian on the boundary points (|xt | + c) yt = 1 is not well-defined. Similar assumptions are also needed in Ahn et al. (2023). Lemma D.4. Under Assumption D.3, let s := inf{t ≥ 0 | xt < 0 or qt yt ≤ 1},

(Entrance Time)

then for sufficient small step size η, we have s ∈ O(1/η). Proof. For any k ≤ s − 1, according to the definition of (Entrance Time), we have xk > 0,

qk = xk + c,

qk yk > 1,

thus the trajectory lies in the linear region, and the dynamics as defined in (148) can be written as qk+1 = qk − η yk ,

yk+1 = yk − η qk .

(150)

Define Dk := yk2 − qk2 . We first compute D0 , where (x0 , y0 ) is initialize according to (EoS initialization). Since in this case, q0 = x0 + c, we have D0 = y02 − q02 = (y02 − x20 ) − 2c x0 − c2 = (2 + δ)/η − 2c x0 − c2 . Since c > 0 is fixed and x0 = O(η −1/2 ), we have 2cx0 + c2 = O(η −1/2 ). Thus, for sufficiently small η which depends on c, D0 ≥ (2 + δ)/(2η), and hence D0 = Ω(1/η).

(151)

Moreover, in time region k ≤ s, the trajectory lies in the linear region, we have 2

2

2 2 Dk = yk2 − qk2 = (yk−1 − η qk−1 ) − (qk−1 − η yk−1 ) = (1 − η 2 ) (yk−1 − qk−1 )

= (1 − η 2 )Dk−1 .

(152)

Adversarial Training with Large Step Sizes

Using above recurrence relation, we get yk ≥

p

Dk = (1 − η 2 )k/2

p D0 .

(153)

Moreover, we have 0 < xs−1 = x0 − η

s−2 X

yk ≤ x0 − η

p

D0

k=1

s−2 X

1 − η2

k/2

,

k=0

where the inequality in the right hand side used (153). Thus we have s−2 X

1 − η2

k/2

 p  ≤ x0 / η D0

k=0

According to (EoS initialization), we have 1

x0 = O(η − 2 ), and

p

1

D0 = Ω(η − 2 )

from (151),

these gives s−2 X

1 − η2

k/2

= O(1/η).

k=0

The left hand side is a geometric progression, with an explicit solution given by s−2 X

1−η

s−1 1 − 1 − η2 2 p = . 1 − 1 − η2

2 k/2

k=0

For the denominator term 1 −

p

1 − η2 =

√η 1+

2

1−η 2

(154)

, since η < 1, we have

1≤1+

p

1 − η 2 ≤ 2,

thus η 2 /2 < 1 −

p 1 − η2 < η2 ,

which gives 1 − 1 − η2 η2

s−1 2

s−1 s−2 X
k/2 1 − 1 − η2 2 p < = 1 − η2 = O(1/η). 1 − 1 − η2 k=0

This gives 1 − 1 − η2

s−1 2

= O(η),

i.e.,

∃ M > 0, 1 − η 2

s−1 2

≥ 1 − M η.

Now we take log to the both side, which gives s−1 log(1 − M η) M 1 + O(η) < = · = O(1/η), 2 log(1 − η 2 ) η 1 + O(η 2 ) this finished the proof. √ Lemma D.5. Under Assumption D.3, at entrance time s as defined in (Entrance Time), we have |xs | ∈ O( η). Moreover, 1 we have ys = O(η − 2 ) and ys > 0.

Yi Feng, Andrea Paudice 1

Proof. ys = O(η − 2 ) is easy to prove since in the linear region k ≤ s − 1, we have 1

yk+1 = yk − η qk , qk > 0 ⇒ ys ≤ y0 = O(η − 2 ).

(155)

According to the definition of s, we have the following possibilities: Case 1 : qs ys < 1 with xs > 0, and Case 2 : xs < 0. In the following, we will prove the statement holds in both cases. We first consider Case 1. Recall that case 1 implies ∀t < s, the trajectory lies in the linear region, where the following recurrence holds according to (152):
s Ds = D0 1 − η 2 . Since s = O(1/η) according to Lemma D.4, we have (1 − η 2 )s = Ω(1). Moreover, we have D0 = Ω(1/η) according to (151), these together gives Ds = Ω(1/η). Since Ds = ys2 − qs2 , above gives ys ≥

p p √ ys2 − qs2 = Ds = Ω(1/ η).

Since qs ≥ c > 0 and c is fixed, the preceding lower bound on ys implies qs ys ≥ cys > 1 for sufficiently small η. This contradicts qs ys < 1. Therefore, xs < 0 and Case 1 can not happen. Now we consider Case 2. In this case, we have xs < 0 and xk−1 > 0 for all k ≤ s − 1. This gives xs = xs−1 − η ys−1 < 0 ⇒ |xs | = η ys−1 − xs−1 < η ys−1 . 1

(156)

1

Since ys−1 = O(η − 2 ) according to (155), this gives |xs | = O(η 2 ). Finally, since Ds−1 > 0, we have ys−1 > qs−1 , and ys = ys−1 − η qs−1 ≥ (1 − η)ys−1 > 0. This finished the y-part of the proof. From Lemma D.5, there exist constant Q, Y which are independent of η, such that |xs | ≤ Q

√

1

η, 0 < ys < Y η − 2 .

(157)

Now we fix some constant M such that M ≥ max{Q, Y },

(158)

and our aim is to prove the following lemma about the invariance of the tube. √
2 Lemma D.6. Under Assumption D.3 and assume η satisfies η c + M η < 1, we have for all t ≥ s, the following holds: |xt | ≤ M

√

1

η, 0 < yt ≤ Y η − 2 .

(159)

Moreover, yt is a non-increasing function after t > s. Proof. We prove by using induction. The base case t = s is true from (157) and the definition of M . Assume that for a time point t ≥ s, the inequalities in (159) hold. Then we need to prove that at time t + 1, (159) still holds. √ We first note that the assumption (c + M η)2 η < 1 implies √ 2 η qt2 ≤ η (c + M η) < 1.

(160)

We dived the discussion into two cases. Case 1 : yt qt > 1 and Case 2 : yt qt < 1, where we do not include the case yt qt = 1 for Assumption D.3.

Adversarial Training with Large Step Sizes

We first consider Case 1. In this region, according to (148), we have yt+1 = yt − η qt , yt > 1/qt .

(161)

It is easy to see yt is a non-increasing function. Moreover, since η qt2 < 1, we have η qt < 1/qt < yt , 1

therefore 0 < yt+1 < yt ≤ Y η − 2 , and this finished yt+1 part of the induction. For the xt+1 part, we have √ |xt+1 | = |xt − η Sign(xt ) yt | = | |xt | − η yt | ≤ max{|xt |, η yt } ≤ max{M, Y } η, and this finished the proof of Case 1. Next we consider Case 2. If yt qt < 1, then according to (149), we have yt+1 = (1 − η qt2 )yt .

(162)

Moreover, since 0 < 1 − η qt2 < 1 according to (160), we have yt+1 = (1 − η qt2 )yt ≤ yt ,

(163)

and this finished yt+1 part of the induction. For the x-update, (149) gives |xt+1 | = |xt | − ηqt yt2 ≤ max{|xt |, ηqt yt2 } ≤ max{|xt |, ηyt } √ √ ≤ max{M, Y } η = M η, where the second inequality uses qt yt < 1. This completes the induction.

In the following, we combine Lemma D.4-D.6 to provide a proof of Proposition 5.1. Proof of Proposition 5.1. From Lemma D.6, we know yt > 0 and it is a non-increasing function of t, thus limt→∞ yt exists, we denote y∞ := lim yt ≥ 0. t→∞

We will show in fact y∞ = 0. If y∞ > 0, note that in the linear region qt yt > 1, after each iteration yt will decrease η qt > η c. Thus there must exists some T > 0, such that for t > T , the trajectory (xt , yt ) always lies in the quadratic region where qt yt < 1, and we have yt+1 = (1 − η qt2 ) yt . Since qt > c, we have yt+1 ≤ (1 − η c2 )yt , and this enforces limt→∞ yt = 0. Finally, according to Lemma D.2 and Lemma D.6, we have √ 2 λct ≤ (yt + qt ) , qt ≤ c + M η. Through taking the limit in above as t → ∞, we get lim λct ≤ lim sup qt2 = O(η + c2 ),

t→∞

and this finished the proof.

t→∞

Yi Feng, Andrea Paudice

D.2

Experimental Details of Section 5.1

In this section, we summarize the experimental details in Figure 2 and Figure 3 in Section 5.1. Our experimental setting follows the standard setting of the edge-of-stability literature (Cohen et al., 2021, 2025) with a modification to the adversarial training setting. All experiments were conducted using two NVIDIA RTX 5090 GPUs. Neural network architectures & Data Set. We use four architectures: MLP, CNN, ResNet, and ViT, all applied to a 4 class, 1000 example subset of CIFAR-10 (250 examples per class). The architectures are the same as those used by standard EoS literature (Cohen et al., 2021, 2025). MLP. A fully connected network with two hidden layers of width 256 and GELU activations, followed by a linear output layer. This gives 854K parameters. CNN. A two-layer convolutional network: two 3 × 3 convolutions (base width 32, doubling to 64 in the second layer) with GELU activations and 2 × 2 average pooling after each, followed by a fully connected hidden layer (width 128) and a linear output layer. This gives 544K parameters. ResNet. A pre-activation residual network with 3 stages of 3 basic blocks each (9 residual blocks total), base width 16 doubling at each stage transition, GroupNorm, GELU activations, and residual branches initialized to output zero at initialization (so the network starts as the identity map). This gives 293K parameters. ViT. A Vision Transformer with patch size 4 (64 patches per image), embedding dimension 64, depth 4, 8 attention heads, and MLP dimension 256, using learnable LayerNorm and global average pooling in place of a class token. This gives 661K parameters. Adversarial attacks. In Figure 2, adversarial perturbations are constrained to an ℓ∞ ball with radii 2/255, 3/255, and 4/255, which bound the maximum absolute perturbation to each pixel channel. In Figure 3, perturbations are constrained to an ℓ2 ball with radii 28/255, 70/255, and 112/255, which bound the Euclidean norm of the perturbation over the entire image. The adversarial example is generated by the FGSM method. These radii are smaller than those commonly used in adversarial robustness benchmarks on CIFAR-10, such as 8/255 for ℓ∞ attacks and 127/255 for ℓ2 attacks (Pang et al., 2021). This choice reflects our experimental objective: to characterize differences in sharpness evolution between standard and adversarial training, rather than to maximize robust accuracy. Our experiments demonstrate that these differences arise even with relatively small adversarial perturbations. Sharpness is estimated from the parameter Hessian with the generated adversarial inputs held fixed. We use warm-started LOBPCG to refresh the leading eigenvector every 100 training steps, with the solver tolerance parameter set to (10−10 ). Between refreshes, we estimate sharpness using the Rayleigh quotient along the most recently computed direction. D.3

Additional Experimental for Section 5.1

Different attack methods. In Figure 5 and Figure 6, we present numerical results that use PGD to generate the adversarial example. Besides this, all the experimental setting are the same as those in Figure 2 and Figure 3. Claims in Section 5.1 are also supported by this group of experiments. Evolution of adversarial losses. In the edge-of-stability phenomenon, when sharpness begins to oscillate around the 2/η threshold, the standard loss also begins to oscillate while decreasing over longer timescales (Cohen et al., 2021). We observe similar loss behavior in adversarial training: the adversarial loss initially decreases almost monotonically while adversarial sharpness increases. Once adversarial sharpness begins to oscillate with an overall decreasing trend, the adversarial loss also begins to oscillate while continuing to decrease over longer timescales. We present the comparison between the sharpness and loss curves by using the smallest step sizes in above experiments (η = 0.005), as in these experiments the sharpness have the longest increasing period. Different Dataset. In Figure 9, we present experimental results on the SVHN dataset. SVHN consists of 32 × 32 RGB crops of house-number digits. It can be observed that the sharpness also exhibits the two-stage behavior. Different Sample Sizes. In Figure 10, we present numerical results with sample sizes n = 600 and 800 fo the deterministic gradient descent. These experiments show that two-stage behavior described in Section 5 holds for differnt sample sizes.

Adversarial Training with Large Step Sizes

Figure 5: Sharpness evolution under standard training and ℓ∞ -adversarial training on CIFAR-10. Adversarial examples are generated using (PGD).

Figure 6: Sharpness evolution under standard training and ℓ2 -adversarial training on CIFAR-10. Adversarial examples are generated using (PGD).

Yi Feng, Andrea Paudice

Figure 7: Comparison of the oscillation behaviors between sharpness and losses. It can be seen that when the sharpness starts to oscillate with a decreasing trend, the losses also start to oscillate. The experimental setting is step size η = 0.005 with different architectures on CIFAR-10, and the adversarial attacks are generated by FGSM with ℓ∞ geometry (upper) or ℓ2 geometry (lower).

Figure 8: The experimental setting is same as Figure 7, besides the adversarial attacks are generated by PGD.

Adversarial Training with Large Step Sizes

Figure 9: Sharpness evolution of CNN, ResNet, and ViT on the SVHN dataset. The adversarial examples are generated by the FGSM method with ℓ∞ geometry. It can be observed that the sharpness also exhibits the two-stage behavior described in Section 5.

Yi Feng, Andrea Paudice

Figure 10: Sharpness evolution of CNN, ResNet, and ViT with different sample sizes.

Related documents

• Neither Adversarial Training Nor Purification: Emergent Adversarial Robustness from Oscillatory Predictive Learning#986014
• Watch your steps: Dormant Adversarial Behaviors that Activate upon LLM Finetuning#799861
• ROAD: Modern Adversarial Training for Simple One-Step Distillation at Scale#1490934
• Unveiling the Backdoor Mechanism Hidden Behind Catastrophic Overfitting in Fast Adversarial Training#138829
• Explaining and Harnessing Adversarial Examples#6539