Benign Overfitting in Single-Head Attention
Authors: Roey Magen
Shuning Shang
Zhiwei Xu
Spencer Frei
Wei Hu
Gal Vardi
Venue: NeurIPS 2025 poster ()
Keywords: benign overfitting
single-head attention
transformers
Primary area: theory
TL;DR: We prove that under appropriate conditions, a single-head softmax attention mechanism exhibits benign overfitting

Abstract: The phenomenon of benign overfitting, where a trained neural network perfectly fits noisy training data but still achieves near-optimal test performance, has been extensively studied in recent years for linear models and fully-connected/convolutional networks. In this work, we study benign overfitting in a single-head softmax attention model, which is the fundamental building block of Transformers. We prove that under appropriate conditions, the model exhibits benign overfitting in a classification setting already after two steps of gradient descent. Moreover, we show conditions where a minimum-norm/maximum-margin interpolator exhibits benign overfitting. We study how the overfitting behavior depends on the signal-to-noise ratio (SNR) of the data distribution, namely, the ratio between norms of signal and noise tokens, and prove that a sufficiently large SNR is both necessary and sufficient for benign overfitting.

Benign Overfitting in Single-Head Attention
Rocy Magen"
Shuning Shang"1 Princcton University shuning@princeton. edu
Zhiwei Xu University Michigan zhiveixu@umi ch. edu
Weizmann Institute of Scienee
roey. www.mmmaeneeeizzann.cooo ac i1
Spencer Frei*
Wei Hu
Gal Vardi
UC Davis sfrei Sireiducdavis.edu
University of Michigan vvbdumich. edu
Weizmann Institute of Science gal. vardi rediidueezaann
Abstract
The phenomenon of benign overfitting, where a trained neural network perfectly fits noisy training data but still achieves near-optimal test performance, has been exten- sively studied in recent years for linear models and fully-comeecc//cooovltiiio networks. In this work, attention model, which is the fundamental building block of Transformers. We prove that under appropriate conditions, the model exhibits benign overfitting a classification setting already after two steps of gradient descent. Moreover, we show conditions where benign overfitting. We study how the overfitting behavior depends on the signal- to-noise ratio (SNR) of the data distribution, namely, the ratio between norms of signal and noise tokens, and prove that sufficiently large SNR is both necessary and sufficient for benign overfitting.
study benign overfitting in a single-head softmax
interpolator exhibits
Introduction
Neural networks often exhibit a remarkable phenomenon, known benign overfitting, where they achieve a perfect fit to noisy training examples and still generalize well to unseen data 2 This phenomenon contradicts classical wisdom machine learning, and has become central research question in the theory of deep learning. Existing works on benign overfitting study under what conditions the phenomenon occurs in different architectures. These works focus on linear models. and on shallow fully-connected and convolutional neural networks.
In recent years, Transformers have emerged impactful applications across a wide range of domains such as natural language processing and computer vision. The fundamental building block of Transformers is the attention mechanism, which allows them to process sequences and focus on different parts of the input. Despite the central role of the attention mechanism, currently do not understand its overfitting behavior and the conditions under which it exhibits benign overfitting.
leading neural network architecture, with
In this work, show benign-overfitting results for the attention mechanism. We consider classifi- cation with a single-head softmax attention model, and study the conditions that allow for benign overfitting. In our results, the data distribution consists of multiple tokens: signal token, which can
"Equal contribution
Work performed while visiting the University of Michigan $ Now at Google DeepMind
Equal advising
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

be used for correctly classifying clean test examples, and noisy tokens, which are independent of the label but can be used for interpolating (i.e., perfectly fitting) noisy training examples. We study the signal-to-noise ratio (SNR), namely, the expected ratio between the norms of signal and noise tokens, that allows for benign overfitting-
Below we summarize our main contributions:
In Theorem 3.3 (Section 3 we show that under appropriate conditions, gradient descent with the logistic loss exhibits benign overfitting already after two iterations. This result holds when the SNR Q211 vT), where n is the number of training samples.
We then turn to consider other natural learning rules, which allow for benign overfitting under the same requirement the SNR. In Theorems 4.2 and 4.4 (Section 4 we prove that minimum-norm (i.e., maximum-margin) interpolators exhibit benign overfitting when the SNR is 2(1/
In Theorem 4.6 (Section 4 we prove that the above requirement on the SNR is tight. Namely, if the SNR is smaller than it, then the min-norm interpolator exhibits harmful overfitting, where fits the training data but has poor generalization performance.
In Section[o] we complement our theoretical results with an empirical study. We show that sufficiently large SNR and input dimension are necessary and sufficient to achieve benign overfitting.
The paper is structured as follows. In Section we provide some preliminaries and define the data distribution and the single-head attention model. In Sections 3 and 4 we state main results benign overfitting with gradient descent and with min- min-norm interpolators. In Section | we discuss the main proof ideas, with all formal proofs deferred to the appendix. Finally, in Section 6 we show empirical results.
1.1 Related Work
Optimization in Transformers. Li ct al. [4] provided a theoretical analysis of training a shallow Vision Transformer (ViT) for a classification task. They showed that the sample complexity required to achieve a zero generalization error is correlated with the inverse of the fraction of label-relevant tokens, the token noise level, and the initial model error. Ataee Tarzanagh et al. (5) showed that optimizing the attention layer via gradient descent leads to convergence to an Support Vector Machine (SVM) solution, where the implicit bias of the attention mechanism depends are represented as a product of key-query matrices or directly as a combined matrix, with different norm-minimization objectives in each case. Ataee Tarzanagh et al. [6] provided a regularization path analysis and proved that the attention weights converge in direction to a max-margin solution that separates locally optimal tokens from non-optimal. They also showed that gradient descent with a specific initialization direction and without optimizing the attention head converges in direction to the same max- max-margin solution. 7 expanded on their findings by identifying non-trivial data settings for which the convergence of GD is provably global, i.c., without requiring assumptions about the initialization direction. They also provided convergence rate bounds and analysis for optimizing both the attention weights and the attention head, although they did not consider the case of noisy data labels, as we do in our work. Another line of work looks at the learning dynamics of single-layer linear attention models trained on linear regression tasks 8810 Additional works that consider optimization dynamics in Transformers include [1] 12].
whether the parameters
Benign overfitting. A significant body of research has explored why neural networks (NNs) that perfectly interpolate the training data can still generalize well [T] [2. This has sparked substantial interest in studying overfitting and generalization in NNs trained to fit datasets with noisy labels. The literature on benign overfitting is broad and cannot be reasonably covered here. We refer the reader
to the surveys Bartlett et al. [13,, Belkin [4]. Most relevant to our work are Cao et al. [15], Kou al. [16]. Meng et al. [17] that studied benign overfitting in convolutional neural networks. Their data distribution resembles ours, as we discuss in Section 2.1] Benign overffiting in fulle-connected
two-layer neural network classification was studied Frei et al. [8 19. Xu al. (20), Xu and Gu
211, Kornowski et al. (22), George et al. 23 Karhadkar et al. 244 for various activation functions, data distributions and loss functions (both the logistic and the hinge losses). Recently, Jiang et al.
25 studied benign overfitting in simplified transformer model. However, in contrast to work,

---

they do not allow for label-ffipping noise, which is a fundamental aspect for understanding whether interpolation is compatible with generalization. Indeed, including label noise is the common setting in the literature on benign overfitting and it plays a key role in our analysis. Concurrent with our study, Sakamoto and Sato [26] also examined benign overfitting (with label noise) similar model. They showed that, depending on the step size, there exists time step at which benign overfitting occurs. However, their approach differs significantly from ours: they do not optimize the attention head and instead assume strong condition, namely that the angle between the fixed attention head and the signal is bounded below by a constant (see Assumption 3.3 in their paper). Notably, this assumption is highly restrictive; if the attention head is drawn from standard d-dimensional Gaussian, the probability of satisfying this condition decreases exponentially with d. contrast, we optimize both the attention head and the softmax weights, and show that both learn different patterns for clean and noisy examples. Additionally, we provide an asymptotic analysis.
2 Preliminaries
Notations. We use bold-face face letters denote vectors and matrices, and let [m] be shorthand for (1.2....,m? m.). Given a vector æ, we denote by Ij its j-th coordinate. Let Ia be the d x d identity matrix, and let O2 (or just 0, if is clear from the context) denote the zero vector in Rd We let [I-I] denote the Euclidean norm. We denote multivariate Gaussian distribution with mean vector μa and covariance matrix Σ by (H, Σ). We use standard big-Oh notation, with ((),, O(-) hiding universal constants and (. (.)),, (-) hiding constants and factors that are polylogarithmic in the problem parameters. We use T(-) to denote the indicator variable of an event. For finite set A, denote the uniform distribution over A by Unif(AA and let [AA] be its cardinality.
2.1 Data Generation Setting
In this work we focus on the following data distribution:
Definition 2.1 (clean data distribution). Let μi 42 E IR such that || || p for some p > 0 and ( = O, be two fixed orthogonal vectors representing the signal contained each data point. Define Delean as the distribution over IR Txd {=1} of labelled data such that data point (X, 5) is generated by the following procedure:
1. Sample the label ÿ ~ (ni.
2. Generate vector u, which represents the signal, follows: If = +1, set pi; and if 142.
7/ = -1, set u
3. Generate i.i vectors Eg...., Er which represents the noise, from the Gaussian distribution &, (0, Ia Mil /0² P2 /p²) for any 7 E (2, (2.....7 T).
4. Denote X = (I!(1) (2) (T) Select h ~ Unif(1...., .......]]...... and set (k) u. Set the other tokens (x!11) (k x (b+11) (T)) to be . Er.
To study the overfitting behavior we also need to introduce label-flipping noise:
Definition 2.2 (noisy data distribution). Let 7 E [0, 1/2) be the label flipping probability. We define D as the distribution over T Txd x {+1} which is the n-llabelffipped version of Detean Namely, to generate (X, ~ D. first generate (X, D) Deleans then let y y with probability 1 1) and y - with probability 1)-
Our data distribution resembles the distributions considered by Kou et al. [16, Cao et al. [15 Meng al. [7]. They proved benign overfitting in two-layer convolutional neural networks, and in their setting each data point consists of two patches (1),, (2) (rather than T tokens in our setting). Since our single-head attention model is invariant to the order of the tokens, we assume without loss of generality throughout this work that (1) the signal token and (2)) (7) are the noisy tokens
in all data points. Note that the noise token (r) = & is independent of the label, and that it is
'Without label noise, many existing benign overfitting results can be trivially explained through standard uniform convergence arguments (e.g., the classical result of Bartlett et al. (2) on benign overfitting in linear regression).
3

---

generated from - u Zadtr / /²)). ensuring that it is orthogonal to the signal vector. Note that when the dimension d is large, ||E:|| R vd - 2 x by standard concentration bounds. Therefore, denote the signal-to-noise to-sssse-neeeeeeeeee ratio (SNR) SNR |||| / p/ /d.
We consider a training dataset (1) of n samples generated i.i.d. from the distribution 'D. Denote the index set of data whose labels are not flipped by C [i: Di y/ ("clean examples"), and the index set of data whose labels are flipped by N = (i 3/4 = -V; ("noisy examples"). For
indices in C. we further denote C₁ := cn (i z; (1) pi C1 = Cn { : u2),, and define the subsets N1. N2 of N analogously.
2.2 Single-Head Attention Model
Self-attention serves the core building block of transformers. Given an input consisting of II' tokens TRxx self-attention with key- matrix W E Rdxd and value X = (a(),, x(²), ...")....,."" ( E
matrix V E RRdk the self-attention model is defined as follows:
f(x) = X(XWX X
where S: Rd + IR is the softmax function. In practice, additional tokens are often appended the raw input features X, and this position is used for the model prediction. For example, [CLS] token added for classification purposes [27]. and prompt vectors can be appended to adapt pretrained models to new tasks. Let R denote the tunable token ([CLS) token or prompt vector) and concatenate it to X to form X, == [q X J E (TT+))xd The cross-attention features derived from Xg and X are given by:
Siq W X S(XWX
f(X) = S X, WX JVV
XV,
Then we can use the upper term for classification, set and denote e = E Rd. This brings us to our attention model of interest:
f(x: - = q)
=
(2)
Here the trained parameters are W and v. We note that self-attention with respect to such tunable token was considered in several other theoretical works (see, e.g., 26)).
In this work, follow Ataee Tarzanagh et al. 66 and consider the following model:
f(X; u. p. = V X T 3(Xp)
(3)
Here, the trained parameters v. Rd. Note that model corresponds to fixing q O1,0......0 0) in Eq. (2). We note that Ataee Tarzanagh et al. 6 showed that in the model from Eq. W (with fixed q) and on q (after setting W = La) admit one-to-one mapping (see Lemma from their paper), and hence the dynamics in models (2) and (3) are essentially similar for any choice of fixed q. Thus, instead of the key-query matrix W we have a vector p that controls the attention. We denote the output of the softmax layer S x,P) by 8; = (8t.1 81,2 )t.r)" and denote the output of the attention layer X, 8, by r; = 8t, 14 + $1,2 + ... + S..TE. where 0 S si.1 Si,r S 81,1 + +... Si,r are the attention on T tokens the i-th sample.
gradient iterations
3 Benign Overfitting with Gradient Descent
In this section, we study the joint optimization of the head a and attention weights p using the logistic loss function. We show that the model exhibits benign overfitting after just two iterations of gradient descent (GD), Formally, for a training dataset (Xi, Hi) we define the empirical risk as
C(v.
E( f(X;u,)))
where ((z) log(1 + exp(-2)) is the logistic loss function, and f is the model from Eq. (3). We consider GD optimization. Starting from po 0 and vo = 0, we have
L. (v. Pt) and p:+ Pt BV PVp((v, Pd). Ut+1 U. vV

---

where 8 is the step size. When we discuss some fixed t, we sometimes write in the subscript "t = =", e.g., P:-2 instead of p2-
We make the following assumptions:
Assumption 3.1 (Assumptions for GD with SNR ((1/v7)) Let ò > 0 be desired probability of
failure. Let cp 2 6(T - 1) be a parameter that controls the signal strength. For any constant cT 2 there exists sufficiently large constant C' C(er) that may depend cr, such that the following conditions hold:
1. Number of samples n should be sufficiently large: n 2 C' C'log(1/8)
2. Dimension d should be sufficiently large: d 2 C. n² n- log(n/0).
3. Signal strength is: p = Cpvd/n.
4. Label flipping rate 1f: 0 S 1/ - 1/C.
5. The step size satisfies: [z, 1.02 =] for z cœ n/d, where cæ == ca(1, Cp. T).
6. Initialization at zero: |
= | 0.
7. The number of token T satisfies: 2 < T cr.
Item D is required to estimate the number of clean examples compared noisy examples. The assumption of high dimensionality (Item is important for enabling benign overfitting (see Figure 4 the appendix), and implies that noise tokens from different training samples are nearly-orthggonal.
This assumption appears in many prior works on benign overfitting in neural network classification
(c.g., Cao et al. [15]. Kou al. (16). Meng al. [7.. Frei al. [8 19] Xu al. (20). Kornowski
et al.
[22 Xu and Gu (1 Item 3 states that the signal-to-noise ratio (SNR) is P
vV (2(1/vn) In
Section
we will discuss how the SNR affects the dynamics of GD.
Interestingly, SNR of ((1/Vn) matches the tight lower bound of the required SNR that al- lows for benign overfitting with the min-norm (i.c. max-margin) learning rule that we will
SNR 2.1/n
study in Section Item 4 fensuress the flipping rate is small enough to allow the model to learn the signal token. Item 5 required to achieve benign overfitting after two iterations; with smaller step size, the model will need more it- erations to fit the noisy samples, which will demonstrate empirically in Section 6 Item ensures that the number of tokens is constant.
Sumple Size
6.
SNR
Remark 3.2 (random initialization). The as- sumption of zero initialization (Item is with- out loss of generality, as the model is smooth around O. Indeed, the gradient with respect to the softmax weight p is Lipschitz (as shown in Lemma 6 of Atace Tarzanagh et al. (6), and the same also holds for the gradient with respect to the attention head v. since f(x; p) is linear in v. Consequently, the loss and gradient for any sample under random initialization with zero ex- pectation and sufficiently small variance closely resemble the loss and gradient under zero initialization. Thus, our result can easily extended to
Figure 1: A heatmap of the test accuracy (aver- aged over runs) after achieving training accuracy 100%, plotted across varying signal-to-noise ra- tios (SNR) and sample sizes
(n). The red curves represent the expression SNR = 2.1/n. This validates our tight bound of SNR ((1/vn) achieve benign overfitting, and with smaller SNR the model exhibits harmful overfitting. Pa- rameters: = 900, T = 5, = 0.015, = 0.1, test sample size 2000.
small random initialization. This is also demonstrated empirically in Figure 8 in the appendix.
We now state main result on benign overfitting with GD:
Theorem 3.3. Suppose that Assumption holds. Then, with probability at least 8 over the training dataset, after two iterations of GD have:
5

---

The classifier X H sign(f ((X; 01=2, Pt=2)) correctly classifies all training data points:
yi = sign (X; u1= Pr=2)), Vi E [n].
The classifier X + sign( ( Vt=2 Pi=2) generalizes well:
P (y # sign(f(X; Ut=2, P( S exp(-v/r/2) exp (-Cind/(e, (c. (X.u)-D
enennnnn n!.))),
where Ci == Ci(r) > is constant. We can also conclude that for the clear-labeled distribution Delan we have
(
Vt=2, Pt=2)) S exp( exp (-Cind/ (.. )))
(X (X.a)~DDaae
which approaches zero as d and n grow (see items
assumption 3.1.
High softmax probability for "optimal" tokens:
ViEC:
1
ViEN:
E 1+ (T 1)c2
(T
where و is the softmax probability of the j"h token in the 7th sample time t.
The third item in Theorem 3.3
provides insight into how benign overfitting occurs in attention mechanisms. After two iterations of gradient descent, the model assigns enough attention to the signal tokens for clean examples and to the noise tokens for noisy examples. This enables the model interpolate noisy training examples using the noise tokens while still achieving good generalization performance through the signal tokens.
Remark 3.4. When cp is constant (i.c., the constant C' in Assumption 3.1 may also depend cp), the bounds on the attention probabilities can be improved to a + for all i C.
4 Benign Overfitting of Max-Margin Solution
In the previous section we showed that GD exhibits benign overfitting in a setting where the SNR is ((1/vn) Vn). We now turn to study the overfitting behavior of single-head attention models, when using another learning rule, which returns solutions that interpolate the training data with large margin while keeping the parameters norms small. As we will show, such a learning rule allows us obtain benign overfitting under the same requirement on the SNR.
We note that learning rules that return min-norm (or max-margin) solutions are considered natural, and hence understanding properties of min-norm interpolators has attracted much interest in recent years, even in settings where the implicit bias of GD) does not necessarily lead to min-norm solution (see, e.g., Savarese et al. (28), Ongie et al. [29]. Ergen and Pilanci (30), Hanin [31], Debarre et al.
work, min-norm interpolation with Transformers has been studied Ataee Tarzanagh al. 5), and benign/tempered overfitting in min-norm univariate neural network interpolators has been studied in Joshi et al. (34).
32] Boursier and Flammarion (33). More directly related
The motivation for analyzing min-norm solutions also arises since they roughly correspond training using GD with weight decay (which encourages norm minimization). Thus, while in the previous section we showed that GD exhibits benign overfitting after two iterations, this section our results suggest that GD with weight decay may exhibit benign overfitting also after long training.
We first consider the following learning rule:
(B(r,))) P(.,))) [al|| Stlllllnee
argmax min y: f(X;;
(4)
where is the model from 3). The learning rule returns solution that maximizes the margin minsejn] f(X;; v. p) under à restriction on the norms. We make the following assumption:
Assumption 4.1 (Assumptions for max-margin with SNR = (01/(1())))))))) Let E (0, 0.5) be a desired probability of failure. For any constant er 2 2 there exists a sufficiently large constant C = C(cr) that may depend on cr, such that the following conditions hold:

---

1. Dimension d is sufficiently large: d 2 Cn² log(n/6).
2. Number of samples n is sufficiently large: n 2 C log(1/6).
3. Signal strength: p 2 CVd/n
4. Label flipping rate: 1/ 1/C.
5. Norm constraint of satisfies: R 2 C C/mn/d+1/p log pn.).
6. Number of tokens: 2 T' S Cr.
Items 2 and 4 are similar to Assumption 3.1 Item requires SNR 2 S(1///), as in Assump-
tion 3.1 We will show later a lower bound on the requied SNR for benign overfitting, implying that the (T)/v)) bound is tight. Item 5 provides the lower bound for the norm constraint of p so that the model can allocate enough attention on signal tokens to achieve benign overfitting. Note that the norm constraint r for a can take any positive value. Intuitively, since the model is linear in e, once p is properly learned, v can achieve accurate classification even with a small norm.
With these assumptions in place, we give our result benign overfitting with the learning rule (4.
Theorem 4.2. Suppose that Assumplion 4.1 holds, and consider the classifier X sign(](X; (),,)), P(y, where (M(y. P().R) is solution Problem (4). Then, with prob- ability at least å over the training dataset. have:
The classifier sign(f (Xx; ; ((r,)))P(r,n)) correctly classifies all training data points:
= sign( (x; (), P(r,B))), Vi E [m].
The classifier sign [ [X; (rrr ((r,R))) generalizes well on test data:
P (X (X.))~D
(y + signi / X ((r, ((. (().)))))
S + exp exp( (Q(d//2))))) + exp 12( (1-
log(n) )²)
40 R
where = /wn/d
(Gp
Remark 4.3. To see why Theorem 4.2 implies benign overfitting, consider the limit R + cc. Then, the upper bound for test error becomes 7) + exp(-S(dd 2) + exp( ((ppppp(1pppp mn/d)-//// -))), which can be arbitrarily close to v if d is large (see Assumption
item
Next, we consider the following learning rule, which explicitly requires to minimize the parameters norms while allowing interpolation with margin at least y:
(u., P.)) = argmin s.t. min yx Y. ||l| ||w
(5)
(E(n]
where / is the model from Eq. 3 benign overfitting for large enough 7 and d:
We show that under Assumption
4.1 the solution (v,,, p.) exhibits
Theorem 4.4. Suppose that Assumption 4.7 (Items] 7 through 4 and 6) holds, and consider the classifier + sign(f( X; (oy, Py)), where (w-y, p-)) is a solution of Problem ( Then there exists
Yu such that for any 7 2 "fa with probability at least 1 8 over the training dataset, we have:
The classifier sign(f(X (X; p,)) correctly classifies all training data points:
y/-
Vi [m].
The classifier sign( [[[[ U, p.)) generalizes well on test data:
IP (u # sign X: u,, P)) S exp( exp((S0(d/1)))) +cxp(-0(11/ mm/d-11) (X
Thus, for large enough 7, the theorem implies that the trained model interpolates the training data, and the test error approaches 77 as d 00.
7

---

Note that Theorems 4.2 and 4.4 hold only when SNR ((1/v/). This raises the question: what the overfitting behavior min-nomn interpolators when the SNR is smaller? We now consider the two-token case where p I /I/Cn for some sufficiently large universal constant C. We will show that in this case, although the model can correctly classify all training samples, the test error of learning rule 4 is at least a universal constant, indicating that benign overfitting does not happen. Formally, we make the following assumptions:
Assumption 4.5 (Assumptions for max-margin with SNR = O(I/Vn). Let å E (0,0.5) be desired probability of failure. Consider the case where every sample composed of two tokens, X; (pis Ex) There exists a sufficiently large constant C such that the following hold:
1. Dimension d sufficiently large: d Cn² log(n/6)
2. Number of samples n is sufficiently large: n 2 C Colo(11/)
3. Signal strength: p S / d/Cnn.
4. Label flipping rate is a constant: 77 E (0, 1/2).
5. The norm of p should be sufficiently large: R 2 CV à log ("f).
Compared with Assumption 4.1 the main difference is in the second item, namely that SNR < 0(1//n) Additionally, the condition on is relaxed, as in our analysis clean and noisy samples can be treated equivalently when the norm of the signal token is sufficiently small. With these assumptions in place, we can state the following theorem which characterizes the training error and test error of the single-head attention model when the SNR is small:
Theorem 4.6. Suppose that Assumption 4.5 holds, and consider the classifier X sign(f(X: ((r P(r, R)), where (V(r.R) Ry. R().R)) is a solution of Problem (4) Then, with prob-
ability least ô over the training data, we have:
The classifier (f ( (r. ((r correctly classifies all training data points:
ys = sign( f (X: (), P(r,,))), Vi [m].
The classifier sign(s(X ((, R)) does not generalize well on test data:
P (u + sign(j (() P(r.))))) 2 16
(X (X.g)
5 Proof ideas
Proof ideas for Section 3 Here, we discuss the main proof idea of Theorem 3.3 Since the initialization is at zero, 82 is a linear combination of the training data tokens. Specifically, we can
express vt=1 as 1 #1 X1 M2 Σn y Σr= EL,T, where A/ 0, X/
0. Note that X₁ > 0, 2₂ < 0 holds since CCI > WT. We begin by analyzing the first step of GD. We show
that after one step, the coefficients of vt=1 can be estimated as | s 41 - 2n), k E [2] # and 0-=1 शा [n)] Moreover, we have p 0, and hence for a training sample (X, (14: E Er), the margin is:
T Σ T=2
0 (X = T 11 + (T) -i | + T
||,
where in the last approximate equality we use the high dimensional setting (i.e. by item 2 in our assumption d > n² log(n)) to neglect the "i.rr" U:1;05=1E. ET, Ej. term, since it is much smaller (in absolute value) than the other terms. Indeed, we have w.h.p. that E.. S log(n). ||& 12 d and recall that || (d//)) (item in our assumption). Therefore, for a clean sample j E and large enough cp. the margin is yj Ut
0.-1, Pt=1) R cg > O, where eæ
parameter that controls the step size B.. On the other hand, for noisy sample j E W, we have y/ [) Dt=1 Pt=1, R -cg < This implies that after one iteration of GD the classifier sign(f (X:: Ut=1, 1t= does not correctly classify noisy training samples, but still correctly classifies
8

---

0.95
Probeiiitt
+B5
Nccurary
from
0.5
10
10 lterations (Log Scale)
10"
10' Iterations fLog Scale)
(a) Train and test accuracies.
(b) Softmax probabilities.
The top panel shows the train and test accuracies during training. It shows that benign overfitting occurs after 2 iterations. After the first iteration, the model correctly classifies the clean training examples, but not the noisy ones. In the bottom panel, show the softmax probability of the signal token for clean and noisy samples (average of the softmax probabilities $),1 over C and N respectively). We see that after 2 iterations, the attention focuses signal tokens for clean examples, and on noise tokens for noisy examples. This aligns with Theorem 3.3 and Remark 3.4 Parameters: 200, d 40000, T = 2, B = 0.025, p = 30, 0.05, test sample size 2000.
Figure 2:
clean training samples. Together with pt=1 = O, the classifier (f v Pt=1)) will also correctly classify, with high probability, a clean test sample. Moreover, since the loss function & is decreasing, the loss of noisy samples, denoted f=-1.. E N, dominates the loss of clean samples i= i E C. This implies that after two iterations, the coefficients 10)-2). E N, of the noisy tokens in 0t=2, corresponding to noisy samples, grow faster than the coefficients |A!=2 of the first (signal) tokens. This property important to allow for interpolation of noisy examples. We also show that P:=2 focuses on optimal tokens, namely, on noisy tokens for noisy samples (i.e. 6 > 1/1++ (T D) vi E N), and on the signal token for clean training and test samples. Using this property we conclude that the model parameterized by (Vr=2, Pt=2) exhibits benign overfitting.
Remark 5.1. Note that our proof implies the following behavior of GD. After the first iteration, the model correctly classifies only the clean training samples, resulting in an expected training accuracy of 1 - 17. Additionally, the model successfully classifies a clean test sample w.h.p.. leading to the same expected test accuracy. After the second iteration. the model interpolates the training data, achieving a training accuracy of 1. This is shown empirically in Figure 2 When using a smaller step size, we empirically observe similar trend: after the first iteration, the model learns the signal tokens, and with more iterations, it captures the noisy tokens of the noisy samples and fits the entire dataset. This behavior is shown in Figure 3
Proof ideas for Section 4 We now discuss proof idea for Theorem 4.2 Consider the behavior of P()..)) and (t) as R, r + oC. The main insight is that p converges to a direction that focuses on signal tokens for clean samples, and approximates the corresponding max-margin classifier over the attention outputs. First, we consider the attention output r; = X," S(X,p) as a selection of signal and noise tokens based softmax probabilities. We define learning rule that selects the signal token μ4 for clean samples and a fixed noise token & for noisy ones. Then we show that any p which is not aligned with this rule (that is, does select clean tokens for clean samples) leads to a strictly smaller margin. This implies that the optimal solution also tends to select signal tokens for clean samples. Since test data shares the same signal tokens, the attention output test samples also concentrates on the signal token when R is large. Combined with a near- maximal margin vector (r) the model predicts correctly on test samples with high probability.
6 Experiments
We complement our theoretical results with an empirical study on benign overfitting in single-head softmax attention. We trained single-head softmax attention models (Eq. (3)) on data generated as specified in Section 2. using GD with a fixed step size and the logistic loss function. In all figures, the x-axis corresponds to the time and has a log scale. We add 1 to the time so that the initialization t t=0 0 can be shown in the log scale (i.e. iteration 10 is the initialization).
In Figure 2 we consider a setting similar to Theorem 3.3 and demonstrate that benign overfitting occurs after two iterations, and that the behavior of GD aligns with our discussion in Remark [5] We also plot how the softmax probabilities evolve during training, and see after two iterations a behavior similar to the last item of Theorem 3.3 and Remark 3.4 In Figure 3 (Appendix A.44).

---

consider a similar setting, but with smaller step size, Here, benign overfitting occurs after about 150 iterations. In Figure[[ we present a heatmap of the test accuracy across varying SNR and sample sizes, validating the SNR threshold of ((1/v/) established in this work. Additional experiments are provided in Section A.44 including investigation of the overfitting behavior for different dimensions, self-attention w.r.t. the first token, multi-layer transformers, GD with weight decay (which encourages norm minimization, as in our learning rule from Section ( and experiments with real-world datasets (MNIST and CIFAR-IO) 10). These experiments demonstrate that our results capture the overfitting behavior also more complex settings.
Acknowledgments and Disclosure of Funding
GV is supported by the Israel Science Foundation (grant No. 2574/25), by a research grant from Mortimer Zuckerman (the Zuckerman STEM Leadership Program), and by research grants from the Center for New Scientists at the Weizmann Institute Science, and the Shimon and Golde Picker Weizmann Annual Grant. Part of this work done while ZX, SF, and WH were visiting the Simons Institute for the Theory of Computing.
References
[1] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3): 107-115, 2021.
[2] Peter L. Bartlett, Philip Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48), 2020.
[3] Vaswani. Attention is all you need. Advances Neural Information Processing Systems,
2017.
[4] Hongkang Li, Meng Wang, Sijia Liu, and Pin- Yu Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. arXiv preprint vrXiv:2302.06015. 2023.
[5] Davoud Ataee Tarzanagh, Yingcong Li, Christos Thrampoulidis, and Samet Oymak. Transform- ers as support vector machines. arXiv preprint arXiv:2308. 16898, 2023.
[6] Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-margin token selection in attention mechanism. Advances in Neural Information Processing Systems, 36: 48314-48362, 2023.
[7] Bhavya Vasudeva, Puncesh Deora, and Christos Thrampoulidis, Implicit bias and fast conver- gence rates for self-attention. arXiv preprint arXiv:2402.05738, 2024.
[8] Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 25(49):1-55, 2024.
[9] Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers lear to imple- ment preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36, 2023.
[10] Jingfeng Wu, Difan Zou, Zixiang Chen, Vladimir Braverman, Quanquan Gu, and Peter Bartlett. How many pretraining tasks are needed for in-context learning of linear regression? Preprint, arXiv:23 2023.
[11] Samy Jelassi, Michael Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. Advances in Neural Information Processing Systems, 35:37822-37836, 2022.
[12] Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis. On the role of attention prompt-tuning. In International Conference on Machine Learning, pages 26724-26768. PMLR. 2023.
10

---

[13] Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta Numerica, 30:87-201, 2021.
[14] Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-248, 2021.
[15] Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 25237-25250. Curran Associates, Inc., 2022.
[16] Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer relu convolutional neural networks. In International Conference on Machine Learning, pages 17615-17659. PMLR, 2023.
[17] Xuran Meng, Difan Zou, and Yuan Cao. Benign overfitting in two-layer relu convolutional neural networks for xor data. arXiv preprint arXiw:2310:01975, 2023.
[18] Spencer Frei, Niladri Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning T'heory, pages
2022.
[19] Spencer Frei, Gal Vardi, Peter Bartlett, and Nathan Srebro. Benign overfitting in linear classifiers and leaky relu networks from kkt conditions for margin maximization. The Thirty Sixth Annual Conference on Learning Theory, pages 3173-3228, 2023.
[20] Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi, and Wei Hu. Benign overfitting and grokking relu networks for xor cluster data, arXiv preprint arXiv:2310.02555 2023.
[21] Xingyu Xu and Yuantao Gu. Benign overfitting of non-smooth neural networks beyond lazy training. In International Conference Artificial Intelligence and Statistics, pages 11094- 11117. PMLR, 2023.
[22] Guy Kornwwkii, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in relu neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[23] Erin George, Michael Murray, William Swartworth, and Deanna Needell. Training shallow relu networks on noisy data using hinge loss: when do we overfit and is it benign? Advances in Neural Information Processing Systems, 36, 2024.
[24] Kedar Karhadkar, Erin George, Michael Murray, Guido Montúfar, and Deanna Needell. Benign overfitting in Ieaky relu networks with moderate input dimension. arXiv preprint arXiv:2403.06903 2024.
[25] Jiarui Jiang, Wei Huang, Miao Zhang, Taiji Suzuki, and Liqiang Nie. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization. arXiv preprint arXiv:2409.19345 2024.
[26] Keitaro Sakamoto and Issei Sato. Benign or not-benign overfitting in token selection of attention mechanism. arXiv preprint vxXiv:2409.17622 2024.
[27] Alexey Dosovitskiy. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint
2020.
[28] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
[29] Greg Ongic, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01635, 2019.
[30] Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of machine learning research, 2021.

---

[31] Boris Hanin. Ridgeless interpolation with shallow relu networks in 1d is nearest neigh- bor curvature extrapolation and provably generalizes on lipschitz functions. arXiv preprint (2t:::2009//9600) 2021.
[32] Thomas Debarre, Quentin Denoyelle, Michael Unser, and Julien Fageot. Sparsest piecewise- linear regression one-dimensional data. Journal of Computational and Applied Mathematics, 406:1 14044, 2022.
[33] Etienne Boursier and Nicolas Flammarion. Penalising the biases in norm regularisation enforces sparsity, arXiv preprint wrXiv:2303.03355 2023.
[34] Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate relu networks. arXiv preprint arXiv:2307. 15396, 2023.
[35] Roman Vershynin. High-dimensional probabilit:: An introduction with applications data science, volume 47. Cambridge university press, 2018.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly describe the main contributions of the paper, including theoretical results on benign overfitting single-head softmax attention models, the role of signal-to-noiss ratio (SNR), and conditions under which gradient descent and min-norm interpolators exhibit benign overfitting. These claims are matched by the formal results and empirical validations presented in the main body. The scope and limitations, such as the dependence on SNR and model structure, are also properly stated.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses several important limitations throughout the introduction and main results. Specifically, the theoretical guarantees rely on assumptions such as a sufficiently large signal-to-nois to-so ratio (SNR) and a simplified single-head attention architecture. These assumptions are clearly stated, and the paper analyzes the tightness of the SNR condition by showing that lower SNR leads harmful overfitting. Additionally, the empirical results limited to controlled synthetic settings, and the paper does not claim generalization to real- world datasets or multi- head models. These limitations are acknowledged and contextualized in the appropriate sections of the paper.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All theoretical results in the paper are clearly stated with full set of assumptions. Fach theo- rem is numbered and referenced in the main text. The main paper provides proof sketches to convey the core ideas and intuition, and all formal proofs are included in the appendix. The assumptions, such as the signal-to-noise ratio requirement and model structure, are explicitly stated either in the theorem statements in the surrounding discussion. The results build on standard tools and are self-contained, with all dependencies clearly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The paper fully discloses the necessary information to reproduce the main experimental results. All experiments are synthetic and based on simple, well-specified setups. The main text describes the model architecture (single-head softmax attention), the data generation pro- cess (signal and noise token distributions), and key parameters such signal-to-noist ratio (SNR), input dimension, number of tokens, and learning rate. In the appendix (Section A.4). the authors provide additional experiments under varied settings, including smaller step sizes. self- aef-attention variants, Gaussian initialization, multi-layer and multi-head architectures, and gradient descent with weight decay. These results not only confirm the robustness of main claims but also provide detailed context for reproduction. While code is not released, all critical implementation details and parameters are clearly documented in the paper and supplement.
13

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The paper includes synthetic experiments that support the theoretical findings. Although the code is not released at the time of submission to preserve anonymity, we plan to release the full implementation, including data generation scripts and instructions for reproducing all figures, upon publication. The code will include details on environment setup and execution commands to ensure faithful reproduction of the experimental results.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The paper specifies all relevant experimental details necessary to understand and interpret the results. Since the experiments based on synthetic data, there is train/test split in the traditional sense. The model structure (e.g., single-head softmax attention). data generation process (signal and noise tokens), optimization method (gradient descent or GD with weight decay), initialization schemes, step size, and number of iterations are all described in the main text and in Appendix A.4 These details sufficient for reproducing the setup and understanding the empirical trends presented.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
The paper does not report error bars or confidence intervals in the experimental figures. The experiments are designed to illustrate theoretical trends in synthetic and deterministic settings, and each experiment is run with fixed parameters without multiple random seeds. While this suffices to support the qualitative conclusions drawn in the paper, acknowledge that reporting statistical variability (e.g., over multiple random initializations or data draws) would further strengthen the empirical analysis, and we leave this to future work.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments in the paper are computationally lightweight and were single NVIDIA T4 GPU. We will include note in the appendix specifying the compute environ- ment and approximate runtime for reproducing the experiments. No large-scale compute or specialized infrastructure is required.
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httt:::s//heurps..coom http::/ss...pppoootttcccccccnnnn
Answer: [Yes]
Justification:
The research theoretical in nature and uses only synthetic data. It does not involve human subjects, personal data, sensitive attributes, any real-world deployment. The work
14

---

follows all ethical standards outlined in the NeurIPS Code of Ethics, including transparency, reprodueibility, and fair representation of results, All authors have reviewed the Code of Ethics and confirm compliance.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper purely theoretical and does not involve real-world data, human subjects, or any deployed systems. It studies simplified attention-based models under synthetic settings and is not expected have any direct societal impact. We therefore consider this question not applicable.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not involve the release of pretrained models, real-world datasets, other assets that carry a risk of misuse or dual use. All experiments are conducted using synthetic data, and the work is purely theoretical. Therefore, safeguards for responsible release not applicable to this research.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use any third-party assets such as datasets, pretrained models, or existing codebases. All data synthetically generated, and all model architectures defined within the paper. Therefore, no external licenses or terms of use apply.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does release any new assets such as datasets, pretrained models, or software packages. All experiments are based on synthetic data generated according to procedures described in the paper. No additional artifacts are bundled or released as part of this submission.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve any crowdsourcing research with human subjects. All experi- ments are conducted using synthetic data without any human participation or annotation.
Institutional review board (IRB) approvals or equivalent for research with human subjects
15

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does involve any research with human subjects. All experiments are conducted using synthetic data and do not pose risks to individuals or require IRB approval.
16. Declaration LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
No large language models (LLMs) were used as part of the core methods, theoretical analysis, experiments this research. Any potential use of LLMs was limited to minor language editing and did not affect the methodology, rigor, or originality of the paper. Therefore, this question is not applicable.
16

---

A
Appendix
Proots for Sec.
17
Notations for Sec.
17
A 1.2
Additional Lemmas Definitions for Sec
18
Proof of Thm. 33.
19
A.2
Proofs for Sec.
30
A.2.1
Proof Idea for Section
30
A.2.2
Notation for Section
30
A.2.3
Proof of T.1.
31
A22
Proof of Thm 4.2
57
2.5
Proof Thm,
67
A.2.6
Proof of Thm. 4.6
69
A.3
Supplement Lemmas
84
Additional Experiments
87
Remark A.1. Throughout our proofs, we assume without loss of generality that μ4 (p. 0, ...., 0)T,
H2 = (0, ..., 0) and & (0, 0, 5 { for & ~ (O, L2-2). Indeed, since f4 and are orthogonal, we can find orthogonal matrix A E Raxd such that Apr = (p. 0, o... 0) Ap (0, p. O..... 0) and A&; ~ (AA,, A(I - pi /p2 قسعu A which mean that Ag; (0, < ) for & NOO 22) We emphasize that orthogonal transformation does affect our results.
A.1 Proofs for Sec. 3
A.1.1 Notations for Sec.
3
Given a, b, E R, we denote by c(a + b) the close segment Ic(a - b), c(a b)). Given vector we denote by ar]i the 7hh coordinate of æ, and æ!i j] denotes the subvector containing the elements from the 7th to the jth inclusive. We also list some key notations used in this section for convenience.
Table 1: Usefull notation.
5hh token in the th sample you, ai i.c. jth token score in time t
Zi Th
a
softmax probability of the 1th token in the ,hh sample in time t
4s
We remind that C.N C [n]] denotes the indices of clean and noisy training examples, and Cx, denotes the clean and noisy examples from cluster à: E (1, For example if E C₁, then Fi = #1 and y1 1, and for j Mi we have that Ij,1 Mii and /1 -1. Let S'(v) = VS(v) diag(S(v)) - (())S(u)) denote the Jacobian of the softmax function S(v) at Rd
17

---

A.1.2 Additional Lemmas & Definitions for Sec
The following equations will be useful throughout the proof:
VoC(u,p)
x , S(X.p)
(6)
n
8 x 5' 8X.pp) where 7/ = =; X; vp((u,p) Σ
(7)
(x) 1 S'( = diag(S(u)) (())S(D)
(8)
(9)
Definition A.2 (Good Training Set). We say that training (X I...., Xn) is good if exsists some universal constant ep (that may depends just on the number of tokens 7) s.t.
| + on (1))d, for all E [n], T E f2.
(Ei,:Eirr1 S cD /llog(n//), for any i,j E Tn E (2, (,T').
,..,,, T) such that (i, +
NWl E ( on (1)) and [Cxl (1- - 7
(1)), for k {1,2}.
Definition A.3 (Good Test Sample). We say that test sample (X (I), .2........ TT). is good w.r.t. a training set (X1,.... Xn) and C₁ if
d Civn'
[ E+ii s
Vi (n), E (2..... T) 7
Next we write Lemma A.68 slightly different, and also add a formal proof for completeness:
Lemma A4. Let 8 > 0 and > 0. Suppose that Assumption 3.7 (itm] 7 holds with constant C, then with probability least 1 6/2 we have that
|C&l (1 /2/C), Wal Th (1 v (1,2).
Moreover, we have
|Cx| 5 -1-n1 n Wile n 71 o,,)),, wk (1,2).
Proof. By Hoeffding's inequality,
(1 - -1 m) 2 - /nlog(1/0))/) s 28/8,
which means that with probability at least 1 - 8/8 we have that |c,l E (1- cn), where
On 22 log(16/8)/n. Hence, if > Colog(6/8)), then c. / 2 1llg(1660) Vn 2/C. Similarly, we can estimate [W&l for E {1,2], and by union bound, the result follows.
The next lemma A.5 allows us to analyze vpC as a function of the score gap.
Lemma A.5. Let z, 7 E Rd and let a = S(p). Define "min == min 22 Yr, Ymar = max 7/r
7 = =mmmi + "maa)/22 and : ("maa 1/mn) Then
Σ 2,04
T #
=T'' E (n 77) 01)a1
2002
01
Σ
2:0, (1 01)0121
a1
i=2
1=2
18

---

Proof. Observe that E/=1 ai =1 1. Therefore,
='s((p)y dingg(()) 2=aaa 7=
2170:
200
7/44
i=1
T
E21711 + + (7 Σ
Σ
7100 + +x + Σ
2,00
2101
+
2,04
04
1=2
1=2
i=2
I
T
= -(1=0) - a11 +
Σ
ai
Σ
2,04 +
71 a171 + aann
+ +e)
Σ
aa)
a1
1=2
1=2
1=2
T
(()=c) (a1 a1))) Σ
(m1 (arm + -a) 2,0;
=on17 =) an + 2c)
20; + (1 an)(n - 7 - =)
T
T 2 2
T
=01 (7 - 11) Σ
2j04 + (1 01)(11 701 t
2,00 + on
Σ
2,00 + (1 - 01 011
1=2
1=2
1=2
Σイ= 2 2;00
T
(n 7) - an)m
t
2 1=2
2,00 +
2,04 + (1 01 01)01
1 01
1=2
We will show that in our setting the score difference between noisy tokens (i.e. e from Lemma A.5 relatively small and thus the second term in Lemma A.5 is negligible compare to the first term Remark A.6. To prove Thm. 3.3 we demonstrate that pp can be expressed
function of the score gap between the optimal token to the noisy tokens. Specifically as a function of 71, - 7 where Y : y X, is the vector score of the sample, and with some additive term that depends on the score gap between any two distinct noisy tokens, defined as 6; == maxtyrr' |7,,r - -,,r' (see Lemma A.5). We establish that in our case 6; is relatively small. This technique noteworthy on its own, as it enables the analysis of softmax weights in multiple-token setting without relying on
potentially unnatural assumptions, such as all non-optimal tokens having identical scores 77 or the presence of single noisy token with larger norm compared to other noisy tokens (25).
Lemma A.7. Let æ1, I2...., In be independent random variables such that [[x,] 0 and H E
[-b, bj almost surely. Consider the sum of these random variable Sn T1 + + Fn. Then Hoeffding's 's theorem states that
Pr[S 2 n o.75b] S <exp(-22 22n
/462/44bn) 25xp(-2n156//440- = exp(-no.5
A.1.3 Proof of Thm.
Proof. To simplify the proof, we express the step size 33 in an alternative form:
C9 c= Ci C (iooog(c))// where Ci
167
167'3
[
0.998(T 1) 1.02
V 0.998 1)
8 = cg n/(e,. d),
(10)
which is equivalent Item 5 We emphasize that eg can be arbitrarily larger than any constant whenever 7/ is small enough i.c. C' from Assumption 3. large enough.
Next, under Assumption 3.1 we argue that with probability at least 1 - the training set is good
(Def. A.2 i.c.:
Cal E (n o and No (1 (1 = (1)), for & E {1,2}.
(1 on (1)) for any i [n], T = (2....,T),
19

---

((.r)))))))) ccD cD /dlog(n/6), for any i,j E [n], T, E f2,... ,....TTy T such that (i, + (,T'),
where cp is some universal constant. Indeed, this holds by Lemma A.65 Lemma A.4 and the union bound. We emphasize that the notation o, (1) represents a term that becomes arbitrarily small as n increases, and thus it can be bounded by small constant if C. from Assumption
T iis large enough. iterations. See Remark A.1 for the data setting used throughout the proof.
Next, we show that under good training set, the model exhibits benign overfitting, already after two
GD after iteration. We start by analyzing the first coordinate of vi (i.e. after one iteration of GD). By assumption 3.1 (item we have that po Uu = O, which implies that 6, - 11/2, for
any E [n]. Hence
VV. (c.Co(o
8
Σ
%
111
B 2Tn
Σ
yiP
3 2Tn
Σ
y&P
Tn
i=1
sEC1
8
(ICr1 -WG1)p
2Tn
8
(1 - 2n = on (1))p
"good" training set
47
In the same way, we can estimate the second coordinate V;=1:
3
2
Σ
yip +
Σ IEN
yip E 47 (1- 2n + on (1))p,
2Tn
2T
vel2
where we remind that y/ = -1, when E C2, hence tt=1 [2] has the same bounds as 0==1 (1=1 just with opposite sign. We move to analyze the rest of the coordinates of 0==1;
3
u 3 d
E..
2Tn
i=
T=2
Overall, can write vt=1 as X/=1
11 11=
112
Li=1 110
D
Eir with
3
B
B
A E (1 21 + on (1)), 1 E
(1 2n + on
0111
(11)
4T
47
2Tn
Moreover, since -0=0 for every E [n]. we have that pt = (see Eq. 7
Preparation for next iteration. To estimate (#==)Prt=2) we first need to estimate the loss for clean/noisy samples and the score 7/r (see Table 1]
We remind that ||,,,10 p² = e,d/n (Assumption have that
(item 31). For j CR. where &s E (1,2) we
1 T
Vif(Xzi 1t= Pt=1)
T y,
since pi 0
T=1
T-1 where the last inequality holds since the training set is "good" and a constant i.c.
E + | - p4
| 2 *+
y > 0 (12)
Σ
E E (1x .d.
20

---

Since the training set is "good" then by Eq. 11
we can bound yj [ 0/ Pt=1) as follows:
d +
3(T - 1)
8
Pt=1) -
47 (1 - 2n (1)) of
d(1 o1) (n)
n2
2
2 - 22n) + 2(T - 1) + on(1)
3d
Assumption 3.1 (item
4T
n
(1- 11-221 2n) + 2(T - 1)/2 + 0n(1)
Cg
Eq. 10
47
1.1cs
(13)
47
where the last inequality holds since cp 2 5(T -1), which implies that 2(T 11//2 0n(1) > 0.1. Similarly, we have that
8
B
on (1)) _ o(d)
y, f U1=1, P
2
(1 - 27 - (1)) Ep- +
d(1
47
21
2 2n) + 2(T - 1) On (1)
3d
472
( (1 (1-2n) 2n) 2(T 1) p (1)
cg
4T
0.9cg
(14)
4T
For E N3. where {1,2] we have that
T
= T
y5 T
Σ ZラJ
since p1 = 0
T=1
1 E - T
1 T
T
3 oodd
11
+
00
|5 +
yj 1
t= >0 0 (15)
where the last inequality holds since that the training set is "good" and T is constant. Since the training set "good" then by Eq. II we can bound y fXx Ut 1. Pt-1) 1) as follows:
BT 1)) d(1 + o1) o(d)
47 (1 2n - -o,(1))
c.. n
2
n
22(1 2n)) + - 1) on (1()
3d
Assumption
3.1 (item
2
0.9cg
(16)
47
where the last inequality holds since cp 2 5(T'-1), which implies that 2(T-1)/ S 0.1. Similarly, we have that
B
2n (n)) 2 d
3
3
yi fx y; 11 P:=1)
11
d(1 on)
(
47
n
2T2
21 2n) + 2(T 1) - (1)
3d
47
n
(11 - 2n) - 2(T - e/ (1l()
C9
4T2
-1.1c
(17)
2
21

---

We remind that -6 1/(1 + exp(vx 1/=1, Pi=1))) and that 3 = cg : nn(dee)) (Eq. 10
Combine with Eqs. 13 and [4 we have that
i C, 1 2 + cxp(.1e111111 4T == m [ > 0
(18)
i E C, - S 1/(1 + exp(0.9ca :- - - 1/(4(T - 1)
(19)
where the last inequality holds since cg 2 log(cp)/ / and since 1 + exp(0.9cp) 2 4ep for any Cp 2 6.
Moreover, by Eqs.
16 and 17
we have that
jEN, -
1x0++cx((0090g/444)) m/y' 2 0.99
(20)
j JEN, - 1/ (xp(++xx((_11e/AAT)) :- M 1
(21)
The notations Mc and m (My and m denote the upper and lower bounds, respectively, on the derivative of the loss for clean (noisy) samples at time t, and we use them throughout the proof. We remind that 1f, you, Tt Then by Eq. 11 for i Cg we have that
1=1 E
3 (1 - 2n + on())))² =
Cg (1 - 21, = o
47
4T
7 2Tn
B
d(1 + on (1))
2T (1/2g + on (1)). VT [2
CB
|=1
(1 - 2/02 - 2n + on (1)) N222" 4T
CB
(22)
where in the calculation of //. we use Eignn Villi Enjr' ET, E =0x(1) d, which holds since the training set is good, For i E NR. we have that
B
(1
2n + oz (1))p²
C3 (1 22n + on()))
47
47
1=1
B
d(1
+ o,
CB (1/22, + on vr (2....,T] T}
2In
2T
7,2
M6.1
1=2
CB
(1 + 2/62- + on (1))
(23)
47
GD after 2 iterations. Analysis of 0z=2. Observe that
8 - -V
33
Σ
1 Xi S(X.P))
y/
Σ
Tn
i=1
i=1
r=1
We start by analyzing the first coordinate of V L(U1,)))
3
-DV,C(or.Pi111
G y,
[1]
G [.
Tn
Tn iE
B
Tn
Tn
E
iNNi
B
Tn
1,
-his
pp.
(24)
iEC
JEN
Observe that
Σ 1 iEC
Σ
1 2
(1) + on oL)) Mx
good training set
JEN
n (n + on (1))
Eq. 21
2
22

---

Substituting it into Eq. 24 we obtain that
VV.((v) PT)[
2T (n o, (1))p
On the other hand, by Eq.
we can upper bound the first coordinate of the gradient of a by
B3
f ).
Tn
VEC
B
17T P
G < 1/177, Eq.
19
Similarly, we estimate the second coordinate of V.L(vn PI):
B
3
(17
om (1))p -V 12]
p.
2T
17T
Write V.=2 = Xp
+ X
+ Em= 11 Σズー &. Together with Eq.
11
we get that
8
B
5,3
X = x V Po1
(1 + on (1))
S
(25)
47
17T
16T
3
x|3 >
(1 4n on (1))
(26)
4T
3
53
1 = _ - V L (1)
(1 (1))
2
(27)
47
17T
16
B (1 - An - (1))
(28)
4T
Next, we analyze the rest of the coordinates of V VeL(u1.P1) P1).
8
3
-VV,C(o, d|
Σ 9
yi
Σ
E
Σ
Gi Yj Σ Ej
Tn iEC
Tn
jEN
r=2
and use it to analyze the coefficients of the noise (second) tokens in Vt=2, i.e., 0 Indeed, for i C we have that
B
3 (- G, + 0.5)
0--2 00=1
Tn E1
Eq.
Tn
B
E
(me + 0.5), (Me 0.5) Tn
(29)
Tn
For j E N we have that
Tn ( -- + 0.5)
Eq.
j
Tn
B
E
(mw + 0.5),
(MN + 0.5)
(30)
Tn
Tn
Next we move to analyze Pi=2-
Pi=2 focuses on noisy tokens for noisy samples.
Define Timmin min,22 Vi.r, Mamaz max+ 22 Yi.r 7k (Tmin + +mmaa//2 and E; (Tiar Imin) )/2. 2. In words Nomin Mamaz and 6; are the maximun, minimum and the gap among the scores of the noisy tokens the 7th sample respectively. By Eqs. 22 and 23 we have that & = o,,(1) (1) ca for any E [n]. Observe that P2 VppL(( p1). Therefore, for any j Ae. and {?..... T) have:
po (æt - 2zjr)
T 3 n
=- -j.e) T PVpL(v, p.) (0z11 xzjT))
8
E x , X 5' (X.ppt) 13
l X
s'(ppt))
S'
(31)
iml
23

---

Write Z1, == ,. Observe that 21,.j = (I .......) 0) for i E Cj U.,, and 21,.,J = 0
otherwise. By Lemma A.5
we can lower bound the first term Eq. 31
8
8
T 1 21,
S'(ipi)
Σ
On (1))a
71 iEC
8
Σ iEN
4
on (1))
where the (1)) term is from the second tern in Lemma A.5
Now we move to the second term of
Eq. 31
Write ž == X, Observe that X, = (0. x 1 j.,.......
T. 1, j,rs
x , Tz,r)
By
Lemma A.5 we can lower bound the second term in Eq. 31 as
8
1
S' (Xip:))
t=1
B
Ey (71 1=1
- on (1))
Σ
T 1)n
r/ml
B
(-11,)
-1 (1 on(())
||00,,|12 + Σ
TT
1)m
T'şT
3
-= - -1- "a
on(())
Σ
(T 1)m
iEnsigj
r'=2
where once again where the (1 - on (1)) term is from the second tern in Lemma A.5 Overall,
P2 B - 23,1)
2
3
- - )1 a311)0,,11111111 on())) (1ærHall + ||,,-11 |/T,-11/((TT (T--1) 1))
2=1
3
Σ
-h,s - a . |
on (1))a (0]]
n
sECu:sj
+ n
Σ
-1- - on (.)(
8
Σ
N 2 (1
a )a 11 + on (I)) Σ (a
(T 1)n vE(n)iist
Observe that a 1 1/T and that (1 -1,1)a;111 (T 1)/T² for any E [m]. In Eqs. we calculate the score (e.g. (! Overall, we can lower bound the above equation by:
22 and 23
3
CB (1 2/+2/ 22 - o,)) d(1 on (1))
mN
T2
4T
(T - 1)8
(1 (1- on
Me
C8
(1 - 2//c/ - -2n on (1)) -
T
2
47
(T - 1)8
[Wal - my 47
CB
(1 + 2/6 2n + on (1)) d
T
- (1)))
n. MN C3
(1 + 2/c² 2n + 0n (1))en/
T2n
47
24

---

By Assumption 3.1 (item d >> n² log(n))), the first term dominates the last term. Then we can lower-bound the above term by
(T-1)
(1-1) 11-
on (1))
"
d Me CB (1 - 2/02- - 27 on (1))
T
2
47
n
(T- 1)33
(Wul . my C3
(1 + 2/ 27 + on (1)) d
21)
T
4T
(T - 1)c3
(1- 1| On (1)) -Mc
2/68 2n On (1))
27
4T
(T 1)
1) (1 - (1)) mN
(1 + 2/06 - 2n + on on()))
27
4T
where in the last inequality we use 3= (cg n Next, we argue that the second term in the above Eq. is at least 1000 times the absolute value of the first term (i.e. the second term dominates the other terms). Indeed for eg > 1/1 we have that Mc < 0.0002y for small enough 1j (Eqs. and 21.. This means that my 1 2 0.0002 Mc. Then we can conclude that the second term is at least 1000 times bigger than the absolute value of the first term. Overall, for any i E N we have that:
P2 (zg, 2z,1) 2 0.999
(T - 11
(1 11-11onm0 on mN
n
1
(1 + 2/ 2n + oo((1))
2T
47
T T-11 1
0.999 czn-
(my (1- 2n - on (1))
8T
T (T-1
0.998 czn-
8T3
2 2log(cp))
where that last inequality holds since c3 2 2 2llg((p)m
87
(Eq. 10p. We conclude that,
0.998(7
1
1 Σー exp ex (2),r xz,1))
1+ (T
1 (T 1)02
(32)
1) We also conclude that for any j E N we have that
1
Σ
(33)
1+ ( 1)e p
1+ (T - 1)c2
In the next part, we assume that C from Assumption 3.1 may depend on cp and we show that pt=2 focuses on the signal tokens for clean sample.
p:-2 focuses on the signal tokens for clean sample. Similarly to the previous case, for any j E Ca.
and r E [,....,T) we have
p (z),1 =z,,))
3
on (1- (1=,,,11 + || 112 /(T ((T-11) 11) (755 1=1 - -
B
Σ
-e ( 7 (1 (1- (1))at (1 a..)
B
Σ
G : (7/ (1-1-
(1 o (1)) (1)) (
iEN
T
B
Σ
E
G. h - (1 . (o' (1)) Σ
(T 1)m
iEin]:is T/:
7'=2
25

---

Observe that a = 1/T and that (1-a::))) -0,11100 = (T 1)/T² for any i E [n]. In Eqs. 22 and 23
calculate the score (i.e. ) Overall, we can lower bound the above equation by:
8
47 (1 2/c2 2n on (1)) d(1 - oo
mc
T
(T
1)8
"
on(11) d n (1 2//2 -2n -21-on(1))
(1-11-on(1)))
me
T
2
4T
(T - 1)/8
C3 (1 2/c 2n on (1)) of
(n + (1)) MN
T
47
(T - 1)8
n My C (1 + 2/c 2n on CD v dlog(n/6)
(34)
7
4T
Observe that the first two terms are non-negative. Then we can lower-bound the above term by
(T 1)8
d
(17 on
.M 2/ 2n o (1))
T
n
(T' - 1)8
C3 n MM
(1 +1+ 2/2 21 on (1))cn (ll))////lg(n/////l// dlog(n/0)
T2n
47
(T' l)03
1
(1) + On (1)) .Mx
(1 4 2/ 2n on (1))
T2
4T
(T' 1)
1 47 + 2/ - 21 + on (1))cnn
Vlo(n/5)
MN
T2
vdee
By Assumption 3.1 (item 2) the first term dominates the second term whenever C' from that assumption is large enough, which means that we can lower bound the displayed equation by 1.0002 the first term i.e. by
1.0002
(T (--1) 1)c3
1 (1 2/c (n (1+ on())) 1/2 .MN 47
2n + on on)(
T2
(T - 1)03
2 110002
(In Mv + 2/0, - 2n on (1)))
873
(T-
2 1. 11.000
873
> 2.1 log(ep):
where the last inequality holds by Eq.
10
We conclude that
1
2
(35)
1+ r= exp(p2 (o,,r - x1,1))
1+ (T - 1) (2. (oop(.11og(c.))
1+ (T 1)
Together with Eq. 33 this proves the last part of the Thm.
P:=2 focuses more the signal tokens for clean sample when ep is constant. In this part, prove Remark 3.4 this case, C from Assumption 3.1 may depend on Cp- We can start directly from Eq. 34 that states that for any j C2 and t E {2...., we have
P2 [.j.11 Fzj.))
T
(36)
> 9
CB
(1 - 2/ - 2n - (1)) d(1 on on(()))
me
T
4T
+ (T- - 1)B8
(1-1) (1- (1))
n
mc
C9
(1 - 2/c, - -27 - (1) d
22n
2
47
(T- 1)B8 -11)
(n (1)))(1)) n Mr C3
(1 + 2/23 - 2n + no (1)) d 2.)
T
4T
(T- 1)B8
n MM
C3 4T
(1 + 2/c² 2n + on (1))
22n
26

---

Since C' from Assumption 3.1 may depend on Cp. Then My,me are also constants. Overall, the first
term dominates the last term since d > ny n dloggn//) (see Assumption 3.1 (item 2 The second
term dominates the third term for small enough 7) (see Assumption 4 Overall, we obtain that for any
(....., T} that
P2 (x)11 - Iz,7) > 0,
(37)
which means that for any we have:
1
1
1 Er= exp(p) (x - xz,1))
T
(38)
Next, we move to original assumption and don't assume that C' from Assumption 3.1 may depend on Cp. We show that: The classifier sign(f [Xx; P1=2.P==2) classifies correctly clean training samples. Let (X, (a........, Ry,r), 95) for j E C. We remind that æ = μt for l E {1,2) and zj.r = Ej.r- we have that,
T
Pt=2) = ajJ1 02
2
14 +
Σ
a
jir
2=2
T=2
and it suffices to prove that
(,( 0.
Indeed,
T x₁ + 8U Σ
v,f(Xx;u.p) = y
j.r
1=2
Dj.t
T=2
T
1=2 a
1el 11
+ Σ
aj.r
= 0, ||) 11
+
jjr
Vj
Σ
0:0 2 T E1
UjdR > 0
7=2
r'
T
max dg57 min +E(T]
||m8x|12 0, 1|5 11²) +
Σ
j.rr
1=2
y/
Σ
0= 2T.
7m2
T
min
57
B
-
d
pr
2
2n
B
d(1 - on()))) d(1-o
- nnI B
Tn
(MN - 0.5)cD dlog(n/0)
Eqs. 30 26 and 28
V
d s ncp / dlog(n//)
as required.
The classifier sign( (f[( 21=2, (P=2) classifies correctly noisy training samples. Let (X, for j N. We remind that æj.1 = μ4 for E {1,2) and o,,r = Ej.r. we have
that,
T
J(X, U, 2, Pr 2))
1=2 a
02
1=2 1=2 a
4.7 02
Mj.rr
and it suffices to prove that
Vf(f(X; U2. P2)) > 0.
27

---

Indeed,
T
yj 3;f(Xx;u,p) = yy (= 22 J11 + yj
Σ
j,z 02 2/
T=2
T
= =- N15l |Ax/ 1?2 +
Σ
0, 0
|1 11 + Σ
aj. yj
E
y Es
3322 < <0
7=2
7=2
53
d
1=2 3
1=2
p
2
Σ
(mx + 0.5)d(1- on))
16T
n1
Tn
T=2
1=2
nT
1),
(MN 0.5) dlog(n/0)
Eqs. 30 25 and
Tn
5,9
d - -
(1-
8
(mw + 0.5)d(1 - on((1)
16T
c/
Tn
B
(T 1) Tn 0,
(Mx + 0.5) v / log((//))
Eq. 33
d > NeD v dlog(n/0)
as required.
The classifier sign(f(X:; 0t=2, Pt=2)) classifies correctly clean test samples.
Let (X- = (ax1.... .r), v) be fresh clean sample i.e. (X, y) ~ Delean Observe that œ1 = μt for some 1: E [1, and y = iff k = By Remark A6 exists some constant 61 such that with probability at least - n exp( (-sp(dd/p d/ d/2iCnn! for some C2 = (p(Cp.11n) that will be chosen later, we have that (X, 3) is good test sample w.r.t. C2 (Def. A.3 i.c. | xt.7' < d/C2n
0.75, We work under the event that (X, y) is a good test sample and show that y = sign( tt=2, Pt=2). Recall that P2 -BVpL(n Pi) and therefore (similar to the clean sample case) for any E , T):
12 (x1 xz)
1, (7 - a (1-
a, (1))
π1 iEC
8 Σ
(1 - (4 (1-) x1,1)
iEN
B
E h t=1 - (1 - a [a 1=1 (1 + (1)) Σ (xf 7'=2
)
iE(m]
2=2
Observe that a² = 1/T and that (1 a (T- - 1)/T² for any E [m]. In Eqs. we calculate the score (e.g. 1 Overall, we can lower bound the above equation by:
22 and 23
(T - 1)B8
(1 (1- 17 on() n C9 (1 (1- - 2n- - on)))) d
n 2
me
2'n
2
4T
(T-1)8
(n + (I))
n
MN
C3
(1 + 2/ - 2n + on (1)) d
12n
2
4T
(T - 1)8
n1.75
0.75
MM
C9
(1
2/ 2
2n + (1))
d
n'
4T
C270.75
Observe that the first term is positive, and the second term 100 times smaller than the last term whenever C2 201/( Then we can lower bound the above equation by 1.01 times the second
28

---

term i.c. by
1.01 (T-1))
CB
(1 2/ 2n (1)) [
(17 + on (n))
My
T
4T
n
1.01 (T' (T'-1) 1)cg
(n7 + on 0x))
MN
(1 + 2/ 2n + on
7
47
1.02 (7 - 1)
-1.c3
87
2 2.1 log(cp);
where the last inequality holds for e3 s 2
( (I.02((T-))
(sce Eq. 10 and note that
8 2.1 2.1/1.02 < 1.022 16/0.98). We conclude that
1
011
1=2
1 1 e (a, - xz)) 2 1+ (T exp log(cp))
(39)
1+ ()).))
Let 0 = Me for A E [1, and 2t = Er for TE TT.. We have that,
P() = aj 1-2 22 x1 +
Σ
2m 22
a
xr.
7=2
and it suffices to prove that
y(f(X; 0.
Indeed,
uf(Xz; = u 11 + Σ
1=2 dx a
r=2
= =
du
9:0!=2
ET, Er'
ydx
Note that 0:=2 is independent E.r. Moreover, since v E,r is a symmetric random variable with
d.CCnn0775 (assuming the test sample is good with respect C2), by Lemma A.7 with S E-
probability at least exp(-n".5/) /2) we have that y Eiem,, 0.00=22) ST,, 2 -n 0.75 0.75 max; 00 (/255.775 Overall, we can lower bound the displayed equation by
T-1
d C2
2 1- 1x
|
12
Σ
of
(T
1) max 10:
2
d
2 a1
1=
(T - 1)²
(MN + 0..5)
Eqs. 30 26 and 28
+
n
Tn
C2
1
3
d 2 - (T 1)2 B
(Mx + 0.5) C2
1 (T - 1)c2.1
4T
+1
n p
Tn
> 0,
where the last inequality holds for C2 = Cg c011 where C3 is large enough constant which depends on T. Overall by choosing C2 mar (C3c 0.1 11/)) and union bound, we have that
P(X.)~D(V + sign (X U1=2, Pi=z)))
5 n P( (y + sign( (Xx; 0t= p()))))
1n + ex-ee + exp( dn/ C2c n 1.5 + log(n)).
This proves the last part of the theorem.
29

---

A.2 Proofs for Sec. 4
A.2.1 Proof Idea for 4
We first provide the proof sketch for Theorem 4.2
Our key proposition that Pir.n)) will converge
to direction that focuses on the signal token for clean samples, and ((r.R) will converge to the corresponding max-margin solution. To begin, consider the output of the attention layer r; X; 8 (P) which is combination of signal and noise tokens. This can be considered as a "token selection" based on softmax probabilities. Consider the following second-toker selection rule:
P x (1) pks i Ck. k E {1,
r: x; (2) E1 i E.
This selects the signal token for all clean samples and the first noise token for all noisy samples. Following this token selection rule, we define the corresponding max-mane margin solution as Psee and
Vsec: Definition A.8 (p-SVM for Second-token Selection).
Psec argmin || PER
subject to:
p (ar (0 x. 21, a; = for iEC and = 2 for i E N, tE (l....,, T) faz}.
Let =:: = 1/el be the margin induced by Psec-
Definition A.9 (v-SVM for Second-token Selection).
Usec == argmin ||l||| s.t. ric 2 1, for all i [n],
vERa
Let see == u/ol be the label margin induced by Usec.
We prove that P(r,R) has direction that selects the signal token for every clean sample, since
otherwise it will induce max-margin at most sec TT=::112pp> mmx 8;,1), where 8,, is the attention probability on signal tokens. This is strictly smaller than l'sec-
iEC
Then, we show that when jointly optimizing p and v for (4), we obtain solutions that induce similar max max-margin Pre and Usec R. To be specific, have
min PT, (14x Ei,)) 2 rE[2,T] induced by Psec-
C)ER for all i e Cr, [2], where is the margin
The label margin for clean samples induced by (/r /r in SVM is at least (1 - 7 sec.
Here, 7 are some small value quantifying the difference between (P(r.R)) 1)(,.))) and (precs Diec). As R -> co, both Ç and 7 converge to O. Thus, for sufficiently large R, we conclude that P(r, (1 {.) becomes large for i E Ca.
This ensures that P(r. captures sufficient information about signal tokens, which enhances the accuracy of test sample predictions. Since the signal token remains invariant between training and test data, for a given test sample (X,9) y) with X (μ² E ..., {7), w.h.p. the attention layer Prr. will focus on fe when R is sufficiently large. As a result, the signal token μ* will dominate the attention layer's output. As Ur, R) converges the corresponding max-mare max-margin solution, can make accurate predictions (n²*, (.) Thus, the component induced by the signal token y (V(r, 14*) is large enough eliminate the randomness introduced by the noise token (denoted by A(E*) here) and the model will make an accurate prediction with high probability: y P(r..) X) 2
y 1 (r, H² - A(E*)= 2 0.
A.2.2 Notation for Section 4
We first introduce some additional notations. Denote
n1 [C], n2 W/] ni4 |C,).
72 [M] for i 1,
30

---

Denote the output of the softmax layer ((X;p) by
8, = (1 -1-11 -11-)
Denote the output of the attention layer X, 8 by r; (1 3;) + B.C. where 0 S 3r S 1 is the attention on the noise token of each sample. Then f(X;; v. = (v, r.) can be treated as a linear classifier (Ue, [r)) Additionally, from the property of log function, item I in Assumption 4.1 can be understood as d 2 On log (po(py((())/8) and the same is for item For the proof of this section, we consider the case when
(v,
2 Assumption[4.1 I. have the following theorem.
2, and consider the classifier X + ifgnf((X, ( P(r, )), where (v(r, P(r,n)) is the solution to Problem (4). Then, with probability least - over the training dataset, have:
Theorem A.10. Suppose that Assumption 4.1 holds when
The classifier (i (r. ((. R()) correctly classifies all training data points:
y/ sign(/ [ (5;; (r, ((r,n))) Vi [n].
The classifier sign(](X: (r P(r..))) generalizes well on test data:
P(X.))~D() # sign (f (X; (rr n2) P(r,n))))
I + exp( - ((dd//)))))))))))))))))))))))( exp (-2( (1-5)
log(1) (12)
)²).
/nndd 1/p²
R
where Ç = =0(ymm/d+ log(p))
A.2.3 Proof of Thm. A.10
Proof Sketch
There are two main parts in our proof. the first part, we prove that only by selecting signal tokens for clean samples and noise tokens for non-clean samples reach the maximum margin when doing SVM on (yi, r:)vejn)-
Definition A.11 (Optimal Token). We define the "optimal token" " for sample (X,, ys) as
r H4, iEC r = E., ieN
(40)
Next we define the respective max-margin solution for p and v. We will show that when jointly optimizing parameters and for (4), they will converge to their respective max max-in solutions as R, r oc, which are Prom and Vmo defined as follows. Definition A.12. (P-SVM)
Pmm argmin |p||
subjected
pd (14 - 2 p" TS, p4) 2 1,EEN
(41)
for all E [n]. E = 1/| Pmm is the margin induced by Prom-
Then for a given p. we define v(p) as the standard max- max-margin classifier on (3/, rs)ie(nj and Umm as the standard max-margin classifier on (yi, rf re)))))))))))))))))))) which can be understood as the limit scenario when p Pm and R - +00
Definition A.13. (v-SVM)
(p) = argmin ||||| s.t. y/ u 2 1, for all i E [m].
(42)
vERd
T(p) = (p)] is the label margin induced by and p.
When r; = r2,6 e [m),
Umm argmin ||l|| s.t. yi w TTr 2 1, for all i [n].
(43)
vER
I 1/ ummll is the label margin induced by Umm
31

---

After proving the convergence direction of P(r.P) and ((),)), we can utilize their properties similar to Pum and Umm to proceed with the training and test error analysis. Therefore proving that the model exhibits henign-overfitinng
It is worth noting that in the first part, we show the optimality of the token selection in (40) is strict in the sense that mixing other tokens in r, will shrink the label margin. We formalize this into the following proposition:
Proposition A.14 (Optimal Token Condition). Under Condition 4.1 for all p. the token selection
under p results in a label margin of at most I' 1i Pmp
max (1 Sia.) in (A.13) where
a; = I(i E C) + 21(i E N) and C' > 0 is some constant.
We now highlight some aspects of the technical novelty of our work compared Ataee Tarzanagh et al. [6), Jiang et al. [25). Unlike Atace Tarzanagh et al. [6]. our results are in a non-asymptotic setting, while their work focuses on the case where both R, r - co. Additionally, we do not rely on any additional, unnatural assumptions about the data distribution. In contrast, Ataee Tarzanagh al. 6 specifies the optimal token indices that achieve the maximum margin, and Jiang et [25] assumes that for each sample, the first noise token has a much larger norm than the other noise tokens.
We give detailed proof in the following.
Optimal Token Condition
Since Urm satisfies the KKT conditions of the max- max-margin problem (42) by the stationarity condition, we can represent Umm as
2 mm
A1141 + X2142 +
Σ
M:O,E.
(44)
RE(n]
Note that the conditions in (42 can be written as: Condition (Optimal tokens).
2
11 2 1 y:
& Z L,iEN
Plugging 44 in the condition
we can rewrite these conditions as:
A || 2|2 2
- ||22| 2 1
0, | + your
(E, 21iEN
Then we introduce a lemma to estimate the coefficients 0, of Umm under this condition:
Lemma A.15 (balanced noise factor for KKT points). Suppose that Assumption 4.7 holds, under Condition 7 we have that for Umms
8, 0, E
(45)
(1-k) 4nz d (ellog((n?" (6n
0, E
i LEW.
(1 + +))((1 k)d 2n2 / d dlog Gn2 (nog(Gn2/5)) (1 - (1-k)d- 2n / log (6n
(46)
Note that Condition 1 does not have any constraint for samples with E Thus we have 6, = 0 for any i C in the representation (44). For 0 with i E W, we first prove the upper bound by contradiction. Denote j = argmax 0,, Then we have
Proof of Lemma A.15 A.1
iEN
u E, Σ y.ygOr Eg) = 0 12+
Σ *HEEN
iEN
2 03 (1 k)dd - n20; 2 dlog(6n2/5))
32

---

where the inequality is from Lemma A.65 and the definition of j. Consider the contrary case when
0j (I- 2m2 2 (o02)(
we have
1
x)dd 2nz / (ogg(66222 ((1 - K)d - n2 2/ (lloo6nn2//)) 1. yz E
By the complementary slackness, y Ej 1, then we must have 0j = 0, and thus we reach contradiction.
Then we prove for the lower bound. For vj e N we have
< 05115111 +
Σ
1 0 (1 + r:dd n2 max 0g 2 d dllo(6n2/0) TEN
0 (1 s)d
712
2/ dl log(6n2/00)
(1 k)d 2m2y d' (ollo(6n2//5
The second inequality due to Lemma A.65 and the last inequality is from the upper bound we just get. Therefore, we have
(1- 4n2
/ log((n2//)
0j (1 + k)d((1 x)d 2nz dooo (6n (6n²/8)
This completes the proof.
Then we introduce a lemma to estimate |[ l|:
Lemma A.16 (Norm Cmm). Suppose that Assumption
4.1
holds, for the solution Vmnm of 42
under the token selection 40
have
2
7/n
1
2
<
2
+
5mm
2
2d
Ø
d
This implies
|1mm
= 0
7p12
p2
d
Proof of Lemma A.16 represented as
As Umm the max-margin solution and satisfies KKT condition, it can be
Umm N1S4 + A2112 +
En.0.. + 5.00E.
(47)
iEN
As Umm satisfies Condition we have d 2 1/p² and A2 S -1p22. So we could lower bound
as |
|| |mmma
2| 2 2? 11 +
p221 +
0.115.112
y:0,0,0, (E.,
VEN
iEN JEN
2 12 k)
2
17n
p
d3/2
12
2d
The second inequality is from Lemma A.15 that A; (l/dd) for i N and the last inequality is from Assumption 4.1
Then to upper bound [|ummlll I| consider the following possible solution T
④ = p 211 m1
p= -2 u2 +
2y.E:/d /d
SEN
For E C, we have
y. r; - # 2 1.
33

---

And for i E N, we have
D: r; y: E: =2 //2
2yhy (E:, E33/d
JEN J+i
2 2 x) 2n1 v
/8)/d
The first inequality is from Lemma and the second inequality is from Assumption 4.1 Therefore, i is possible solution of SVM problem A. 13 when converges to Pmm So we have
1mm 1 < o 2/0² +
4 |
+
Σ
4yay, (E., E.). <
5mm
d
iEN
iEN JEN
The last inequality is from Lemma A.65 above, we have | 1|2
Lemma A.68 and Assumption 4.1 Combine the results
(
Based on the lemmas above, we introduce our main proposition in this section:
Proposition A.17 (Optimal Token Condition). Under Condition 4. for all p. the token selection under p results in a label margin of at most I' 1/ Pnp
max -ia.)) in (A.13) where
a, = -1=((EEC) 21(i E N) and C' > 0 is some constant.
Proof of Proposition 1. The main idea is to show the optimality of the token selection rule in the sense that mixing any other tokens will shrink the label margin. For a given p. we say a sample æ; is "mixed sample" if r, of r. We say r, is mixture of optimal token and non-optimal token in this case. Note that for any with finite norm, T; + r, This notation is introduced for the clearness of the proof.
We use contradiction to prove Proposition A. by showing that any token selection different from 440) can only result in strictly smaller label margin than that for the max- max-margin problem (42 Since satisfies the KKT conditions of the max- max-margin problem, we can write e as
A1 + A2
Σ y.O,E:
Σ m:
(48)
iEC
iEN
For a given denote o' as the max-margin solution in According to Lemma A.16 we have
42 and 1
1/||0o| as the new label margin.
1mmm 1| =
+
m
2(11/²).
22
d
Then we have
C
C
r
Uumm 3np2
nnp2
max xE(ni
Sias
Uma 3mp2
for sufficiently large d. Here the last inequality uses ||mmmll ||
(211p²).
Thus we only need
consider the case when the new label margin 1" 2 11/2, or equivalently,
||ol|| < 2 2mmll
(49)
Assume that there i samples (0 < h S n) that violdate the token selection rule 440 and among them, samples are from clean set C and I- p samples are from label-flipped set set N. Denote the indices of the samples I,. Then consider the following three scenarios:
p 0, - 0. (All mixed samples come from C)
2. p- 0, -
b 0. (All mixed samples come from N\)
3. p 0, p 0. (Mixed samples are from both sets)
We will separately discuss each scenario and show that Proposition A.14 holds in all cases. Case 1: * 0, k p 0
Under this scenario, we have:
I G I, L Ø.
We proceed to analyze this scenario by dividing it into three distinct subcases.
34

---

p< p< 40,4444+44 2
p p<m,ne + 2. nc, 2. (i, (2),
p-=m
Case 1.1 nD To nC + 80, I nC #
In this case, both clusters exist clean samples that are not mixed. Denote the index of mixed samples I, as (2,,,,,... kp). For every mixed sample kÜ we have rk. = Sx, MA, + (1 3x,) Jk. Then the conditions under Case 1.1 become
Condition 2 (p clean samples violating optimal token selection).
P1 21 - u12 2 1 yov & T y: r; 1,iii,
From the condition above, we could see that in this case, mixing one more clean sample is equal to adding one more constraint. Therefore, mixing p samples will not result in a better solution than only mixing one sample, i.e. larger max-margin in our setting. So we can reduce this case to mixing only one clean sample with index k argmin B,. Denote Tk- Bp + (1 B) for some E [0, 1).
iET.
Without loss of generality, we assume μą. = μr, y4* +1. Then the conditions become: Condition 3 (one clean sample violating optimal token selection).
v Mi N - U2 2 1 you & 2 L yk. rk 21
Denote v' as the optimal solution under this condition. v' can also be written in the form of 48 with coefficients denoted as X1, N/2 and 8% i [n]. Plugging this representation into the condition we
have:
X |1 21
-22- || 21
0 1|2.11 + Σ 0 (E,, Ev) 2 N
BX || + (1 (0% E 112
ye 2
ifk
First, we introduce another lemma similar to Lemma A.15 to characterize the scale of 8/ i [n] in this case.
Lemma A.18. Suppose that Assumption
4.1 holds, under Condition we have
6, 0,
0, E (1-R)d d- 4nz log
(6n
i iEN.
(1+x)d((1 K)d 2m2 (ong(6n2///0 (1-k)d ) - 2n (lo
Proof of Lemma A.18 Same Condition I Condition does not have any constraint for samples with E CV(Kk*) Thus we have 0 = 0 for any i (
Meanwhile, Condition introduces an additional constraint compared to Condition | Consequently, the feasible region for (eE under Condition is subset of the feasible region for {0.) hev under Condition I
Therefore, the bounds established in Lemma A.15 remain applicable to (8) (eN.. O
From this lemma, We can see that 0 (1/d)) for E N. To proceed, we introduce crucial lemma:
35

---

Lemma A.19. Suppose that Assumption 4.1 holds, denote a and o' as the optimal solutions under condition 7 and condition respectively.
We have
1
1mm 11
+
m
(1 - 3)
d3/2
where 0 < Ci & 1 is constant.
Proof of Lemma A.19
We consider two cases under this scenario:
0 0 in v'
In this case, from Lemma A.18 we have 3X1 2 (1 (1+ o(1))/p² and all other conditions are
the same the optimal selection. In order to get min | have X (1 o Bp?
Consider another solution vy which has parameters Au1 = 1/p². A02 = X2. ous = 6 E
[n]). As vo satisfies all the inequities under Condition
1 have To S I So have
1 (>0) Xp) 1
r 2 2 p 1
10022
|
|00012 ||00/12
(1 + +11))/33
-
(1 + () B) + o(1)
1
10o1
.120112
3 2000 2 ||101
0p 2 |
Therefore,
1-8 B
1 1-8
r' 2
voll 1|001 2
(Tu +
I
2Tol/ 1|0'12"
Set c
2 1p we have 1
< r - c(1 B8. Moreover, we could
21 2o
upper bound
c=
2/| | S 2r mm
The last inequality is from ||o0|| 2 |1000|| 2 Imm-
8% * 0 in
From KKT condition, we have
oz- [3 || 1 + (1- (1-3))00 110.-11Ex.112--
(e 1| O. iitle
Σ
As 8/.. > 0, we have
3x: + ||E.- 112 ++x Σ
yk 0; = 1.
iEN
So we can estimate f/ as
1-
p²
yk- (.0, Ex+) S 1- B2
04-1lEA- 1|2
Σ
+ 22ng max f V //doog(6n2 iEN
1-8 3
1
iEN
- B2G
2n / dlogg(6r)) (6n²/5)
(50)
B
(1 - (1-k)d- 2nz / (llo(6n2)))) /5)
The first inequality is from Lemma A.65 and the last equality is from Lemma A.18 We can also lower bound it as
3x,
1- B-2Xpp²
8% ||E 2|2
Σ
yk y.0.0 Exr) 2 1 B
22n max 0f / /ogg(6n22/// /8)
1-
iEN
EN
1-8X,p2
2nz / ddlog (llo(66n2//)
(51)
1-8
(1 k)d 2nz / loo (n dlng(6n2//))
36

---

The first inequality is from Lemma A.65 and the last equality is from Lemma A.18 fore, we have oz- - 0 - p²
There-
8X
+
12 4572
(1 Byd
Then from the third inequality in Condition
we have
0 11
Σ
y.Ve (5: Ex) 2 Yelkk 0%- (E:: Ex-)
PEN
(1 - B)(1 + K)d + 0 m
BX1
2
IKE, Ek-)
2(1 Bx, V /log(6n2/00
Ō mm
(1-8)(1 + k)Vd
2 (log(662/00) Ō (m
vd
3vlog(6n2/8)
(52)
vd
The second inequality is from (50): The third inequality is from Lemma A.65 and the last
inequality is from the first inequality in Condition that Xip² 2 1.
Consider e = =1111 + Napts + E M. which has b1 = M, d2 = N22 0, = 01/(1-
vEini
3y Enngg(Bn? (8) for i N and 0 for i e C. We can verify that ö satisfies all conditions
Vi for Umm
For Vi E N,, we have
0 . 11:11:11
+
Σ
V: (E:, Ev)
(Es, (1-11 3 VVVlo(66n///
= 0, ||
+
Σ
2 1.
Vd
The last inequality is from 522. Meanwhile, have Xı 11
X| 2
-Aell 2 = N/ |2|| plies |m || S |
So o is a possible solution for Condition 3 which im-
Next we estimate the difference between || and | We write the expansion of || and ||01||
| 2 = Xi 1112 1| X
p2
1
Σ
01 Σ
2,,,0,0(EE:1 (E:,E))
iEN
iJENNAS
||06|12 |||| 2 + 1212 +
Σ
0,113111 +
Σ
vay, (E, E2)
(E
NJENUp Kig
From the construction of ö, we have X1 = =>,, 1/2 = >2. So we have
| 1|2
f E+. 2 + Σ 10 07)115711++
Σ
Σ
0 (E.
(ENU(R)) JENU(N
Σ Σ
0,0
TEN JEN?(
13
From 51 we have
1- 32,
8/ ||- || 2
7/M
(1 - (1-B) (1 #x)d
d
37

---

We then bound the last three terms respectively. First we have
(1-0V1/V 11) 18
111= = Σ (0 0.
iEN
iEN
Õ(/vV))
n2 + x)d
(1 - ((1VV))) (11 k)d - 2nz v (llo(662/00)
7m d3/2
The first inequality is from the definition of 0;: The second inequality is from Lemma A.15 and Lemma A.65
Then we bound [/2 Ig as:
12 13l
Σ Σ
(0,0, - 0,0)) 1(5., + 8% Σ E
iEN JEN
EEN
(1 Ō(1/Va))2 - 1 -1 Σ Σ 0000 K(E + n226/=
max 6 E.)l iNN
IEN JEN
Õ(1/V7)
(n2) dllo((622 6n² (6n²/6)
mm
2 + 8/.- A
((1/V/)) ((1 -))d 2nm / /dlogo(g(22///0
Vd
12
δ
mm
+
dc
d3/2
o Qm d3/2
The first incquality is from the definition of 0.: The second inequality is from Lemma A.15 and Lemma A.65 Combining the above results, we finally have
||
1mmm 12 2
C1 - x +
mm
(1 - 3) k)d
/3/2
Now we can prove the main proposition in this case.
Proof of Proposition A.14 in Case 1.1. From Lemma A.19 we have
C1 - 3)2
C1 C1- 101-3Mp0 3X,
|o'12 - ||
3)2 + k)d +
(1 []d (1- = T(1 - -).
C1-1 (1+a)d
In the last equation we substitute
0. Then have
1
1e'12
|| 1
T(1 3)
r
1mnm
|
1
2
|
Uumm
2 1
Therefore,
T(1 - B)
T(1 B)
T(1 3)
T(1 B)
r r-r2 ( + ['] Umm 12 -|/1011
21 4mm 12 11100112
2
1mmm
11|0112
2/
The last inequality is from ||00||
|/mmmll ||. This implies
T(1 3)
C1
I' r'
ST
(1 B).
2 2
1 1sp22
The last inequality is from assumption that || /mmmll and p² 2(d/n).
38

---

Next we consider the other case.
Case 1.2 p
Next consider the case when all clean samples mixed. In this case, all samples in clean set mixed, so the first two incqualities in Condition 3 do not hold, which means that X1 may be smaller than Å₁. But could still prove that Lemma A. 19 holds. We first write down the condition in this case:
Condition 4 (All clean samples violate optimal token selection rule).
{
y & 2 1iEN y: T r; 2 1,iEC
Plugging the representation (48) into the condition, we have:
8% 11 Σ your (Es, Ev) 2 1,1E
B. || 1 (1- 8,)(0; || Σ j71
Dey E 1,iCC
Proof of Lemma A.19 First we assume that max (X}
| -22
[2] = q in optimal v'. If
q 1, this is the same Case 1.3. So we assume that q 1. Denote k- argmin 1-8g and #EC 1-9:
3 = 3k., consider the following condition
Condition 5 (Relaxed version of Condition
0g 1
Σ U,y,O, 2,) Z 0 | Σ
y.yr
Ev) (E, 1-33 E
Compared with Condition 4 the second inequality is relaxed for E C. Therefore, denote the max-
margin solution as T under Condition 5 we must have ||0|| < ||2'|| Then we will prove that Lemma
A.19 still holds between ||umol|| and Tol. which indicates || 112 || 112 Z | |/ Mmmm Z
(1+x) + o()). Denote the parameters in T X1 X2 and O,, first introduce the following
C111-8X PX
lemma to estimate 0. Here we denote a 1-8q for convenience.
1-8
Lemma A.20. Suppose that Assumption holds, under Condition we have
0
E
2n / d log 18)
a ((1 k)d 2n log (6n2//)
iEC,
(1 + k)d
K x)d 2n / doogg6n22//
1
2on / log(onnn (6))/))
0, E
1
1 E.W.
(1 + x)d
(1 x)d d - 2n / log 6n 2/2)
((1 - k)d - 2n dlog 18)
Proof of Lemma A.20
Denote j argmax 0. have vE(N)
0,
| +
(E,, May (E, E 2 01115,11 - n00, / d dogo(6n2/50
2 0, ((1 -)d - 2n
The two inequalities are from Lemma A.65 and our definition jf Consider the contrary case when
0
((-x)) (1-x))d-u 201 we have
4 E, >
By the complementary slackness condition, reach contradiction.
y &, > 2 1, then we must have 0, 0, and thus
39

---

Then we lower bound 0, for E C we have
S 0,
||E:112
Σ
yoy, 0, (E:, Ej) 0, k)dd + 2n max A, d'log(6n2//)
xE(m]
j#i
S 5 x)d + 2am / (6g
(1 (1-x)d 2n log(6n2
The second inequality is from Lemma A.65 and the last inequality is from the upper bound of 0; just derived. Therefore, we have
2n d log (6m² (6)
0 2 (1 + x)d
1-
(1 k)d 2 (lng26n22/)) (6n2/8)
Similarly, for i E N, we have
(1 1- 2 d (ong66nn// 15)
0, z (1 + k)d
(1 k)d 2n / log 6n /
Note that we only consider the case when |||| < ||''|| < 2 1mm || And from Lemma A.20 we have 0, (a/d)) for E C. So we must have (llog n) is some constant. Otherwise, for E C we have
way 0, 2(a). 0. 12:1 a Σ
It further yields that
1 m7 | 96 22(
02
) Σ
87 |EE1
52(
p²
1
+
mm
d
+ no²
) 2 n lolo mloggnn n, (53)
iEC
which contradicts with || 0/V11/p mm/d)
Then the difference between | 113 and |011 becomes
1 |
|mmml || >
11 2/0² + Σ 00 03)13 JEI])
Σ Σ
U.U,O.0,(E..6 Es)
SEC
IN
Σ Σ iEN JENHO
y:,,0,0,(E,,E.))
We will bound every term sequentially. For E C, we have
0.11E 2 a
Σ
v. Ex) 2 aa-
max 0, 2 logg(6n222 6n²//) sE/m]
a
2om log(6n2//)
Ō Ō
(1 x)vd d 2n log(6n2//)
Vd
The second inequality is from Lemma A.65 The first equality is from Lemma A.18 and the last equality is from Assumption 4.1 This implics
Σ REC
111 - 2/p²
a2a²
2
δ
72
Cania²
(1 + k)d
p²
d3/2
k)d
d3/2
The second inequality is due the SNR condition p/vd (II/vn) so there exists constant C²2
that 3 < (1-C))mo [1+k)d
40

---

Then for [1 we have
111 < (max 0f
minn
02)
15:11
iEN
iEN
sEN
1
2
2n d log 6n 6n²
))
- (1 k)d
22 + x)d
(1 k)d 2nn / dlog (6n² 18)
(1 x)d 2n ddlog(6n2/8)
((1 + k)d
(1 - 13)d - Amp doo (ong(6n2// /0) )) 12
1
(1 k)dd 2mm d log (6n2
(1 k)d
mauy log (6n2 16)
θ
72
Vd
n²n2
Ö
d3/2
The second inequality is from Lemma A.15 and Lemma A.20 The third inequality is from the fact that 1/ <1. 1.
As for the last two terms, we bound them respectively, for 12 we have
122 S Σ Σ
Iu.,, (E,, E,ح S n² max KEnn
03 2 dlog(6222
iE[m] ME
a²
< n² ((1 (1--R)d R)d 2n d 6n² (llog(662/8)))) 2 d dlog(6n2/8))
= n²
d3/2
The first inequality is from triangle inequality; The second inequality from Lemma A.65 inequality is from Lemma A.18 Last for Is, we have
The third
1al S
(E,, S (nz)² max 68 22 dloo(6n2//5) iEN
EEN jE
(nz)²
((1 k)d - 2mm dlog(6n2/55)) 2/ /log(6n22//
12n2
δ
d3/2
The first inequality is from triangle inequality; The second inequality from Lemma A.65 The third inequality is from Lemma A.15 Combining the results above, we have
C2n1 (1 3q)²
n
C1 (2)
| 2
|
Ō
(1 () + k)d
d3/2
(1- 0)=1 x)d
Therefore, we could then use the same method as above to prove that Proposition A. also holds in this case.
Case 1.3 p n1, T. nC + 2, I, nCp =
For the case when only one of the clusters clean sets are all mixed, we can follow similar method in Case 1.2 to prove that Lemma A. A.19 still holds. Without losing generality, assume all clean samples with label y: = +1 violate optimal token selection while only part of clean samples with label
Y: -1 violate. we have
Condition (One cluster and a clean sample in the opposite cluster violating optimal token selection).
v #2 2 1
y:v g, 2 1, E you r, 1,, C41 y: r; L
41

---

Similar to previous analysis, mixing multiple samples with label -1 will not result in a better solution than only mixing one sample with label -1. Thus we can reduce this case mixing only one clean sample and denote this mixed sample as - Therefore, we have
X22 || 2
0f ||E 112
Σ y:ye (5:, Ex) 2 L
8
yk_ ,12 || (1 -0) 11E,.,114
E yk yk..v. Ek_ 2
ig
BM 111111 + (1 - () 15x.1?++ + E
01 Ex.)) 2 1, C+1
isk.
Denote q X1 | 2| and 1. Denote k argmin iEC+1 I-P,
1-8g and B Bbr, further reduce
the condition Condition 7 (Relaxed version of Condition 6).
{
0% || + Σ 0 (E, 1,
0 116
Σ wavr 0 (E: Ee) 2 +-3 i E C+1
Condition 7 relaxx the constraints in Condition Mcanwhile, it differs from Condition only in that the last inequality holds for clean samples with label +1. Therefore, we can follow the proof above to show that Lemma 19] holds in this case.
Then consider the second scenario.
Case 2: 0, k p 0
Similar to the previous part, there are two cases we need to consider under this scenario:
1. k - 122.
2. k - n22.
We will go over every case sequentially.
Case 2.1 k: < n22
In this case, part of noisy samples are mixed. Denote the mixed samples kj. ky,,... kg kk-p- And for every mixed sample k, we have B,Ex. + (1 3,) Then the conditions under Case 2. become:
Condition 8 (k p noisy samples violating optimal token selection rule).
v μ1 N To μ2 ž y &, 2 1 E. [k: --pp)
yk, v rk. 1 kk -p]
We could also write the last inequality as
U,, T + Uk. (1 - 8.) 1h: 2 1, E [A: - p)-
Therefore,
yk. Ee, 2 (1 yk, 3,) pk. 3/., i [k pl.
For noisy samples, we have y/ = -1 when μ4; = μm and y = 1 when μ4; = μ2N so yk. uk., S and thus (1 - yk. (1 -1:3))0' 3/3 2 Compared the constraint in Condition that yk, v ps: > 1, N,, the new condition is strengthened. So mixing I more noisy samples is equal to strengthening
42

---

1 constraint in the original setting. Therefore, mixing k samples will not result in a better solution than only mixing noisy sample. Similarly, we can simplify this case to mixing only noisy sample and denote this sample as li.. We have r A + (1 P) and assume that E /41.
Denote v" is the optimal solution under this condition, and the parameters in v" are Xi: X and 6". Then the conditions become:
Condition 9 (1 noisy sample violating optimal token selection rule).
f1 N - μ2 2 1 y:u0 &, 2 W,i
yk.v TH- 21
Plugging the representation (48 into the condition, we have:
X Illl >
X/ || 2
-1E: + Σ
yzy- 0 0z Ex) 2 ( 1,iEN
(1 3)X" || 2 3(0 ||Ex- + E
yk ye0% Ex-)) 2
We first introduce the following lemma which estimates the parameters of the noises. We define
1 + (1 B)A p1 12
B
for the convenience of the following proof.
Lemma A.21. Suppose that Assumption 4. holds, under Condition 9 we have
0%-
(1-1)) -2n2 / log (6n (6n2/8) /8)
8h 2 (1 + +n)d (1- 2nz v dl log (6n2/0)
(1 k)d 2n d log (n2/8)
kd) 2((a 122) / d log( (6n²
max
0 S
((1 k)d 2222 / (l log (6n /5))
(1- 20m v d log Gn 6
min iiik
0" 2
+ kt)d
k)d 2m2 log 6n
Proof of Lemma A.20
From the last inequality in Condition 9 we have
IE.. 2|2 +
Σ
yelk. 2a>)
iEN.
The last inequality is because Mfllur 1|2 2 1 and 0 < 3 Denote argmax 0", have
(E(M]
U E, = 11,11 +
Σ
V. (E
iEN
2 (1((1 (1- - k)d n2 max 0'" 2 log((n2)/))
iE(m]
= 07((1 K)d - n2 2 dlog(6n2)))
The first inequality is due Lemma A.65 and the last equation from our definition of Consider the contrary case when 0²
we have
(1 (1-x)d 2012 / d (olg(66' /8)
y "T E, > a.
43

---

By the complementary slackness condition, y, & (+ then we must have 8 = 0, and thus we reach a contradiction. Therefore, we have 0% S 83 S
3
(1-m)d- 2nd / doog(6n222 /5)
Then denote j' argmax 0 we have
yyu" "T Es 03 11,11+++11++
Σ
Billy 0 (5:, Eyr
iEN
2 0j x)dd - max
0/ 2) - 8% v (oog(6n2//0) /6)
2a / dddo/dlonnnn
((1 - x)dd n2 2 (og((622/8))
(1 K)d 2/z dllo//llogo//0/
The first inequality is from Lemma A.65 and the second inequality is from the upper bound of 0%. we just get. Consider the case when oz. (1-x)d+2(a m2) y (6n2(()
we have
(1-=)d (eled-ddd 2na (dlog(6n2) /8))2
Vy Ey > 1.
By the complementary slackness condition, if yy Ey then must have f7. = 0, and thus we reach a contradiction.
Then we estimate the lower bound of 0% when j # k. We have
1 1 " Ej 0
y, (E;, Eソ} < 01 (1 + k)d + max 0f 2 lloo(6n2/8) iE(m],iA
Σ
kE(m)
1 + (1 3) 11
S 07 + x)d
2n2 v dllo(6n2/0))
B((1 - k)d 2n2 / (6ng/66)))
where the last inequality is from the upper bound we just get. Therefore, we have
2112 v d dlogg6n22/11 10) (1-(1-))
1 X 3) M1
02 2 k1+
--)= d 2n1 / /d (llo((6226))
3
for all j N and hi.. Lastly we lower bound 0% We have
1 (1 11 S yu. n Ev. 0% (1 + k)d + n2 max 0'' 2 dlog(662/1) 18).
rE
Similarly, we have
1 1 (1 3) m1l1 (1 x1+
2112 / d log 6n /0)
0% 2
3
(1 k)d 2n (6g
(6n 2
After getting the bound of parameters, we could derive the norm difference as above
Lemma A.22. Suppose that Assumption 4.1 holds, denote and v" as the optimal solutions under condition 7 and condition 9 respectively.
We have
Cs(1 -8)
| 112 |
d
where C3 +(1).
Proof of Lemma
A.22
From the third inequality in Condition 9 for i E N, of k* we have
8 [e:ll +
Σ
O. (E. y:bke 0% (E:, Ex-)
44

---

Then we add Vizk- (E:; Ex+) on both sides, where we set w =0% Then we have of || +
(1+x)d-2 2 2l010((622/8)) S S
a-1
O.V Ev) + y:tk- wi::
2 1 Vilkk (0%- w)(E:: Ex-)
2 1 - 112(00% w) v dl log (og(6n2/))
(1 + x)d 2a / d dlog (6n² 10)
(54)
(1 a)d 2 dl log(Gnn 18)
The second inequality is from Lemma A.65 Now consider a new : = 11 + Tap + Σ 8, scin
with
A = Xi; 1== = X/:
0, 01 - 11=0/11-2(000
-2
w)v w) //loll(6nn (6n2 (6)) for i [n). K*
and
Tz-- 1 2(0% w) d'lo (6n² 18)
W
We can prove that & satisfies all constraints for Umm-
From the first two inequalities in Condition 9 we have π1 |م 12 X 2 1, 1 u2 1
X2 u2 1 > 1. Then by dividing 1 2(0% w) v d (logg6n22/0 (6) on both sides of 54), for
Vi E N. i o k- we have
0, 21.1::11 + Σ
0: (Ei, 11
Lastly we prove that O2- ||E=- 112 + E
Yelk (,, 2 1. From the last inequality in Condition 9
itk
have
0%. ||Ex 1 +
Σ
uke U:0' (Ei, 2
Dividing - 2(0%% w) / (loog(6n 15) on both sides, get
0/. Exx 112
Σ
yelka (E,
1 1-2(0% ww) / log(6222/))
1 2(0% w) / (log(6n2//1
if
Therefore we have
a 10% - w) E1 1|2
10% w) + :zdd 1.
F.- ||Ex. 11 + Σ
yo (E,, Ex.) 1 200 - w) / log (ogg
20% w) ddoog(662///
k
The second inequality is from Lemma A.65 and the last equality is by our definition 8% w a-1
(iin)d-2/dlo((erz/ Thus, T is a possible solution under Condition and || 2 |mmmll
Next we estimate the difference between ||o" 12 and || The expansion of ||
2|2 and || are:
||l|||2= = x || 2 +
X!?
Ueel 1 +
0 + +
01 (E).
iEN
IEN JEN
||a|| X|
X 122
112
+ Σ
||E + ΣV Σ
iEN
iEN JEN
According to the condition 49 we have || that a O(vn logn)) l). Otherwise, we have
S 2/
Wmm
0 1/p22 + nm/d), which implies
1l 2|2 2
Σ ifk
yv (E., a(aa)
45

---

It further yields that
1 0
1 /2
+
52
mm
5)
+ 0% Ex. 112 = Q2
1
+
mm
+
-)= 22
a²
d
n
loog* 2
d
d
d
which contradicts with || ( v 1/p² mm/d). We decompose the difference between ||00| and || into four terms:
||0|| |
(0
8x E1EE 122+
(0
Σ>
E
y,0,0,0, Ej)
NEVa*
VEN JEN
12
E EN JEN
y.y, (E
We now estimate I to I4 sequentially. For the first term,
11 N (0 0z.) )1 k)d (0% (0% + +0xx)( )(1 k)d
(a- 1)(1 28% v //llog(6n (6n (8))
.2 d (1 - k)d
(1+ + K)d 2/ log(6n2) 6n (6n²/6) /8)
a Ca-11 0
d
where the first inequality is from Lemma A.65 the second equality is from Lemma
A.20 and the last
equality uses the fact that a = O(Vn(lol log n). Then we can further upper bound
max /
0 as
(1 (1-k)d+ + 2(a - n2)) d log logg(o22//)) = o ((1 x)d 2m2 / dlog (n /8))
max
0K <
(55)
EN J
For the second term 1z, we have
122 < Σ
0 + k)d
IEN K
(1 (0% - w) / d log 6n? /8)2 -1)
1
0.2 1mm(1 k)d
max sEN
(a 1) d (ogggoggbo 6n 15)
m 0 7h
o (a
(aa--1)mp 1)mm
+1+ k)d log (6n2 /8)
d3/2
The second inequality is from Lemma A.20 from Assumption 4.1
The first equality is from (55) and the last equality is
Then we bound|
- Ta + Tal as:
| - 1/ + 14| < Σ
Σ
10.0, 0.001 KS, EA)
VEN JEN
<
Σ
Σ
10.0, 0 KE,, E3)| +2
Σ 10--0, -02. -KEK,, Ex)
VEN' HENTMA--JENNNE HENN
DEA
<(m))²
-1)
max i
0-2 2 log log((n2//))
(1 (1- - w)
T2.
+ nm 0%
0/4v dlog(6n2))) iEN
max
1 1-210% - w)) dlog(6n²/0)
(a 1) [dlog(6n2//) 0 (mm)²(1 x)
a-1 0m - -2)-2222 dlog(6n2//)
(1 + k)d
Vologg(nn (6n2 /0)
d3/2
(a (a-1)nn'') 1n
(a 1)mm
d²
d3/2
46

---

The third inequality is from Lemma that
A.15 and Lemma A.20 The fourth inequality is from the fact
0 0x. - 28% (0% - ww) w) / doog(6n2))) /6)
0%.
2(0%-
w)
log 6n²
1 - 2- w) dog (eolog((ng") (6n²/6)
12( 12(=-1) 0 (
>0
1 2(0 w) / lllgg6222//
gR So we have 6- 1-2 w)) / /6) Combining the above results, we have
S 8% A The last equality is from Assumption 4.1
| |m 112 0 ( ( +0
(a (a-1))mm)
C3(1 B)
d3/2
Here C3 (1) is constant.
Now we can prove the main proposition in this case.
Proof of Proposition A.14 under Case 2.1. From Lemma A.22 we have
Ca(1
||00 1 U
T'11 - 3).
d
Here substitute T"
O. Then have
le"
Ummm 2
T¹ B)
22- P1/
1mmml 1|
1
>
12
Uma
1|
Therefore,
(1 3)
(1 9)
T 3)
T² B) 2|
( + (+) Umm 112 -1101112 21 10 1mm 2 ||0012
2 Umm
|| 00112
The last inequality is from
||0"|| 2 1mmml ||. This implies
(1 B) < 1mmm 1| 133 (1 -3).
C1
r" < r
2||3
The last inequality is from assumption that ||~0|| s 2 2//ummm || and p² (dd/n).
Then we consider the other case.
Case 2.2 k: - p=
In this case, all noisy samples mixed. From previous analysis, this is equivalent to strengthening all conditions y &: 2 I while other conditions remain the same. As mixing p samples will not result in better solution than only mixing noisy sample, the proof is the same as Case 2./ and omit it for convenience.
Finally, we consider the last scenario.
Case 3: p # 0, p # 0
This scenario is more complex both clean and noisy sets mixed. There are four cases to consider
1. p n1, k p T22. (Both clean and noisy sets are partially mixed)
2. p n1, k p n2 (Clean set is partially mixed, noisy set is all mixed)
3. p n1 p no (Clean set is all mixed, noisy set is partially mixed)
4. p n1, k p n2 (Both clean and noisy sets are all mixed)
47

---

We will go over every case to prove Proposition A.14 holds.
Case 3.1 p < n1.
This case is simple because from the analysis above, mixing more clean sample is equivalent adding I more constraint and mixing I more noisy sample is equivalent to strengthening I original constraint. So mixing both will result in better solution than only mixing clean sample. Therefore, the proof is the same as Case 1.1 and we omit is for convenience.
Case 3.2p < R1.
In this case, all noisy samples and part of clean samples mixed. We consider this case an extension of Case 2.2 by mixing some clean samples. From previous analysis, mixing more clean sample is equivalent adding
constraint. So this case will not result in better solution than Case 2.2. The following proof is the same as Case 2.2 and we omit for convenience.
Case 3.3 p T1, k - < 112
In this case, all clean samples and part of noisy samples are mixed. We can consider this case an extension of Case 1.2 by mixing some noisy samples. From previous analysis, mixing more noisy sample is equivalent strengthening original constraint. So this case will not result in better solution than Case 1.2. The following proof the same as Case 1.2 and we omit for convenience.
Case 3.4 = n1,
V1/
This case is more complex. We cannot simply consider it as extension of Case 2.2 because the analysis of Case 2.2 is based on the condition that there exist clean samples that follow optimal token selection rule. Denote condition this case becomes
B. + (1 B:) for E C and r; (1 B; 44 + B&&; for i E N. The
Condition 10 (All samples are mixed).
y: "T ri 2 1.
This indicates
B.B (1 11 + E 0 E,)) 2 I,iEC
J#
(1- 11-3) (100
00y (E: E)) 2 1,iEN.
j71
Assume that min 11,1133-1 || = g in optimal v". If 2 can directly follow the proof in Case 2.2. Otherwise, denote Without losing generality, assume X |M 2| q < 1. Then consider the following relaxed condition
1-B:g We have a > due to g < and 3 - 1-B,
Condition 11 (Relaxed version of constraints in Condition 10
8
E + Σ 1 Eg) 2 e.
Denote the optimal solution under Condition and 0, i.c.
11 as ö and the corresponding coefficients in ö as X, X
Amp Rape +
Σ U.5: *E(m]
Since the constraints in Condition 11 is subset of the constraints in Condition 10 we have || < || Meanwhile, we have the following lemma estimate 0,:
Lemma A.23. Suppose that Assumption holds, under Condition we have
0: 0, [m]]Cr;
0, (1+ k)dd (1- n log 6n²/8)
1 EEC.
(1 k)d ny dlog 6n 28) ((1 - k)d - 2 / dlog
48

---

Proof of Lemma A.23 Note that Condition I1 does not have any constraint for samples with
C1. Thus we have 0, 0 for any i e [n] C in the representation (4)) Denote j argmax O,.
ieCh
then we have
0, ||
Σ
Suy E)) 11 24, n11 V ( k)d 2m11 |llog66n2/0)
The two inequalities are from Lemma A.65 and our definition of j. Consider the contrary case when 8
(dlog(6n2/8) (1 we have
((I-s)d-2m) 2011
y E, > a.
By the complementary slackness condition, if " &, > then we must have 0z = 0. and thus reach a contradiction.
Then lower bound 6, For Vi C1 have
0, 1|E.112 + Σ
U.,, En) S 0,(1 +xd+++)+++- 2011 max maxxiv d
iE(n)
iti
( + R)d + 20m11 d Gn (oog(6n2/8)
(1 (1- k)d 2n11 / (llog(6n2))
The second inequality from Lemma A.65 and the last inequality is from the upper bound of Ú, we just derived. Therefore, we have
1 2n11 / dlog(6n2/0)
8, (1 + k)d
(1 x)d - 2m / dolog(6n2//
From this Lemma we have 0: = (ar/d) for i C1. Similar as 53 under our assumption
|ö|| < 2 Ummill we have a = (log(n)). Next we estimate the difference between ||ø||² and |mam 2 We can prove that Lemma A.22 still holds in this case.
Proof of Lemma A.22
Under this case, the difference between ||ö|| and ||0mm becomes
||0|| Ummml 2
11 (A
1e (A3 12
[E(ma]
Σ Σ 3.,,0,0,(E,,E)) SE JEN
Σ
(,,, Ex)
EE jEC
We then bound 1 Is respectively. For I we have
| Z 0 11 Σ
2 2/p² 2 nn min 0 (1 x)d no max 0f (1 x)d -2pp iEN
sE(n)
IEC1
iEN
a2mn( -k) (1-
2Vdlog(6m2 662
nz x)dd
(1+ k)2d
(1- (1- (1- 2n11 / /loog ((1 - [[1-x)d= 2nz v log(6n22//
pa
Ω n
The second inequality is from Lemma A.65
The third inequality is from Lemma A. 15 and A.23 The
last equality is due to the SNR condition p/ Vd = 2(1 (n) so that # S x. For Iz. we have
2n / log 6n 2n22// 15)
= o d3/2
1 <
max 0 2 d lolo 6/2 S eN
((1 k)d 2n / log /8))2
EN
49

---

The first inequality is from Lemma A.65 [Za] we have
The second inequality is from Lemma A.15
Similarly, for
Tal S Σ
max
iEC 0f
2n1 d (on
δ n
((1 k)d 2 / lo (nn /6))
d3/2
iEC
The second inequality is from Lemma A.23 Combining the above results, we have
)
C3m(1 3)
~ [ 1 2 θ
((d))
d3/2
d
The remaining proof is the same as Case 2.1 and we omit it for convenience.
Therefore, we complete the proof for all possible scenarios.
Training and Test Error Analysis
From Proposition A. we can analyze the properties of both parameters to estimate the training and test error. In this section, first get the convergence direction of parameters and The main difference between our setting with Ataee Tarzanagh et al. [6] is that they only consider the infinite case and their results hold only when R, - We extend their results to the finite case. Specifically, given fixed upper bound R and r for ||p|| and || respectively, we denote the solution of the constrained optimization (4) (v(r,)) R().)) in this section for brevity.
Our main theorem in this section estimates the corresponding deviation of P(r.R) and (r. from their convergence direction Pmom/ //pmm//mmmmmmmmmm and Ummm Pyomall Il. For given it is elementary that the margin induced by p is mitl;,,, (Fio, - -x,r,) p/lppl| , thus when ||p|| = 1, the margin becomes ming,,,a (Fia. att)) p. And for given v, label margin induced by e is min; yo To rr: m//l|=/]|- Recall that the label margin induced by mm is r and the margin of P-SVM induced by Pm is E.
First we introduce lemma to estimate the norm of Pmmml This will benefit our proof of the main theorem.
Lemma A.24 (Norm of Pmmm). Suppose that Assumption 4. holds, recall that the solution (p-SVM)
Pmm- With probability at least 5 on the training dataset have
1 n
17mm
+
|Pmml
112
S p² d
+
2 d
This implies
Pmmm
=
(
m
Proof of Lemma A.24
First we prove the upper bound. Consider the following possible solution po:
2( + p2l
(56)
0²
d
iEN
We then proved that P satisfies 41
For k E C we have
(E,, Ex)
4na d log(6m22/5
T (px
==)= 2
22
2 1.
SEN
The first inequality is from the definition of in Lemma A.65 and the second inequality is from Assumption 4.I And for l E N, we have
p. (EL-
m4) = -2 Σ
2 -2 4(1 R))
Σ
d
iNN
IEN a
4nz v
> - + 4(1 k)
1.
The first and second inequalities from Lemmal A.65
The last inequality is from Assumption 4.1
50

---

Therefore, the max max-in solution Pmm must have no greater nomn than p. So we can upper bound Pmm as
Pmmm
|
8
+
16
Σ
(E):EE)
p²
d²
IEN
JEN
16
17m
(1
+ k)ngd= + 2m v dlog(6n2/0))
-
p²
d
p² d
The second inequality is from Lemma A.65 Assumption 4.1
The last inequality is from the definition of d in
Then we prove for the lower bound. As Pmm is the max max-marge margin solution and satisfies KKT condition, it can be expressed the sum of signal and noise tokens. Then decompose Pmm Py mm + P
where pi f1 p4 + f u2 and Pe
Eie(n) 9, g.mm E.. Note that μı 1 &, for all j
{+1}, i E [m). From Lemma A.29 we have s 2 p0 so we can lower bound ||p/ 12 as
2 0.92
Ip p fmmm2 ||| + f2mm2
|2
p²
p²
As for || 12, from P-SVM condition, for every noisy sample have
Prim (E: 14) 21,
which indicates
E:
P E:
P Pmnm pi; 1.9.
The last inequality is from Lemma
A.29
Sum up the inequality for all noisy sample, we have
Σ
PE
mmm
&: 2 1.9m2.
iEN
Thus,
1.9ma
1.9n2
1.9m2
m
P
2
Σ
Eill
1
Σ
E,)
V2 112
(1+K)d
d
VEN
JJEN
The second inequality is from Lemma A.65 and the last inequality is from Assumption 4.1 Therefore,
1
Pm
1p"
+
PE
d
Combining the results above, have
171i
P
d
Definition A.25. Let f: IR2 + RR.. We say that
lim f(x, v) L
2000000
iff Ve 3M such that Vx, y M have that [I5 - Lll <e.
Remark A.26. Let R + I be function with lim g(x) = oc.
Assume that
lima.yy+oo f(x, y) = L, then lim f(x, = L and lim f(g(x), = Now we introduce our key theorem:
Theorem A.27. Suppose that Assumption 4.1 holds, with probability at least 1 å on the training datusel, we have
* The margin induced by R(r,R)/ R in P-SVM is at least (1 - <) where
log(4 p2 + k)d U 113pp)
Ç
RE
51

---

The label margin induced by P/r,n//r in v-SVM is at least (1-7)I where
2/1r-11+)
1 (1))(())))
Proof of Theorem A.27
From Proposition A.14 we have that for any ||p||, the label margin 1/ l/|[(p)]
is at most
C max (1 Sta.)
Ummm 1np2
where a; = 1 for E C and Or; = 2 for i E N. Recall that 8; S x;)) is the softmax probability vector. We define q." 1 8io; to measure the amount of non-optimality (attention on non-optimal token).
We first consider the convergence of It) and use contradiction to prove the first statement. Denote
PR Rpmm/ / |l which has the same norm as P(),R) and the direction of Pm Suppose
the margin induced by P(r,R) R is most (1 Q)E, i.. ta (Zea. Fze.) ) (r. S
(1 () RE, vi E [n]. Note that here each sequence only has two tokens, thus 4, 04 E [2]. and
t = aze.
According to Lemma A.24 we have
= |lpmm 11 0(mm//4+1//)--11
Following the definition of of above, we set Fmax supie(n| qi be the worst non-optimality in Ri) and pR Then we have
Pir, and amaz supie|n) ph to
TETE PR
exp(x PR mm
exp(x
PR
S exp((-RE).
EeE(2) ( PR mmm
exp(2 x
to PR
The last inequality is from the definition of Prom that PTmm (Dio, v.) 2 1, so Pk TR (Din, - Dt. 2 R/ Pm RE. Thus, Ima = SUP]E[[) of Pram I exp( RE). Then denote the output of attention
layer r; = x X.TS(X.PPp))) mm)) Define e; = ||: Dza,ll ll. we have r.. Unm 2 y: z!o, 2mm
||r; - -Dia, |mmmll 2 1 - 4/T. So if we set Emar supre(n) Es, Vmm achieves label margin of at least Cmar on (Vi, rs)ie(n)- To better estimate Cmars we define M = supse|n] I| & S
VØ² + (1 x)d, then we have
Cmaz
M Linax S M exp(-RR)
(57)
This implies the max- max-maree max-margin achieved by (p(r.)): mm is at least (r.
ye (olii) ((r, mn) y ".mmm ri 2 rr remaz 2 - rM exp(-RE RE).
(58)
The first inequality is from yi r. umm 2 r(T 6s) and the last inequality is from 57
Then we consider the case when min (Zia; xH,)) P(r.R) I (1 - () RE the minimal margin
constraint is (-violated by P(, Without losing generality we assume that 1 argmin (Faa :E[u]
xx) Pir. Plasaaa Then we have
exp(x1t,
1 exp(xI P(r.)))
Tmazz
p exp(x;
2 exp(x P(r,) eexp((1 RE)
From Proposition A.
optimizing VVS on (ys, Pt)ee()) can achieve the max- max-margin most
C'
min /i y (V(r P(r.))); < T- 2 Mmlmmmll 1/p
(1-$)
(59)
Ei|
And from the definition
RE log(2M /umm [3np2/C), we have
Ummm 13p0= exp( (xp(-(1-Q)R3) ()) > M exp(-Ite
52

---

for sufficiently large R, which implies
min Us (() P(,n): < min yi xE(m]
f(pl" " ; xz).
EE|n]
This contradicts with the problem definition to maximize the margin.
Then prove for the second statement. When the margin induced by P(r,n) / in p-SVM is less than (1-()E, we can use the proof above derive contradiction, (Itan ..a P(), 2 (1 C)RE
must hold. Then set r; = X ((..)(). we have that
min y: (r, iE(n]
min y: (1. + sup (0.. (F: x...)l iE[m]
sE/n]
< (1 r) M exp(- (1pp((11-)13)) R)Er)r
(1 7/2)[rr.
The second inequality is from previous analysis that (Dia. -x;t) P(r, 2 (1-() so [r 7:11 M exp(- (1 - RE); The last inequality is from our definition [exx((1-()1E))
2M
Therefore, combining with (58) we have
7Lr/2 > rM exp(-
which implies
min ys ((((()))) P(r x2) < min ys f(0Ø mm pr.m; ans).
=E|m]
sE|m]
Again this contradicts with the problem definition
Then we have the following lemma to bound the derivation Ç and 7;
Lemma A.28. Suppose that Assumption 4.1 holds, consider the same setting in Theorem A.27 we have Ç < 0.2 and y < 0.1.
Proof of Lemma A.28
From the definition of in Theorem A.27 we have
< log(2M (2M)
Umm
pppp//0 10) C₁ //m// d 1/p²
log( M [|mmml| (1pp²)
RE
R
/ mm/d + 11p2 log
n²(pp² + d))p2mm + +dd))=
Ca CaVin/d 1/2²
C2
log(pn) < 0.2.
R
p²d3
R
Here C2,C2, C3 = O(1). The first inequality is from the upper bound of || in Lemma A.16 and the last inequality is from the definition of R in Assumption 4.1 And for y, we have
2M
M Mmmm exp((R/ (mmml))
v (p² + d) 1/p²) < 1.
7 r Teep(((1 ()RE) C
C2
exp(Rt / /////ddd + 1/p2)
Here Cj, C₁2- = ((). The first inequality is from the lower and upper bound of [| in Lemma A.16 and the last inequality is from the definition of R in Assumption 4.1
Then estimate (p( μ)) with the following lemma:
Lemma A.29. Suppose that Assumption 4./ holds, with probability at least 5 on the training
dataset, P(r.)) should satisfy
0.5(1 - RE < (Prr, U3) S Rp
for j (1,2).
Proof of Lemma A.29
The upper bound is given by
(p(r.)), m4) ( || Rp.
53

---

Then we use contradiction to prove for the lower bound. From Theorem A.27 (rr satisfies
P( (M: E.) (1 (1- C)
P(r,R) (5: - (4) 2 (1 - i)
(60)
1b) Σ 0.5(1 - R), then for every clean sample from cluster j we must have (G Ei) S -.5( - <) and thus
(Pr,.))
E.P -0.5(1 c)
iEC,
iEC,
So we could estimate [IP(r,z))] as follows
1
1
P(r,)) 2 0.5(1 C)RE mij Σ
0.5(1 <) ni
&ill
Σ
|E:11 + Σ E,)
iEC,
V VEC,
S.JEC,
V
2 -) mij
2 0.4RE
V2.11, n1j (1+
/2(1 k)d
The first inequality is from the property of innerproduct; The second inequality is from Lemma A.65
and the definition of d in Assumption 4.1: The last inequality is from Lemma A.28
Meanwhile,
from Lemma A.24 we have | & 8/pp2 17mn/d. Recall that E Pma
Therefore,
we further have
0.42m1;
P()l 2 0.4RE.
2 V (8/p² + 17mm/d) 2(1 + k)d R 22 k)d
0.04(n 7m - O(vn))
R R. (8/p² 17mn d) + k)d
The second inequality is from Lemma 2.24| The third inequality is from Lemma A.68 and the last inequality is from Assumption 4.1 about SNR and 17. This leads contradiction.
Now estimate the output of attention layer for some test sample (X, y).
Lemma A.30. Suppose that Assumption hooldddslhllssss with probability at least 1 5 on the training dataset, for a given a test sample X, y, where X (n* E μt can be μn or μ2, we have with probability at least cxp
2 2 C) K/ R/R)²) that
((r,,)) μ²) - (p n): 8*) K,
where K < 21 -1 and ç.E are defined in Theorem A.27
Proof of Lemma A.30 Note that p ** follows Gaussian distribution (0, RR²), we have
P((PG.R)) n²) (P(r.)): K) (((((,)))) E*) ((r.,)) 1²) K) < P(PTT 1 =" (1-C))-- (1- K)
1 - -E- K/R)²) -(KK)K)
S exp
The first inequality is from Lemma A.29 and the second incquality comes from the property of Gaussian tail probability.
We also have the following lemma to estimate (). We first prove that (r.R) can be expressed as the sum of signal and noise tokens.
Lemma A.31. The solution of constrained optimization problem (r. can be expressed in the form that
n
(r.R) = iaplr + Aat22 +
0.E
54

---

Proof of Lemma Similar to Theorem A.27 define f; = x; ((X,((r)))) as the output of attention layer, we have
Rr. argmax min yeu Vi- sE(n)
(61)
Then denote = min you ry and = min ye (r,t)) Then 61 can be written ie(n)
ie(n
((G,)))5)) = argmax 8, s.t. y:u Ti 2 s, 1sisn
| S.
The corresponding Lagrangian function
L(s, v) - + Σ vanis y:u0
y:uTr)) y:: vio(1lu11 -2).
Take derivative of this function on (s, v), we have
byrr + 2260
Therefore from the last equation we can get
24/o
As r; 3,pu + (1- B for every i [m]. v can be expressed as the combination of signal and noise token of every sample:
(r.R) = A1111 + A2p22 + Σ E
Based on this representation, we can then bound the parameters in (r. Lemma A.32. Suppose that Assumption 4.1 holds, denote (r.,n) = A111 + A2p2 +
Σ 0,5,
Then
rE|m]
with probability al least 5 the training dataset, have
A (1 (1-7)Tr/p² \ 11- (1-))\/pppp
|0 < 2//1/2+ 5mm/d dd Tr/Vd.
Proof of Lemma A.32 The first two statements are obvious because from Theorem A.27 we have
3.U( pi 2 (1 7)1'r,
for Vi E C. This implies |Ayl 2 (1- 1/r//p2 for j E {1,2}. Mcanwhile, we decompose
R(, Up + Ve where Ur \1p1 + X2 and Be Σ 0.E.- And we can upper bound [e as
:E(m]
|| = [| Ry 2| - || 12 < , -,, -
X20 < r - 2(1 -
The first inequality is from ||8|| < r and the second inequality is from the first two statements we just proved. Therefore, denote argmax 0,. we have
VE mx)
03 | < |iell S
2(1 -11-221-7))1110
55

---

Then we can upper bound 18y| as
0g S rr - 2(1 - // <1 2 - -/ //))////////1 -x)d
n 1 2(1 - 7)
1(1 -Rd p2
(2/ 5mn/d)p² ((1 - k)d
11mm 1222
5mmpp /d
p2
5nm
r2,2
+ 5mmp2/d
(1 K)d
2d
The second inequality is from Lemma A.65
The third incquality is from Lemma A.16 that 2V
|maml || 22 5mm/d and definition of y (' The last inequality is from T= == |/mmml 11 1--22220 (2/p² + 5mm/d)=1 Thus, we can bound [8,| as
18 $2 Somndd-rr//
Therefore, prove the main theorem.
Proof of Theorem A.10 First show that the model can perfectly classify all training samples.
From Theorem A.27 we have
T 9.u (r. 2 (1-
for Vi E [n]. The last inequality is from Lemma A.28
Thus y, (f [X;; (), P())))) for all
i [n]. Then we bound the test error. Given test sample X, v. where X- (p', (E"), μ1 can be μt
or μ2. From RemarkA.66. with probability at least 6n exp(-d/ACnn²).
d
( Cin
(62)
According to Lemma A.30 with probability at least - exp ( - (1) K/R)3), we have
(r), ek n +*)
ek - (1-1))/r(1u=111
y. (() P(,R)) X) 2
Σ SE(M]
|0.|
KE
E*)
c +1
(e +1)
ek +1
(63)
Let K log(Va + mm/d) +C [1 RE. By uniform bound, we have that with probability at least 1 6n exp( -d/4Cin²) - exp (- ( - <) -K)K/R)²)
ck (1 - -) n d/(Cin) 2//1/p² + mm/dd Pr/Vd
y ((..
1tek
0r vT/C1 2 1/1² + mm/d. .r.
1tc
0,
where the first inequality uses (62)
63
and Lemma A.32 The second inequality is from Lemma
A.28 and the last inequality from Assumption 4.1 and our selection of K. Therefore,
Ply # ((V().)) - P(r.)) X)) S exp ( - 1 1-2 C)
K ))) + exp(-S(dd/n) -)=-
log(2M/ m Pnp?)
= 0 (0(ymm/dt1)) / log(pn)) K log( /d 1//p + + =
where (
R5
1t
Ologg( /d/p² + mm) and = ||pmmll 11 O((m/d + 1/ -1/2). Plugging in the order of 3 and
56

---

K, we have
P(x:)/~(y + sign( (f (1.
= =P(X
P P(r.)))) , = -7)
+ + # ((1 P(.,)))) y= y)
= 1) u DD # sign( (X: (r, P ((r, ()))))) 7)
$ n + exp( d/ Cin²) + exp (-0(
(1 (1-) ()
log( (og((Vo dd/p² 2 + =mm) )²)
v /mm/d+11 1/
R )²).
= + cxp( - 01 d )2)) + cxp - Vmn/d 1/p²
(1 - ()
log(n) R
n?
where Ç = 0 ( Yunjat1/0 log(pn)): This completes the proof.
A.2.4 Proof of Thm. 4.2
In the case of multiple tokens setting, denote the 7-th token in input a (² Et, And we introduce the definition of Combined Noise Token.
Definition A.33 (Combined Noise Token). E is called combined noise token E; = -'=2 Eir and t, [0, 1J, E tr = 1.
Then we have the following lemma to estimate the norm and innerproduct of these combined noises: Lemma A.34 (Properties of Combined Noise Tokens). Suppose that > 0 and k² O //oo((6/00)/))) ((1/Vd) Iff Lemma A.65 holds, we have
(1 K² d')d/T=
E 1 (1 k')d
(EE E,) < 27 clog((622/
for any i,j E [n]] Definition A.35. If the event in Lemma A.65 and occur,
occur, let us say we have a good run.
Lemmas A.65 A.34 show that good run occurs with probability least 1 5. In what follows, we will assume that good run occurs.
Because the optimal tokens are data specific and not fixed, consider the following token selection rule:
8ec (1 uk: i CG, E {1,2}
46c ar E1,,, i.W.
(64)
This selects signal token for all clean samples and the first noise token for all noisy sample. Following this new token selection rule, we redefine the P-SVM and v-SVM: Definition A.36 (p-SVM for Second-token Selection).
Peec argmin |p||| pERd
subject to:
p (z) (0x)
x (2) 1, a = for iE and a = for ieN, t (a,))
(65)
Eet Psell be the margin induced by Psec-
Then for given p, define v(p) the standard max- margmn classifier on (rx; M))ee())) and Usec as the standard max-margin classifier on (r:"s, which represents the limiting case when p = Psec and R + +00.
Definition A.37 (v-SVM for Second-token Selection).
(p) argmin || s.t. yi v Tr; 2 1, for all i E [n].
(66)
vERd
57

---

r(p) == 1/ [[p) is the label margin induced by v(p). When r, i E [nd], we define
Usec
argmin ||
s.t. Y v rine 2 1, for all i E [n].
(67)
eER"
: secl the label margin induced by Usec
Since Usec satisfies the KKT conditions of the max-margin problem (66). by the stationarity condition, we can represent Meec
Daec A1/11 + 22/22 +
Et.r.
(68)
[EiN] T=2
Note that the conditions in (66) can be written as: Condition 12 (Second-token Selection).
pi 2
22 21 1
y Ê12 2 W
Plugging 44 in the condition J
we can rewrite these conditions as:
Å ||
-x2 || 2 2 1
(=,0 ||E +
Σ
Og (Ei. Ev L
r'E/377]
Then we introduce a lemma to estimate the coefficients Oi,- of Usen under this condition:
Lemma A.38 (balanced noise factor for KKT points). Under Condition 4.1 and 72 we have that for Usec
good run,
Grr 0, iE [3,T]i
(69)
(1- d 4m2 / log (6)
0.2 E
EEN.
(1+n)d((1 k)d 2n²T dlog (6n2 (1 - K)d - 2n:T (ong(6n2//5))
(70)
Proof of Lemma A.38 Note that Condition 12 does not have any constraint for noise tokens with index i E C, E N. * 2. Thus we have 0,r 0 for any C. e W, * 2 in the representation
(68)
For 0g2 with E N, we first prove the upper bound by contradiction. Denote j = argmax 0,
ieA
Then we have
y Esi E
Σ iEN
M.,,Or2 E,2) = 03
Σ
2.3.0, E1.2)
iFJENN
2 ,,2 (1 x)d nzT0,, no 2
logg(6nn (6n2/)),
where the inequality is from Lemma A.65 and the definition of j. Consider the contrary case when have
0j,2 (1-x)d 2n,2' (lg((6n2/8)
yjv' E
((1 - k)d - n2T 2 dogg(6n2/8)) 1.
(1 K)d Tn d
By the complementary slackness, if y, fx.2 > 1, then we must have 0, = O, and thus we reach contradiction.
Then we prove for the lower bound. For Vj e N we have
< 022 1 +
Σ $EE.EN
(22.0.
00,0 + (1+k)d + n2 max 0.2 2 dlog(6n2/8))
iEN
< 80, (1 +x)d+
n22
2 d log(6n2/8))
(1 k)d - 2n2T (lgg(6)2/0)
58

---

The second inequality is due to Lemma A.65 and the last inequality is from the upper bound we just get. Therefore, we have
(1 - k)d - 4n2 4m2 d (onggnn2///)))
, (1+ ()d((1 k)d 2ng2 (6ngg())//8)
This completes the proof.
Then introduce a lemma estimate ||Useell:
Lemma A.39 (Norm of Uecc). Under Condition
4.1 on a good run, for the solution Usec of (66)
under the token selection 64
we have
2
2
5mn
+
Useol
+
2d
p
This implies
|seell =
+
n
0²
d
This lemma is the same Lemma except that substitute & with &,2 So omit the proof for clarity. The remaining proof idea is similar to that of two-token sctting: 1) Prove the (relative) optimality of this second token selection. 2) Prove the convergence of parameters and training/test erro.
We first prove the optimal token for clean samples from the max-margin they induced.
Proposition A.40 (optimal token condition). Suppose that Assumption 4.7 holds, on a good run, for all that 3i E C, E [2. 7) (p. μ4 E..r < /1ll2// PP the token selection under results in label margin (Def. A.37) of at most I sec M. 12pp
max(1 8:1).
Proof of Proposition A.40
As we consider the non-asymptotic case here, 8.1 cannot be exactly I for T
Vi E [n)) so we only consider the case that all clean samples mixed. Denote r; Σ
(r)
8,p4; + (1 A, for i C, where & is the combined noise token in Definition A.33 The condition in this case becomes
Condition 13 (Mixed clean samples, multiple case).
y: r; 2 1.
This indicates
BayA 1ul + (3) 1 + Σ 3t3
liE
Assume that min(X" || 11,,-- -X'- |2
in optimal v". Similar to the two-token scenario, I-3, We have a > due to < and assume X; || = q 1. The special condition //e//ppeelll 22 here is to guarantee that there always exists an upper bound for 3,
we consider the case when q < 1. Denote a = I-ßa
0 1. Without losing generality,
(p. p4, E.,r) < ||pl|//||peed Then consider the following relaxed condition:
Condition 14 (Relaxed version of constraints in Condition 13
11
Σ O5 aiiic.
Denote the optimal solution under Condition 14 as i and the corresponding coefficients in ö as X₁ X and Ö,, i.e.
Ø 7ipl + Xat2r + Σ ..C.
(71)
(E(m)
Since the constraints in Condition 14 is a subset of the constraints in Condition 13 we have ||
<
||l'| Mcanwhile, we have the following lemma to estimate 0,;
59

---

Lemma A.41. Under Condition 4.1 and 14 on good run, we have
0. 0, [n]]C]:
(1 (1-
2T V
& E [a+w)jd (1 x² )d/dd 2T /d ((1 k')d/T 2I mn dong (6n2/6)
a
1 E EE.
Proof of Lemma A.41 Note that Condition 14 does not have any constraint for samples with
[n]]Cr, Thus we have 0, for any [n|] C in the representation (T Denote j argmax 0,.
iEC,
then have
0, ||, +
Σ V., 0, 2T mi ((1
(11( 21 n dlog(6n') (6)2
The two inequalities are from Lemma
A.65 and our definition of j. Consider the contrary case when
8j > (1-=))d/T-2T'mm) w (log(6n2
we have
2 E,
By the complementary slackness condition, if y &, > a, then we must have 0j = 0, and thus we reach a contradiction.
Then we lower bound 6, For Vi E C1 we have
a $ 8: 1E,1
Σ
y.u, (E,, E,) S 01 R')d+ 2T nn max H, d'lo((62//8)
j
27 am 2
/ (on2 (6n²/8)
s 0 k')d+
(1 (1-w'dd/1 - / /ooo(6n2//))
The second inequality is from Lemma A.65 and the last inequality is from the upper bound of 0; we just derived. Therefore, we have
2m / (
0 (1 x')d
1 1- (1 (1-x')d/T - 21 / dolo 6n?
From this Lemma we have 8, = (aad) for C₁. Similar as (33). under our assumption
|öl| 2/luseells have (log(n)) Next estimate the difference between || and |Useell We can prove the following Lemma similar to Lemma A.22
Lemma A.42. Suppose that Assumption 4. holds, denote Usen and io as the optimal solutions under condition 12 and condition 14 respectively. We have
Ca(1-
[ |
where C3 +(1).
Proof of Lemma A.42
Under this case, the difference between || 12 and ||ssell2 becomes
||01|2 - || >
02 0. (A} x 1| (A3 12)
[n]
Σ Σ
u., +
Σ U.y,0,0,(EEEEE) iEC JECT
jEA
60

---

We then bound 1
13 respectively. For 1 we have
2
Σ
1 - 1 midiiiinnnee min 0, iEC1
n2 max Of k)d 2/p² iEN
IEC
iEN
1 1
2 / x')d/T (1-x')d//1 21 /1o ((1 -x))) 2n2 / (on /0))² p²
ng R)d
1
(1 + k')d
Ω
The second inequality is from Lemma A.65 The third inequality is from Lemma A.38 and A.41 The last equality is due to the SNR condition p/ V = (21 T)) so that # S n2 For 12. we have
2n12 v log alloo(nnn (6
12 < Σ max 0f TEN iEN
2 log(6n()))/) S
((1 x)dd 2nz / log(6n2 (o))))/)))2
63/2
The first inequality from Lemma A.65 The second inequality is from Lemma .3 Similarly, for [T| we have
2 /dlog(6n2/8) ((1 x² x'/dTT 22 dloo(6n22/000 /8))
Lsl S Σ
max iEC1
8. 2T V /dlog(6n2/8) <
Ō
11
d3/2
iEC1
The second inequality from Lemma A.41
Combining the above results, we have
2 Can(1 - B)
||0 |001
13/2
The remaining proof is the same Case 2 for two-token scenario and omit it for convenience.
In this way, we prove the relateve optimality of this second token selection rule. Then we introduce lemma estimate the norm of | This will benefit our proof of the main theorem.
Lemma A.43 (Norm of Psec). Suppose that Assumption 4.1 holds, recall that the solution of (p-SVM)
seee- On good run, we have
+
1771
5
Psen
2
17m
2p
p2
This implies
|peelll 11
-9 / 1
m d
02
Proof of Lemma
First we prove the upper bound. Consider the following possible solution p:
2( + p2)
(72)
02
d
ENN
We then proved that p satisfies
65
For k E C, E [2,
have
(k..)
4nz ad (og(6622/8)
pd (nL
Ek.r) = 2 Σd
2 2
2 1.
d
d
eNN
61

---

The first inequality is from the definition of d in Lemma A.65 and the second inequality is from Assumption 4.1 And for N [3. T). we have
(5 Ex.2) 2 -2 - xx)
(5 Ex.2)
p (Eu.2
+
Σ
d
iEN
iEN
4n2
d'log((nn' (oog(6n2//))
2 -2 + 4(1 k:)
21
T
(Ex.2
Ek,r)
Σ iEN
(5i.2 Ek.2)
(5,2,
2 4(11 K) +
(51.2.
4
(51.,
Sk,T)
EN
REN
iEN
8m2 V dlog(66n2/0 15)
2 4(1 ([]-))
The first and second inequalities are from Lemma Therefore, the max- max-margin solution Psec must have no greater norm than p. So we can upper bound Psec as
A.65
The last inequality is from Assumption 4.1
Peecl
< |p|
8
16 de
Σ
E1
Σ
(55,26
1
ijENsiAs
8
16
8 17mm
+ ((1 + k)ndd + 2n log(6n2/0))
S
p2
p
The second inequality is from Lemma A.65 The last inequality is from the definition of d in Assumption 4.1
Then we prove for the lower bound. As Psec the max-margin solution and satisfies KKT condition, it can be expressed as the sum of signal and noise tokens. Then we decompose Paec P7 + P
where ph f [41 + f2 #2 and p Eiein) "f Note that μ4 1 Ei. for all {+1), [n], [T'. We first prove that (peec: {4} 2 0.5 by contradiction.
(peecs 13) < 0.5, then for every clean sample from cluster we must have (psecs Ex,2) S -0.5 and
thus
(P),R)) E Σ
(P(r.)) C1,) < -0.5m1j-
iEC
SEC
So we could estimate ||Peell as follows
Pseell 2 0.5m1,
0.5m
Σ &12ll
Σ V /EC,
Er, 2
E iJEc,,its
(Ex.2 E,22)
TEC,
2 0.5m1
/ n1 (1+ R)d
/8(1+ + +xd
The first inequality is from the property of innerproduct; The second inequality is from Lemma A.65 and the definition of in Assumption 4.1 Meanwhile, we have ||||| S v8/p2 17mn/d which also satisfies (65) Therefore, we further have
Vnij
Pseel
v8/p² 17mmd |p|.-
V8(1 k)d
The second inequality from Assumption
4.1
This leads a contradiction. we have (peecs Mb) 2
0.5. This directly indicates free 0.5/ p² we can lower bound |p See as
2 0.52 1
psec2 | + +
Frec2
|12 12
p²
2p²
As for ||pge1112. from P-SVM condition, for every noisy sample we have
P TT (E.2 14) 2 1,
62

---

which indicates
Pg
f,,
SiccSi,2 2 1 + Pseaf4 2 1.5.
The last inequality is from Lemmal
A.29
Sum up the inequality for all noisy sample, we have
Σ
Pe
T
Sx. 2 1.572.
iEN
Thus,
1.5mz
1.5mz
1.5m²
m
[|
Σ
E,2ll
Σ
Ei,2 1|2
(5,,,
S3.2)
/2 712 (1 + k)d
d
ENN
iEN
The second inequality is from Lemma
A.65 and the last inequality is from Assumption 4.1
Therefore,
ssee
1 +
lip
2
+
m
2p
d
Combining the results above, we have
m
|secl =
p²
With the above lemmas in place, we can conduct the analysis of the convergence direction of P(r. and R), which is similar to Theorem A.27
Theorem A.44. Suppose that Assumption 4.1 holds, good run, we have
min P(.RR (1t - E1.5) 2 (1 C) for Vi Ck. Is E [2], where the margin induced rE(2,T]
by Psec and C= RE log(277 /
k) Usce 1 2 /C).
* the label margin for clean sample induced by (), in SVM is at least (1 -1) see, where +
(J-))
Proof of Theorem A.44 From Proposition A.40 we have that for all p that Ei E C,T
[2 (p. {.r) plll/ P2cel12, 2, the label margin 1/][m(p)]| is at most
T seec
max(1 s.1). REc
||
Recall that 8; = S(X,p) the softmax probability vector. We define of = - 851 for i E C to measure the amount of non-optimality (attention non-optimal token).
We use contradiction to prove the convergence of Rr) Denote Pnt Rpsee/ |Peee which has the same as (r,,R) and the direction of Psec- Suppose the margin induced by P(r.R) R is at most (1 {) ie. min Pl (14 E,.) S (1 <)ER, vi e [n].
7E[2.1]
According to Lemma A.43 we have
= |Pseclla" (((mnd(mmm)//// -
Following the definition of of above, we set amaz = supie be the worst non-optimality in P(). and see Then we have
P(r.) and Fmaz = supie(m) q PR
to
Σ exp(x 1f1
(1) D
Σ exp(x
p
PR C
11
S eexp(-RE).
ELETT exp(x!!) ()
exp(a. (1)T
pic
63

---

(2) (1)) 2 1 for / + 1, 80 PR (ar The last inequality is from the definition of Psec that D (a) -a:
2. 2 Psecll RE. Thus, Fmaz = supigin] o Paee I exp(- -RE). Then denote the output
of attention layer ri S(,'(( pR) Define E, I|r: æull. we have Vi r. Usec 2 yi a. Usec ||r: æall |I 11useell 2 Ei/T sec. So if we set Emor = suprc(n] fis Usec achieves
label margin of at least Teee Emar Ts)EE())) To better estimate Emaxs define M (EP ||l Ee in(2.7] Ei,t S 0² + (1 k)Td, then we have
Emar M Imaz I MT eX)(
(73)
This implies the max-margin achieved by s00 1 (r,R)) is at least
yi (pr,,)) oeee (r,n) æ.) y.u, w.eTe r; 2 rI sec Témax rI' aec rMT exp(-REE)
(74)
The first inequality is from yi r, u,ec 2 r(I sec 6,) and the last inequality is from 57
Then we consider the case when min
(2,,, P(r. (14s Ei,)) S (1 <)ER the minimal
margin constraint is Ç-violated by P(r.))- Without losing generality assume that argmin min ((., (H: E.,r)) Then we have sECx TE[T]
exp(μi P(r.m)
1 Imaz Everye exp(a] P(r,8))
(6)
1+ Σ exp((E1,7 p1, ((r.)) rE(2.7]
S 1 exp( R)
1 exp( max exp (1,P(r)))) rE|2,T]
This indicates amar 2 [- ex))- From Proposition A.40
optimizing
V-SVM on (yi, Pe)eejn) can achieve the max-margin at most
Cr
min yr P(..R))) I Teerr 2//Usee 12
(1-
(75)
sE(n]
And from the definition (= log(2MMT) Usea usea ||3pp /C), we have
RE
C
exp(-(1 R)) MT exp( RE),
2 ell
for sufficiently large R, which implies
min ys f(V 04) < min ys f(e ; *E(n]
:E|n]
This contradicts with the problem definition maximize the margin.
Then we prove for the second statement. When min P Pir.ay (Mi Ei,r) S (1 C)ER, Vi [n]. we
rE(2.T]
can use the proof above to derive a contradiction, so (14, - Ei,>) P(r.R) 2 (1 <) RE must hold
-.,,))P(r.RR))
for Vi E C, E [2, 77. Then set F; x, ((X,)()))) for i E C, assume (r, achieves the label
margin at most (1 reer
seeT on clean samples, we have that
min KEC
M4 y. S min (r + +sup (/r, p:)1 iEC
sEC.
sect +M exp(- RE) S (1 see
(1 7/2)r sect.
The second inequality is from previous analysis that (14- -..-) P(r.R) - 2 2 (1-C) so pi p:l S M exp(- R)) The last inequality is from our definition 7 Prec ())
2M
Therefore, combining with (74). we have
II soor /2 > TM exp(-
which implies
min yi f( P(rmi)))))))) <E(n] Again this contradicts with the problem definition
min y: f(pft v,e;; :E(n]
64

---

Then we have the following lemma to bound the derivation Ç and
Lemma A.45. Under Condition 4.1 consider the same setting in Theorem A.44 we have < 0.2, 0.1.
Proof of Lemma A.45
From the definition of in Theorem A.44
have
== log(2M (2MT) ueeel nnplllnppn/))) = //n/dd 1/p²
RE
R
mp/d 1/p² log
n2 d) mm d)a
C2
0.2.
R
p
Here Ci C2 (1). The first inequality is from the upper bound of Ussce in Lemma A.39 and the last inequality from the definition of It in condition 4.1
And for have
2M
M| Mlesseel exp((R) (e/p////eeelll S dmm/ddmm//d+11/ 1/p²)
C
0.1.
T sec exp((1 ( R)RE)
exp(R/ 1tt///mm... m/n///ddddd 1/p²)
Here Cj C22 ((1). The first inequality is from the lower and upper bound of Useeel in Lemma A.39 and the last inequality from the definition of condition 4.1
Then we can estimate (P(r, p)) with the following lemma: Lemma A.46. Suppose that Assumption 4. holds, a good run, R() should satisfy
0.5(1 - RE S (P(r,n),k)) Rp
for 21.
Proof of LemmalA A.46
The upper bound is given by (P(r,)), Mj) S (IP(, = Rp.
Then contradiction to prove for the lower bound. From Theorem A.44 P(r,)) satisfies
min (o - Ei,r) 2 (1 C)RE, E C, [2,7] rE[2.7]
(76)
If (P(,,)) M2) & 0.5(1 - RE, denote = argmin PT. (v) (14 - Ei.)). then for every clean sample
rE[2,7]
from j j must have (p(r, Ei.T.) S -0.5(1 RE and thus
(p(r.)) Σe,) = Σ (prr. Eim.) < 005((1 R)
iEC, iEC,
So we could estimate |IP(,.))ll as follows
(p || 2 0.5(1 - -) nn
0.5(1 CRRE mi
Σ VEC,
E.
Σ
11 + Σ
LEC,
WJE,
711
2 0.5(1 R) RE mij
0.4RE
/2 /2.n1 (1 [1+ =')d
2 + k')d
The first inequality from the property of innerproduct; The second inequality is from Lemma A.34 and the definition of d in Assumption 4.1: The last inequality is from Lemma A.45 Meanwhile,
from Lemma A.24 we have |peeell further have
V8/p2= 17mn/d. Recall that =\t
P Therefore,
0.4
(P(..)) 2 0.4RE
(8/p2 + 17mn/d) 2(1 + k')d R
/2(1 + R')d V
0.04(n 1m1 O(vn))
R> R.
(8/p2 17mm/dd.. + s')d
The second inequality is from Lemma A.43 The third inequality from Lemma A.68 and the last inequality is from Assumption about SNR and n, This leads contradiction.
D
65

---

Now we can estimate the output of attention layer for some test sample (X,y). v).
Lemma A.47. Under Condition 4.1 for the test sample (X,9) ~ Detean X = {'), with
probability at least - exp 2 2 () --=-K/o k/)))2 we have
(P n²) (P) 5 2 K,
where S 21 R) and Ç, are defined Theorem A.44
Proof of LemmaLA A.47 Note that p' follows Gaussian distribution (N0,, R²), we have
P((PG..0 u²) - (PG..) 5* K) = P((P()))) 5*) (Pr,,)) n²) - K) s (( -1- () - K)
1 2 <) C)= K/R)²).
I exp
The first inequality is from Lemma A.46 and the second inequality comes from the property of Gaussian tail probability.
L
Then we can follow the proof of Lemma A.31 to prove that ()),R) can be expressed as the sum of signal and noise tokens.
Lemma A.48. The solution of constrained optimization problem form that
V (r. can be expressed in the
(rr.R) = A1 + A2122 +
C1.
1= 1=1 TE(27]
Based on this representation, we can then bound the parameters in (r.,)):
Lemma A.49. Under Condition4.1 denote ((r,)) = A1 + Aapak + Em= rE[2,T]
Σ Gi, Then
we have
X 2 (1-))//r/p3
A 5 (1-
00, < 2 1/p² 22 + 5mm/d I sect /d.
Proof of Lemma A.49
A.49
The first two statements are obvious because from Theorem A.44 we have
y: (r (1) 2 (1 (1-7) 7]'
for Vi E This implies AAyl 2 (1 2) beot/2² for j E {1,2). Meanwhile, we decompose
(rr, Un + te where Un AMMl + λ2R22 and Ue Σ 0,5; And we can upper bound |ee as
sE(n]
l [[ 12- || 1| 22 x
X²p² 2 2(1 2 s
The first inequality is from || S r and the second inequality is from the first two statements we just proved. Therefore, denote Ty argmax 0r.,, have
S,., |K 11 < || 12 < (1- ((1--))122 //ee//pp)
Then we can upper bound (0,rr, as
03,, < 2 2(1 1 /2tp////1////// 112 <1 2(1 2
seal /p2/ (1/11110) k)d
2(1 - 7)2
=
/(1 111- (1_
(2/ + 5mmm//d d) /(1 k)d
| 1 02
+ 5mmp2/1 /d
5mm
r2
(1- [1= <
+
sec
+ 5mmp2/d
22
d
2d
66

---

The second inequality is from Lemma A.65
The third inequality is from Lemma A.39 that ||seell - 2 Tsee exp((1-()RE) The last inequality from Tscc |Macc|| 2 (2/p² 5mm/d)-- Thus, can bound j0,r,] as
/2/0² + 5mn/d and our definition
1g.r, S 2//1/222222 5mm/d seet Vd.
Therefore, we can prove the main theorem.
Proof of Theorem 4.2 First we show that the model can perfectly classify all training samples. From
the construction Paecs Usees
we have
(r 2 (0 r2 >
for Vi E [n]]. Here peee is the token selected by PR Thus = sign(f (r),)) R(),))) ((..)) for all
i [r)]. Then we bound the test error. Given a test sample X, where X = (n*, (")), μ4 can be
or μ1g. With probability least 1 5 a good run will occur. Similar to the proof Lemma A.65 with probability at least - exp( (((((=)(d//))),
K E1r=1 S 2//dlg((n2/8))
(77)
According to Lemma A.47 with probability at least exp (1- ()- K/R)²), we have
(y) ee " + 5*) ek +1
ek - sc 11
y- ((. P(r,) X)
0,.l- ((E..:
p² +1)
e +1 <E(n) [2
(78)
Let K = log(nTT /1/p² + mn/d) + log(log((nnn////// (6)) + )1 R). By uniform bound, we
have that with probability at least 1 - expl (xxp(-Q(d/nn)) - exp - -1 -1--))(3----- K/R)²), +m//d seer /dd
(() P(, X) K (1 - 7) seoT - nT / /dlog(662//0) (6n2/6) -0112/0))2//////// 12212221++++0
1 c
0.9e seer n²T
2 2/1/2² + mn/d d Tseer secr/Vd
c
where the first inequality uses (77) 78) and Lemma A.49 The second inequality is from Lemma
A.45 and the last inequality from Assumption 4.1 and our selection of K. Therefore,
X)) I exp (- (-12 (
)²²) QF R
K
P(y # ()))
((ddn)))
where < log(2M/T pnpp 1C)
0 /mn/ut1/p2
log (n"((mad/o"" 2 +d) )) K
RE
R
log(nT 11/p² + mn/d) + log(log(6n') (n (6)) C O(log(n nT /1/p² + ml/d (6n (n2/5)) and
E = =||pseoll2 -1 @(mm/
Plugging in the order of E and K, have
(-
Vnm/d /d ( 1/12
(1 (1-C)
log(n) (n) 2) )t).
((X.e)~Deennl (y * sign(f (r. P(r,)))) S exp(-
log where Ç 0 Vmn/d+1/p² n
n? 2)) (00 d
) This completes the proof.
A.2.5 Proof of Thm.
Lemma A.50. Consider the next jointtjoonsstraaii max margin solution:
(v),P:)= = argmax min y [Xx;; v. v.P).
(79)
Lef ||ull and R2 = | then (w., P:) (Vir (Vir.. R.): P(r. R.)) where (U)r solution to Problem 4 Moreover, under Assumption 4. ( (items 1-3), with probability at least 1 over the random data generation, we have that T 00, Rd + 00 as 20.
Re), P(r.. is
67

---

Proof. By Proposition A.40
with probability at least 1 - 6. for E R the token selection under
p results label margin of at most I c max -//) in A.13 (with r; X (p)))) where
VEC
sp. S(X,)) .P) is the softmax probabilities, and : C/ Useel 'npp is some constant (which may depends on n. and d, but not in 6).
Observe that as the norm of v increases, the margin increases; thus, it's casy to verify that ||0, |o + 0o + 00. We argue that also |p:]| +
+ oc. To that, assume by contradiction that |prl| _ Rg for some arbitrary large that will be determined later. Set [ 1/ |Useell, || = Tr.
Usec = (re- - 1)eesee- Hence i. = r3 + Rg and 0/ = (r 1)2 The idea is that by decreasing | by we can choose with ||p|| + (r: 1)² t r? RR. ie. ||p|2 2r, 1 Rg. which can be arbitrary large for large enough Set II == 1/ |secc]] and Psec V 2r, + Rýllp The proof strategy is obtaining contradiction by proving that (Üsec: Paee) is strictly better solution
compared (we, Pt). Define of = sn1 for E C to be the amount of non-optimality softmax probability. Then we have that
max qf' 2
where 6 > 0 a constant that depends just on Rg and data parameters (e.g. n, d, Ps 6). On the other hand, for every >> O, have that
q = max Pace E,
for large enough rt i.c large enough Therefore, By Proposition A. 14 proof), we can upper bound the margin induced by vs on (Y,, r; for x, S(X,p;) by
(see the first paragraph in the
min y.u r, S rT ck),, tEin]
for some constant e O. On the other hand, the margin induced by Üsec on (Y,, r;) for r. Dio is (r= 1)T. This means that we margin induced by Usec on (yi, r;) for r; X, S(X:Pscc) is at least
min yor, T Usec min Yar Bsec q² |o! (1)
x. (2)
|sseel
(r: 1)(T Me),
x (1) - x; (2)
where M = supien
Observe that this lower bound is bigger than the previous upper
bound when
(r: - 1)(T - Me) > rT(T - CK)
Me -T M + CK.
Choose large enough such that (T - Mc)/r: < ck/2 and Me < CK/2, gives us the desired contradiction. Recall that R2 == ||p||| and ri : 1/|l Since r + R2 S I, we have that (v, Pr is solution to Problem with rt, R = R. and (c)... P.r... is solution to Problem 79
Proof of Thm. 4.4 By Thm. 4.2 with probability at least 1 - 8, the training set is feasible, i.e. exists (v, such that min f (X,0, v.p) 0. Therefore, for any 7 O, with probability at least 1- have that minge[n] yi (XX
6;;00 Uyy PT) 2 7 > which proves the first part of the Thm. Next,
show that the classifier sign(f(X: U. P.)) generalizes well, for large enough 7. Recall the next
joint-constrained max margin solution:
(Ve, pt)
argmax yi
(80)
N| P+ +Ill
which was introduced in Lemma A.50
Fix 7 0, and let (v,, P+) be the solution of Problem
Define ((>) == | Ip, We argue that (wy, (..) is a solution to Problem 80 for 1(7).
Indeed, let
m =
max
min JX
| S()) RE(m]
68

---

be the maximum margin for Problem
80 with t = t(7). Assume by contradiction that
min yi (X;; 0.) < m, <E(r]
which implies that
Y S min yi (xx; Py; vy) < m.
iEin]
Let (o",p") be solution Problem
80 with ((7) i.e. ||0*12 |p0112 ((7) and Write o' == (7/m) o². We remind that v(x;v,p) =
min yi (X::p"; m > X S (()) and overall we get that
. ||'||" ||-|| (7/m)² 101 |p' 1 < | + ||p"1|" ((7)
* min.e[mi (xf """"","''" 2') min.g(m] [n] y: (X p", v*)
%
which contradicts the optimality of (wy, P2) ) to Problem 5 We conclude that (My, Py) is a solution
to Problem 80 for t = t(7), i.e. (uy, P,) = (uu())-Pa(r))) where (Vr(7)) ((())) is a solution for
Problem 80 with = t(7). Let (((s) = (<(>)) and Ri(r) = [[p By Lemma A.50 we have
(u,, (V((T), P((T)) (V(run) P(rn)))Bun)))
(81)
and that ((())) 00, Re(r)) oo t(7) - oc. Clearly t(n) + oo as 7 + 00. By Thm. 4.2 The
classifier sign(f (X;; ((, m().m) generalizes well on test data:
P(x (y # sign ( ((, ((.,)):((r.))
= + =xp(S(()2))) exp exp 0 (1-S) ()
log d))
yn p² R
In particular, there exists ro, Ry such that for any r > ro, R 2 Ro, the above probability can be upper bound by 17 + exp(-S(dd/n) + cxp((0((11p) (mp//))mm///))))) mn/d)-1)) (see Remark 4.3). Choose large enough To such that for any 2 we have that ((()) 2 ro and R((r) 2 Ro. Then we conclude
P(xw>~ (u * (x;
P(X,y\>D y sign [f(X: ((ess) P(n))))an)))
5n exp( ((
mm/dd
where the first equality is from Eq. 81 required.
A.2.6 Proof of Thm. 4.6
Proof Sketch
First we prove that in this case, only by selecting the noise token for every sample can achieve the largest margin in the downstream task,
r = Ei, Vi E [n]
(82)
Similarly, we define the respective max-mn solution for p and in this case.
Definition A.51 (p-SVM, negative case). p should satisfy
Pmm (a) = argmin |p||
subjected to
( p >
(83)
for all 1 Siis E= 1/1|pmmll is the margin induced by Pmm-
69

---

Definition A.52 (v-SVM, negative case). vi (p)
argmin ||l|| s.t. yi 0 vi 2 1, for all i i [m].
(84)
vER-
((p) = 1/]]((p)] is the label margin induced by and p.
When = E, [n].
Omm argmin
vER ||w||| s.t. yi wu.ves g. 2 1, for all i [n].
(85)
-= 1/1l0mmi is the label margin induced by Vmm.
To prove this token selection is optimal, we need to explain that the optimality of the token choice is strict in the sense that mixing other tokens will shrink the label margin. We formalize this into the following proposition:
Proposition A.53 (Optimal Token Condition). Suppose that Assumption 4.5 Shhlds with probability at least 8 on the truining dataset, for all p, the loken selection under p results in label murgin 8:2).
of at most r C max 2E(n)
Then we derive the convergence direction of p and v by Theorem A.27 Note that as ||pll + oo, the attention more focused on the noise token every training sample. Therefore, the output of signal token is upper bounded by a small value.
Consider sample (X, y) X (μ', As ||p|| increasing, the noise token é' will will dominate the overall output if my 2 0, which indicates the output of attention layer will close to the noise token, r' + E'. Meanwhile, we can prove that P(r.)) and (r.R) are near orthogonal, so ((r.re P and n are nearly independent variables subjected to Gaussian distribution. Therefore, the probability that (r, E' < 0 least constant order.
Optimal Token Condition
First we find the optimal token selection in this case.
Proposition A.54 (Optimal Token Condition). Suppose that Assumption 4.5 holds, with probability at least 8 on the training dataset, for all p, the token selection under p results label margin of at most I max(1 $;2).
Proof of Proposition A.53
Similar as above, we consider the following three situations:
1. # 0, p 0. (All wrong token selections come from clean set)
2. - 0, - 0. (All wrong token selections come from noisy set)
3. p - 0. (Wrong token selections are from both sets)
We will discuss each situation specifically and prove that Proposition A.14 holds in every possible case.
Situation 1: # 0, p
First, let's see the condition under the optimal choice of tokens:
Condition 15 (Original Condition).
v E: 2 1, [m]
Similarly, Veom also satisfies the KKT conditions of the max-margin problem 42 in this case, could write v as
A1p41 + A2122
Σ y.
(86)
<E(n)
Plugging (86) in the condition
15
we can rewrite these conditions as:
0:
1
Σ
U. 2 1, [n].
Then introduce a lemma to estimate the parameters of optimal solution under this condition:
70

---

Lemma A.55 (Balanceing noise factor for KKT point). Suppose that Assumption 4.5 Condition 75 we have
holds, under
max 0: S =eiml
(1 -1- k)d 2n 2 (llog(n22/1
(1 - k)d An d log (6n
min 0 iE|n]
(1 + 1) x)d 2m log (og(6n2/)))
Proof of Lemma
A.55
First we prove the upper bound. Denote j argmax 0, have
(E[n]
0 E
Σ UiU Eg) 0,00,11 11,11
iEin]
0g (1 - K)d n0; 22 (oogg6n2//)))
The last inequality is because Lemma A.65 and the definition of Consider the contrary case when we have
0j (1-k)d-26) 2ny (og((nn255)
((1 k)d - n 2 (odloo(6n2/8)) 1. Vj Ej (1 (1-x)) x)d 2n / dllo((6n2/5)
By the KKT conditions, if y, Eú then must have 8, 0, and thus we reach a contradiction.
Then we prove the lower bound. For Vj [ni we have
S 0 + Σ
V. (E: E,) s 0, (1+R)d max 0, 2 dllo((n2//)) iE(n]
s 5 (1 x)d+ +
(1 (1-k)d - / dlog(6n2 2 /d dllog66n2/00
The second inequality is due to Lemma A.65 and the last inequality is from the upper bound we just get. Therefore, we have
(1 1 k)d - (ong
0 N
(1 + +)d(([ - k)d annd-nn/ d dlogg(60))) (6n
This completes the proof.
As for the signal parameters A1 and A2, to achieve the minimal norm for v, obvious that estimate |[ in this case:
A1 X2 0. Then
Lemma A.56 (Norm of Umm). Suppose that Assumption 4.5 holds, with probability at least on
the training dataset, for the solution Umm of (42) under the token selection (2)), we have
n
5n d
<
2 1mam
2d
This implies
= - (7(17)
|mm
Proof of Lemma represented
A.56
As Vmm is the max-margin solution and satisfies KKT condition, it can be
Dmm >1p41 + d2p22
Σ
y:0,E: + Σ ysOiE..
(87)
IEC
iE|m]
71

---

As there is no constraint on λ1, A2, both of them can take 0 to achieve max max-marga margin. So we could lower bound
[umm
as
(,,,,,0(EE..)) o n²
1E
Σ
E
n
d3/2
2d
kE[m]
se|ni je(n]
The second inequality is from Lemma from Assumption 4.3
A.55 that 0, = (l1/d) for i E [n]] and the last inequality is
Then to upper bound [/mmlll consider the following possible solution e
= Σ
29:5:/d.
iE/m]
For i [n]] we have
y: r; y. &: 2 /d
2y,y, (E:, E/)/d
jE(mlsisi
2 2(1 - k) 2n / /ogg(nn (ong(nn/))/d 2
The first inequality is from Lemma A.65 and the second inequality is from Assumption 4.5 Therefore, is a possible solution of SVM problem
A.13 when converges to Pmm- So we have
Σ *E|"
4 /////////d
Σ
5n 4y:Us (Ec, s, =
kE(M JE(n)
The last inequality is from Lemma above, we have |/ 2 (7))
A.65
Lemma A.68 and Assumption 4.5
Combine the results
Denote the mixed samples kn, k2, kip And for every mixed sample k; have rk; Bi),, + E.E Without losing generality, we assume that yk, = +1 for all i E [p]. Then the conditions under Situation / become
Condition 16 (p clean samples violating optimal token selection).
y & 2 1, [n]][]]
v Trk, rk, 2 E [p]
Denote the max-margin solution under this condition of with parameters X1, N2, 0%. Plugging this representation into the condition 16
we have:
{
0% 11 + Σ
O / (E:, Ev) 2 1, E
(1-3)))
| 11 + (,(%% 11 +
Σ 0 (EK. Ex)) 2 1, [p]
We consider two cases: X /| 1 < and X1 |1 11 2 1. First when X, X|1ma11 1|2 < 1, the condition for mixed clean sample becomes:
1. Ex) 1 1- (1-38 ml 1,
%%
112
+
Σ F'yth
which indicates that the condition for 8% is strengthened. So mixing 1 more clean sample is equal to strengthening 1 constraint in the original setting. Therefore, mixing p samples will not result in better solution than only mixing clean sample. Then we can simplify this case to mixing only clean sample and denote this sample as k., rи. = (1 3)14 + 3E... Now the condition becomes: Condition 17 (1 clean sample violating optimal token selection).
{
0g ||Ex>|1
Σ y. (E,, {x) 1, [n]](k.}
(1 B)XG || 3(0%.
||Ex. 11 Σ yr (Ex. Ex)) 21 #tk.
72

---

Similarly, we introduce the following lemma which estimates the parameters in v'. We define
(1 B)X m1l
3
for the convenience of the following proof.
Lemma A.57. Suppose that Assumption 4.5 holds, under condition on the training dataset, we have
17
with probability at least ò
82, S
(1 (1-k)d- 2n dloo(6n22 15)
(1- (1- k:)d 2n dllg(66n2/0 15)
v dlog Gn 6n²
0, 2
(1 + k)d
(1 k)dd 2((a - n) / /log (6n²/5)
max (E:.)
0g <
((1 k)d 2m dllog(ooio)) (6n /5))
(1 k)d (1- (1- - x)d (1-10(1-
2na / (6n
min (Ein)((k.)
0 2
2n (lng (6n²/8)
Proof of Lemma A.57
Denote j argmax 0', we have (E(m)
y E, = 01 +
Σ (E,,
iE(n),ts
2 88 k)d max 8/ 2 (6ng(6nn///))) /5) sEin
((1 k)d 2 dllo(66n2/) /8)).
The first inequality is due to Lemma A.65 and the last equation is from definition of Consider the contrary case when 0¹; >
(1 (1-x)d- 2m I log(nn we have
0 Ej- > a.
By the KKT conditions, if y &, > contradiction. Therefore, 0%._ s 8 (1-x)d 2n (0g(663//8)
1+X (1 m
then we must have 0j = 0, and thus we reach
Then denote j' = argmax 0%, seln),s4h.
have
o E,, = 16.11155111+
Σ
(E
iE(n],etj
2 (1 k:dd
0% 2 [Vllog(62//5) 0%, V /dlog6622/5)
iE(n)
2a /d /5)
2 (2((1 - k)d
(((((1-----)) - n 2/ dlog(6n2
(1 - k)d 2n /lg/ddlognnnn/ (n228)
The first inequality is from Lemma A.65 and the second inequality is from the upper bound of 8% just get. Consider the case when 0r.
((1 ((1 dlogg/ have
o E 1.
By the complementary slackness condition, y Eg, then we must have 0y.- = 0, and thus we reach contradiction.
73

---

Next we estimate the lower bound of 8f when j + h.s We have
1 S 41 T E
0,,16,11
(EI,
iEimliis
s (1 + x)dd max 0g 2 dl dlog(6n2/8) kE[n]
$ f (1 kd
2m d /6)
(1 x)d 2n log((n22/0)
The last inequality is from the upper bound of 0%, we just get. Therefore, we have
0j 2 (1 + #)d
(1 (1-n)d (1-(1-m) 2n/ hel//loge (llog(6)) (6n (6n2
2na d logo(6n2/0)
for all j [n] and j + k..
Last we lower bound 0% We have
S yn Ex.
= 0% (1 + k)dd + max 0 2/ log(6n2/6)
iE(n]
Similarly, have
1
2n dl log(6n2/0)
0g. 2 (1 + k:dd
k)d 2n log( /8)
Therefore, could estimate the difference between ||00|| and | 112.
Lemma A.58. Suppose that Assumption 4.5 holds, with probability at least 5 on the training dataset, denote v and o' the optimal solutions under condition 75 and condition 17 respectively, We have
C1(1 B)
|/00 Ummm 1 2
where C1 = +11 is a constant.
Proof of Lemma
A.58
From the first inequality in Condition 17 for i[n], o k. have
0
1 +
Σ
O (E:. Exr 2 youk. 0%, Ex.).
Then we add yiuk. wEe, Ex,) on both sides, where we set w 0%, (1+x)d dloog(bn2)))) S O
Then we have
0f || +
Σ
(E. + yeyk. WE),
- Yillk. (Op. - w))
2 1 - 2(0%. w) v d log (6n2/8)
(1 + k)d 2a / log 6n 3/)
(88)
(1 K)d / log (6n² 28)
The second inequality is from Lemma A.65 with
Now consider a new e = X M1 + 2 + Σ y,0,E. sEiml
A Xi: A = X₁:
0, = 0,(11 - 2(0%,
w) / d dlog(662 (6)) for E [n], # k.
74

---

and
W
Cx. 1 2(0%, - w) d log (6)
We can prove that satisfies all constraints for Mym-
By dividing 1 - 2(0%, w) dlloo(6n2/) /o) on both sides of 88 for Vi E [rt], i of K, we have
0, |E: +
0. (E:. Ex)
21
Then prove that 2N |EEx- 112+ +
Σ
Yolkk 0 (E, Ek.)
1. From the last inequality in Condition 17
itk
we have
8. 11Ex, 11
Σ
yk. V. Ex.) 2 a.
isth.
Dividing 1-2(0% w) / d Log(Gn22 6n2/6) on both sides, we get
8%, 11ER, 112
Σ ist
yiyk. 8, Ex.) 2 1 2(%% - -w) / dloglg(6i)) (6n²/0)
a
1- 2(0%, -w w) (log(()2/8))
Therefore have
yivk. (E,, Ex.) a - (6%,
w) || 2(0%, -w) v (ogg(66n/8)))
a (6%, - w) + k)d
0x. IE., + Σ
2(0%, w) V dllog66n//)) 1.
itk.
The second inequality is from Lemma A.65 and the last equality is by our definition 8% -
(1+x)d-2 (log((02/0))) Thus, is possible solution under Condition 1 and |||||| |||mml]]
Next we estimate the difference between |0'113 and ||2:| 2 The expansion of ||00| and ||||| are:
10 11 1|
XB2
2 +
|IE.112 +
Σ
Σ
0.V,0,0' E,),
(m(m)
(E(m)
JE(M)
u 2 Ai
111..11
Σ
Σ
y.u, E,)-
(E(N) JE(x]
Similar to the condition
49 O(y (og log n). Otherwise, we have
we have |'1l|| < 2mma = 0 (((vn/d) which implies that a
0% Ek, 112 2 a
Σ
yn. (E:, = l(aa)
Egk..
It further yields that
= (1())) + 02 |1E,, 2= 21 + a²
)) = 52( 20- n n
10'11==02(")
d
which contradicts with ||0'|| 0 ((/n/d)
We decompose the difference between || and |/a|| into four terms:
|| - |0|| == -0fe - Lº )lsk. 11
Σ
O0? 1e
Σ Σ
EE
SEjm]
+ 3
#EIn] jeim]
75

---

We now estimate 1 to 14 sequentially. For the first term,
1 2 (6%) - 6% [1 k)d (6%, - R₂ 18%. + +0x,)(1- 1001-x)) 1)dd
(a 1)(1 20% /dlog((n))) (6n (6n²/0)
1
52
(1 -x)d
(1 + k)dd / (6n 16)
where the first inequality is from Lemma A.65 the second equality is from Lemma A.57: and the last equality uses the fact that a = O(vn log n). Then we can further upper bound
max (E(n)
0 as
(1 x)d (
(6n2 012)
max
S
(89)
EE itt
((1 k)d 2n 2 / (olg(nnn /8))2
For the second term 12, we have
1/ <
Σ
C - (1) (1 + x)d
1)
max iE
0,² n2 + k)dd
(0%, w) log Gn² 10))2
(a 1)) d log 6n²
o
(a 1)n
(1 + k)d / d log (6n² 66/
d3/2
The second inequality is from Lemma A.57 from Assumption 4.5
The first equality is from
89 and the last equality is
Then bound|
I3 + Lal as:
| - Ia + Tal S
Σ Σ 0,0, - 0,651 ((E,,
iE(n) (e/])(
<
Σ
e.e, 0,0011 (E,, +2 sE[n][(k.}
Σ
lx. 0% 01l KKE,, E.)l
<n²
(1 (11
10%, (1- - (w) d dlog(6n22) / -1
0,² 2 cl dlog(6n2//)
max
seinl,ikk
Ox.
+ n 0%, 1- 1-((0% - w) /dlog(6nn (6n? (6n2/5)
max iE|nlitA
0.4y d dlog(6n22
(a 1) ///oog66n2/00 /0) O
ni211 x)
a-1
0 2
+
(1 k)d / (dlog(6n2)
d3/2
-o (a-11 1)n²
(a-1)n²
(a (a- - 1)n
d²
d3/2
The third inequality is from Lemma A.55 and Lemma A.57 The fourth inequality is from the fact that
0x.
0g. Ox. - 20%, (0%. w) / dloo(6n2/8)
0g. 1 - 2(0%. w) log 66228)
1 1 -2((%, w)y / dlog (6m2/8)
2( 0 63/2
-(2(a=1)))
0
1 1 2(6% - w) / /d (llog(6n2///
So have 8%
Br 1-2(6% -w) w /dlog(Gn2/5 18)
I 0%
Ox. The last equality is from Assumption 4.1
Combining the above results, we have
(
a--1
+ 0
(a [a- 1-mmm
C1(1 (3)
| 1|2 || 11
0
d3/2
Here C1 (()) is constant.
76

---

Then we consider the case when X; |1 2 1. In this case, the condition for mixed clean sample becomes:
(1 - 8c) p
8% -15x, 112, +
Σ
yksye (EK.:
I.E.::Er" Ee) 2
3
and 11118A) I 1, which indicates that the condition for 8% is relaxed. So mixing 1 more 3:
clean sample equal to relaxing 1 constraint in the original setting. Therefore, mixing all clean samples will achieve the best result. From the data generalization model, there are (1 -1)nn// + o(n) clean samples with label +1 and denote S+1 as their set. Now the condition becomes:
Condition 18 (All clean samples violating optimal token selection).
{
0 - Er 11 + Σ yaye (E, (E) Ex)) 2 1, [n] S+1
(1 - B) || + 3(0; ||&/| + y.u (E,, Ev)) 2 1, S+1
We have another lemma estimate the scale of parameters in the max-margin solution in this case. Here 1-(1-3) 1e and β = min [.:}-
3
.E(m]
Lemma A.59. Suppose that Assumption holds, under Condition 18 we have
max 8 S EEim]
(1 - (1-k)d- 2n / dlog(Gn2/0))
min 0 - (1-r)dd- 2n (oogoonnn//))))) +1) (E|U
(1+ ksd((( K)d 2n d 66n//))
Proof of Lemma A.59
First we prove the upper bound. Denote j argmax 0,, have
(E[N]
yjw E = Σ
0z (E,,
(E(M)
0g 1|,
Σ Oe
i
2 - (1 kd nd,- 2 dogg(6n22//)
The last inequality is because Lemma A.65 and the definition of Consider the contrary case when
0j > (l- 2lg/dlo((B22//)) we have
1
x)d - 2m / ////lllo6n///// ((1 x)d n loggoo66n2//00 1.
By the KKT conditions, if y E, then must have 0, O. and thus we reach a contradiction. Then we prove the lower bound. For Vj S+1 have
$ 0, 11 +
Σ
0, Ei)
$ 50 (1+ + max 0, 2 d dlog(6n2/0) vEm)
<0; (1 + (1+x)d+
(1 - k)d / d dlog(6n2//) 2 d doog(6n2//) /8).
The second inequality is due to Lemma A.65 and the last inequality is from the upper bound we just get. Therefore, we have
(1 x)da 2n / log 66n (8) +1)
0, 2
+ +++n)d((11 k)d 2n dlog((n2)))
This completes the proof
77

---

Then we can estimate the difference between || and
| 2l with the following lemma:
Lemma A.60. Suppose that Assumption 4.5 holds, denote v and o' the optimal solutions under condition 73 and condition 18 respectively. We have
C2(1-A) B)
10'12 1mmm 112
1
where C2 = (1) is constant.
Proof of Lemma A.60
Recall the expansion of ||0 2|2 and |100
1mmll
11?
Σ
111 + Σ
Σ
iE[n]
||001|2 = X/2 | 11 + Σ
0 11
+
Σ
viu, 0,U,
Se [n]
jE[m]
Then we have
|| - mmmll 11 = 1 +
(0.2 01)
Σ Σ
y.0,0,0,(E:. E,)
iE|n]
jE(m]
Σ Σ Yyy,
(E.
iE(M]
We now estimate 1 to 44 sequentially. Here we use the same notation a 1-(1-8) u=ll" and
B min {8: in Lemma A.59 First from our assumption X/ || 2 1 we have
<E(r)
1 = x || 2 1/p².
Then for I2, we have
[T2l S n (max 0º
min 0?2) (1 k)d
vE(n)
iE(n)
(1 k:) 2n dlog (6n )²) -(1 + k))dn.
1
(1 + k)) (a (a-
2n d log (nn (6g2/8)
((1 x)d 2n / d
d(1 + k)m- (1tafa03 ((1 x)da 2( + 1)n (6nl/)(((///))))
((1 k.dd - 2n, /lgg(onn2/
o -a()
The second inequality is from Lemma A.55 and Lemma A.59
Then bound|
I4| as:
| la + 44 <
Σ (0,0' - -,0,) (E. E;)l
EE|m (E(
< (n)² (max 0 min 0?) 2 log (6n2
(E(n)
=E(n]
(n)²
(1 - (1-k)d- 2n / dloo(6n22// )
(1+ k1)( x)d 2n 2 (og((62)/))) 2 dlgg()22//)
(1 - k)d - 4n 4n (11
)
kn²
n²
0
d3/2
d
78

---

The third inequality is from Lemma A.55 and A.59, Combining the above results, we have
The last two equalities are from Assumption 4.3
C
12 +
C2(1 ((1--)) C2(1--))
|
Umm
+
p
d
p²
Here C2 (1) is constant.
Therefore, combining Lemma between ||||| and [/mmll:
A.58 and A.60
A.58
we have the following statement for the difference
Ca(1-
| 112 1mm
(90)
Here C3 (1) is constant. The inequality is from the SNR condition that p o(vd/n) /d/n.
Now we can prove the main proposition in this scenario.
Proof of Proposition A.53 in case
From 90p we have
Ca(1 B)
| ||01
-S(1 ((1--)) 3)
d
Here we substitute S = Ca 2 0 Then we have
1
// 1
|
S(1 3)
r 12
|
||
|//12 |
Therefore,
S(1 - B)
S(1 3)
1
2
( + 1 ||0 12 ||00|2
21
2|
|
Set ".
have 1
<
d(1
B). And can upper bound as
S
S
C3
S
<
2|
r3
3
mm d'
The first inequality is from ||l`||
2 || and the second equality is from S = d.
Situation 2: p = 0, #
Then we consider the case when all wrong token selections come from noisy set. Same as above, denote the mixed samples as k,, k2, kx-p- And for every mixed sample k; we have Tke (1 - 3 + B.Ex.- Without losing generality, we assume that yk, +1 for all E [k - pp. so the corresponding signal token is p22 Then the conditions under Situation 2 become
Condition 19 (Change k-p noisy samples).
yo E. 1, [n]][- v TT rh: 1, E jk --p
Denote the max max-margh margin solution under this condition o' with parameters X1, X2. 8% we can interpret the condition for parameters:
{
02 02-116: 11 + Σ yay (E,, Ev) 2 1, [m]][k
(1 (11%
2 + (, ||Ek, 12 Σ t*k
yk. Uy (E,, Ex)) 2 1, E [k - p]
Compare with Codition 16 the only difference is that we substitute X |/ml with 12112 From the symmetry, we can see that the two conditions are actually the same. Thereofre, we can follow the proof of Situation 1 to prove for Proposition A.53 under this situation.
79

---

Situation 3: p - p
Last we consider the case when wrong tokens come from both clean and noisy sets. Denote the mixed clean samples as kı, k2...., kp and the mixed noisy samples as ς1, 92, 92,.... Ik -k-p- p-Without losing generality, we assume that yk, +1 for E [p) and y/, - for i [k
p), which indicates that their signal tokens are all p4. Then the conditions under Situation 2 become
Condition 20 (p clean samples and k-p noisy samples violating optimal token selection).
{
y:u T & 2 1, E [n]]][]]
v r'r 2 1, E [p]
-v rq. 2 1, -p pl
Denote the max-margin solution under this condition as v" with parameters Xi, Mi, 0f, we can interpret the condition for parameters:
8 ||5 + Σ Ukyr O Ex)) 2 1,1 [n]][]]] 'ept
(1- - B:) || + 3,(0%, |E,, 112
E
yr 1N, Ev)) 1, [p]
i'tk;
-(1 3,)XK' || 1|2 3.(0% 112.112-
Σ
Yq Vn. (Eg, Ev)) 2 1, [k pl
We consider three cases: x 112 111> Xi |1ll
-1 and Xi H1l? -1.
||
First when Xf' (|1111111" 2|| 2 1, we have Bi for mixed clean samples' parameter 0%, is relaxed. Mcanwhile, for the mixed noisy samples we have
< 1, which indicates that the condition
1 + (1 3. m1l 2 1,
04 -1E,, 112
Σ Vq. O4 Ev) 2..5:
B
which indicates that the condition is strengthened. Therefore, this case is an extension the second case of Situation I with strengthening some constraints. These constraints will not result in a better solution than Situation 1. The following proof the same as Situation and omit it for convenience.
1 pl 1 -1
In this case, the constraints for both mixed clean and noisy samples strengthened. So this can be taken as an extension of the first case in Situation with strengthening some constraints. The following proof is the same as Situation and omit for convenience.
X 2 <-
In this case, the constraints are strengthened for mixed clean samples while relaxed for the mixed noisy samples. So we consider it as the extension of Situation when X111/41 12 < -- with strengthening some constraints. The following proof is the same as Situation and we omit it for convenience.
Therefore, complete the proof for all possible situations.
Training and Test error analysis
From Proposition A.53 we can derive the convergence direction of p and u, i.e. Pram and 8mmn- Note that Theorem does not depend on the selection of optimal tokens, so still holds in this case when optimal tokens are noise tokens for all samples. We restate here for convenience:
Theorem A.61. Suppose that Assumption 4.5 holds, with probability at least 1 - on the training dataset, we have
the margin induced by p(r,n)/ in P-SVM least (1 <).. where
Ç log(4 (1 a)dd u |dpp
RE
80

---

the label margin induced by Vir, in v-SVM is at least (1 7)I, where
(1(xx) ()
Then we could estimate the test error in this case. From Theorem A.6 we have
PT m4) (1 <) vi e [x]
(91)
yo (r, RY 2 (1 Tr, Vi E [n].
(92)
Here 7, E are the same the definition in Theorem A.61 Similarly, we have the following lemma for 7,
Lemma A.62. Suppose that Assumption 4.5 holds, with probability at least on the training
dataset, consider the same setting in Theorem A.27 we have Ç < 0.2 and
0.1.
Proof of A.62
A.62
First we upper bound
Pm
Consider the following possible solution p:
p
(93)
d
iE [n]
We then proved that p satisfies
83
For Vk: E [n]. we have
(E:, Ex)
(En, Ex)
p (Ex
mb))
= Σ iE(n)
2 2(1 - k)
d
d
iE(n).ipph
2m d /8)
2 2(1 R) +
1.
The first and second inequalities are from Lemma A.65 The last inequality is from Assumption 4.5 Therefore, the max-mare max-margin solution Pmm must have no greater norn than p. So we can upper bound Pmm
P Pmmm
1| 1112
E
Σ
(E:: Es)
d2
[E(n]
4
5n d'
((1 + x)nd 2n doog(6n22 (8))
de
The second inequality from Lemma A.65 The last inequality is from the definition of d in Assumption 4.5
Then from the definition of ( in Theorem A.27
have
( - Hog(4v/1 R)d
Umm
/ddp²)
/ndd
< C
log( +x)ddduum /dpp
RE
R
V
Vn/d
C²
log
< 0.2.
R
d
Here C1, C2 = (1). The first inequality is from E-1 Pmmm S /5n/d: The second inequality
is from the upper bound of || /mmll ll in Lemma A.56 and the last inequality is from the definition of R in Assumption 4.5 And for 7, we have
2M
M [| exp( RR/ [mm
Vd. (n/d)
C²
C.
0.1.
I Texp((1 - RE)
( /
Here C₁, C% (1). The first inequality is from the lower and upper bound of || in Lemma A. 16 and the last inequality is from the definition of Assumption 4.1
Then we have the following lemma to estimate the innerproduct of P(r.)) and signal token:
81

---

Lemma A.63. Suppose that Assumption 4.5 holds, with probability at least 1 5 on the training dataset, we have
(((r,))) 14)1 0.9(1 RE
for j {1.
First we use contradiction to prove for the lower bound. Assume that (P)).)) M4)) 0.9(1 - <). We estimate (r)
Proof of Lemma A.63
PP(r.)) 2| (0.9(1 - <) (0.55"/p²)
R² 2 (0.1d/np²) R² R?.
The second inequality is from Lemma A.62 The third inequality is from E² = l || d/ (5m);
The last inequality is from our SNR condition p o( vd/n). This leads to contradiction.
From Lemma A.31 we can denote (rr,R)) as
(r. = siri + 22 +
Σ v:0,E:
<E(m
Denote vgg
Eie(n) yr0 as the noise part of (r, Then we prove that P(r, De are near
orthogonal
Lemma A.64. Suppose that Assumption 4.5 holds, with probability least 5 the training dataset, we have
(p),, ue) S
for some constant c E (0,
Proof of Lemma A.64
First plugging in the parameters in ve have
(P(r,)), vz4) = Σ
iE[m]
Σ 0.
Σ ny
3
31--1
< (m11 + n22)) (max (.E + O(Rp)) - (ni2 + (22) 0:) -
< (n/2)(max8 min 0, RE + O (7) RE (max (.) O(P)))
15
The first inequality is from Theorem A.61 that (1 () S PT..R) (E: -4:) S RE and P.T. Rij,
O(Rp) and the second inequality is from Lemma A.68 Then we bound I I3 respectively, For It. we need to first bound 0,. From Theorem A.6l we have
- (1-7)1r+ S y. S Tr, e [n].
Denote j argmax; 0G, have
y, (r. & 2 d 12 + nd, v d (00 2 ( - k)d + ny dlog((nn2/)))
Therefore, we can upper bound 0j as
yソ (T. E:
Fr
0g - (1 - x)d + n (log(6n2/)) (1- k)d + n (log(6n2/8))
(94)
Then lower bound 0:
Trn d (ogg(6n2/8))
y T. S 0.116.111 + n0, / dloog66n2// < (1+ k)d0, + (1 k)d + no /log (6
82

---

Therefore,
- () - - /lgg
-Trn
0, 2
(1 (1+x)d(11- x)d + nl dlog (on2/ (6n2/0)
So we can estimate 1 as
(1- - w)d + ny ('lo(6n2//5)
Tr
h (nRE/2)
(1 + +)) m /
1+x [-= + n lop((6n
Rv RiVnd/2.Ir Tr-
(1+x)
(1 (1-x)d + ny log 6nn 6n²
s Rr 7)).
The second inequality is from E: || || e (d// and the last inequality is from r |[
|l O d//n..
Then we bound Iz. From 194 we have max, 0; Therefore,
2 0(v)))((()/) Rr O(1/v)))
The last inequality is from
Last we bound /3 as
la - 3==00(T7/0((((E++000))))
S ((rvn//)(bbgAA// x)d Myam
I 1/ O(Rp))
Rr -Rr-0(pyn)
The first inequality is from r, 0 d//n))) and the last inequality is from Assumption 4.5 Combining the results above, we have
(Pr,.)), ve) S 11 + 12 Rr O S
sufficiently large and n. Here the last inequality comes from Assumption 4.5
With the lemmas above, we could prove for the main theorem
Proof of Theurem 4.6
First we show that the model can perfectly classify training samples. From
Theorem A.27 we have
y: (r..)) ry Tr + y:(1 3.)0 2 8:(1 -r 0.9(1 B:)(1 -)) O,
for vi E [n]. The last inequality is from Lemma A.62 Thus y/: sign(f(X;; ((r,)) P())))) for all i [n).
Then we bound the test error. This is equivalent estimate y f(v P(r,)): X) and we could write it as
y (() X) = exp( μ²)) exp( "")
expl 1z)) + expl (P E
We first upper bound the term y exp((P(r.R)) )')) T. From Theorem A.61 the non-optimality
of i-th sample is
expl(p mi) exp( (P 14)) +
1 exp((1 - () for all i [n].
())((()))))))
The last inequality is from the first statement in Theorem A.6l Consider the sample that contains the same signal token μ have
exp (pp((P..00 p.) (r.
(1 - Bi) B.) exp( (P(r.) (4)))) exp( (P(r.))) Ei)
83

---

Therefore,
y ex)(( M.) (0 I exp((p(.. (4) Ro exp((p(r..)) u.)) + exp (P(r.))) ,)))))))))))))))))
106 M4)
1 1+ exp( - (
2 eepp( Ei)
2 2exp(ER)
exp((1 () -10 11r.
exp((1 - ()ER) 1106,,1011
< 2 exxp((ERt) pr = =
ummm |dp²) - pr S Cn3/2
(95)
for some constant C > 0. Here the third inequality is from P Pir.. (E, m4) 0; The fourth inequality
from the fact that (r,, Et) S E. and the last inequality from (())))) s r, || S p. Then we can bound the test error
Ply (() P(r,)) X) s 0) Ply exp( (p (p.,)) Ry, 11) ()) + cxp(((( ( (') 5
2 Fy exp( (P T,) -Cn
2 p you T E' S - ---e-i R/c Cn3 p'r (Pir.n) R, E`) 1//,01)
1 cC' + Ceexp(-R/CTT) 4 2
22T
16
The first incquality from 95 : the second inequality use the fact that there exists a constant C' >>
such that P(N (0. 1) [L/C.C]
2 1/4; the third inequality comes from Lemma A.69 and the last
inequality uses Assumption 4.5
A.3 Supplement Lemmas
Here we list some technical lemmas for the main proof.
Lemma A.65. (Properties of Training Data) Suppose that 5 > 0. Then exists some constant cp > (that depends just on the number of tokens T) and k S cD /ogooo/////// ((1/Vi) such that with probability least 8, we have
(1 -1- k)d - 113 S (1+ [m], (
IKS,r I cp / dlog(n/5) Vi.j E [n), E (2..... T) +
Proof of Lemma A.65 Note that Ei = d. then by Bernstein's inequality (see Theorem 2.8.1 in Vershynin 35)), with probability at least 5/(3n) we have
111,,-112 d S c1 v Vdlog(n/8)).
where ej is some universal constant. Therefore, for & S e1 wlooooloo////// we have that
(1-s)d || < x)d.
Moreover, (E,,),),))) has mean zero for any i,j E [n], ,, E f2.... T such that (i,T) # (j. r²). By Bernstein's inequality, with probability at least 8/ n3) we have
KE E,tr' S c2 /2 dlog(/8)))
where 02 is some universal constant. Applying a union bound and setting ep = max(ci, 02) completes the proof.
Following Lemma A.65 we conclude the next remark:
84

---

Remark A.66. (Properties of New Test Sample) Let (X = (uu (2.....(r),.)) ~ D. Then exists universal constant ep such that for any C > with probability least n neepp -exx((dd/C9(3m) we have
d KE (1 C
for any i [n]] and T, 7' E (2....,T).
Proof. Similarly to the proof of Lemma A.65 exists some constant ep such that with probability at least 1 we have that
(E f),r! s cDV dlo((n/)))
Setting 8 n cxp(cd/c2 completes the proof.
Lemma A.67 (Properties of Combined Noise Tokens). Suppose that ô 0 and K²
( log(66/0))4ul O(1/Vd) If Lemma A.65 holds, we have
(1 K¹) x')d/T
| 112 (1 + R')d
((5 E,) - 27 / log (oll((nn2/) 18)
for any j [n].
Proof of Lemma A.34 Note that E, - - Σf= Si, and E li, = Lemma A.65 holds for each noise token Ei,,, for the composed noise token have,
11
Σ 4 E.,
Σ
Gr Er 11
Σ
E
I tyt Eira)
1=2mm
(1 R)d Σ
Gr 2 dogg(66n2 /0)
Σ Σ
2
(1 x/d/T 2 dlog(662/0) TT0(1)
(1 k'ddTT.
The first inequality is from triangle inequality; The second inequality from Lemma A.65 The third T
T inequality is from Cauchy-Schwarz inequality that Σ 12 TT > E 4 1 and 4, br 0(1)
The last inequality is from the definition k'. To upper bound || 112, we have
1
Σ
T
T
< Σ
Σ Σ
In (irr))
r=2
Ti T1=2 mfn
T
T
< (1 + k)d Σ
Gr 2 log( 6n226)
Σ Σ Inttrll
r=2
1=22Tm
$ (1+ kjd 2 hlgg/llno///// -20(1
$ (1+ k')d.
The first two inequalities similar as above; The third inequality is from 17, S tir for tir [0,1]. so ET= th
ΣT= ti, = 1; The last inequality is from the definition of r'.
85

---

Last we consider the innerproduct of composed noise tokens. For Vi,j E [nt] à + we have
T
(S., 5,)1 =
Σ
2 T2
T
T
< 22/dlog(6n
Σ
Σ
li
T1=2 r2=2
s / /dog(6n2//))
The first inequality is from triangle inequality and the second inequality is due to This completes the proof.
E [0. 1].
Lemma A.68. With probability least 1 - 66,
|||| n(1 -n)l S nlgg(=))
||-1| ner
Vn log log())))) 7)
|c,||
n(1 1 11) S V moggg)) )
|
wy
S n log( } i= 1,2.
2
Proof. Note that [C] ~ Binom (n, 1 1 m)) Applying Hoeffding's ' inequality, we have
P([[C| (1 7)ml t) S exp( 212
n Let / (1g(/)) We have that with probability at least 6,
|C| (1 - n)ml - V n log( g).
Similarly, note that IW ~ Binom (, m). | Binom (n, (1 n))22,, /C2 Binom(n, (1
7)/2), [ii Binom(n, 1//2) and [22 Binom(n, n/2), we have that each of the following events holds with probability at least
8:
|||| - n(1 - n)} s
n nogl(
||- mn/ S V nn
||C,| - n21 - s
nlog( 8). i= 1,2;
1 )) V
||Val nnn
i 1,2.
Lemma A.69. Suppose X ~ No, Ia), and v. E R.d. are two vectors with ||0||| = |||||| = 1, < c. for some constant e (0, 1). Given some constant C > for 0,
1
cC -
P(u X (E
2
2t v1 - c²
Proof of Lemmal A.69 Denote Ty = T N(O, 1), T N(O, 1). Then we have
Te, Tp NO, 1). Denote the covariance between Te, Ip by Co then we have
co = Cov(o,, xp)) = w. Cov(()) w PSc.
Note that
d 2. cp / 11-c.r cfr,
where r NOO, 1) is independent of sp.. It follows that
P(a,- < =|22 E (/. CT) PP(r- - co
xp c)
1
2 P(r
< 2- cC
cC
vI
V1 2
2
2m
v1
86

---

A.4 Additional Experiments
In this section, we present additional experiments, including various architectures (different from Eq. (3), alternative relationships between parameters (e.g., deviating from Assumption (.11). and gradient descent with weight decay, and more. Additionally, all experiments were conducted on single NVIDIA T4 GPU with 16GB memory. Each individual run was completed in under minute. The total compute cost for all experiments presented in the paper and appendix is negligible. No parallelization or distributed training was used.
In Figure 3 we use the same settings and parameters as in the main paper (i.e. as in Figure 2 but with a smaller step size, In contrast to Theorem 3.3 and Figure 2 benign overfitting occurs after about 150 iterations. This provides empirical validation for Remark 5.1
In Figure 4 we explore the relationship between the number of samples n and the input dimension We observe that even when d z the model exhibits benign overfitting. For intermediate values of d, the model demonstrates harmful overfitting, where the test error increases. For smaller values of d, the model fails fit the data.
In Figure we examine self-attention with respect the first token, as in 7 Here, the model exhibits benign overfitting with behavior similar to that observed under self-attention with respect to tunable token (Remark (.J)) Additionally, the attention probabilities are consistent with those the tunable token attention model (see the resemblance to Figure 2
In Figure 6 and we set the number of tokens T =. 5. The results show benign overfitting after two iterations. Furthermore, for clean samples, the softmax probability of the signal token, $i.1 dominates the overall attention. In contrast, for noisy samples, the softmax probabilities of the noise
tokens, Σm= f dominate. This align with Thm. 3.3
In Figure 8 we use the same settings and parameters as in Figure 2, but with Gaussian initialization instead zero initialization. The results remain consistent, providing empirical validation for Remark 3.2 that states that zero iniiaaiization is without loss of generality.
(X))))) where R (T+1)xd + (T++)xx for i E (2, 3, 4] is defined in Eq. (1) and fi R[T+1)xd + R is defined in Eq. 3 The results show benign overfitting after roughly 20 iterations. Moreover, the softmax probabilities in the first layer align with the behavior observed in the single-layer model.
In figure 9 consider four-layer attention model defined as f(X)
In Figure we consider a four-head attention model which concatenates the results from all heads as the attention output. The results show benign overfitting after roughly 2 iterations. Moreover, the softmax probabilities in the first layer align with the behavior observed in the single-layer model.
In Figure we examine GD with weight decay, which encourages norm minimization (or margin maximization). Here, benign overfitting occurs after approximately 150 iterations. Also here the attention mechanism continues to separate signal tokens from noise tokens.
To further validate our theoretical findings, conducted additional experiments on real-world datasets, including MNIST and CIFAR-10. In both cases, we trained one-layer Transformer model (d 1024) to perform binary classification. Since the tignal-to-noise ratio (SNR) is fixed for each dataset, we varied the training sample size to examine how train and test accuracy evolve with n. The results table 2 and 3 indicate that while training accuracy remains near 100%. the test accuracy improves as increases. This corresponds to our SNR threshold ((1/ that determines the transition between benign and harmful overfitting.
87

---

1.0
0.
clinn sample
0.7
may Somple
Accuns
0.6
Talft oes
0.5
0.7
0.4
0.6
0.3
10
10"
Iterations (Log Scale)
10
20
0.1
10'
10+
10
10
Rerations (Log Scale)
(h) attention weights on signal token Figure The left panel shows train and test accuracies during training with small step size. The clean training samples are correctly classified already after one iteration, but in contrast to Theorem 3.3 and 2 benign overfitting occurs after about 150 iterations. the right panel, we see that the attention starts separating signal and noise tokens shortly before benign overfitting occurs. Parameters: n = 200, d = 40000, T = 2, = 0.0001, p = 30, r = 0.05, test sample size = 2000.
(a) train and test accuracy
Accuracy
0.8
0.7
005 0.5
005
-.000
d-10
d=100
d=230
d=1000
109 10 10 10 10'
10
Reeations (log scale)
Figure 4: Comparing train (solid lines) and test (dashed lines) accuracies with different dimensions. Here, we see that for small d (purple line), the model is unable to fit the data (at least in the first 10sh first iterations), and both the train and test accuracies are at the noise-rate level. For intermediate values of d (green and blue lines), the model exhibits harmful overfitting, and for larger (yellow line) the model exhibits benign overfitting. We note that benign overfitting occurs here for d = 2n < n², which suggests that the assumptions on d in our theorems are loose. Parameters: n 500, 3 = 0.02, T = 5, p = 30, = 0.1, test sample size 10000.
1.0
1.0
rion cx
rolay comppe
probability
0.8
Accuracy
0.8
Toil Ne1
0.7
Taa
0.4
0.2
0.5
10
10a
10
10
Iterations (Lag Scale)
Ieeations (Lag Scalo)
(a) train and test accuracy
(b) attention weights signal token
Figure 5: Self-attention experiments. The model: X - XTS(X (1))),, same as Vasudeva et al. [7] The left panel shows the train and test accuracies during training. It shows that benign overfitting also occurs after 2 iterations. the right panel, we show the softmax probability of the signal token for clean and noisy samples (average of the softmax probabilities 6f.1 over C and N respectively). We see that after iterations, the attention focuses on signal tokens for clean examples, and on noise tokens for noisy examples. This indicates that our results also capture the behavior in a self-attention mechanism. Parameters: n = 200, = 40000,T=2,, = 0.025, p = 20, = 0.05, test sample size 2000.
88

---

0.96
softmax grobabiity
Actuney
Trans
0.5
16'
16
Barations (Log
Bondtoons (Log
(a) train and test accuracy
(b) attention weights on signal token
Figure 6: The left panel shows train and test accuracies during training. It shows that benign overfitting occurs after 2 iterations. In the right panel, we see that after 2 iterations, the attention focuses on signal tokens for clean examples, and on noise tokens for noisy examples. Parameters: n 200, d = 40000, T = 5, = 0.1, = 40, = 0.05, test sample size 2000.
Assumey
0.5
0.5
10
10"
16'
10"
Itraaion (Log Scale)
Iterations (Log Scale)
train and test accuracy
(b) attention weights on signal token
Figure 7: The left panel shows train and test accuracies during training with a small step size. The clean training samples are correctly classified already after one iteration, but benign overfitting occurs after about 22 iterations. In the right panel, we see that the attention starts separating signal and noisy tokens shortly before benign overfitting occurs. Parameters: 200, d = 40000, T = 5, B 0.003, p = 50, r) = 0.05, test sample size 2000.
rdiy sample
0.9
0.6
Teal acc
0.4
0.3
0.6
0.1
Berwfions (Log Scale)
Herstions (Log Scale)
(b) attention weights in signal token Figure 8: The left panel shows the train and test accuracies during training (with Gaussian ini- tialization, where each entry has variance 0.01). As in Figure It shows that benign overfitting occurs after iterations. After the first iteration, the model correctly classifies the clean train- ing examples, but not the noisy ones. In the right panel, we show the softmax probability of the signal token for clean and noisy samples (average of the softmax probabilities s over and A respectively). We see that after 2 iterations, the attention focuses signal tokens for clean examples, and on noise tokens for noisy examples. This aligns with Theorem Parameters: 200, d 40000, 3 0.025, p 30, 0.05, test sample size 2000.
train and test accuracy
89

---

1.0
/len camp-
Dilly cergle
0.9
0.0
Acciracy
0.8
055
0.5
Test
5otmax
0.3
0.6
0.2
0.5
0.1
10
10a
Iterations (Log Scale)
Ieeraiooss (Lag Scale)
train and test accuracy
(b) attention weights on signal token
Figure Multi-layer experiments. The left panel shows the train and test accuracies during training in 4-yayer single-head attention model. It shows that benign overfitting occurs after roughly 20 iterations. After the first iteration, the model correctly classifies the clean training examples, but not the noisy ones. In the right panel, we show the softmax probability of the signal token for clean and noisy samples (average of the softmax probabilities $1,1 over C and respectively) in the first layer. We see that the attention focuses on signal tokens for clean examples, and on noise tokens for noisy examples. This indicates that our results essentially capture the behavior also multi-layer models. Parameters:
200, d 10000, T 2, 3 0.025, p 20, rj 0.05, test sample size 2000.
1.
0.9
deat
0.9
probabiltt
0.8
nsty cyrple
0.7
Accuracy
0.6
Text
ser
0.5
0.4
0.6
0.3
0.2
10
10a
10
10: Iterationn (Log Scale)
Iterations (Lag Scale)
(a) train and test accuracy
(b) attention weights on signal token
Figure 10: Multi-head experiments. The left panel shows train and test accuracies during training in a 4-head attention model. The clean training samples are correctly classified already after one iteration, and benign overfitting occurs after iterations. In the right panel, we see that after 2 iterations, the attention focuses on signal tokens for clean examples, and on noise tokens for noisy examples. Parameters: 200, d 10000, 2, 0.3, p 15, 0.05, test sample size 2000.
0.7
sofrmax probebiitty
0.6
Ancurey
0.8
C
0.5
0.4
0.3
0.2
0.5
0.1
10
10'
10
10
10"
10
10"
Berafions (Log Scale)
Bersioon (Log Scale)
(a) Accuracy during iterations
(b) Softmax prohability for signal (first) token
Figure 11: The left panel shows train and test accuracies during training with GD with weight decay. The clean training samples are correctly classified already after one iteration, and benign overfitting occurs after about 150 iterations. In the right panel. we see that the attention starts separating signal and noise tokens shortly before benign overfitting occurs. Parameters: weight decay 0.01, 200, d = 40000. T = 2, 0.0001, 30, 1 0.05, test sample size 2000.
90

---

Training Size
Eval
80
400
800
2000
Train
100%
100%
99.9%
99.9%
Test acc (on clean data)
87.6%
91.9%
94.1%
95.8%
Table 2: Training and test accuracy label-noisy (1) 0.1) MNIST dataset for 500 iterations in one-layer, two-head Transformers.
Training Size
Eval
40
400
4000
40000
Train acc
100%
100%
100%
100%
Test acc (on clean data)
77.6%
80.9%
86.6%
88.9%
Table Training and test accuracy on label-noisy (7) = 0.05) CIFAR- dataset for 500 iterations in one-layer, four-head Transformers.
91


Reviews:
[{"review_id": "SrlvhayJ6A", "reviewer": "Reviewer_pRmd", "summary": "The authors study benign overfitting for a single softmax attention model. Using a specific data distribution (Section 2.1), a simplified attention model (Section 2.2)  and specific assumptions (Assumptions 3.1) which include a given signal-to-noise ratio, they show that benign overfitting occurs at the 2nd iteration of gradient descent. This is the main result and verified empirically for synthetic data from the specified data distribution. Complementary results for a max-margin learning process are developed and proven.", "questions": "- To what extent does the studied data distribution restrict the value and significance of the findings?\n- The simplified attention model includes a combined key-query. Given that having these separate or combined displayed different optimization characteristics in [5], is this choice worth commenting on in the context of the current paper?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This seems to be a solid theoretical analysis of benign overfitting in the studied context.\n- New perspectives on the conditions required for benign overfitting to occur for a single attention head.\n- Empirical results confirming theoretical predictions for the specific setting: both in the main paper, and the additional results in the appendix, Section A.4.\n\nWeaknesses:\n- In addition to the assumptions listed in 3.1. which can be considered ‘appropriate conditions’, the specific data distribution studied is very specific: two signals orthogonal, and noise also orthogonal with the signal. While this is a valid setting to investigate, it is not clear from the paper how this restricts the applicability of the analysis, or how significant the findings are. The study context itself can be better motivated.\n- 74 pages of supplementary material is excessive – very little of this was reviewed.\n- I struggled to follow the proofs, and was unable to do so in the time available.\n\nMinor comments:\n- Fig 2: check top/bottom vs left/right panels; ‘exsists’ line 487\n- Even if obvious, please consider adding the longer form of abbreviations on first use (GD, SVM etc).", "was_revised": true, "final_justification": "This is a step towards understanding benign overfitting in attention models. Theoretical results are provided for a restricted setting, but this is supplemented with empirical results in a more relaxed setting. A complex problem is tackled carefully and methodically.", "rebuttal": "We thank the reviewer for their thoughtful feedback. Below we respond to each concern and question in order.\n\n**W1**: We adopt this specific signal–noise data distribution to enable a clear and tractable theoretical analysis. This setup is motivated by image data, where inputs are composed of distinct tokens and only some of these tokens are related to the image's class label. \n\nSuch a distribution is typical in theoretical studies on benign overfitting in convolutional networks (where the input has several patches) and transformers (where the input has several tokens). For convolutional neural networks (CNN), we are aware of three papers that studied benign overfitting [1,2,3], and all of them consider a data distribution where there is a single signal patch and a single noise patch, and the signal is either $\\pm \\mu$ for some vector $\\mu$ [1,2], or has an XOR pattern [3]. Moreover, in [1,3] the noise patch is exactly orthogonal to the signal patch. The prior work [4], which studied benign overfitting in transformers (albeit without label noise), considered a distribution similar to ours: one signal token and several noise tokens, where the signal is either $\\mu_+$ or $\\mu_{-}$ for orthogonal $\\mu_+,\\mu_-$, and the noise tokens are orthogonal to the signal. \nHence, in our paper we follow a common setting, which is also the focus of previous works on related topics. \n\n[1] Cao Y., Chen Z., Belkin M., Gu Q. Benign overfitting in two-layer convolutional neural networks\n\n[2] Kou Y., Chen Z., Chen Y., Gu Q. Benign overfitting in two-layer relu convolutional neural networks\n\n[3] Meng X., Zou D., Cao Y. Benign overfitting in two-layer relu convolutional neural networks for xor data\n\n[4] Jiang J., Huang W., Zhang M., Suzuki T., and Nie L. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization.\n\n**Q1:** see the Answer for W1\n\n**Q2:**  We chose to combine the key and query representations to simplify the analysis, which is already technically involved. We note that this simplification is common in prior works studying attention mechanisms. For example, [6,7,8,9,10] (as well as many other papers) also used a combined key-query matrix. \n\nAs the reviewer noted, Tarzanagh et al. [5] explore optimization behavior under separate key and query matrices, but their analysis focuses only on the optimization of the softmax weights, with the attention head (denoted by $v$ in both papers) held fixed. In contrast, our setup involves optimizing both the softmax weights and the attention heads, so their technique does not directly apply to our setting. We will add a comment on this issue in the final version. \n\n[5] Davoud Ataee Tarzanagh, Yingcong Li, Christos Thrampoulidis, and Samet Oymak. Transformers as support vector machines.\n\n[6] Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-margin token selection in the attention mechanism. \n\n[7] Vasudeva, Bhavya, Puneesh Deora, and Christos Thrampoulidis. \"Implicit bias and fast convergence rates for self-attention.\" \n\n[8] Johannes Von Oswald et al. Transformers learn in-context by\ngradient descent. \n\n[9] Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. \n\n[10] Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett. Trained transformers learn linear models in-context."}, {"review_id": "iKWcTh176m", "reviewer": "Reviewer_wMV9", "summary": "This paper investigates benign overfitting in a single-head softmax attention model trained with noisy labels. The authors prove that when the signal-to-noise ratio is $\\Theta(1/\\sqrt{n})$, the model can interpolate noisy training data while generalizing well to test data. This is shown both for early-stage gradient descent after two iterations and for max-margin solutions. They provide tight conditions on the SNR for benign versus harmful overfitting and support the theory with synthetic experiments.", "questions": "1. Can you extend the gradient descent analysis beyond two iterations? Does it eventually converge to the max-margin solution, or does it behave differently?\n2. In the multi-token setting (e.g., multiple noise tokens), how robust is the token selection pattern? Does the model consistently attend to one dominant noise token for noisy samples, or does attention fragment across them?\n3. What fundamentally distinguishes the attention model in your setup from a standard linear classifier trained on convex combinations of signal and noise tokens?", "limitations": "This paper offers a rigorous and technically interesting analysis of benign overfitting in single-head softmax attention models under noise. However, the theoretical results are limited to early-stage training and rely on strong simplifying assumptions about both data and architecture. While the paper improves our theoretical understanding, its insights into realistic attention models remain preliminary. Stronger justification of the attention mechanism's unique role, extended training dynamics, or theoretical treatment of more general token structures would significantly enhance the impact of this work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper addresses benign overfitting in attention-based models, a relatively underexplored setting compared to linear regression, kernel models, and CNNs. This aligns with growing interest in understanding generalization in Transformers.\n\nWeaknesses:\n1. The theoretical results for gradient descent stop after just two iterations, and do not analyze convergence behavior or connection to the max-margin solution. As a result, the relationship between early dynamics and implicit bias remains unclear.\n2. Although each input has $n$ tokens, only one is a signal token and the rest are orthogonal noise. In clean samples, attention rapidly concentrates on the signal; in noisy samples, it shifts to a single dominant noise token. This dynamic resembles a two-mode selection process, so the attention mechanism effectively reduces to selecting between signal and noise, limiting the richness of attention interactions typically seen in real-world applications.\n3. Signal and noise vectors are assumed orthogonal, noise tokens are Gaussian, and all vectors have fixed norms. These stylized assumptions are typical in theoretical work on overparameterized models but limit practical relevance.\n4. While the authors emphasize that softmax attention leads to token selection, it remains somewhat ambiguous how this differs fundamentally from a model that linearly interpolates signal and noise under logistic loss. In the current setup, the attention head largely acts as a soft selector, and it’s unclear what inductive bias is unique to attention beyond this selection.", "was_revised": true, "final_justification": "This paper provides a clear and rigorous theoretical study of benign overfitting in single-head attention models under label noise, supported by synthetic experiments. While the setting is simplified, the work addresses an underexplored architecture in the benign overfitting literature and offers interpretable conditions on the signal-to-noise ratio. The rebuttal clarified the technical challenges in extending the analysis to more iterations and in handling richer multi-token dynamics, and helped distinguish the role of attention from simpler linear models. Although the scope remains somewhat limited, the contribution is meaningful for understanding overfitting behavior in attention mechanisms, and the technical execution is solid. I am therefore raising my score to 4.", "rebuttal": "We thank the reviewer for their thoughtful feedback. Below we respond to each concern and question in order.\n\n**W1:** See the answer for Q1.\n\n**W2:** Indeed, under our setup, the attention mechanism exhibits a two-mode behavior, selecting between signal and noise tokens in clean and noisy samples respectively.\nThis token-selection behavior is a reflection of an important inductive bias in softmax attention. It aligns with recent empirical findings in real-world models, where attention often becomes highly sparse or concentrates on a few dominant tokens([1, 2, 3]). \n\nBesides, the real-world attention settings are highly complex and currently out of reach for comprehensive theoretical analysis. We were inspired by image data to design this simplified but still representative data model to capture essential aspects of token selection while remaining analytically tractable. Similar distributions are common in theoretical studies of the benign overfitting phenomenon (see [4, 5, 6, 7]) \n\nFinally, even in this simplified setting, the two-mode behavior poses significant technical challenges. Our analysis requires careful handling of randomness across noise tokens and a detailed understanding of how parameter norms relate to generalization in the overparameterized regime. While we agree that richer token interactions are important in practical applications, our focus here is to isolate and understand this core mechanism. We believe that this is a meaningful step toward more general theoretical frameworks, and we view extending the analysis to broader data distributions as an important direction for future work.\n\n\n[1] Ataee Tarzanagh D., Li Y., Zhang X., Oymak S. Max-margin token selection in attention mechanism\n\n[2] Jelassi S., Sander M., Li Y. Vision transformers provably learn spatial structure.\n\n[3] Wang Z., Wei S., Hsu D., Lee J. Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot\n\n[4] Cao Y., Chen Z., Belkin M., Gu Q. Benign overfitting in two-layer convolutional neural networks\n\n[5] Kou Y., Chen Z., Chen Y., Gu Q. Benign overfitting in two-layer relu convolutional neural networks\n\n[6] Meng X., Zou D., Cao Y. Benign overfitting in two-layer relu convolutional neural networks for xor data\n\n[7] Jiang J., Huang W., Zhang M., Suzuki T., and Nie L. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization.\n\n**W3:** We adopt this specific signal–noise data distribution to enable a clear and tractable theoretical analysis. This setup is motivated by image data, where inputs are composed of distinct tokens and only some of these tokens are related to the image's class label. \n\nAs the reviewer mentioned, such a distribution is typical in theoretical studies on benign overfitting in convolutional networks (where the input has several patches) and transformers (where the input has several tokens). For convolutional neural networks (CNN), we are aware of three papers that studied benign overfitting [8,9,10], and all of them consider a data distribution where there is a single signal patch and a single noise patch, and the signal is either $\\pm \\mu$ for some vector $\\mu$ [8,9], or has an XOR pattern [10]. Moreover, in [8,10] the noise patch is exactly orthogonal to the signal patch. The prior work [11], which studied benign overfitting in transformers (albeit without label noise), considered a distribution similar to ours: one signal token and several noise tokens, where the signal is either $\\mu_+$ or $\\mu_{-}$ for orthogonal $\\mu_+,\\mu_-$, and the noise tokens are orthogonal to the signal. \nHence, in our paper we follow a common setting, which is also the focus of previous works on related topics. \n\n[8] Cao Y., Chen Z., Belkin M., Gu Q. Benign overfitting in two-layer convolutional neural networks\n\n[9] Kou Y., Chen Z., Chen Y., Gu Q. Benign overfitting in two-layer relu convolutional neural networks\n\n[10] Meng X., Zou D., Cao Y. Benign overfitting in two-layer relu convolutional neural networks for xor data\n\n[11] Jiang J., Huang W., Zhang M., Suzuki T., and Nie L. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization.\n\n**W4:** See the Answer for Q3.\n\n**Q1:** In general, there is no known characterization of the implicit bias in softmax transformers that applies to our setting, so it remains unclear whether GD converges to the max-margin solution. This is indeed a very interesting open direction. We note that min-norm/max-margin solutions roughly correspond to the convergence of GD with (a small) weight decay. Indeed, \nGD with weight decay tends to prefer solutions that minimize the loss while preserving a small weight norm.\nWe also refer the reviewer to lines 232-238, which provide additional motivation for analyzing min-norm/max-margin solutions, even in settings where the implicit bias of GD does not necessarily lead to a min-norm solution (e.g., Savarese et al. [28], Ongie et al. [29], Ergen and Pilanci [30], Hanin [31], Debarre et al. [ 32], Boursier and Flammarion [33]).\n\nWhile we don't know how to extend the analysis beyond a constant number of steps. We note that analyzing even two steps of GD in our setting is challenging. This analysis gives us many insights into how attention handles noisy label data, how the attention focuses on the signal token for clean samples and on the noisy tokens for noisy samples, sufficient and necessary conditions to allow benign overfitting, and the relation between different parameters. It also provides insights into how the trajectory looks after more steps of GD (see Remark 5.1, line 371), which we validate in our experiments (Figure 3 in the appendix). Our experimental results suggest that our theoretical findings extend beyond the two-step setting, demonstrating consistency with longer training and a broader range of learning rates. While a full trajectory analysis is an interesting direction, our results already highlight fundamental phenomena. \n\n**Q2:** In our current setup, even with multiple noise tokens, attention mechanism consistently concentrates on a single dominant noise token in the noisy samples. This is due to the softmax amplification and randomness in token scores. Since all noise tokens are sampled independently from the same Gaussian distribution, their dot products with the learned query vector exhibit random fluctuations. As a result, one noise token typically achieves a noticeably higher score than the others, and the softmax function amplifies this gap exponentially, which leads to sharply concentrated attention on that token.\n\nHowever, which specific noise token is selected does not significantly affect generalization, as long as the model avoids assigning high attention weight to the signal token in noisy samples. Therefore, in our theoretical analysis, we focus on the aggregate attention weight assigned to all noise tokens, rather than tracking the exact distribution across them. This abstraction allows for a cleaner and more interpretable characterization of benign overfitting behavior in the attention model.\n\n**Q3:** First, we note that our motivation in this work is to understand benign overfitting in attention mechanisms. Thus, our focus is on analyzing the behavior of our model, rather than understanding whether the same data distribution is also learnable with other models.\n\nRegarding the question, while the attention output is indeed a convex combination of token embeddings, our model differs fundamentally from a standard linear classifier trained on convex combinations of signal and noise tokens in several key ways.\n First, in our attention model, the combination weights (attention scores) are learned via a softmax over dot products, and are therefore **data-dependent and nonlinear** in the output. This differs from a linear classifier, where the convex combination is fixed and independent of the data. Second, the attention model does not assume that the position of the signal token is fixed. Hence, it is more flexible compared to non-attention models like linear models and MLPs."}, {"review_id": "NwpzvrnSmK", "reviewer": "Reviewer_Ta2Q", "summary": "This paper studies benign overfitting in a model for single head softmax attention. The attention layer is adapted to perform binary classification by adopting a vector valued value matrix and considering its sign. The data consists of $n$ points, or inputs, where input consists of $T$ vectors or tokens: one of these tokens correlates with an output label paired with the input while the rest are gaussian noise. The attention layer is trained by tuning the output value vector along with a prompt vector inside the softmax function and benign overfitting is established in a certain regime and under a variety of training processes.", "questions": "- Is there a typo where $W \\in R^{T \\times d}$ should be  $W \\in R^{d \\times T}$\n- On the model:\n\n     i) In equation 2 why do we suddenly ignore / remove the $S(XWX^T)$ term? \n\n     ii) It seems a little odd to me that on the one hand you argue that $W$ and $q$ are fixed relative to one another and therefore you can simplify $Wq$ to $q$, but on the other you train $v$ and $q$ together. If $q$ is a prompt while $W$ and $v$ are parameters then does it not seem more relevant perhaps to consider them trained via separate processes?\n\n- Assumptions\n\n   i) The required dimension of the tokens seems very large, i.e., $d$ needs to scale like $n^2$. What is the reason for this in this setting and could it be relaxed? For example, in some of the works you cite for linear classifiers and ReLU networks then analogous results can be proved for $d$ scaling like $n$.\n\n  ii) What breaks down if the number of tokens is not bounded by a constant? Intuitively a larger $T$ feels like it would help one achieve benign overfitting?\n\n- General comments: for any data set you might sample is it always true that a solution pair $(v,q)$ exist that solve the constraints of your optimization problem?\n\n- Theorem 3.3\n\n   i) Item 3 confuses me a bit: shouldn't for clean data the result imply that the attention mass is focused on the first token while for the noisy data points the mass on the first token should be very small and the mass distributed amongst the other near orthogonal tokens? For large $T$ I don't see how the result states this. Maybe this is why you only allow for a few tokens?\n\n  ii) What happens if you keep training for more steps?\n\n\n- Can you comment on any differences between benign overfitting across the different models people have studied, i.e., linear, shallow feedforward, CNN and single head attention? In particular, are some models in some sense more or less biased towards the benign overfitting in some or any sense you can identify?", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well written and of high quality. The assumptions made are clearly stated and remarks are provided throughout to add interpretation and highlight key aspects of the work, as such I rate the clarity also highly. The technical contributions are the study of benign overfitting in the context of an attention layer, which to the best of my knowledge is new, but under pretty standard data assumptions. Therefore, and although not exceptional, I think the originality of the paper is good. Overall I think this is a good technically solid paper. If I had to identify the weakest dimension of the paper I might say significance: in particular, the paper seems to adapt single head attention to binary classification in a manner which feels a little contrived. The wider implications of the results also do not seem particularly well discussed.", "was_revised": true, "final_justification": "Overall, and despite the limitations with regards to the setting and assumptions, I think this paper is a good early step towards a better mathematical understanding of how benign overfitting can occur in attention.", "rebuttal": "We thank the reviewer for their thoughtful feedback. Below, we respond to each concern and question in order.\n\n**Q1:** Thank you for pointing this out. There is indeed a typo in the expression, although it should be $W \\in \\mathbb{R}^{d \\times d}$. We will fix it in our revised version.\n\n**Q2:**\n\n**2.1:** The output of the softmax function in Eq. 1 is a matrix in $\\mathbb{R}^{(T+1)\\times(T+1)}$, representing interactions between all pairs of tokens. However, for classification (or regression) purposes, the model must produce a scalar as an output. To achieve this, both in theory and practice (e.g. [1], see Figure 1), it is common to introduce a classification token (CLS token or prompt), whose corresponding output is used for prediction. Thus, in Eq. 2, we focus on the row corresponding to the \"classification\" token, which leads directly to Equation 3.\n\n[1] Dosovitskiy et al. \"An image is worth 16x16 words: Transformers for image recognition at scale.\"\n\n**2.2:** If q is a fixed vector (i.e. corresponds to a fixed prompt), then only $W$ and $v$ need to be trained. In this case, we follow the approach of [2], which showed that optimizing W with a fixed q is equivalent to optimizing q and removing W, as done in our paper. We note that in Section 3 of that paper, they are optimizing both v and q, exactly as we do. We agree that this approach can be viewed as a kind of simplification. \n We also note that our model in Eq. 3 can be obtained by fixing $\\mathbf{q}=(1,0,\\ldots,0)^\\top$ in Eq. 2, and then the vector $\\mathbf{p}$ from Eq. 3 is simply the first column of $W$ in Eq. 2.\n\n[2] Tarzanagh et al. Max-margin token selection in attention mechanism.\n\n**Q3:**  \n\n**Q3.1:**  The $\\Omega(n^2)$ dimension requirement arises from our need to ensure sufficient separation between token inner products and large dimension will help the model to overfit all training data more easily. This assumption is crucial for our theoretical analysis of token selection and margin gaps, and is also common in prior works on benign overfitting (e.g., [3, 4, 5]).\n\nNevertheless, we acknowledge that refining the lower bound on $d$ with respect to $n$ is an interesting direction, as explored in works like [6]. However, such relaxations are typically more tractable in linear models or ReLU networks, where feature mappings are fixed and the inductive biases are simpler. In contrast, the softmax attention mechanism involves data-dependent and dynamically evolving token weights, making the analysis more delicate. We have also done relevant experiments (see Figure 4 in the Appendix) and note that benign overfitting occurs for $d = 2n \\ll n^2$, which suggests that the assumptions on $d$ in our theorems are loose.\nWe view our current dimensionality assumption as a step toward a better understanding of benign overfitting in attention models. Investigating whether this condition can be relaxed while preserving the phenomenon would be a valuable direction for future work. \n\n[3] Frei S., Chatterji N., Bartlett P. Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data.\n\n[4] Kou Y., Chen Z., Chen Y., Gu Q. Benign overfitting in two-layer relu convolutional neural networks.\n\n[5] Jiang J., Huang W., Zhang M., Suzuki T., Nie L. Unveil benign overfitting for transformer in vision.\n\n[6] Karhadkar K., George E., Murray M., Montúfar G., Needell D.\nBenign overfitting in leaky ReLU networks with moderate input dimension.\n\n**Q3.2:** While increasing $T$ introduces more tokens to interpolate, it also raises the risk of the attention mechanism focusing on high-scoring noise tokens due to softmax sensitivity. Besides, the definition of signal-to-noise ratio also needs to be redefined when the token number increases dramatically. In our current analysis, we fix $T=\\Theta(1)$ to ensure analytical tractability to study the token-selection mechanism in the attention model. Extending our results to the large-$T$ regime, where a phase transition might occur, is an interesting direction for future work.\n\n**Q4:** In our data model and architecture, with high probability over the training data, we can construct a pair $(v, p)$ that interpolates the training data and satisfies our constraints, and we even showed that GD reaches such a solution (Thm. 3.3).\n\n**Q5:**\n\n**5.1:** Item 3 in Thm. 3.3 shows that the attention mass for noisy examples is focused on the noisy tokens as expected. We therefore believe that the reviewer's concern is more about the clean examples, which indeed yield a relatively small lower bound on the softmax probability of the first token, especially when the number of tokens $T$ is large. This lower bound is actually more closely related to the SNR threshold. Our proof suggests that for clean examples, when the SNR is large (i.e. $c_\\rho$ is large), the attention head $v$ has a significant component in the direction of the first (signal) token, compared to the direction of the noisy tokens. In such cases, even if the softmax probability of the signal token is not very large, the model still prioritizes the signal token. Conversely, when the SNR is smaller, we can obtain a stronger lower bound on the softmax probability of the first token for clean examples, as stated in Remark 3.4 and formally proved in the appendix.\n\n**5.2:** While our current analysis of GD  is limited to two steps, we believe that benign overfitting persists well beyond this point: First, our experimental results suggest that the theoretical findings extend to longer training, showing consistent behavior with our analysis even after many GD steps.  \n\nSecond, we proved that min-norm/max-margin solutions also exhibit benign overfitting, when these solutions roughly correspond to the convergence of GD with (a small) weight decay. Indeed, it is natural to expect that GD with weight decay tends (after enough iterations) to a solution that minimizes the loss while preserving a small weight norm. We also refer the reviewer to lines 232-238, which provide additional motivation for analyzing min-norm/max-margin solutions. \n\nTaken together, these points reinforce our belief that benign overfitting persists beyond the two-step regime.\n\n**Q6:** \n- **Linear vs single-head attention**: Benign overfitting was first studied in the context of linear models (Bartlett et al.[7]). However, for linear models and MLPs the data has a different structure (without tokens) and the implicit bias is better understood in these cases.\n\n- **CNN vs single-head attention:** Compared with two-layer CNN with ReLU$^q$ activation (Cao et al.[8]), when the signal-to-noise ratio is small (SNR$\\le 1$), our results show that the single-head attention model requires a smaller number of samples to achieve benign overfitting, which reflects the advantage of the attention mechanism.\nCompared with two-layer CNN with ReLU activation (Kou et al.[9]), they only analyze the case where SNR is small ($\\|\\mu\\|/\\sqrt{d} = O(1/n^{1/2})$) as they impose the lower bound of $d$ is related with signal strength $\\|\\mu\\|$. So their results cannot apply to the case when SNR increases while our results show that attention model can generalize well without an upper bound for SNR due to its token-selection mechanism. \n\n\n[7] Bartlett P.L., Long P.M., Lugosi G., Tsigler A. Benign overfitting in linear regression.\n\n[8] Cao Y., Chen Z., Belkin M., Gu Q. Benign overfitting in two-layer convolutional neural networks\n\n[9] Kou Y., Chen Z., Chen Y., Gu Q. Benign overfitting in two-layer relu convolutional neural networks"}, {"review_id": "kdNhRxBYCO", "reviewer": "Reviewer_zipP", "summary": "This paper studies the benign overfitting phenomenon in single head attention. Specifically, when signal-to-noise ratio (SNR) is larger than $\\Omega(1/\\sqrt{n})$, the test loss will be small after training.\nTo show that the requirement on SNR is tight, this paper provides a harmful overfitting result when SNR is smaller than $O(1/\\sqrt{n})$ in the max-margin scenario.\nThe experimental results verifies the theoretical results.", "questions": "Q1: Line 172, this paper requires $d \\ge C \\cdot n^2 \\log (n / \\delta) / \\eta^2$, then as $\\eta \\rightarrow 0$, we have $d \\rightarrow \\infty$. Is the method in this paper able to analyze the situation when $\\eta = 0$ (no lable flipping) ?\n\n\nQ2: The condition of benign overfitting is determined by SNR and n. Would it be related to label flipping rate $\\eta$ ? \n\nIn my intuition, the $\\Omega(1/\\sqrt{n})$ requirement may become more specific if $\\eta$ is considered.\n\n\nQ3: This paper only validate the theoretical results on sythetic datasets.It is recommended that the authors consider more experiments on real datasets, such as MNIST and CIFAR10.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "strengths:\n\n1. This paper demonstrates the importance of SNR for generalisation through rigorous theoretical analysis, and characterizes the boundary between benign overfitting and harmful overfitting.\n\n2. The theoretical result are verified by the experiments (especially the heatmap).\n\n3. The writing is clear and easy to follow, all the assumptions and theorem are well structured.\n\nweaknesses:\n\n1. The assumptions are oversimplified: The original attention mechanism consists of the QKV matrices, but this paper reduces them to two vectors, making it misaligned with reality.\n\n2. Lack of training dynamics: This paper only consider two step of GD in Section 3. It is better to consider a smaller step size to characterize the dynamics of $v$ and $p$.\n\n3. The benign overfitting phenomenon has been studied in [1] and [2], thus this paper seems not novel.\n\n4. In terms of gradient descent (Section 3), no harmful overfitting results are provided in this paper.\n\nreferences\n\n[1] Jiang, J., Huang, W., Zhang, M., Suzuki, T., & Nie, L. Unveil benign overfitting for transformer in vision: Training dynamics, convergence, and generalization. In NeurIPS 2024.\n\n[2] Sakamoto, K., & Sato, I. Benign or not-benign overfitting in token selection of attention mechanism. In ICML 2025.", "was_revised": true, "final_justification": "This work studies benign overfitting for Transformer from a distinctive perspective compared to other works. I am glad to see the experiments on MNIST and CIFAR, and the relaxed assumption on $d$.", "rebuttal": "We thank the reviewer for their thoughtful feedback. Below, we respond to each concern and question in order.\n\n**W1:**  First, we chose to combine the key and query matrices to simplify the analysis, which is already technically involved. We note that this simplification is very common in prior works studying attention mechanisms. For example, [1,2,3,4,5] (as well as many other papers) also used a combined key-query matrix.  Then, following many prior works on classification (or regression) tasks in transformer, we introduce a classification token (CLS token or prompt), whose corresponding output is used for prediction, which leads us to Eq. 2, that is, $f(X; W, v) = v^\\top X^\\top \\mathbb{S}(X W^\\top q)$, that also has been studied in prior works (e.g., [1,2,6] and more). We then follow the approach of [5], which showed that optimizing W with a fixed q is equivalent to optimizing q and removing W, as done in our paper. We note that in Section 3 of that paper, they are optimizing both v and q, exactly as we do. We also note that our model in Eq. 3 can be obtained by fixing $q=(1,0,\\ldots,0)^\\top$ in Eq. 2, and then the vector $p$ from Eq. 3 is simply the first column of $W$ in Eq. 2.\n\n**W2:** We agree that considering a smaller step size and analyzing the trajectory for more than two steps is interesting. However, analyzing even two steps of GD in our setting is challenging. This analysis gives us many insights into how attention handles noisy label data, how the attention focuses on the signal token for clean samples and on the noisy tokens for noisy samples, sufficient and necessary conditions to allow benign overfitting, and the relation between different parameters. It also provides insights into how the trajectory looks after more steps of GD (see Remark 5.1, line 371), which we validate in our experiments (Figure 3 in the appendix). Our experimental results suggest that our theoretical findings extend beyond the two-step setting, demonstrating consistency with longer training and a broader range of learning rates. While a full trajectory analysis is an interesting direction, our results already highlight fundamental phenomena.  \n\nMoreover, we prove that min-norm/max-margin solutions also exhibit benign overfitting, where these solutions roughly correspond to the convergence of GD with (a small) weight decay. Indeed, GD with weight decay tends (after enough iterations) to solutions that minimize the loss while preserving a small weight norm. We also refer the reviewer to lines 232-238, which provide additional motivation for analyzing min-norm/max-margin solutions.\n\n**W3:** Benign overfitting has been studied across a variety of architectures, including CNNs, MLPs, and linear models. Given the widespread interest in Transformers, we believe it is natural and valuable for multiple studies, including ours, to explore benign overfitting in this context. We view this as a sign of growing interest in the topic, and believe our contributions offer a significant and distinctive perspective. \n\nAlthough [7], [6], and our paper all study the benign overfitting phenomenon in attention mechanisms, there are several fundamental differences in setting, assumptions, and theoretical scope. Below we provide a detailed comparison to clarify the novelty of our contribution.\n\n- Jiang et al. [7] do not incorporate label noise in their analysis. The presence of label noise is not a minor extension but a \\textbf{crucial element} in understanding whether interpolation is compatible with generalization. In fact, label noise is central to the definition of benign overfitting in the literature and appears in almost all relevant works, with only a few exceptions such as [8], and [9].\nWithout label noise, many existing results on benign overfitting can be trivially explained through standard uniform convergence arguments. For example, consider the classical result of Bartlett et al. [10] on benign overfitting in linear regression, where they proved under what conditions on the data covariance matrix minimum-norm interpolators exhibit benign overfitting. In linear regression, generalization in a realizable setting with a sufficiently large dataset follows from standard norm-based uniform convergence bounds. Hence, [10]’s result is challenging and interesting mainly because it considers label noise.\n\n- The work of Sakamoto et al. [6] (which was developed in parallel to our work) fixes the attention head $v$ and performs gradient descent only on the attention weights. They also make assumptions on the correlation between the fixed attention head $v$ and the signal token to ensure benign overfitting happens. Their assumption on $v$ holds with exponentially small probability (in the dimension $d$) if $v$ is drawn from a spherically symmetric distribution. In contrast, our setting allows both the attention vector $p$ and the prediction head $v$ to be fully trainable, and we analyze their joint optimization dynamics. \n\nFinally, both works show that there exists a training step where the model achieves a low test loss and zero training error, but they do not characterize behavior beyond that point. In contrast, we go further by analyzing the behavior of the min-norm/max-margin solution, which can be viewed as a fully converged solution, since it corresponds to the convergence of GD with (a small) weight decay. We prove that the min-norm or max-margin interpolator also exhibits benign overfitting, and thus our results describe not just a transient stage but also the asymptotic behavior of a trained model.\n\n**W4:** We can show harmful overfitting results in the first two steps (when SNR = $o(1/\\sqrt{n})$). Roughly speaking, the attention will be focused on the noisy tokens, both for clean and noisy examples, which leads to a small training error but poor generalization. We will add a remark about that in the revised version. Moreover, our experiments (specifically Figure 1) indicate that for SNR = $o(1/\\sqrt{n})$, harmful overfitting persists even after many training steps.\n\n**Q1:** Our GD analysis focuses on the case where there is at least one noisy sample, which occurs with high probability as long as $\\eta \\gg 1/n$, where $n$ is the number of training samples. When there are no noisy examples, the problem becomes significantly simpler and has already been addressed in prior work, such as the GD result of Jiang et al.. More broadly, the typical regime studied in the benign overfitting literature is when the label flipping rate $\\eta$ is large enough (typically, a constant), so that noisy samples exist in the training set (with high probability). \n\n**Q2:** In our work, we assume the label flipping rate is bounded by a certain constant $1/C$ (Assumptions 3.1 and 4.1, Item 4) to ensure that the label flipping rate is relatively low so the noisy samples will not outweigh clean samples in deciding the convergence direction of model parameters. This assumption is typical in the study of benign overfitting with label flipping noise (e.g. [6, 12, 13]) and we follow this line of work to study it in attention mechanisms. We agree that increasing $\\eta$ will add difficulty to achieve benign overfitting, and the SNR threshold might also grow. We leave it as an intriguing topic to study in the future.\n\n**Q3:** To further validate our theoretical findings, we conducted additional experiments on real-world datasets, including MNIST and CIFAR-10. In both cases, we trained a one-layer Transformer model ($d=1024$) to perform binary classification. Since the signal-to-noise ratio (SNR) is fixed for each dataset, we varied the training sample size $n$ to examine how train and test accuracy evolve with $n$. In both cases, the results indicate that while training accuracy remains near 100\\%, the test accuracy improves as $n$ increases. This corresponds to our SNR threshold $\\Theta(1/\\sqrt{n})$ that determines the transition between benign and harmful overfitting.\n\nMNIST, $\\eta=0.1$, 500 itr, 2 heads:\n| Sample size $n$ | 80    | 400   | 800   | 2000  |\n| --------------- | ----- | ----- | ----- | ----- |\n| Train accuracy  | 100%  | 100%  | 99.9% | 99.9% |\n| Test accuracy (on clean data)   | 87.6% | 91.9% | 94.1% | 95.8% |\n\nCIFAR-10, $\\eta=0.05$, 500 itr, 4 heads:\n| Sample size $n$ | 40    | 400   | 4000  | 40000 |\n| --------------- | ----- | ----- | ----- | ----- |\n| Train accuracy  | 100%  | 100%  | 100%  | 100%  |\n| Test accuracy (on clean data)   | 77.6% | 80.9% | 86.6% | 88.9% |\n\n[1] Tarzanagh et al. Max-margin token selection in the attention mechanism. NeurIPS 23.\n\n[2] Vasudeva et al. \"Implicit bias and fast convergence rates for self-attention.\" \n\n[3] Johannes Von Oswald et al. Transformers learn in-context by gradient descent. \n\n[4] Ahn et al. Transformers learn to implement preconditioned gradient descent for in-context learning. \n\n[5] Zhang et al. Trained transformers learn linear models in-context. \n\n[6] Sakamoto et al, I. Benign or not-benign overfitting in token selection of attention mechanism. In ICML 2025.\n\n[7] Jiang et al. Unveil benign overfitting for transformer in vision.\n\n[8] Cao et al. Benign overfitting in two-layer convolutional neural networks.\n\n[9] Wang et al. Benign overfitting in binary classification of gaussian mixtures.\n\n[10] Bartlett P.L. et al. Benign overfitting in linear regression.\n\n[11] Shang et al. Initialization Matters: On the Benign Overfitting of Two-Layer ReLU CNN with Fully Trainable Layers\n\n[12] Kou et al. Benign overfitting in two-layer relu convolutional neural networks\n\n[13] Meng et al. Benign overfitting in two-layer relu convolutional neural networks for xor data"}]

Author rebuttal:

Meta-review: This paper studies 
benign overfitting in a single-head softmax attention model.

The reviewers appreciate the **strengths** of the paper: 
(pRmd) solid theoretical analysis, new perspectives on the conditions, empirical results confirming theoretical predictions,
(wMV9) addresses a relatively under explored setting (attention-based models), aligns with growing interest in Transformers,
(Ta2Q) well-written, clearly stated assumptions, originality is good, technically solid, 
(zipP) rigorous theoretical analysis verified by the experiments, clear writing, well-structured (assumptions and theorem).

The reviewers also find the **weaknesses** of the paper: 
(pRmd) specific data distribution, 
(wMV9) theoretical results for GD stop after just two iterations, no convergence analysis or connection to the max-margin solution, (binary signal/noise settings) limiting the richness of attention interaction
(Ta2Q) weak significance (binary signal/noise settings), 
(zipP) oversimplified assumption, lack of training dynamics, not novel.


**After the discussion**, many concerns seem resolved and clarified (e.g, experiment on MNIST/CIFAR; relaxed assumption on $d$), and the reviewers agreed upon accepting the paper as it is a good early step despite the limited setting and assumptions.
Decision: Accept (poster)