Provable Benefit of Cutout and CutMix for Feature Learning
Authors: Junsoo Oh
Chulhee Yun
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Cutout
CutMix
feature learning
theory
Primary area: learning_theory
TL;DR: We investigate the benefit of Cutout and CutMix for feature learning

Abstract: Patch-level data augmentation techniques such as Cutout and CutMix have demonstrated significant efficacy in enhancing the performance of vision tasks. However, a comprehensive theoretical understanding of these methods remains elusive. In this paper, we study two-layer neural networks trained using three distinct methods: vanilla training without augmentation, Cutout training, and CutMix training. Our analysis focuses on a feature-noise data model, which consists of several label-dependent features of varying rarity and label-independent noises of differing strengths. Our theorems demonstrate that Cutout training can learn low-frequency features that vanilla training cannot, while CutMix training can learn even rarer features that Cutout cannot capture. From this, we establish that CutMix yields the highest test accuracy among the three. Our novel analysis reveals that CutMix training makes the network learn all features and noise vectors "evenly" regardless of the rarity and strength, which provides an interesting insight into understanding patch-level augmentation.

Provable Benefit of Cutout and CutMix for Feature Learning
Junsoo Oh KAIST AI junsoo... wwwkaist..toooooo.ooo.......... ac.
Chulhee Yun KAIST AI chulhee, yuakkas..u ac.kr
Abstract
Patch-level data augmentation techniques such as Cutout and CutMix have demon- strated significant efficacy in enhancing the performance of vision tasks. However, comprehensive theoretical understanding of these methods remains elusive. In this paper, we study two-layer neural networks trained using three distinct meth- ods: vanilla training without augmentation, Cutout training, and CutMix training. Our analysis focuses on a feature-noise data model, which consists of several label-dependent features of varying rarity and label-independent noises of differing strengths. Our theorems demonstrate that Cutout training can learn low-frequency features that vanilla training cannot, while CutMix training can learn even rarer features that Cutout cannot capture. From this, we establish that CutMix yields the highest test accuracy among the three. Our novel analysis reveals that CutMix training makes the network learn all features and noise vectors "evenly" regardless of the rarity and strength, which provides interesting insight into understanding patch-level augmentation.
1 Introduction
Data augmentation is crucial technique in deep learning, particularly in the image domain. It involves creating additional training examples by applying various transformations to the original data, thereby enhancing the generalization performance and robustness of deep learning models. Traditional data augmentation techniques typically focus on geometric transformations such as random rotations, horizontal and vertical flips, and cropping (Krizhevsky et al., 2012), color-based adjustments such as color jittering (Simonyan and Zisserman, 2014).
In recent years, several new data augmentation techniques have appeared. Among them, patch-level data augmentation techniques like Cutout (DeVries and Taylor, 2017) and CutMix (Yun al., 2019) have received considerable attention for their effectiveness in improving generalization. Cutout straightforward method where random rectangular regions of an image are removed during training. In comparison, CutMix adopts more complex strategy by cutting and pasting sections from different images and using mixed labels, encouraging the model to learn from blended contexts. The success of Cutout and CutMix has triggered the development of numerous variants including Random Erasing (Zhong et al., 2020), GridMask (Chen et al., 2020a), CutBlur (Yoo et al., 2020), Puzzle Mix (Kim et al., 2020), and Co-Mixup (Kim et al., 2021). However, despite the empirical success of these patch-level data augmentation techniques in various image-related tasks, a lack of comprehensive theoretical understanding persists: why and how do they work?
this paper, we aim to address this gap by offering theoretical analysis of two important patch-level data augmentation techniques: Cutout and CutMix. Our theoretical framework draws inspiration from a study by Shen et al. (2022), which explores a data model comprising multiple label-dependent feature vectors and label-independent noises of varying frequencies and intensities. The key idea of this work that learning features with low frequency can be challenging due to strong noises (i.e., low regnal-to-oiin ratio). We focus on how Cutout and CutMix can aid in learning such rare features.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1 Our Contributions
In this paper, we consider a patch-wise data model consisting of features and noises, and use two-layer convolutional neural networks learner networks. We focus on three different training methods: vanilla training without any augmentation, Cutout training, and CutMix training. We refer to these training methods in our problem setting as ERM, Cutout, and CutMix. We investigate how these methods affect the network's ' ability to learn features. We summarize our contributions below:
We analyze ERM, Cutout, and CutMix, revealing that Cutout outperforms ERM since it enables the learning of rarer features compared to ERM (Theorem 3.1 and Theorem 3.2). Furthermore, CutMix demonstrates almost perfect performance (Theorem 3.3) by learning all features.
Our main intuition behind the negative result for ERM is that ERM learns to classify training samples by memorizing noise vectors instead of learning meaningful features if the features do not appear frequently enough. Hence, ERM suffers low test accuracy because it cannot learn rare features. However, Cutout alleviates this challenge by removing some of the strong noise patches, allowing it to learn rare features some extent.
We prove the near-perfect performance of CutMix based on a novel technique that views the non-convex loss as a composition of a convex function and reparameterization. This enables us to characterize the global minimum of the loss and show that CutMix forces the model to activate almost uniformly across every patch of inputs, allowing it to learn all features.
1.2 Related Works
Feature Learning Theory. Our work aligns with recent line of studies investigating how training methods and neural network architectures influence feature learning. These studies focus on a specific data distribution composed of two components: label-dependent features and label-independent noise. The key contribution of this body of work is the exploration of which training methods or neural networks most effective at learning meaningful features and achieving good generalization performance. Allen-Zhu and Li (2020) demonstrate that an ensemble model can achieve near- serr-perfect performance by learning diverse features, while a single model tends to Iearn only certain parts of the feature space, leading to lower test accuracy. In other works, Cao et al. (2022); Kou et al. (2023a) explore the phenomenon of benign overfitting when training two-layer convolutional neural network. The authors identify the specific conditions under which benign overfitting occurs, providing valuable insights into how these networks behave during training. Several other studies seek to understand various aspects of deep learning through the lens of feature learning (Zou et al., 2021; Jelassi and Li, 2022; Chen al., 2022, 2023; Li and Li, 2023; Huang al., 2023a.b).
Theoretical Analysis of Data Augmentation. Several works aim to analyze traditional data augmentation from diffcrent perspectives, including kernel theory (Dao et al., 2019), margin-baser based approach (Rajput al., 2019), regularization effects (Wu et al., 2020), group invariance (Chen et al., 2020b), and impact on optimization (Hanin and Sun, 2021). Moreover, many papers have explored various aspects of a recent technique called Mixup (Zhang al., 2017). For example, studies have explored its regularization effects (Carratino et al., 2020; Zhang et al., 2020), its role in improving calibration (Zhang al., 2022), its ability to find optimal decision boundaries (Oh and Yun, 2023) and its potential negative effects (Chidambaram et al., 2021; Chidambaram and Ge, 2024). Some works investigate the broader framework of Mixup, including CutMix, which aligns with the scope of our work. Park et al. (2022) study the regularization effect of mixed-sample data augmentation within a unified framework that contains both Mixup and CutMix. In Oh and Yun (2023), the authors analyze besking-based Mixup, which is class of Mixup variants that also includes CutMix. In their context, they show that maakingg-assed Mixup can deviate from the Bayes optimal classitier but require less training sample complexity. However, neither work provides rigorous explanation for why CutMix has been successful. The studies most closely related to our work include Shen et al. (2022): Chidambaram et al. (2023): Zou et al. (2023). Shen et al. (2022) regard traditional data augmentation as form of feature manipulation and investigate its advantages from a feature learning perspective. Both Chidambaram et al. (2023) and Zou et al. (2023) analyze Mixup within a feature learning framework. However, patch-level data augmentation such as Cutout and CutMix, which are the focus of our work, have not yet been explored within this context.

---

2
Problem Setting
In this section, we introduce the data distribution and neural network architecture, and formally describe the three training methods considered this paper.
2.1 Data Distribution
We consider a binary classification problem on structured data, consisting of patches of label- dependent vectors (referred to as features) and sabel-independen vectors (referred to noise). Definition 2.1 (Feature Noise Patch Data), We define a data distribution DD on RdxP x (-1,1) 1) such that (X, y) ~ where X = (x(1), ,..., (P)) E R and E
{+1} } is constructed as follows.
1. Choose the label E { { uniformly at random.
2. Let ( ((1)))
Rd be set of orthonormal feature vectors. Choose the feature vector v Rd for data point X as v Uy.k with probability Ps: from [ C Rd where P1 +.... PK = 1 and #1 ... PK- In our setting, there are three types of features with significantly different frequencies: common features, rare features, and extremely rare features, ordered from most to least frequent. The indices of these features partition [K] into KR).
3. We construct P patches of X as follows.
Feature Patch: Choose p" uniformly from [P] and we set x(p") =
Dominant Noise Patch: Choose uniformly from [P] (p"). We construct (0) = or + 1 (())
where or is feature noise drawn uniformly from {aru1, 00 -01-111 with 0 < < and (()) is
Gaussian dominant noise drawn from N N(0, A²
Background Noise Patch: The remaining patches p E [P] | (p", [p",p] consist of Gaussian background noise, i.e., we set (x) ((r) where g(r) ~ N(0, (A).
Here, the noise covariance matrix is defined as A = I Σ U. which ensures that Gaussian noises are orthogonal to all features. We assume that the dominant noise is stronger than the background noise, i.e., ob od.
Our data distribution captures characteristics of image data, where the input consists of several patches. Some patches contain information relevant to the image labels, such as cat faces for the label "cat," while other patches contain information irrelevant to the labels, such as the background. Intuitively, there are two ways to fit the given data: learning features or memorizing noise. If a model fits the data by learning features, it can correctly classify test data having the same features. However, if model fits the data memorizing noise, it cannot generalize unseen data because noise patches are not relevant to labels. Thus, learning more features crucial for achieving better generalization.
In real-world scenarios, different features may appear with varying frequencies. For instance, the occurrences of cat's faces and cat's tails in a dataset might differ significantly, although both are relevant to the "cat" label. Our data distribution reflects these characteristics by considering features with varying frequencies. To emphasize the distinctions between the three training methods we analyze, categorize features into three groups: common, rare, and extremely rare. We refer to data points containing these features as common data, rare data, and extremely rare data, respectively. We emphasize that these terminologies are chosen merely to distinguish the three different levels of rarity, and even "extremely rare" features appear in nontrivial fraction of the training data with high probability (see assumptions in Section 2.4).
Comparison Previous Work. Our data distribution is similar to those considered in Shen et al. (2022) and Zou et al. (2023), which investigate the benefits of standard data augmentation methods and Mixup by comparing them to vanilla training without any augmentation. These results consider common
two types of features coatmone-commmon and rare rare-wirl with different levels of rarity, along with two types of noise: feature noise and Gaussian noise. However, we consider three types of features: common, rare, and extremely rare, and three types of noise: feature noise, dominant noise, and background noise. This distinction allows us to compare three distinct methods and demonstrate the differences between them, whereas Shen et al. (2022) and Zou et al. (2023) compared only two methods.
3

---

2.2 Neural Network Architecture
For the prediction model, we focus on the following two-layer convolutional neural network where the weights in the second layer are fixed at and -1, with only the first layer being trainable. Several works including Shen al. (2022) and Zou et al. (2023) also focus on similar two-layer convolutional neural networks.
Definition 2.2 (2-Layer CNN), We define 2-layer CNN fw : Rdx + R parameterized by E RdxPP, we define
W = (wi, w-1} } E Rdx22 For each input X =
Sw(X)
E (w01, PE[P]
Σ PE
where of.) is smoothed version of leaky ReLU activation, defined follows.
(1-9)r
22r
((2)
1-8
22
+ f2
0 2 SSr,
2r
Az
2 2
where 0 < 8 1 and 0.
Previous works on the theory of feature learning often consider neural networks with (smoothed) ReL.U polynomial activation functions. However, we adopt smoothed leaky ReLU activation, which always has positive slope, to exclude the possibility optimization trajectory. Using smoothed leaky ReLU to analyze the learning dynamics of neural networks is not entirely new; there is body of work that studies phenomena such as benign overfitting (Frei et al., 2022a) and implicit bias (Frei al., 2022b; Kou al., 2023b) by analyzing neural networks with (smoothed) leaky ReLU activation.
neurons "dying" during the complex
A key difference between ReLU and leaky ReLU lies in the possibility of ReLU neurons "dying" the negative region, where some negatively initialized neurons remain unchanged throughout training. As result, using ReLU activation requires multiple neurons ensure the survival of neurons at initialization, which becomes increasingly probable as the number of neurons increases. In contrast, the derivative of leaky ReLU is always positive, ensuring that single neuron is often sufficient. Therefore, for mathematical simplicity, we consider the case where the network has single neuron for each positive and negative output. We believe that our analysis can be extended to the multi-neuron case as we validate numerically in Appendix A.2.
2.3 Training Methods
Using training set sampled from the distribution D, we would like train our network fw to learn to correctly classify unseen data points from D. We consider three learning methods: vanilla training without any augmentation, Cutout, and CutMix. We first introduce necessary notation for our data and parameters, and then formalize training methods within our framework.
Training Data. We consider training set Z ((x,, ()) Jeta) comprising n data points, each independently drawn from D. For each E [n:]. we denote X; (a (1)
x !))
Initialization. We initialize the model parameters in our neural network using random initializa- tion. Specifically, we initialize the model parameter (0 (o) w
())), where (0)
itd.
w
(O Ta). Let us denote updated model parameters iteration (+)) {u0 m (t)
(t)
11.
2.3.1 Vanilla Training
The vanilla approach to training model fw is solving the empirical risk minimization problem using gradient descent. We refer to this method as ERM. Then, ERM updates parameters ((() of model using the following rule.
(++1)= ((() v/V LERM (Wr(t),

---

where 1) is a learning rate and (ERM( (.) is the ERM training loss defined as
LERM W) = Σ
(ouff(X.)).
(1)
vE(m)
where E(-) is the logistic loss {(z) = log(1 + t
2.3.2 Cutout Training.
Cutout (DeVries and Taylor, 2017) a data augmentation technique that randomly cuts out rectangular regions of image inputs. In patch-wiss data, regard Cutout training as using imputs with masked patches from the original data. For each subset C of [P] and E [n]], we define augmented data X,c E RdxP as data point generated by cutting the patches with indices in C out of X, We can represent X as
(nl1)) ( a.f). where (p)))
a0 0
p C. otherwise.
X,c
Note that the output of the model f-(-) (-) on this augmented data point X is
fw fw(Xic) = [ )),
Σ
2 (p)
Pdc
PdC
Then, the objective function for Cutout training be defined as
1 Σ Be AE|m]
CCutont (W)
where De is uniform distribution on the collection of subsets of [P] with cardinality C, where C We refer the process of training our model using gradient descent on Cutout loss LCutout (W)& as Cutout, and its update rule
hyperparameter satisfying 1 C.C- <
( (t() 1/ w (w(()).
(2)
where 7) is learning rate.
2.3.3 CutMix Training.
CutMix (Yun et al., 2019) involves not only cutting parts of images, but also pasting them into different images well as assigning them mixed labels. For each subset S of [P] and i,j [n]. define the augmented data point Xij,s dx as the data obtained by cutting patches with indices S from data X; and pasting them into X, at the same indices We can write X as
X X
(P) i.j.s)
where x L.s.s
(p)
if S otherwise.
S.
(p)
The one-hot encoding of the labels ys and y, also mixed with proportions respectively. This mixed label results in the loss of the form
| and 1 P
[S]
|S] P
E(yafw (X + (1 (S|
elusfw ((u,f((Xigss)) (Xir.s)).
From this, the CutMix training loss LoutMix (W) can be defined
S P ((,.f((X.))s)) + (1 |S] P lly, for (wi,s)))..))))
LoutMix (W) =
Σ (.j((n)
EsnDs
2
where D& is probability distribution on the set of subsets of [P] which samples S Ds as follows.?
Deeriees and Taylor (2017) also employ moderate size of cutting, such cutting 16 16 pixels
CIFAR-I0 10 data, which originally has x 32 pixels.
'Other types of distributions. such as those considered in Yun et al. (2019), make the same conclusion. We adopt this distribution make presentation simpler.
5

---

1. Choose the cardinality of S uniformly at random from {0, 10..,...,
.,. P), and
2. Choose S uniformly random from the collection of subsets of [P] with cardinality
We refer to the process of training our network using gradient descent on CutMix loss LCutMii ( W) as CutMix, and its update rule is
w W(() v/V CCutMix (W()),
(3)
where 7) is a learning rate.
2.4 Assumptions on the Choice of Problem Parameters
To control the quantities that appear in the analysis of training dynamics, we make assumptions on several quantities in our problem setting. For simplicity, we use choices of problem parameters as a function of the dimension of patches d and consider sufficiently large d.
We use the standard asymptotic notation R()), ((-), o(),,(() to express the dependency on d. We also use (()),(())) (.) to hide logarithmic factors of Additionally, poly(d) (or polylog(d)) represents quantities that increase faster than d (log d) and slower than d (or (log d) for some constant < C1 < C2. Similarly, o(1/poly(d)) (or o(1/polylog(d)) denotes some quantities that decrease faster than 1/d (or 1/olo d))) for any constant c. Finally, we use f(d) (achl//oollo((e00 when f(d)//(d) = o(1/polylog(d)) for some function / and g of d.
Assumptions. We assume that P = (1) and P 2 8 for simplicity. Additionally, we consider high-dimensional regime where the number of data points is much smaller than the dimension which is expressed
(a30 o, /polylog(d)). We also assume that p. pæn= w (n log d)
for all & E [K], which ensures the sufficiency of data points with each feature.
In addition, we will describe in Section 4, the relative scales between the frequencies of features and the strengths of noises play crucial roles in our analysis, as they serve as a proxy for the "learning speed" in the initial phase. For common features & E Kc. we assume Pv: +(1) and the learning speed of common features is much faster than that of dominant noise, which translates into the assumption of o(3n). For rare features E KCR, we assume Pt (pR) for some pg. and we consider the case where the learning speed of rare features is much slower than that of dominant noise but faster than background noise, which is expressed as pam o (a² /ddoo//oly ofd o(ppzn). Finally, for extremely rare features E KE. we say Ps ((pr) for some PE and their learning is even slower than that of background noises, which can be expressed as Pgn (22o[d/polylog())
and
Lastly, we assume the strength of feature noise satisfies a o (n- (odd and T,, 7 > 0 are sufficiently small so that do. r = o (a/polylog (d)) 1 = o (ro /ro_dd-/polyyog///
We list our assumptions in Assumption B.1 and there are many choices of parameters satisfying the set of assumptions, including:
P= 8, C 2, = 2 (d O (d-0..))) polylog(d)" 50 = O(d (.)))..),r (((
Oa = + (d- 0.305 ob = A (d-0.370) pn e (d-0.1) ,PE = θ (d- , (d
3 Main Results
In this section, we provide characterization of the high probability guarantees for the behavior of models trained using three distinct methods we have introduced. We denote by T the maximum admissible training iterates and we assume T poly(d) with a sufficiently large polynomial in d. In all of our theorem statements, the randomness is over the sampling of training data and the initialization of models and all results hold under the condition that d is sufficiently large.
7
The following theorem characterizes training accuracy and test accuracy achieved by ERM.

---

Theorem 3.1. Let W be iterates of ERM. Then with probability least 1 o (polyaa) ). there
exists TERM such that any T [TERM: TM) satisfies the following:
(Perfectly fits training set): For all i E [m], Bi.wer (X;) > O.
(Random on (extremely) rare data): P P(X,)>>D byfwor x]
E
pk
| poly(d))
REKRUKK
The proof provided in Appendix C.2. Theorem 3.1 demonstrates that ERM achieves perfect training accuracy; however, it performs almost like random guessing on unseen data points with rare and extremely rare features. This because ERM can only learn common features and overfit rare or extremely rare data in the training set by memorizing noises to achieve perfect training accuracy.
In comparison, show that Cutout can perfectly fit both augmented training data and original training data, and it can also learn rare features that ERM cannot. However, Cutout still makes random guesses on data with extremely rare features. We state these in the following theorem with the proof provided in Appendix D.2:
Theorem 3.2. Let W (f) be iterates of Cutout training. Then with probability at least 1- 0 (pllyld)
there exists Tutoout such that any E [Tcutout, T"] satisfies the following:
(Perfectly fits augmented data): For all E [n)] and C [P] with |C| C. Vilwia (tt/wwrr(((())>>>>)))) 0.
(Perfectly fits original training data): For all i [ri], Vifwen (X,) 0.
(Random on extremely rare data): TP P(X (ySwer) (X) > =1 2
Σ Pk + polyyay)) kEKE
(pob(ar))
In the case of CutMix, it is challenging to discuss training accuracy directly because the augmented data have soft labels generated by mixing pairs of labels. Instead, prove that CutMix achieves a sufficiently small gradient of the loss, and the training accuracy on the original training data is perfect. We also demonstrate that CutMix achieves almost perfect test accuracy, learns all types of features regardless of rarity.
Theorem 3.3. Let (() be iterates of CutMix training. Then with probability at least 1- - (poly(d) )
1
there exists some TCutMix E [0,T*] that satisfies the following:
(Finds a near stationary point): V CouMixx (W(IcomMax))
poly
(Perfectly fits original training data): For all i E [n],, y:fw(rourmm)) (Xi) > O.
(Almost perfectly classifies test data): P x)DD (V Wff((Toraaa (X)
> 0 =1 (poly(a))
To prove Theorem 3.3, we characterize the global minimum of objective loss of CutMix. Surprisingly, the global minimum, the model has the same outputs for all patches of the input data. In other words, the contributions of all feature vectors and noise vectors to the final outcome of the network are identical, regardless of their frequency and strength (see Section 4.2 for more details). Moreover, this uniform "contribution" is large enough, which allows the model to learn all types of features by reaching the global minimum. We provide the detailed proof in Appendix E.2.
Our three main theorems elucidate the benefits of Cutout and CutMix. Cutout enables a model to learn rarer features than ERM, while CutMix can even outperform Cutout. These advantages in learning rarer features lead to improvements in generalization performance.
4 Overview of Analysis
In this section, we discuss key proof ideas and the main challenges our analysis. For ease of presentation, we consider the case = 0. Although our assumptions do not allow the choice a = O, the choice of nonzero a is to show guarantees on the test accuracy and does not significantly affect the feature learning aspect.
7

---

To provide the proof overview, let us introduce some additional notation. For each i [rz]. recall that the corresponding imput point can be written as X; = (a) ". ". We use po and ý; to denote the indices of its feature patch and dominant noise patch, respectively, For each feature vector vs.k. where s E {=1} and [K], let Va, C [nx] represent the set of indices of data points having the feature vector Us.k, and V. U k= Ve. denotes the set of indices of data with label s. For each data point E [n] and dominant or background noise patch p E [P] \ {pī }. we refer to the Gaussian noise inside x (p) as 4%
4.1 Vanilla Training and Cutout Training
We now explain why ERM fails to learn (extremely) rare features, while Cutout can learn rare features but not extremely rare features. Let us consider ERM. From (1), for 8, E [=1],,4 k E [K], E [n] and p [P] {pT). the component of w. in the feature vector uy direction is updated as
(wfth (arkk) ( (oo u.
8s'n
Σ
Swoo (X;)) ((w)²) uwr)))
JEVEIK
and similarly, the "update" of inner product of w, with a noise patch el(²) can be written as (uo! (1o(++1) (."") W ((())
syell e' (y.ffwo) (X:))o' ((us)) s.('' [|{
(5)
n
where the approximation is due to the near-orthogonality of Gaussian random vectors in the high- dimensional regime. This approximation shows that (w (t) u. 's and (wo!) ; </Ply's are almost monotonically increasing decreasing. We address the approximation errors using variant of the technique introduced by Cao et al. (2022), as detailed in Appendix B.3.
From (4) and (5), we can observe that in the early phase of training satisfying -f(yiSwro (Xi)) ((1), the main factor for the speed of learning features and noises are the number of feature occurrence VV kl and the strength of noise ||c!") 1|2. From our assumptions introduced in Section 2.4, we compare the learning speed of different components, we have
common features >> dominant noises >> rare features >> background noises > extremely rare features,
in terms of "learning speed." Based on this observation, conduct three-phase analysis for ERM.
Phase 1: Learning common features quickly.
Phase 2: Fitting (extremely) rare data by memorizing dominant noises instead of learning features.
Phase 3: A model cannot learn (extremely) rare features since gradients of all data small.
The main intuition behind why ERM cannot learn (extremely) rare features is that the gradients of all data containing these features become small after quickly memorizing dominant noise patches. In contrast, since Cutout randomly cuts some patches out, there exist augmented data points that do not contain dominant noises and have only features and background noises. This allows Cutout to learn rare features, thanks to these augmented data. However, extremely rare features cannot be learned since the learning speed of background noise is much faster and there are too many background noise patches to cut them all out.
Remark 4. Shen et al. (2022) conduct analysis on vanilla training and training using standard data augmentation, sharing the same intuition in similar but different data models and neural networks. Also, we emphasize that proved the model cannot learn (extremely) rare features even if we run poly(d) iterations of GD, whereas Shen et (2022) only consider the first iteration that achieves perfect training accuracy.
Practical Insights. In practice, images contain features and noise across several patches. A larger cutting size can be more effective in removing noise but may also remove important features that the model needs to leam. Thus, there is trade-off in choosing the optimal cutting size, a trend also observed in Vriei and Taylor (2017). One limitation of Cutout is that may not effectively remove dominant noise. Thus, dominant noise can persist in the augmented data, leading to potential noise memorization. We believe that developing strategies that can more precisely detect and remove these noise components from the image input could enhance the effectiveness of these methods.

---

4.2 CutMix Training
In learning dynamics of ERM and Cutout, inner products between weight and data patches evolve (approximately) monotonically, which makes the analysis much more feasible. However, analyz- ing the learning dynamics of CutMix involves non non- non-monotone change of inner products, which is inevitable since CutMix uses mixed labels; this is also demonstrated in our experimental results (Section s,especially the leftmost plot in Figure 1). Non-monotonicity and non-convexity of the problem necessitates novel proof strategies.
Let us define Z := (2)))) U (2(") PE(()))))(P))))) function of W as follows, (p) o ((w),)(")) ((((L.,)
2 <( (ww,, v,,,)) o (w- Vs,k))
Then, Z represents the contribution of each noise patch and feature vector to the neural network output, and the nonconvex function LCueMix () can be viewed as the composition of Z(W) and a convex function i()). By using the convexity of (Z), we can characterize the global minimum of LoutMix Surprisingly, we show that any global minimizer W = {wf, w" w-1} satisfies
(W))
① ((w0) ae.")))) - ((wi,,. )
= =Ca,
for all E {+1},i Ve, and p E [P], with some constants C₁, = (().. In other words, at the global minimum, the output of model on each patch of the training data is uniform across the of data with the same labels. We also prove that CutMix can achieve point close to the global minimum within poly(d) iterations. As a result, the model trained by CutMix can learn all features including extremely rare features. The complete proof of Theorem 3.3 appears in Appendix E.2.
Remark 4.2. Zou et al. (2023) investigate Mixup in a similar feature-noise model and show that Mixup can learn rarer features than vanilla training, with its benefits emerging from the early dynamics of training. However, our characterization of the global minimum of CCutMix (W) and experimental
results our setting (Section Figure 1) suggest that the benefits of CutMix, especially for learning extremely rare features, arise from the later stages of training. This suggests that Mixup and CutMix have different underlying mechanisms for promoting feature learning.
Practical Insights. The main underlying mechanism of CutMix is that it learns information almost uniformly from all patches in the training data. However, this approach also involves memorizing noise, which can potentially degrade performance in real-world scenarios. We believe that a more sophisticated strategy such as considering the positional information of patches as used in Puzzle Mix (Kim et al., 2020) or Co-Mixup (Kim et al., 2021) could improve the ability to learn more from patches containing features and reduce the impact of noise.
5 Experiments
We conduct experiments both in our setting and real-world data CIFAR- to support our theoretical findings and intuition. We defer CIFAR-I0 experiment results to Appendix A.I.
For the numerical experiments on our setting, we set the number of patches P = 3, dimension d 2000, number of data points strength a, = 0.15, and feature noise strength a = 0.005. The feature vectors are given as the standard basis e1, E2, e3. C3, es, C₁ E RR.. where e1, C2, ey features for the positive label y 1 and 64, é5, eg are features for the negative label = -1. We categorize e and e4 as common features with a frequency of 0.8, 62 and e; rare features with a frequency of 0.15, and lastly, es and eg as extremely rare features with a frequency of 0.05. For the learner network, we set the slope of negative regime 3 = 0.1 and the length of the smoothed interval r 1. We train models using three methods: ERM, Cutout, and CutMix with learning rate 1 = 1. For Cutout, we cut a single patch of data (C' 1). We apply full-batch gradient descent for all methods; for Cutout and CutMix, we utilize all possible augmented data points.' We note that this choice of problem parameters does not exactly match the technical assumptions in Section 2.4. However, we empirically observe the same conclusions, which suggests that our analysis could be extended beyond our assumptions.
300, dominant noise strength σα 0.25, background noise
FFor CutMix, this may induce different choices of Ds from those assumed in our analysis, but we mention that other general choices of Dg do not alter the conclusions analysis.

---

For each feature vector of the positive label, we plot the output of the learned filters for the feature vector ( (ww) (6) v)) ői (w v)) throughout training in Figure 1. Our numerical findings confirm that ERM can only learn common features, Cutout can learn common and rare features but cannot learn extremely rare features, and CutMix can learn all types of features. Especially, CutMix learn common features, rare features, and extremely rare features almost evenly. Also, we observed non- monotone behavior the output the case of CutMix, which motivated our novel proof technique. The same trends are observed with different architectures, such as smoothed (leaky) ReLU network with multiple neurons, as detailed in Appendix A.2.
ERM
ERM
ERM
0.8
Extremely Rare Feature Output
0.8-
Common Feature Output.
CutMix
CutMix
CutMix
Rare Feature Output:
4-
0.4
2.4
2-
0-
0.0
0.0
6000
10000
Iterations
Figure 1: Numerical results our problem setting. We validate our findings the trends of ERM, Cutout, and CutMix in learning common feature (Left), rare feature (Center), and extremely rare feature (Right). The output of the common feature trained by CutMix shows non-monotone behavior.
6
Conclusion
We studied how Cutout and CutMix influence the ability to learn features in patch-wise feature- noise data model learning with two-layer convolutional neural networks by comparing them with vanilla training. We showed that Cutout enables the learning of rare features that cannot be learned through vanilla training by mitigating the problem of memorizing label-independent noises instead of learning label-dependent features. Surprisingly, rare features that Cutout cannot learn. We also present our theoretical insights on the underlying mechanism of these methods and provide experimental support.
further proved that CutMix can learn extremely
Limitation and Future Work. Our work has some limitations related to the neural network architecture, specifically, the use of a 2-layer two-neuron smoothed leaky ReLU network. Extending our results to neural networks with deeper, wider, and more general activation functions is a direction for future work. Another future direction is to develop patch-level data augmentation based theoretical findings. Also, it would be interesting to perform thcoretical analysis on state-of-the-ar patch-level data augmentation such as Puzzle Mix (Kim al., 2020) Co-Mixup (Kim et al., 2021). These methods utilize patch location information, thus may require the development of a theoretical framework capturing complex characteristics of image data.
Acknowledgement
This work was supported by three Institute of Information & communications Technology Planning Evaluation (IITP) grants (No. 1S-2075- Artificial Intelligence Graduate School Program (KAIST); No. RS- 2S-2002--12201 184, Development and Study of AI Technologies to Inexpensively Research Hub Project) funded
Conform to Evolving Policy on Ethics; No. RS-2024-00457882 by the Korean government (MSIT), and a National Research Foundation of Korea (NRF) grant (No. funded by the Korean government (MSIT). CY acknowledges support from grant funded by Samsung Electronics Co., Ltd.
10

---

References
Zeyuan Allen Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.098/6, 2020.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-337, 2015.
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convo-
lutional neural networks. Advances in neural information processing systems, 35:25237-25250, 2022.
Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On mixup regulariza- tion. arXiv preprint wrXiv:2006.06049 2020.
Pengguang Chen, Shu Liu, Hengshuang Zhao, and Jiaya Jia. Gridmask data augmentation. arXiv preprint arXiv:2001.0400 2020a.
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. A group-theorrtic framework for data augmentation. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 21321-21333, 2020b.
Zixiang Chen, Yihe Deng, Yue Wu, Quanquan Gu, and Yuanzhi Li. Towards understanding the mixture-of-experts layer in deep learning. Advances in neural information processing systems, 35: 23049-23062, 2022.
Zixiang Chen, Junkai Zhang, Yiwen Kou, Xiangning Chen, Cho-Jui Hsieh, and Quanquan Gu. Why does sharpness-aware minimization generalize better than sgd? In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Muthu Chidambaram and Rong Ge. For better or for worse? learning minimum variance features with label augmentation. arXiv preprint arXiv:2402.06855 2024.
Muthu Chidambaram, Xiang Wang, Yuzheng Hu, Chenwei Wu, and Rong Ge. Towards understanding the data dependency of mixup-style training. arXiv preprint arXiv:21 10.07647, 2021.
Muthu Chidambaram, Xiang Wang, Chenwei Wu, and Rong Ge. Provably learning diverse features in multi-view data with midpoint mixup. International Conference on Machine Learning, pages 5563-5599. PMIR, 2023.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. A kernel theory of modern data augmentation. In International conference on machine learning, pages 1528-1537. PMLR, 2019.
Terrance Vries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint
2017.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pages 2668 2703. PMLR, 2022a.
Spencer Frei, Gal Vardi, Peter L Bartlett, Nathan Srebro, and Wei Hu. Implicit bias in leaky relu networks trained on high-dimensional data. arXiv preprint arXiv:2210.0708) 2022b.
Boris Hanin and Yi Sun. How data augmentation affects optimization for linear regression. Advances in Neural Information Processing Systems, 34:8095-8105, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, and Taiji Suzuki. Graph neural networks provably ben- efit from structural information: feature learning perspective, arXiv preprint arXiv:2306. 13926, 2023a.

---

Wei Huang, Ye Shi, Zhongyi Cai, and Taiji Suzuki. Understanding convergence and generalization in federated learning through feature learning theory. The Twelfth Interaatoonal Conference on Learning Representations, 2023b.
Samy Jelassi and Yuanzhi Li. Towards understanding how momentum improves generalization in deep learning. In International Conference on Machine Learning, pages 9965-10040, PMLR, 2022.
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, and Michael C Mozer. Characterizing structural regularities of labeled data in overparameterized models. In International Conference on Machine Learning, pages 5034-5044. PMLR, 2021.
Jang- Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. In International Conference on Machine Learning, pages 5275-5285 PMLR, 2020.
Jang-Hyun Kim, Wonho Choo, Hosan Jeong, and Hyun Oh Song. Co-mixup: Saliency guided joint mixup with supermodular diversity. arXiv preprint arXiv: 10Xiv:2102.03055, 2021.
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, 2023a.
Yiwen Kou, Zixiang Chen, and Quanquan Gu. Implicit bias of gradient descent for two-layer relu and leaky relu networks on nearly-orthogone data. In Thirty-seventh Conference on Neural Information Processing Systems, 2023b.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Binghui Li and Yuanzhi Li. Why clean generalization and robust overfitting both happen in adversarial training. arXiv preprint arXiv:2306.01277 2023.
Junsoo Oh and Chulhee Yun. Provable benefit of mixup for finding optimal decision boundaries. In International Conference on Machine Learning, pages 26403-26450. PMLR, 2023.
Chanwoo Park, Sangdoo Yun, and Sanghyuk Chun. unified analysis of mixed sample data augmentation: A loss function perspective. Advances in Neural Information Processing Systems, 35:35504-333 1555500--551.,. 35518, 2022.
Shashank Rajput, Zhili Feng, Zachary Charles, Po-Ling Loh, and Dimitris Papailiopoulos. Does data augmentation lead to positive margin? In International Conference on Machine Learning, pages 5321-5330. PMLR, 2019.
Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation. In International conference on machine learning, pages 19773-19808. PMLR, 2022.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale scale image recognition. arXiv preprint arXivv 2014.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
Sen Wu, Hongyang Zhang, Gregory Valiant, and Christopher Ré. On the generalization effects of linear transformations data augmentation. In International Conference Machine Learning, pages 10410-10420. PMLR, 2020.
Jaejun Yoo. Namhyuk Ahn, and Kyung- Sohn. Rethinking data augmentation for image super- resolution: A comprehensive analysis and new strategy. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8375-8384, 2020.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of the IEEE/CVF international conference computer vision, pages 6023-6032, 2019.
12

---

Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz mixup: Beyond empirical risk minimization. arXiv preprint 17X..0171. 2017.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou, How does mixup help with robustness and generalization? arXiv preprint arXiv:2010.04819 2020.
Linjun Zhang, Zhun Deng. Kenji Kawaguchi, and James Zou. When and how mixup improves calibration. International Conference on Machine Learning, pages 26135-26160. PMLR, 2022.
Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data aug- mentation. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 13001-13008, 2020.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108. //37/, 2021.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. The benefits of mixup for feature learning. In International Conference Machine Learning, pages 43423 43479, PMLR, 2023.
13

---

Contents
Introduction
1.1
Our Contributions
1.2
Related Works
2
Problem Setting
2.1
Data Distribution
2.2
Neural Network Architecture
2.3
Training Methods
2.4
Assumptions on the Choice of Problem Parameters
3
Main Results
4
Overview of Analysis
4.1 Vanilla Training and Cutout Training
4.2 CutMix Training
5
Experiments
6
Conclusion
10
Additional Experimental Results
15
A.1 Experiments on CIFAR-10 Dataset
15
A.2 Additional Experimental Results on Our Data Distribution
19
B Proof Preliminaries
20
B.1 Properties of the Choice of Problem Parameters
20
B.2 Quantities at the Beginning
21
B.3 Feature Noise Decomposition
23
C Proof for ERM
29
C.1 Proof of Lemma B.3 for ERM
29
C.2 Proof of Theorem 3.1
30
Proof for Cutout
45
D.I Proof of Lemma B.3 for Cutout
45
D.2 Proof of Theorem 3.2
46
Proof for CutMix
62
E.1 Proof of Lemma B.3 for CutMix
62
E.2 Proof of Theorem 3.3
62
Technical Lemmas
75
14

---

A Additional Experimental Results
For all experiments described in this section and in Section 5, we use NVIDIA RTX A6000 GPUs.
A.1 Experiments CIFAR-10 Dataset
A.1.1 Experimental Support for Our Intuition
We compare three methods, ERM training, Cutout training, and CutMix training on CIFAR-10 classification. For ERM training, apply only random cropping and random horizontal flipping on train dataset. In comparison, for Cutout training and CutMix training, we additionally apply Cutout and CutMix, respectively, pixels of input images, and for CutMix training, we sample the mixing ratio from a beta distribution Beta(0.5, 0.5). We train ResNet- 18 (He al., 2016) for 200 epochs with batch size of 128 using SGD with a learning rate 0.1, momentum 0.9, and weight decay x 10 Trained models using ERM, Cutout, and CutMix achieve test accuracy 95.16%, 96.05%. and 96.29%, respectively.
training data. For Cutout training, we randomly cut 16 x 16
We randomly generate augmented data using CutMix from pairs of cat images and dog images in CIFAR-10 with varying mixing ratios À 1, 0.8, 0.6 (Dog:Cat = X : A). We randomly make 000 (cat, dot)-pairs in CIFAR-10 10 training set and apply CutMix randomly 10 times. By repeating this procedure 10 times, generate total 5, 000 x 10 x 10 500, 000 augmented samples for each mixing ratio A. We plot histogram of dog prediction output subtracted by cat prediction output (before applying the softmax function), evaluated 500, 000 augmented data in Figure 2.
0.40
ERM
ERM
ERM
5.35
0.35
CutMix
CutMix
CutMix
0.30
0.25
Frequecyy
0.25
Feqquncy
0.25
0.20
0.20
6.15
6.15
0.15
6.10
0.05
3.05
-3
Dog Output- Output
Dog Output-
Output
Cat Output
Figure 2: Histogram of dog prediction output subtracted by cat prediction output evaluated data points augmented by CutMix data using cat data and dog data with varying mixing ratio (Dog: Cat = A: - A) (Left) À 1, (Center) À 0.8, (Right) À 0.6
The lefumost plot represents the evaluation results for original dog images, as it uses a mixing ratio of 1. We can observe that the output of the model trained using Cutout is skewed toward higher values compared to the output of the model trained using other methods. We believe this aligns with the theoretical intuition that Cutout learns more information from the original image using augmented data.
The remaining two plots show the output for randomly augmented data using CutMix. We observe that the models trained with CutMix exhibit a shorter tail, supporting our intuition from the CutMix analysis that the models learn uniformly across all patches.
A.1.2 Experimental Support for Our Findings
We train ResNet-1e 18 using ERM training, Cutout training, and CutMix training following the same experimental details described in Appendix 1.1.1, except using only 10% of the training set. This data-hungry setting is intended highlight the benefits of Cutout and CutMix. We then evaluated the trained models on the remaining 90% of the CIFAR-10 10 training dataset. The reason for evaluating the remaining training dataset is to analyze the misclassified data using C-score (Jiang et al., 2021), which is publicly available only for the training dataset.
15

---

C-score measures the structural regularity of data, with lower values indicating examples that are more difficult to classify correctly. our framework, data with harder-to-learn features (corresponding to rarer features) would likely have lower C-scores. Since directly extracting and quantitatively evaluating features learned by the models is challenging. we use the C-score proxy to evaluate the misclassified data across models trained by ERM, Cutout, and CutMix.
Table illustrates that Cutout tends misclassify data with lower C-scores compared ERM, indicating that Cutout learns more hard-to-learn features than vanilla training. Furthermore, the data misclassified by CutMix has even lower C-scores than those misclassified by Cutout, suggesting that CutMix is effective at learning features that are the most challenging to classify. This observation aligns with our theoretical findings, demonstrating that CutMix captures even more difficult features compared to both ERM and Cutout.
Table I: Mean and quantiles of the C-score on misclassified data across models trained with ERM, Cutout, and CutMix. The results indicate that Cutout tends misclassify data with lower C-scores compared to ERM, while CutMix exhibits even lower C-scores.
Method
Mean
Q1
Q2
Q3
ERM
0.687
0.615
0.782
0.841
Cutout
0.679
0.599
0.775
0.837
CutMix
0.670
0.575
0.767
0,835
Since directly visualizing features learned by a model is challenging, we present data that were misclassified by the model trained with ERM but correctly classified by the model trained with Cutout instead. In Figure 3, we show 7 samples per class with the lowest C-scores, which are considered to have rare features. Similarly, but correctly classified by the model trained with CutMix to represent extremely rare data in Figure 4. This approach allows us interpret some (extremely) rare features in CIFAR- 10, such as frogs with unusual colors.
also visualize data misclassified by the model trained with Cutout
16

---

Cautre
ColDre:
Cosore 2.100
Coctre:
Coucre:
CaLoTE
Locan
C.
CAO0E 2/17
C:20ve 2002
Oxare 6355
CaMeRE 0.553
CoOoE 7750
Cacaee 1001
CScorc 005
Cacae 0.SE
CoLP 0.24
COLOTE 21.6
Cocoe: 1213
C- 0L25
COLATE E2553
C-em 0:125
C.00.600 6.13
C400 2013
L-50W0 100
C-W. CLECE
Conus 1.0
1-50W0 1.00
GarOn 0.6
Cacore 20021
1101
1332
TAM
Cazon:
Figure Examples of rare data in CIFAR-10
17

---

Caztee
Contre:
Casone
Coccre::
Cocore
Casore
Cocan
Coor 1037
G-lvv 2002
Colore 205t
Cocare 2052
USSRNC 015CK
Coure 6.71
Gyane 0.13
CAPE 0.52
COSOIE 70M
Cocane 1001
UXARI 010
S-0000 0.14
COLJI 6.40
C-won ELSTE
CODU 2.0
C-C 1000
Gssee 64)
C-5.W 2101
C AUSS
C-2.P 6335
113
126
Cacor 21M
0212
Cazon: 6:336
Figure 4: Examples of extreme data CIFAR-10
18

---

A.2 Additional Experimental Results on Our Data Distribution
In addition the results described in Section 5, we further conducted numerical experiments on our data distribution by applying two variations to our architecture: increasing the number of neurons, and increasing the number of neurons with a smoothed ReLU activation (instead of smoothed leaky ReLU). We observed the same trends as predicted by our theoretical findings and shown in Figure 1.
Let us describe the setting of experiments in detail. In both cases, We the number of patches P = 3, dimension = 2000, and the number of data n = 300. The feature vectors are given by the standard basis e1, Eg, e3, e4, e5, Eg E Rd where e1, e2: e3 are features for the positive label 1 and e4, e6, Eş are features for the negative label y = -1. We categorize e and e4 as common features, E2 and e; rare features, and lastly, e3 and eg as extremely rare features. We apply full-batch gradient descent with learning rate = and for Cutout and CutMix, we utilize all possible augmented data.
For the multi neuron with smoothed Leaky ReLU case (Figure 5), we use 10 neurons for each positive/negative output with the slope of negative regime / 0.1 and the length of polynomial regime r = We set the strength of dominant noise da = 0.25, the strength of background noise Tb = 0.12, and the strength of feature noise 0.05. In addition, frequencies of common features, rare features, and extremely rare features are set to 0.72, 0.15, and 0.03, respectively.
For the multi-neuron with smoothed ReLU case i.e., 3 polynomial regime as = 1, and we use neurons for each positive/negative output. We set the remaining problem parameters follows: the strength of dominant noise da 0.25, the strength of background noise σb 0.12, and the strength feature noise a = 0.05. In addition, frequencies of common features, rare features, and extremely rare features set to 0.75, 0.2, and 0.05, respectively.
(Figure 6), set the length of the
ERM
Cutout
Cutout
Extremely Rate Feature Outgut
0.8
Cutout
Comman Fasture Output
CutMix
CutMix
CutMix
Fare Feature Output
3.6
0.2
anbe
20:0
1060n
40h0 Iterations
ccnno
Iterations
Iterations
Figure 5: Multi-neuron with smoothed leaky ReLU actiation
ERM
ERM CutMix
ERM
Extremely Feature Output
8.
Commann Feature Output
CutMix
CutMix
Rare Feature Output
1.5
2.4
4-
2-
0.3
0-
0.0
0.0
6200
10000
6000
10000
Iterations
Figure 6: Multi-neuron with a smoothed ReLU
19

---

B Proof Preliminaries
B.1 Properties of the Choice of Problem Parameters
In our analysis, we consider the choice of problem parameters function of the dimension of patches d and consider sufficiently large d. Let us summarize the assumptions on the parameters for the problem setting and assume they hold.
Assumption B.1. The following conditions hold.
A1. (The number of patches) P P= ((1) and P 8.
A2. (Overparameterized regime): n = o aa o /po//ooollldd
A3. (Sufficient feature data): For all k [K], pun w (n' logd)
A4. (Common feature vs dominant noise): For all h: E Kc, Ph: = (11) and oîd o(3n).
A5. (Rare feature vs noise): For all KR. Pk = OppR) with pan = o afd = ((ppm))
and
A6. (Extremely rare feature vs background noise) For all l E K Ph O(pE) with Pgn oiddoppoyyloo//
A7. (Strength of feature noise)
A8. agold, o o (a/polylog(d)) //olyo/tt /polylog(d))
We now present properties derived from Assumption B.1, which frequently used throughout our proof.
From (A3), for all k E [K], we have the following inequality:
n 2 Pin 2 p = w (log² d)
(6)
From (A1) and (A2), and given that 8 < 1, < od, we have
d> (Bo o
2 )2 > n > nP.
(7)
From (A2), (A3), and (A6), and given that a, 3 < 1, we have
og > of w(pen) (1).
(8)
From (AI), (A2) and the fact that 0 < a we have
nP3 nP3- d =0 polylog(d)
= polylog(d)
(polylo((c)
1
(9)
From (A7) and (A4), we have
aB < <a3
polylog(d)
(polylog(d)
(10)
From (8) and (A8), 1) = o(1) and then we have
log(
n
(11)
2
From (A2), (A3), (A4), and (A5) have
a -2
oîd
= o (p = 0 (n+)) = o (dt)
(12)
PRT
20

---

B.2 Quantities at the Beginning
We characterize some quantities at the beginning of training.
Lemma B.2. Let Eisi the event such that all the following holds:
26 52
V1 |-11 -
27 52"
For each s [ and k E [K]. PAR <
Va,al I
3
uien (pt) [P]
For any s, E {+1} and & E [K]. ( (w: vor
, >1 - oo log d.
For any E [=1} and E [n]. K (w! (((ai) S gooado log d.
For any E {+1}, i E [n] and p E [P] (pi ( (w>" _<(i>\
- ooondh log d.
For any i,j E [n] with i + j. 2 ||] I L0gd and (c<(").(.))))
ozdd log d.
For any i,j E [n] and p [P] {p). (c/"). - aaondz logd d.
For any j E [n] and p E [P] \ /p E [P] \ (pz p5} with (i.p) + (1. e S ofdt logd.
jofd < | $ fo and (E.)) -
(U.AA)e(L1))AE(() U {2, (MM is linearty independent.
Then, the event Emnt occurs with probability least o (polylat) Also, if NN(0, is independent of w (0) =. and {(X;, Uı) hie we have
(w) 10) .PP.=.l.. (w -1 k s aood log d, and (E. sooad log d.
gogd't
for all all E [m] and p E [P] \ {pi}, with probability least 1 o
1
poly(at)
Proof of Lemma B.2. Let us prove the first three points hold with probability least o (poliaa)) By Höeffding's inequality,
M
n
n
=P
Σ
(1,,=1 - E (1)
>
n
2
52
52
iE[m)
2
< eexp
522
=0 (p)lydd)
where the last equality is due to (6). addition, for each {=1}, k E [K]. by Höeffding's inequality
P
Va,kl
Pk
n
4 n
=
Σ
(1iEvE. - -E(1ie
Pk
n
2
4
.E|m|
2 Pann
< 2 exp
= poly(d)
8
where the last equality is due to (6). Also, for each i [n]] and p E [P].
Pl(i E Ví,1 n (pj =
P1 p
21

---

Hence,
P Pluie,, (pi)
+ [PI] v
Σ
P
Nietul ((fi Vaae {pt = p})
ME[P]
[
P1
P
Pexp
S
(-p")
Pr
ph)
1
=0 poly(d)
Next, we will prove the remaining, Let us refer to the standard deviation of the Gaussian noise vector in p-th patch of i-th data as di.. In other words, for each E [n] and p E [P] \ {pt).
Ja if Pi. Oip = (o
otherwise.
For each s E {+1} and k E [K], ( w (0) vz ~ 2N(,, oo). Hence, by Höeffding's 's inequality, we have
( uo. > oo log d 2exp (- (_
loo log logd)²
(ap
) =o 1 -
(poly(a))
20
Let (uiteaa-2k) be Span(( (pan((aa)he(t))))eE (E(+))) Note that for each E {+1}, i E [n] and p E [P] \ (pt), we
orthonormal basis of the orthogonal
complement of
can write c(P) and & as
w. (, o0
Σ i <(²)
dip
Σ
(p) Ut {=o Σ z
IE [E[
LE|d-2K]
[E[U-2K]
where 2, 2,1
21
idd. N(O,1), The sub- satb-gaussinn norm of standard normal distribution NO0 1) is
Then
(p) 1
I's mean zero sub-exponential with sub-exponential norm 3o (Lemma 2.7.6
in Vershynin (2018)). In addition, Zz,1Z,1 s, 2 Z ' and z;, z/ 's are mean zero sub-exponential with sub-exponential norm less than or equal to (Lemma 2.7.7 Vershynin (2018)). We use Bernstein's 's inequality (Theorem 2 in Vershynin (2018)), with being the absolute constant stated therein. We then have the following:
(p)'s, (p) (a)
(p)
1 - P
3 2
d
SP
<
oi 2K)
2 o log d
(p) 2
=P
Σ
2
-1
2 d log d
[E|d-2K]
9cd log"
< 2exp
64(d - 2K)
9clog² d
< exxp
64
=
poly
in addition,
P [|( { 2 d logd
=
Σ
2,, 2
(p) (g)
2 dà logd d
[E[d-2K]
9cd log? dl
$ exxp
64(d 22)
9clog" d
< 2exp
64
poly(d)
22

---

Similarly, we have
P (oua)),..)))) 2 ppor log d 1 2 exp
(- 64
(- 9c d
))
=
(pol(()))
poly(d)
Lastly, the last result holds almost surely due to (7). Applying the union bound to all events, each of which is at most poly(d) due to (7), leads us to our first conclusion.
In addition, for each E {i1}, e [n] and E [P] \ {pt).
P
P[[ w0!
1000 ,,) 2 apod log d] s 2exp (- 9c logg""
4 =o
(pooyyat)
1
64
and
P [|(E (5) z od log logd| s 2xx
9c d'
64
poly(d)
Applying the union bound all events, each of which is most poly(d) due (7), leads to our second conclusion.
B.3 Feature Noise Decomposition
In our analysis, we use technique that analyzes the coefficients of linear combinations of feature and noise vectors. A similar technique in a different data and network setting is introduced by Cao et al. (2022).
Lemma B.3. If we run one of ERM, Cutout, and CutMix training to update parameters W of model Swi, then there exist coefficients (corresponding to each method) 7/8 (6) (s', ,,)''ss and (9 (i. p)
so that we can write W()) {w]] w 31 as
(8)
w =w +
Σ
7:00 (s, k)uokk
Σ
7o (-s
KE[K]
KE[K]
+
Σ
(t,p)
E
(i.
[c(p)
c(P)
iEV. iEV..E PIMMT
iEV. (EPP)(6))))
+ a
Σ VEF
syaPe (1.
Ua.1
+
syap (1,
U-
[
iEF
where F. denotes the set of indices of data with feature noise Us Furthermore, if we run one of
ERM and Cutout, the coefficients 7/8 (8', RY's and ps (1, p) 's are monotone increasing.
We provide proof of Lemma B.3 for ERM in Appendix C.I, for Cutout in Appendix D.1 and for CutMix in Appendix E.
Since Gaussian vectors in a high--dimensional regime are nearly orthogonal, we can use the coefficients to approximate the inner products or outputs of neurons. The following lemma quantifies the approximation error.
Lemma B.4. Suppose the event Emnt occurs and < 7/ ('', k).,
(4) (i. p) S 5(8-') (( for all s, s' {+1}, k E [K]. i E [n] and p E [P]) {pt } at iteration t. Then, for each E {+1}. h [K] [n],
and p [P] {pt }. the following holds:
W Ua,k) )
2 (s.
10 ((w!)) (1) . vs..)) - (0,
=
( W U v-
+ 10 (-s, k)) 1 (( (w!!) vx.x))))) )) + (-,,(()),))) = o (olylog(d)
((u_))__.)))) (1) (i.p) = (polylog(a)
Knole 151 Pgc
c(p)
(1) (1,1)
( 55 (
(w i s!
+ (9 (i, p)) 1/ (1 )) + "0 (1.p) = (olylog(a))
23

---

+0((uug) o ) (i,(i, (i. pi) . 10
( + "r. o (moniaz
Proof of Lemma B.4. For each (=1), E [K] \ {1), by (A8) and (8), we have
K Kmo50 vakk) 7/ (s, = (u! v3.k) ) -(oo) = polylog(d)
Similarly, by (A8) and (8).
K W (1) v- + 76 (-s, k) = (10!0) v.s.k) > = -((o))= ( (
(ollylo(())
Next, we will consider the case of 11, and 1-1.1. For each E {+1}, we have
w Us - -/ (s. 1)
!0 (0) U/,1 t E
(c.
iE|n]
Ö(an) + Ō (am3- od 2d=1
(olyyoo(d)
where the last equality is due to (8) and (A7). Similarly, we have
+ 7 (-8,1)
< w 00) e v=a.) )/ + a Σ
p50 (i) [2(ai)
xE(m]
Ō(o)) + θ (amp-1oa 21
(polylog())
Hence, from (A8) and the fact that lo(()) 2| S [1-8)r for any 2 2 0, we have
Φ (()) Us.k) - (s, k)
( (t) 1s ) @ (s5 (s, 1b)
+ 10: (3.%(1))) (s.
(1))) 11 mask) ) - 70, k3) + (1- 3)r
(olyyoo(d)
and
| (ww ((u)"))_a..))) +
= ② (( (u((t))_sst ..)))))) - o (-150) (-s,
s, k))
w v-..)) ) + 1600 k))
<
1
(polyoo(d)
For each i E [ni,, and p E [P] \ {pt}. we have
(E c(9))
( (uu(),_("))
of) (i.p) < ( (w (u(".cc.)) ..(i))
Σ
19 (..g) q)
||s500 ||
JEIM] (1.))
24

---

S Ö oooadi
+ InP9-loao, d
polylog(d)
where the last equality is due (A8) and (9). By triangular inequality, (A8), and the fact that ø' S
and [δ(2) - 2|
(1- for any 2 2 0, we have
2
w (6) (p) )) (i.P))
1
(() )) @ (1/2 (c. + +1/00 (1)) - (12((.)))
15
w (t) c(p) ) (1. (i. p) + (1 - 3)r
2
polylog(d)
Also, i E Fg for some E (+1}.
1
w
(p.)
(1.
w
(P:)
(i.
Φ ( (u/h) ,t (e(iai))
((
w (1) (
(i,p.)
(1 Us.1
((
(wnf)
(1
(1.
(1) 1) a.
1 polyyog(d)
1
0 (a.8-1) +o polylog(d)
polylog(d)
where apply the triangular inequality, the fact that Ø' S 1, the triangular inequality again, ( (s, 1) = ((31) and (10) sequentially.
Similarly,
(550) -5/0)
K (1 (1)
(1) E(01) -( + p- (1.p) s -00.s())))
s(>i\{+
Σ
|$5)0
VEP) (1.))
s Ō(oooad ) (ō + (nap5 d
=0 (polylog(a))
and
( (1o0 + 3p (2) (i.P)
= ( w (1. <((i))) )) - o (-P2)
vn c(P)) + 0²) (1,p)
-
1
o (polylo(d)))
Also, i E F, for some s E {+1}.
(( w -y. , (B.)) zz
(t)
+ "p (i.p.)
④ ((w=)), c/ c(pi)) )) + ",,
(1.
+ 16b ((w2))
x (())))
(w c(ai))
25

---

c((i)) ) + -. (i.p.)
+ u v vo.1)
0
(
w 2. ((+))) ) + Bp (1.
+ + 00 (8, 1) + a.
(polyoogdd)
(aB-1) +
polylog(d)
1 polylog(d)
We define the set W as the collection of W = {wi,, w-1), where wi - wi , w are
elements of the subspace spanned by ((=)) U (()))
seini PEPP)M)))))) The follow- ing lemma guarantees the unique expression of any W E W in the form of the feature noise decomposition.
Lemma B.5, Suppose the event Emnt occurs. For each element W {wi, w-1 E W, there exist unique coefficients Yo(s', ,k)'s 's and poli.p) such that
W. = 3 (0)
(8,8, k)Ms,k
Σ
k
kE[K]
<(M))
E
Poli.p)
Σ
Pali.p)
(p)
((())
iEV PE|P
+ a
Σ IEF
st
Us.1
(i,
1-
((0h)
IEF
for each s {+1}. Using this fact, for each s* E {+1} and k E [K], we can introduce a function Q(+*k") WW + gdx2 such that for each W = (w1, w-1} E W.
Q (W) { 0 x (w,1)) ((w))((w_)))))
given by:
c(())
(((""))(( (w.) = -ss ros",, (ooss","""""" J0 + 3s
=ss"
Σ
poli,p)
[((p)]
KEV. w- PE(P
+
88 po(,
Ug.1
Σ
88" ps
V- s.1
((.))
((()))
iEFANV
iEF-An
The function Qi+" plays crucial role in Section C.2.4 and Section D.2.4. The key intuition
behind our definition of Q(=",*" is that Q(s**))(W(()) represents the term updated by the data having the feature vector U. where W(() are the iterates of either ERM or Cutout. As expected
from this intuition, if sum all Q k*) (w)) and Q' (==")))) (w_,) over all s* E {+1} and k- [K].
the result will be equal to wi w (0) and w-1 w respectively.
(0)
Proof. From linear independency of (u of [a(") sE(n))e(())))))
we can express
any element W (wi, w-1) E W
Wy = (0 + Σ
(8, k))
Σ
7s(-8, k.
kE[K]
kE[K]
26

---

5
5
Σ Po(t.p)
Σ Pali,p)
(13)
<(P))
c(T))
VEV
iEV-A. (E(P)
PE[PIM(P2>
with unique (5.(5, (e) and (pa Dett Ta(s, k) and 7x(-5, as 7s(5,, k) = (s,5, 7s(-s,)) = (- k) for ks o 1, and
If we define
(1,,1))(((8)) 1)
Σ
SyaP, (f. 81) ||
iEF
76(-s,1) = (-s,,,1) +
Σ
sy:ps (y.po(i.bi) ||/000|
then we have
w, w (0) + Σ
ko(s,
Σ
Tal ko)-s
kE[K]
kE[K]
c(P)
Σ ps(i.p)
Σ
ps(1,p)
|,,0000
EV PE(PINEP
LV DE(P))(AT)
+ Σ
(1,
Vs.1 [<(
Σ iEF-
v-
||s:
IEF.
Next, we want to show the uniqueness part. Suppose (7,(8, k), (o(- 8, b0 (en satisfies = w,
and
w.
: + Σ
is k)vak
Σ
k)(-s,
kE[K]
kE[K]
<(D)
Σ Poli.p) 5,00)
Σ po(i,p)
c(P)
||/001
EEV PE(PIN(EE)
SEV_ PE(P]MPi>>
+ a
Σ
(1,
UnA1
Σ
sy:Po(t,
v-
(((8)) 2
ieF
iET
We have
W. !! +
Σ
del 8, k,
kE(K]|(1
KE(K]M(3
(u. (b) ||.
(s, +
Us.1
iEF
(o(-s,1) 1) - a si. |cs.ai||1 U-a.1
iET-.
(
Σ Ps(i.p)
Σ
Poli,p)
||s,1)) |p
iev.
iEV.. DE(PIVER
PE|P|MP:T
From the uniqueness of (13), we have
1. = (s, k) = [s((s,))
5-(-8, k) = (,)-- = -75 ki),
for each s E {+1]} lo E [K]] \ [1]. and ps(i.p) (t((.p) for each i E [n].p E [P] \ {pt). Furthermore,
(s, + Σ (t. pb) { |
7o(s, 1) = (s. 1) + a Σ
syap. (t) ieF
[c.00) -2
iEF,
27

---

and
1)--s,1--a a
sy;u, (i, Pi) B || = --(ss, 1) = 77(--s11-0 1)-
Σ
syaps Pi)
|
KEF
IEF
Hence, we obtain the uniqueness of the expression and ((=*.*))) is well defined for each S E {+1} and h E [K].
28

---

C Proof for ERM
In this section, we use 9;
(t)
(x) for each data and iteration é, for simplicity.
C.1 Proof of Lemma B.3 for ERM
For 8 E {+1} and iterate
w (1+1 w!!")
V,,, w. LERM (W(C))
7
(1)
Σ 0' ((w)))
(0,0,,)))) ) x
syigi
n1 EE(m]
pE!P!
7
(1)
Σ
ø (wof
((w!")
, (p) 2 )
E
(1) Σ
8' ((ws).x4) ) z!!²)
9i
9i
n
iEV.
PE(PI
iEV_x
pE[P]
and we have
Σ
Σ
o' ((a])),..'))) x
.EV.
PE[P]
Σ
Σ
9. 0' (ww!0) Uo.k Us + Σ 9
E 8' ((wS0).500) )
KE[K] iEV
iEV.
PE(MIMMT
+ Σ
0 (mm!), ,
0,,,,11 + ) (1vs,1 + c!
kEV,nF
Σ NEV,NE
9 00 ((w!) 0v__,1 1 + )(ai))) (av_a1+ + (((())
and
Σ
(0)
Σ
8' (ww ((w(() xe(")) (n)
iEV
PE[P]
Σ
Σ
Ji & (105),0aa))) 1 U- + Σ (0
(1)
Σ
o ((10S?, ((0)) c.
KE[K] iEV-A,k
iEV_
PElPIMeR
Σ
gi 10 ((w)))
(t) ,oUg,1 + { (ovs.1 + c!au))
V.
Σ FF-
Ki (1)
06 ((wf),a0-..
aro_., + <(aii)) (av_..1 + =((ii)
Hence, if we define
(1) (s', k)'s and ps 1 (i. p)'s recursively by using the rule 7 (())) k) - (00, k)
7
Σ
9h 2
(oof),orr))))
(14)
VEV.
p: (t.p) (i.p) + 9. 19
Φ' ((w(),,(())) (5/0)) ?
(15)
starting from 7s then we have
(0)
(s', k) = ps (i.p) = 0 for each s, E {+1], E [K] [m] and p E [pt)
(0)
w!(
(0) + Σ
(s, Σ
(-s k))
kE[K]
KE[K]
!!-)
(i. (
+
Σ
(i,p)
Σ
|
c(p) 2
iEV PEIPPE
iEV PE(P)Met
29

---

+a
Σ iEF.
(
Σ
syap?" (i,
v-01
(((
|
iEF-
for each E (+13. Furthermore, 7'8 (+) (s', k)'s and pb (i.p)'s i are monotone increasing.
C.2 Proof of Theorem 3.1
To show Theorem 3.1, we present structured proof comprising the following five steps:
1. Establish upper bounds on 7 (s', k)'s and p (i. p)'s to apply Lemma B.4 (Section C.2.1).
2. Demonstrate that the model learns common features quickly (Section C.2.2).
3. Show that the model overfits dominant noise in (extremely) rare data instead of learning its feature (Section C.2.3).
4. Confirm the persistence of this tendency until T iterates (Section C.2.4).
5. Characterize train accuracy and test accuracy (Section C.2.5).
C.2.1 Bounds on the Coefficients in Feature Noise Decomposition
The following lemma provides upper bounds on Lemma B.3 during T" iterations.
Lemma C.1. Suppose the event Eiit occurs. For any E [0, we have
(t) (i.p) S 4log (n)T*, 0 S (s, k) + By (s, < 4log(") 0 0 Pg. (i.p) + 3p
for all [#1], k i [n] and [P] (pt). Consequently. ( (s/,k), Ps (i.p) 0(3-1) for all 8,8' E {++), k [K], i E [n] and p E [P] (pt).
Proof of Lemma C.I. The first argument implies the second argument since log(n)"") polylog(d) and
1h (3' k) S 8- (7 1/ (s), (d.)())))) (i.p)) (pl (p 3p (i.
for all s' E {+1}, E [K], E [n] and [PI {
We will prove this by using induction t. The initial case t 0 is trivial. Suppose the given statement holds at t = T and consider the case t = T 1.
Let T..k S T denote the smallest iteration where 7/ (f..+1) (s, k) + BY (t. (s. > 2 llo((n We assume the existence of T.kk, its absence would directly lead desired conclusion; why, note that the following holds, due to (14) and (11):
7. (T+)) 1:) 3- (s, k)
(T+1)
- + _
(T) (s, k) + 7 Σ
aiTh)
(
+ 30/ v ((w2H,bat))
VEV.
<2log(n(l") 21 4log(T1"))
Now suppose there exists such T,,k S T. By (14), we have
2 (T+1) (s, k) + ( (s,
7s (s, + 3, (t..)) ks
(1
(20())) (s, k) + 13 (1+1) (s, 2(0 (s, (s.
E
<2log(n + log(1)T"))
Σ
Σ
Di
(1)
Φ' ((10)), BBb ((1022) v., 0xx))
t= +1 +1 VEV.,
30

---

The inequality is due to 7ss (T.b) ( k) + B7-0 (a (s (s, s log(n) from our choice T2 and
"
Σ
Φ ((105 (Tr))) maxh) 3 ((ao mass)) s 2n I log(n)T)) (To,))
9i
VEV..
from (11).
For each & Top + I,.., and E Va, we have
HalwooXX
= Φ ((110/ -uskk)))))) ((10=a
E
(<((wo)).a2)) -qt))) @ ((w22
pE(P)((t))
(s, + (s,
E
(pL)(t.) 3p - -2P
polylog(d)
PE(P]((T))
3 2
log(n?"))
The first inequality is due to Lemma B.4 and the second inequality holds due to (A7), (8), and our choice of I, 7/ (s, k) + 3, k) 2 log(r?7")
Hence, we obtain
T
Σ
(1) g:
(8) (((11))), vorx) + 30' ((w02) volk)
Tu.k VEVA
27
exp 1ap(--yifee (-yffwro) (X,))
t=Tu.k iEV..k
2/
(11T** exp
exxp) (-2 log(1((*)
3
n
2
log((1""),
VITT"
where the last inequality holds for any reasonably large T*. Merging all inequalities together, we have 7/ (T+1)) (s,
(> (s,k) k) < 4 log(n1"")
Next, we will follow similar arguments to show that
Py. (T+1)(i.p) + Bp v
(T+)) (i.p) 4log(1
for each E [n] and E [P]
Let 7((x) < T be the smallest iteration such that Pr.
(1 +1) (i,p) + 3p-j.
(T!2) +1) (2.p) > 2 llo(Tn
We assume the existence of (T(()) as its absence would directly lead to our desired conclusion; to see why, note that the following holds, due (15) and (11):
PM (T+)) + 3p (T+1) (i,p)
=p (T) + Bp _p (i.p) + 9
(T)
0 ((wo)),a{)))
36 ((wo)),
|<
n
< 22log(nI") + 2n 4 \log(1I"")
where the first inequality is due to (())
< 2 3o and (A4), and the last inequality is due to (11).
Now suppose there exists such [:()]
T. By (15), have
(i+)) py
3p (i.p)
(T+))
31

---

(1
(1.00)
(1,p) + 3p- (t.p)
Pt
(i + 3p- 2 (i.p) - (i.p) Bp (i.p))
< 2 log(nI") + log(ni
T
(1)
Φ ((we - + B06 ((w0? xc! 2e)))) ||s
+
9i
t= T
+1
The inequality is due to py: (i.p) + Bp- (i. S 210 from our choice of T:(0) and
(T(m)
(I(11)
n 93 0'
"
(
((1m (p(())
w x
(p) )
+ B6' (( (w (T())) (1))
| S 2n I log(n?"))
from
5:
S oo (A4), and (11).
For each
t -((P) 1, T, if E Va,ks then have
yifw()) (Xi)
= (( (wo x (e(")) 2 (1w0 ae("))
Σ
(o (ull)aa()))) -o ((=")..a.))))
(E(PM(p)
2 2 (i.p) + 3p (i. p) + (1, + 37 ", (s)
Σ
(i.g)
() + + (1. (1.)) 2P
+
polylog(d)
(E(P))
3
2 2
log(
The first incquality is due to Lemma B.4 and the second inequality holds because from our choice of 1
t, Pi (i.p) + 3p v. (i. 2 2 log(?"
Therefore, have
n
Σ
(1) (o'
((10/) ((w))))a((())))) 3Ql ((w0"),, 20
|<
Ji
n
3 exp (-y-fwrii (X.)) S (nTT** exp (-2 log( (og()
Σ
17
+1
S log(n)7"),
V1TT
where the first inequality is due to reasonably large T*. Merging all inequalities together, we conclude Py: (i.p) + " S
(<())
2
< Lo.. (A4) and the last inequality holds for any
4 (log(1]"*)
C.2.2 Learning Common Features
In the initial stages of training, the model quickly learns common features while exhibiting minimal overfitting to Gaussian noise.
First, we establish lower bounds on the number of iterations ensuring that noise coefficients ps (i.p) remain small, up to the order of +.
Lemma C.2. Suppose the event Emnt occurs. There exists T > enPoza such that pa (i,p) S 4P
n
for all 0 < t < T, E ( [n] and p [P] \ {p
32

---

Proof of Lemma C.2. Let T be the smallest iteration such that ps p 2 TP for some {+1},iE E [n] and p E [P] {p We assume the existence of T. as its absence would directly lead to our conclusion. Then, for any 0 S < T, we have
0 (i.p) P (i.p)
+
7 0 ((w)")) x 2.) | S p (i,p)
3no 2n
n
< 1. ø < 1, and (( 2
where the inequality is due to g
s oz Hence, we have
1
P8 (1.P)
Σ
Ps (1tt)) (1.P)
3noodd
T,
4P
2n
and conclude T onPoad which is the desired result.
Next, we will show that the model learns common features in at least constant order within T iterates. Lemma C.3. Suppose the event Emnt occurs and Pk = w
a3d Bn
for some k E [K]. Then, for each
8 E {+1], there exists Te,k S
9n 1/.V, such that (1) (s, k:) + (s, 2 for any t Ta, (s,
Proof of Lemma C.3. Suppose 75 (s, + Br k) < 1 for all 0 S S on For each
i Ve,., we have
y.fwoo (X:)
(0) .us..) ( - 1 ((w0") usse)) +
E
(0((1s). ((ul),a(oo))) .q(i)) - b -(((((..
pE(PI((Ft)
$ (s, + (s,
E
(1) Sp + +P
polylog(d)
pE(P)((
1 polylog(d)
$1+2P.
+ +PP
4P
2.
The first inequality is due to Lemma B.4, the second inequality holds since we can apply Lemma C.2, and the last inequality is due to (A1). Thus, st 1+oxp(Mifyrte (x.))
and we have
(s.k) + 33
((+1) ( ks)
= (s,k) - 3y k) + Σ d:ah ((w!)) + 36' ((w v.,))
iEV..
n VaAal
2 2 + (s, +
9n
Notice that VV.ul Pan. From the condition in the lemma statement, we have ")3/,..k
If we choose to
9n no 6n/Pajd
then
BnPoad
37 On
1 (to) (s, k)) + 3y (1o) (8,k)
1 1>
40 2 1,
and this is contradictory; therefore, it cannot hold that 7100
10) (s. k) + (s, k)) < 1 for all 0 StS
PnPaza- Hence, there exists 0 < Tek < n and choose the smallest one. Then we obtain
enPaza such that 7/ (Tex (s, k) + 3T 3 (T. (s, 21
(T..x) ks k) + Sht (s)
n
1> 7s
Tek
9n
Therefore, T.k < 2
9n and this is what we desired.
33

---

What We Have So Far. For any common feature V.S with {=1} and & Kc. it satisfies Pk: add
due to (A4). By Lemma C.3, at any iterate t E [T..T*] with T2 == max. (+ AEEo Ta,k the following properties hold if the event Einit occurs:
(Learn common features): For any $ E {=1) and k E Kc,
(s, k) By [2 (s, 2(11) For any E {#1}, E [n], and p [P] \ 25 (i.p) δ (
C.2.3 Overfitting (extremely) Rare Data
In the previous step, we have shown that common data can be well-classifed by learning common features. In this step, we will show that the model correctly classifies (extremely) rare data by overfitting dominant noise instead of learning its features.
We first introduce lower bounds on the number of iterates such that feature coefficients (2) (s', A) remain small, up to the order of a 2² This lemma holds for any kind of features, but we will focus on (extremely) rare features. This does not contradict the results from Section C.2.2 for common features since the upper bound on the number of iterations Lemma C.3 is larger than the lower bound on the number of iterations in this lemma.
Lemma C.4. Suppose the event Eint occurs. For each E {=1} and l [K]. there exists Te.k
na² such that 7 (s, k) S -223-1 for any S < Te,k and {+1).
Proof of Lemma C.4. Let Ts be the smallest iterate such that 7 s' E {+1]. We assume the existence of Te.ks its absence would directly lead our conclusion. For any 0 E Tskk.
(s, (s, a2 for some
(1-1) 1) (s, k:) = -00 (s, k)) +
(0)
7 Σ
10
( s 25. + 1/ Va.el
Di
72
n
LEV.
and we have
P,
a²3-1
7 (s.
Σ
(s.
7///,. ( (s,k)
Tok
n
t=
We conclude T.
no my V.
which is the desired result.
Next, will show that the model overfits (extremely) rare data by memorizing dominant noise patches in least constant order within T. iterates.
Lemma C.5. Suppose the event Emit occurs and Pk = a²aad
Then, for each i Va,k there
exists T: E Th
18n n80fd
such that
Σ
+ 21,
PE(PIMEP
for any t Th.
Proof of Lemma C.5. Suppose EpE(P + < for Sts
na²
From Lemma B.4 and Lemma C.4, we have
yifwoo (X,)
34

---

= .u.k) )) 2
- (()) +
E (0((wSP.af0)) ,c(oa) o ((wo
PELPIM(F3)
+ (s))+ (s,
E
(p!)(i.)) ( (p + +2p
(posylog(a))
$ (1+ (1+33)a² +1+2P.
polylog(d)
2,
where the last inequality is due to (10). Thus, we have Di (1)
(xxp((iiw(ts) (x:)) 2 g. Also,
P (1. (i) + 100pp"""iiii0 (i.
(( (0 + BD ((20"2200()))) ) |
+ -. +
=
9i
Φ
n
3
2 (1,p. + (1.0))
18n
where the last inequality is due to
(((aa)
2 j and øl 2 3.
Notice that [Va Pkn.
From the given condition in the lemma statement, we have nBagd
no?
we choose to E
na² n n
then have
no Vo,al
Boadd 18n to 2 1.
Σ
(1
+ (t.p) 2 p. (i. + 3p (50 (i.p.) 2
This is a contradiction; therefore it cannot hold that EpE(P))o)) (1% (i, + 3p (1)
(t.p)
for all 0 I S na²
" Hence, we can choose the smallest S T, < n Ve.kl
aa²
such that
Epe(P)(B))
ps ( (i,p)
(i.P)) 2
For any 0 S < Ti
3 Tú
12 Σ
+ 3p (T.) (1.))
(i.p) 2 p. (i.p)) + + (1,p))
18n
pE(P)\EE))
and we conclude that T, S
18n nB8dd
Lastly, we move on to prove T; > Tí. Combining Lemma C.2 and Lemma C.3 leads
Σ
0 (T:) + (i.P) < 2
Thus, we have T, > T3 and this is what we desired.
What We Have So Far. For any E KR Kg. it satisfies Pk ( (a'o3d)
due (A5). By
Lemma C.5 at iterate & [TERM, T*] with
TERM
max
Ti E [
(E(+)) iEV., kEKRUKg
the following properties hold if the event Emni occurs:
(Learn common features): For {+1) and k Kc.
2/ (s, + (2,)) 2(1),
35

---

(Overfit (extremely) rare data): For any SE {=1}, h KR U KE, and i E Va.k-
(i.P) (o = 9((1,
PE|PIMPp)
(Do not learn (extremely) rare features at TERM): For any s, {+1} and & E KR KE. (Tams))
Y (s, k) $ a²
* For any E {=1}, e [n], and [P] (p/). p ( 3 (8-1).
C.2.4 ERM cannot Learn (extremely) Rare Features Within Polynomial Times
In this step, we will show that ERM cannot learn (extremely) rare features within the maximum admissible iterations T = poly(d)
From now on, we fix any 8 E {+1} and k* & KR U KE. Recall that we defined the set W and the function Q ((a",,) x²) : W - Rdx2 in Lemma B.5. Let us omit superscripts for simplicity. For each iteration t, Q(W()) represents the cumulative updates contributed by data points with feature vector .. A until t-th iteration. We will sequentially introduce several technical lemmas and by combining these lemmas, quantify update by data with feature vector Uz- after TERM and derive conclusion.
Let us define W (wi, w= where
w = w (TERM)
(BB))
IEV,
2n for each s E {+1} with M = 48-1 log
Note that (12). B < 1, and T poly(d)
together
a²
"
imply M O (3-1). Note that W(t), W E for any 2 Lemma C.6. Suppose the event Finit occurs. Then,
||e (Wilhass)) Q(W $ 12M s0
where || denotes the Frobenius norm.
Proof of Lemma C.6. For each {+1};
8s" (2s (w,) Qu w (TERAr)
((:))
Q2
8s* M
c((u))
tEV...u
M Σ
+ aM
U=
v 1=o
((()))
VEF.NV x
c
c(8))
IEF sv c
(((:))
and we have
||0 w (W(Teem))) (
= -1(0((w))- -Qi u
(Q-1(w=,)) Q-1 (w (w (muns)) ||²
(E(ON) {/(3:)
S 2
Σ
(
-2
+
Σ
((aii) ||
SEV
ijjvv SeeV,,.eo
36

---

2
+ 2M2
a²
Σ
|
+
Σ
iE
From the event Emit defined in Lemma B.2 and (A2), we have
Ksth .59 .
Σ
Σ
(
2 0
d
(: (.
1|2 ||$5
sEVo-,6*
JEV.-,
Σ
ndt }
$EV,-,
2
iEV
In addition, we have
2
2
a²
Σ
55
2
+ a²
Σ
(
-2
iEF-onVs-,t*
Σ
(B.)
+
E
Si
iEF.NV
iEF iEF-aNV x-
2
-2
Σ
Σ
iEFUNDAT
IEF .
Σ V
[b:)) 2
where the first inequality is due to and the second inequality is due to Σier, x 2/V.' se 10 2d-1 from (A5). Hence, from Emit we obtain
10 (W(TTER)))) - -(( s 6M²
Σ
<: [(
S 12 2d
iEV.-..
Lemma C.7. Suppose the Emit occurs. For any t 2 TERM and i E V R., it holds that
M3
(x.).((W')) 2 2
Proof of Lemma C.7. We have
(yi V w Swiee (X:), (X.), Q(W"))
Σ 0' w (" ( )) (Q.- (w.)), (o)) o' ((=")...()))) (2- (w" (. ) )
(1)
PE[P]
For any 8 E {+1) and p E [P] (11
ss" (Q)(w))) )
(5! c.a))
5 -. {(.)))
= p (TRRM) (i,p) +
Σ
p (TRMs) (j.g) g)
M
2 [(9) ||²
| ||² 1
jEV.,,u- ( (1.))(()p))
JEV
37

---

- nnP o00% 1 - - ((Monno'd d
(16)
polylog(d)
where the last equality is due (9) and M 0(8-)). Also, for any s {+1}.
88* (Qx( us x-) % (TERM)) (s ,k* 2 O. In addition,
(o((w)) x; (B.))
88"
= ss' (o(w)), c((i))
+ ss" (Qo xx; (1.)) - s!0i1)
2 ss" (Q((w)), e(hh))
Ö (a 2 Pk Px-no 2
(())) .c00)
M p
(TRM)) (i,p.) +
@oTERRe (j.9)
|
JEV A" PP (1.6)
(
Σ
M
δ (a 3 Pk- Dg-noo 2d
|s001|
, ((1}
2 M 0
nPp
"aapp nPP3-1a00p -
3 (a²B-) pk- no 00228-pp-noo 2d 1
M
polylog(d)
M
(17)
2
where the first inequality is due to the definition of Q and the second-to tast line is due to (9) and (A7).
Hence, applying (16) and (17) for s", -s* and combining with ø' 2 B, we have
(ponyl
1
MB
Ww/wos/ (X.,,((W)) 2 M3 o (polylog(d)
2
By combining Lemma C.6 and Lemma C.7, we can obtain the following result. Lemma C.8. Suppose the event Eint occurs.
Σ Σ
(ynSwwo (X:) S 0 (W(TERR))) Q(W:))| + +21T 148
TERM iEV..,."
where ||-I] denotes the Frobenius norm.
Proof of Lemma C.8. Note that for any TERM St < T
@ (witt))== =Q (Witt)
" V
Σ
e (X,))
n
SEV..
and thus
(wrctt) - Q @(w>)| | (1Q
2n Vw
Σ ((Wnwo((i))) Q (w - QQw))) n²
172
Vw
Σ
((urwwo(Xi))
veV
38

---

21
Vw
Σ
(x))) Q (wilt)
21
Vw Σ r
(Xi)) (x))
e e ( (Xi))
n
Vw
E
K(nfwio(Xi)) (wilt)
M MB
Σ
((yfwwo(X)))
1/2 n2
Vw
E
Clufwiro (x.))
AEV..,K
VEV
where the last inequality is due to Lemma C.7. By the chain rule, we have
Vw
Σ
((n.wos(X.))
(wrl))
.EV..,.'
Σ
ø' (m (o.. aa!") of ((w2)) an{")) (o (w .z!") )
PE|P]
For each s E {+l]i E ,r, and p E [P] (p)
w (t)
xx
Q+ (w!")) 20!11))
( (w! Qs (u()) 2x
(p))
c/
Σ
(p)
x
[(9)
VElnIVVee (E(P(MpF) AEPPMMMM
+
Σ
o (I.)))
-
11 20 (i
jEANVEr
1//301 | (011,,
Σ
to
JEF_IlVo.
2 nPs nPP3-
ooop d + H (228-~no0 2d-1)
polylog(d))
where the last inequality is due to Lemma C. and the event Einit By Lemma F.I,
Σ
(( (w x0"",,"")))
x0!" )) (Q.- (w!)) ,,?)),)?)))) - 0' (ww"r..a aa")) (o-.- (w!)) x..") ((())
PE[P]
Σ PE[M
④ w ((w!)) (x."i) - o (wo 20 ((==),,)(()))) .(.))))))
+ r
+r +o (polylog(d)
= v: Jw (X,) +
polylog(d)
where the last equality is due to r r (potytogcc)) ). Therefore, we have
(((()))) - (w - (w((cttt)) - Q(("))"
39

---

2m
E
l' (x.l (ufwrco())) (X.) +o
polylog(d) )
1
MB
n
2
|2
V
Σ
Eyyilwio (Xi)
n
21
((xn (ufwro(X)) MB
Σ
1
Vw
((uifri (Xi))
n
iEVO-,
From the convexity of ((-),
MB
M
Σ
(ynswwo (Xi)) (iifwies
2 Σ
4
iE
iEV, de
Σ
(iliwo(X.))
VEV
In addition, by Lemma F.2,
2
r
811² p2 22022 V..
V Σ
(1ifwwo(Xi))
Σ
E(yefwoo (X.))
n
n²
iEV
iEV.
7
(yrswco (X:)),
VEV
where the last inequality is due to (A8), and we have
@ (w()))
( -
Q(wr)))
- -110 -
7 Σ ((u.wwn(X.)) 2ne
n iEV.
From telescoping summation, we have
7
Σ Σ
((ifwi((x)) s ( Q (wr))l² + 2n MB
4
T iEV
Finally, we can prove that the model cannot learn (extremely) rare features within T iterations.
Lemma C.9. Suppose the event Emnt occurs. For any T E [TERM, T*), we have (s" δ (a223-2) 2 for each E {=1}.
Proof of Lemma C.9. For any T E [TERM, T*}, we have
T-1
((T) k) = = (TERM) (s", ",,,,," 1²)² + ?
Σ
n
TERM iEV
T-1
I o (TEnce)) (s",;")
7
Σ
10
9
n
t= -TERM iEV
40

---

T-1
(TTM)) S 7s
(s", ,K*)
Σ
e (yifwoo (Xi)),
TERM SEV
where the first inequality due o' I and the second inequality is due to -0- S f. From the result of Section C.2.3 we know 7/s
(Fram)) (s" k²) S 2- Additionally, by Lemma C.8 and Lemma C.6,
we have
(T-1) Σ T=TERM iEV.
Σ
Σ
E
e (VhSurco (X;))
TERM VEV..,.
< Q (W
- Q(W*)) + 21/7 e- MB
I 12 ,e 2ap2d + 217T
MB
Ö (=²
The last line is due (A5) and our choice M -,- log (2
Thus, we have our conclusion.
What We Have So Far.
Suppose the event Eini occurs. For any E [TERM, T*), we have (Learn common features): For each E {+1) and k Kc.
(4) (s, k) + By 12 (s, k:) = 2(1).
(Overfit (extremely) rare data): For each { k E KR UK and i E Va,.
Σ (1.p) _t 2(1).
PE|PTMPTT
(Cannot learn (extremely) rare features): For each & E {+1} and kt E Kn U Krg,
(s, k), (", k) (a (a²3-2)
For any E (+1), E [n], and [P]
(pt) 2 (1.p) = 5 (8-1).
C.2.5 Train and Test Accuracy
In this step, we will prove that the model trained by ERM has perfect training accuracy but has near-random guesses on (extremely) rare data.
For any Va,a with {#1} and k Ke, by Lemma B.4, have
ViSwio (X:)
Σ
1 w (1(10)) (0(0,a(())))) (1())) ((o_))a(()))))
PE[P
2 (s, k) +
(t) (,,
Σ
(pL((t)))+ +.0=))))0 2P
1
polylog(d)
pE(P)((77
2 (s,k) + (s,
polylog(d)
2(11 polylog(d)
> 0,
for any & [TERM, T. addition, for any E Val. with {+1) and & KR U Kg, we have y.fwoo(X)
41

---

Σ
0 ((107))) 2 0 ((=")
pElPi
( k)) + By (s,
Σ
(1.0 3p + 2P (polylog(d))
1
PEtMi(A7
E
(1.p) + 8p (t.pp)
polylog(d)
pE(P)
2(1 polylog(d)
0,
for any E [TERM, T. We can conclude that ERM with E [TERM, T*] iterates achieve perfect training accuracy.
be test data with X (zx1), .(P)) E RdxP having feature patch index p", dominant noise patch index p. and feature vector ky We have (p()) ~ N(0 of ) for each p E [P] \\ {,=,, and xx -00,,1 ~ A)) for some E {+1}. Therefore, for all E [TERM, T*] and p E [P] {p",p).
Next, let us move on to the test accuracy part. Let (X,y) ,)
④ ( wi (1) )
1
w (t) w 11, 20())
(E
w1 (0) w (0) x0(0)) >
Σ
(1, -((,)0)-09(110
||s0oa|
iE(m), (((m)_)E(P)\(o))
+ + +0(pppp
o0o d=
-
(18)
polylog(d)
with probability at least 1 - 0 (poly(a)) ) s' E {+1}, we have
due to Lemma B.2, (A8), (8), and (9). In addition, for any
w // (P) - ava.1)
P (i. ((/9)) (0))) (0(0) -ons..)
w (0)
(7) av8.1)
Σ
$
(( |
δ (opaad + + Inp3-1oaa5 d
polylog(d)
(19)
with probability at least o poly[a] due to Lemma B.2, (A8), (8), and (9).
Case 1: l KC
By Lemma B.2, (A8), and (10),
④ ( w x (
(t)
((w w (0) )
$ (1)
(t) w (1) x())
< 0
w (1) w 11 Uv.1 )
+ w0
m (r) av221))
42

---

Sa (11 (s. 1) -
a =a/K20 (w)))) (0) ).2l) + a ( 00 +0
(polyylog(a)
polylog(d)
( 0 (a0o) polylog(d)
=o 1 (polylog(())
(20)
with probability at least - p ). Suppose (18) and (20) holds. By Lemma B.4, we have
yfw (X)
( (( 10 vyy1)) @
-6 (12))))))))))
(6) ((wof) (0))))((())) ((w")))(()))
PE[PIV("7]
Yo (1) (v, k) + By (v, k) -o <o 1
(padylog(())
= 2(11 ( (ollylog())
> O.
Therefore, we have
P(X,))~D (ffwn) 0 x(1)) vy E Ko] 11-0 (pollica)
(21)
Case 2: E KR U UKE
By triangular inequality and ø' 1, we have
( (0)) 1) 0b
((10
(t) av0,, )) ((
(w"")
(wo))))...)) .v..))
Φ ( (0!")) x010) )) Φ (wm)),)0))))) 1 (0((
o ((1
W (1) av.,, (( ( ( aru..))
( (t) (0) -v,,1)) > - ( (w (0) - av..))l
addition.
( av.. )) - (0(((
an (0) (s. (-ay
(( m (vws.)) )) a1
( (w an (-a7_((s)) 11)
an, (07 (s,, 11 (-an 11,
( (w!)) Uo - (0, 1) - a (w0 vo.1 + (2.
= -a(11' (1.0 + (s, o (polylo(d)
43

---

= =((a),
where the second equality is due to Lemma B.4 and (A8). If (19) holds, we have
Φ ((w2), - @ x = 2((a) -o (polylog(d) ) = =[(a).
a
(22)
Note that
yfwwo (X)
= Φ (( (uofi) (0)s)))))) & ((wo_)) Uyye )) ((rof)) , o (100)))017))
Σ
④ ((((u)), ( )) 1 ((ro-0) 20111) 1))
PELPIMp'M +
and
④ (( (wott) (oy)))))))))))))) - @ ((w0") Mysk) ((
Σ (6 (((18)) ((ns)))aolo)))
6 ((101)) xx(1)
pE|riMe .0
(1())) w (t)
Byykk)
+
polyyog(d)
(0) (v. k) + (1) k)) +
(no -w
(0) uyyk > + (polylog(a)
11
00a28-1 3) Ō(oo) +
polylog(d)
(polylog(a) < (((w5)) x(()) ((0
where the first inequality is due to (18), second-to-lad line is due to (A8), (8) and (10), and the last inequality is due to (22). Therefore, we have oo (X) > 0 y = s. Otherwise, yf (X) < O. Therefore, have
P(X yfww (X) > 0 xx(0) = Vy E UKU = t (poly(a)) (23)
2
Hence, combining (21) and (23) implies
P(Xw)~ (ySwoo (X) > 0] = Σ
Σ Ps to (ool(d)
Pk
+ 2
kERe
kekic
1
Σ
(poly(at)
1
=
2
Pk -
(poly(d))
kEKnUKe
44

---

D Proof for Cutout
In this section, we use 9:.0 iteration t, for simplicity.
(1)
(o for each data i, C [P] with |C| C and
1
D.1 Proof of Lemma B.3 for Cutout
For E [+1] and iterate 4
w (1+1) !
V w. LCutout (W())
Sy:BenDe
9i
(1)
Σ Ø' (ww!)
x (1)
(n)
P&C
gi Σ Φ ((wo)),of()))
,e((1)) x
EenDe
VEV
P&C
gi,C Σ & ((10(") a0.0 2//0) )
BeNDe
iEV_,
P&C
and we have
Σ ECNDe
Pi, Σ Φ (Lus) (ww()) =e."))) x0
(2)
ieV.
PFC
Σ
ECNDE
Iinc ((w!!) ve.t)) Lp; ec) 1ask
kE(K] ieVo,
+ Σ
ECNDE 10//00' ((w59).E(0))
1pec c!m)
iEV. Pe MI
Σ
EANDO
12.00' (1n5",, a.,,1 + <(.ii)) mxacc (ooe) + t((i))
iEV
Σ BewDe
10:00' av- + <(aii) laed] (av-s1 + slhii))
iEV.nF
and
Σ ECNDE
(1) Die
Σ Φ ((10 w!!"))
iEV..
P&C
Σ
ECNDE 9i.0 ((155) v...)) 1 1p:ec] v-a.6
kE[K] iEV-A.
+ Σ KEV (E
ECNDE [0,00'
(1ic0(((u!)) ((wx") (((i)) mnec] gl
EONDE Ri.C'' ((w!)) ov0.1 + <((i)) mmec] (ars,1 + ((i))
KEV ,DF
ECNDE 9..00' ((wS), ax av + c.bi))) laec (ave + c!hii)..
KEV nnF,
Hence, if we define ( (s', k)'s and ps 6 ()'s recursively by using the rule
1 (0+) k) 1 (s', k) + 1 Σ EewDe 00:00' (o.))), lpsec), (24)
n iEV
45

---

p (i.p) (i. + 2 EcnDo 11) "ico'
((w5)) )
[pge (
|
(25)
starting from 78 then we have
(0) (s', k) Ps (i. p) = 0 for each 8, E {=1}, [K], [m] and E [P])
(0)
{pt).
w (0)
+
Σ
2 (s,
Σ
(-s,
k)u
kE[K]
kE[K]
c!P)
+
E
P! (i.
Σ
(i.p)
((())
2
c(())
(EV
iEV
+ a Σ
SyAPE (1) (1,
Us11
+
syap! (i.
2 v-
((.)))
2
(((
iEF
iEF-
for each E [#1]. Furthermore, (1) (s', and Ps (i.p)'s are monotone increasing.
D.2 Proof of Theorem 3.2
To show Theorem 3.2, we present structured proof comprising the following five steps:
1. Establish upper bounds on 7/ (t) (s', k)'s and p (i.p'' s to apply Lemma B.4 (Section D.2.1).
2. Demonstrate that the model quickly learns common and rare features (Section D.2.2).
3. Show that the model overfits augmented data if it does contain common or rare features (Section D.2.3).
4. Confirm the persistence of this tendency until T iterates (Section D.2.4),
5. Characterize train accuracy and test accuracy (Section D.2.5).
D.2.1 Bounds on the Coefficients in Feature Noise Decomposition
The following lemma provides upper bounds on Lemma B.3 during 7 iterations.
Lemma D.1. Suppose the event Eist occurs. For any 0 S t T", we have
0 S 7 (s. k.) + 22 k)) S 4 log((TT'), 2 P (i.p) + 30 (i.p) S 44lo (1)"),
forall E {+1, k E [K] [n|] and p E [P] }. Consequently, 7/ (s', k), Ps (i, = Ō(3-1)
for all 8,8' E {+1}, k E [K], E [n] and p E [P] (pt).
Proof of Lemma D.I. The first argument implies the second argument since log(n]"*) polylog(d) and
" k)) S 3-1 (70) 11) (.) + (3, (1.))) 8-1 (1.)).)) -
for all 8, 8 E [+1], & E KK E [n) and E [P] {pi}.
We will prove the first argument by using induction on t. The initial case t. = is trivial. Suppose the statement holds
T and consider the case f T 1.
Let T. S. T denote the smallest iteration where 7/ (T.+++) (s, k)) + 3 (f.++++1))))) (s, > 2 log(r
We assume the existence of T.,k, its absence would directly lead to our desired conclusion; to why, note that the following holds, due to (24) and (11):
(s,))s 3. (T+1) ks
-x + + (8,k)
+ 7 Σ EenDe gic 1p7ec (((11 + 30' ((w2, va. ))x)
VEV..
46

---

S logg(1 + 2n - 4log(n
By (24), we have
1 k, 3y-8 (T+1) (s, k)
7a (
(s, k)) + By (f
(++1) (s, k) + (s. (s, (,)
t=
< 2 log(r/"") log(n
T
(0) Pi. (10((0 (KuSS),u...) + Bd ((w=2) 11:40
+ Σ
Σ
BENDE
!= +I
(L.re) (s,k) Br (s, (s, 2 2lg((n] and
The inequality is due 7
7 Σ BCNDE
Fie (te (0' ((105 B ((10_a , .w.))) 1p:40]
(Fan)
n iEVe,
I 21 S log(n)
from our choice of Ta,K and 1/.
For each & TyKk + 1,... T, Vs,ks and C C [P] such that |C] C. and p. & C, we have
Ne/wco(Xi..)
= (( (w! Vark) - (
Σ
(0((m(0,.00))) (ool)),a()))) ob ((wo
DECU(N;}
(0 k) + By (s, k)
Σ
(i.p) (p -2P.
(polyttgg (oolylog(d)
pECU(n;)
2の log(n
The first inequality is due to Lemma B.4 and the second inequality holds due to (A7), (8), and our choice of f, 7 (s, k) + (s k) 2 log(n??")
Hence, we obtain
(1) (d' 0d ((ws)) (o.)))es.))) 36' ((w"i vex))) lozec
7
Σ
EcnDo 9i.
t=T',, REV..
21
EewDe (exp (-Wiiffres 1p:eol
1 T,Kk iEV,,
2 V (TTT") exp (-2 1og(117")
2
< $log(ni""),
VnI
where the last inequality holds for any reasonably large T Merging all inequalities together, we have 7 (T+1)
(s, k) (x+++)((s, (s, < 4 log(n
Next, we will follow similar arguments to show that
(T+1) (+ Pg
(i.p) + 3p 3p (i,p) S 4log(17"*)
(T+1)
for each i E [n]] and [P] {p
47

---

Let T/ I T be the smallest iteration such that Pa.
(I +1) (i. (t.,)) + Bp-y,
(T! +1) (i.p) +1)
> 2 llg(??
We assume the existence of ( .. as its absence would directly lead to our desired conclusion; to see why, note that the following holds, due (25) and (11):
Pg: (t,)) + (T) - (1.p)
P(. + Bp (i.
DE (T)
9i. ppcc (od od ((wo"), xx!" )) + 3d'
|
< 2 log(n1 + 2n S )l
where the first inequality is due to
|5
3 ad and (A4), and the last inequality is due to (11).
Now we suppose there exists such S T. By (25), we have
(1++1) + 3p -
(T+1) (i.p)
Pg:
(1
(1(00)
= Pvi
(i,p) + 3p vi (i.p)
Σ
(+11) (2,p) + (i.p) (i,p)
(i.p) (i.p) 30 (i.p)
Pg.
< 2 log(n + log(1/(*)
+ 7
(0) ECwDe
Pi loze ((wo") + 3d ((w=2) x ()) (c 12
(=
The inequality is due
( (i.p) + 3p (i.p) S 2log(nT**) our choice of T((P) and
! "EwDD
(1(0)
1psc ] ((w!Ti
(TTP)) x _z(")) )) + 30'
(( (ww!7 (T("))
(p)
)) |
91.
x
< 21 S log(n?""),
from |s s 3 3ddd, (A4), and (11).
For each
/ 7(p1) +1,... T, and C c [P] such that |C| C and p & C, we have
ViJwoo(X
= ((m(tt (00(((,a(())) )r("i) - ((w""...."))) gRcU(D)
Σ
(o) ((w() 1 ((w0)) xx
(( ))
Pvl (i,p) + -p (i.p) - 20 (
polylog(d)
3
2 l)
The first inequality is due to Lemma B.4 and the second inequality holds since from our choice of t,
(t) (i.p) + 3p (i,p) 2 2 log(")"") Py.
Therefore, we have
T
ECwDo Pie 1 pxc] ( (5' ((((110),.)) (ral (111)) + 366
(=10) +1
T
EenDe (exp Wiffoo Ingcl $ (nT exp ( (-2 log(nT*)
<n
Σ
(1)
+1
48

---

V1TT I l)
where the first inequality is due to |
||
S 3 3 and (A4). Hence, we conclude Pa:
(T+1) (i.p)
(++ 3p- 96 (i.p) p) - 4log(nT)).
D.2.2 Learning Common Features and Rare Features
In the initial stages of training, the model quickly learns common features while exhibiting minimal overfitting to Gaussian noise.
First, we establish lower bounds the number of iterations, ensuring that background noise coeff- cients ps (i.p) for + Pi Ps remain small, up to the order of J. T
1 Lemma D.2. Suppose the event Emit occurs. There exists T onPoRd such that ps (i.p) S 4P for all 0 & t < T, E {+1},EE [n] and p E [PI P.).
Proof of Lemma D.2. Let T be the smallest iteration such that pa (i.p) 2 i for some e {#1), [n)] and p E [P] {pi}. We assume the existence of T, its absence would directly lead to our conclusion. Then, for any S t < F, we have
+ p (tt = pf
7 RE
(00 (1, Dico' (uu()),a(o))) 1 14c [<(0)) < p
3no
n
2n
where the inequality due to gi.e
(1)
< 1, ø S 1. and |< 2
$ 3 oodd. Hence, we have
π-1
3nd d 2n
4P S (i,p) = Σ
( (i. p (i.p)) <
T,
and we conclude / on.Pod
which the desired result.
Next, we will show that the model learns common features in at least constant order within T iterates. Lemma D.3. Suppose the event Emnt occurs and Pk = w
for some i E [K]. Then, for each 9nP such that 7/s (4) (s,k) (s, k) 2 1 for any t T.,k nB(V.,
a 3n
8 E {+1}. there exists Ts.k S
Proof of Lemma D.3. Suppose TO (1) (s, + (s, k) < 1 for all 0 s & onPoga For each
i e Vo and C c [P] with [C] = C' such that Pf & C and p. E C, we have
y: ViSwio (X.c)
= ((w! vax) (00)))((($0 eax)) ((w0
Σ (o((u(",. (io(",,(('))) -0((10)) a({)))
nECU(F!)
S 70 k) + (s,
Σ
(259 +B00 + 2P. polyyog(d)
1
1
S1+2P.
2P
4P
polylog(d)
2.
The first incquality is due to Lemma B.4, the second inequality holds since can apply Lemma D.2, and the last inequality due to (A1). Thus, Pie T+exp(ysS (X.c)) y and we have
(8)
(t+) + 2 78
(++) (s,
49

---

(s, + (x,,))
! Σ BCNDE
(1) gic
vox))) (0' ((wl)) vest)) BΦ' (ool 1p:e
*EV..
78
2 1/8 ( (s. k) (s,,))
Ec-DeL
9n
iEV..N
n C
9nP(PP PPPPP-1)
n
7 k) + 8 99 (s. k)
9nP
From the given condition in the lemma statement, we have
9nP
0
If we choose
7 V.,al @nPord
tu E
9n n1 V.
n PnPog
then
1 ! (to) (s, By (10) (s,
9nP to 2 1,
and this is contradictory; therefore, it cannot hold that (s, k) + "3
(s, k) < 1 for all 0 st
ByPaaa Hence, there exists 0 S Ta,k < EnPoga such that (T (s, k)) + B
(T.x+1) (8, 2
and choose the smallest one. Then obtain
n 9nP
1 (0 (s.k) + (s,,))
T
P Therefore, T. S V.
and this is what we desired.
What We Have So Far. For any common feature or rare feature Va with E {+1} and k Ke U KR. it satisfies Pk:
odd
due (A5). By Lemma D.3, any iterate t [T,, T*] with
Ti max,e(+ Te,k, the following properties hold if the event Einic occurs:
(Learn common/rare features): For {=1} and Ko KRR 18 (s, (s, ((1).
For any {#1}, E [n], and p [P] (pt) 1 (1. ((-1).
D.2.3 Overfitting Augmented Data
In the previous step. we have shown that data containing common or rare features can well- classified by learning common and rare features. In this step, will show that the model correctly classifies the remaining training data by overfitting background noise instead of learning its features.
We first introduce lower bounds on the number of iterates such that feature coefficients 7. (0'('' k) remain small, up to the order of a-3 This lemma holds to any kind of features, but we will focus on extremely rare features. This does not contradict the results from Section D.2.2 for common features and rare features since the upper bound on the number of iterations in Lemma D.3 is larger than the lower bound on the number of iterations in this lemma.
Lemma D.4. Suppose the event Fmnt occurs. For each E {+1} and k E [K], there exists
na? Tek n such that (t) (s, S 3- for any 0 < Ta and s' (+1).
Proo of Lemma D.4. Let T,,k be the smallest iterate such that 7 (s, {+1}. We assume the existence of Tokk. as its absence would directly lead to our conclusion.
(2, k) > a d for some s' E
For any 0 < < Takk.
((+1) Ts
(s, k) = 7/d (s, k))+ Σ EewDe oo:00' ((w5)
vack) )) 1prec] s 2 (0)00( (s, 17 Va.k
LEV.
50

---

and we have
Po,a-1
a2g-- S To'
(s. (s.))
(Taa)
Σ (1e (1 (s,
7 ( (s.
S
7/Va,a T.
n
We conclude T 2 no² np V...l
which is the desired result.
Next, we will show that the model overfits data augmented not containing common or rare features in at least constant order within Te,k iterates.
Lemma D.5. Suppose the event Finit occurs and Ph: = o "oo such that
(0222 For each E [n]] and C [P] with
n
18m (c)
[C] = C, i Vo and p or (2) [n] and pt C. then there exists Tic E
Ti
Σ pECU
(1.p)) 21.
for any t Ticc-
Proof of Lemma D.5. We can address both cases in the statement simultaneously.
Suppose
Eppcute: (p% (i,p) + 3p (t.pp) 1 for all O < t S ne n
na
From Lemma B.4 and Lemma D.4, we have of (X.c)
Σ ④ ((w() (
PEC
$ (t) (Vi, k) + / (y1, k) +
Σ
(i.p) + (p + 2P. .
(polstog(a))
pECu(P?)
S (1+ 3)a 2 1P
polylog(d)
$ 2,
and 9:6
(1)
2 9.
Also, for each p & C U {pt), we have
1+oxp( (w (x,c))
P3 ((+))(
(1.p)) (i.p)
2 1 (i,p) + 3p (i.p)
+ ? "P = =Clg%/ 0' ((w!",e!")) + 36' ((w")) x ((())))) | 1
20 (i,)) + 30 + BBRRd
18n (c)
where the last inequality is due to |s!ool??
2 food and 0' > 3. We also have
ngofd 18n(2)
Σ
(l(+1) (1 (i.p)
Σ
PECU(
From the given condition in the lemma statement, we have
18n( noagd
0
na?
If we choose
to E
18n
na² then we have
nBagd
n V.ll
Boond
(tto) + -pttt (1.p) 2
(ta)
to 2 1,
(
(ECU(PT)
51

---

and this is contradiction; therefore, it cannot hold that E Epecule: (py. (i,p) + Bp (i.p) no
1 for all 0 1 t S
Thus, there exists 0 < Tic
no? m
satisfying
Epeculo: (p= (i,p) + 3p -p-..
(ffeett)
( (1. 2 1 and let us choose the smallest one.
For any S < Tic, we have
12
E
(ip) 3p 3p (i.)) 2
notd Tí, 18n (8n(()
pęCU(pT)
18n(
and we conclude that Ti,c
Lastly, we move on prove Tic > Tr. Combining Lemma D.2 and Lemma D.3 leads to (i.P)
Σ
2
Thus, we have Ti > Ti and this what we desired.
What We Have So Far. For any Kr, satisfies Ph iterate / [Teutout, T"] with
n'n agd
due to (A6), By Lemma D.5 at
Teutout = max (KEKR,EEV gC
max
Tr., max Tee VE
j [Ti.T*]
the following properties hold if the event Emit occurs:
(Learn common/rare features): For any s SE {+1] and & E KcUKK
(4) (s, k) By (()),
(Overfit augmented data with extremely rare features or no feature); For each E [n], E K C C [P] with |C| = C such that (1) E Vy.,k and pt & C or (2) E [n] and pt EC
Σ (000 (1.p) 3p (i. 2(1).
pECU(PT)
(Do not learn extremely rare features at TCutout): For any s, o {+1} and k e Kg,
(Pestoo)) ) (s, k) s
Vel
For any E {+1), i E [n], and E [P] (pt 10 (i.p) δ (3-1).
D.2.4 Cutout cannot Learn Extremely Rare Features Within Polynomial Times
In this step, We will show that Cutout cannot learn extremely rare features within the maximum admissible iterate T poly(d)
we fix any s* E (+1) and ke E KEg- Recall the function Q(=" ,²) W + dx defined in Lemma B.5 and omit superscripts for simplicity. For each iteration t, Q(W()) represents quantities updates by data with feature vector e-- until f-th iteration. We will sequentially introduce several technical lemmas and by combining these lemmas, quantify update by data with feature vector U.*.a- after T Cutent and derive our conclusion.
Let us define W [wi w w-1}. where
(p)
w w (Temoaa) + M
Σ
Σ
|
VEV, -- PE(P]MEP a.)
where M 4.3-1 log
2T a²
Note that (12), 8 1, and T poly(d)
together imply M
δ (8-1). Note that ((!), W W for any 2 0.
52

---

Lemma D.6. Suppose the event Eiii occurs. Then,
@ (w(Tewoul) - S8M' P 2
where ||-1| denotes the Frobenius norm.
Proof of Lemma D.6. For each & {+1}.
Q. (ww) - Qs (w. (
s8
$10)
88 M Σ
E
Q2
(<(001)
iEV,,, PE(PIMPE det
clm)
M Σ
E
iEV
(P F.)
and we have
Q ( (Wllccttne) Q(w+)
= 11:(w))) Q1
(w) (ooeeosoodd) )|²
+ --
- -Q-1 10:1100000 ( )|²
(< {
< 2M2
Σ
( |s
+
Σ
|/"0|p |/5500 2
ieV, Plee fct
IJEV.
PEPP WEW ((.p)
From Biit and (A2), we have
(<tt) .//0))
Σ LEEV
Σ
Σ
( θ (d-
| 1 |||||
iEV. & PE(PIMPTT P:) (P(P)M
JEV
pel (i.))
Σ
δ (nPdt
iEV. PElPIMPp.
Σ
[(p)
NEV. PEIP
From the event Pinit defined in Lemma B.2, we have
Σ
2 <
iEV.... PE(PIMANS
and we obtain
@ W (TTctooo))
QQ(W-)
< 4M2
Σ
<8M*P|Vss,A00033 5i
(p)
2
20-
iEV . DE PNott)
Lemma D.7. Suppose the Emnt occurs. For any 2 Teutouts Vss k and any C [P] with
|C| = C, it holds that
(y Vwwwwo (X,)) 2 MB
2
53

---

Proof of Lemma D.7. We have
(y6 V Sw (X (Xic), (()"))
Σ PEC
Φ' ( (0 ae)))) (w (1)) o ((w=)r,,,()))) (w-
For any E } and p E [P] {pt pt).
88 (Q.(w c(P)
(outou (i. Kept)
. -.(0)
2 M + Ps (Toaoous) (i.p)
E
||500/
(1.))(((.))
(5)))
c44)
-M
|
jEV. (eeee())((()) (..)(((p))
M - ② nPB
11P8-10005 d b) M
00
polylog(d)
M 2
(26)
where the last equality is due to (9). Also, for any s E {+1}, ss* (Q.(w)), Us- k-)
=
(Teatout) ks* 2 In addition,
Is
(F.)
(Q.(w))) ((()))
ss* (Qo(w()) (6)) x0(1)) c!hi))
(Q.(w))) c(.))) ((81))
δ (n² 2 1-111111 Pk: no 2d
(B,) c(())
,5
03 (Tattou))
(1, +
Σ
(Tnaowe) ) (j.g)
5 (0223-1
n
(5500
gE|n] (1.p))))
2 - (nPP3- oapp ld -d +) - Ō (a²3-1 Pk- no 22=21
(27)
polylog(d)
where the last equality is due to (9) and (A7).
For any [P] with |C| C, there exists p E [P] \ {pt p.P such that p + C since C P. By applying (26) and (27) for s" -s" and combining with ø' 2 B, have
(ys V Ww /ww. (x,c) ((C)))((W)) Q(W*))
w xr (p) )) (w.-) m0 (01) - 18 ((w aa.o (e .a(())
Σ
(w 0' (ww!", (0)) )) (w: ), ra("))) o' (ww )(())) (Q- 2,), )
xe!
(pC
2 MB -
polyyog(d)
MB
2
54

---

By combining Lemma D.6 and Lemma D.7, we can obtain the following result. Lemma D.8. Suppose the event Einit occurs.
E
DE (ynfrrs s 00 (Wirenoot)- 2n/I" 442
Taatous iEV,-.E*
where ||-|| denotes the Frobenius norm.
Proof of Lemma D.8. Note that for any Tutoou 3 < T
Q @wiltu))= Q (w(o)= - 7 Vw
Σ 1EV.'
EeNDe le (yifwre (X..)))
Therefore, we have
@ ( - (wr) @ (wrlttt) 2
(wrlttt)- - (w.))
21
Vw
Σ
ECnDe (ollswooXii)) Q (wr(t)-Q(N)) -Q (w
iEV...
172
VW
Σ
EENDE (yrSwwo
2
$EV,.,
21
ECNDE [(ynswwro ( (wrl))
(
Vw
11
kEV
2n
(BenDe
(W")) Q(W"))
1/2 Vw
Σ
EenDe 1e (
n
sEV,...*
2m
Vw
Σ
ECnDe [(ynfwoo (X.c)l (w(lt)
11
iEV,*.
M 3q
EC-DE (y'ffwer (Xan))eeXXi)))))
1
Vw
Σ
EenDe 1e (oilwoo(iicl
n
iEV.-,6*
iEV.
where the last inequality is due to Lemma D.7. By the chain rule, for each C c [P] with |C| C, we have
Vw
Σ
(X..)wo(Xx.))))eo (wrl)))
Σ
(():fmo((X.c))
<EV,",>
(( mz(P) ag1))) (0or (w!!) -a)p)= & (l)))>(((()) ((00)), (0-.. (10 x!!o) ))
PEC
For each [+1], Vo- be,
ke, and p E [P].
( (1)) (Q. ((()) x [2((1))
(wn!.) Q. (w( xx!
(p)
55

---

5/
Σ
(i.
(P)
(5()
jEln](V. oe (E(PI(()))
+a E
[5/33)
(11.1, 22 (0))
JEFI\V
1- ar! ) (-,
+ E
1 (i.pj)
JEF-
< <ō
( oao d- :) + 0 (a² ( "no 2
nP3
polylog(d)
where the last inequality is due to Lemma D.I and the event Einit By Lemma F.I,
Σ PDC
ae(i))) (Qo. (w!)) ...T)) - o' ((w= ( (Q-.. (w!?). 2x)
Σg
(0 , ae!")) o (100.- 20." (000)) rr
((10
(potylosta)
polylog(d)
PRC
= Jio (x,c) + polylog(d))
where the last equality is due to r
= pollyoo((s) Therefore, we have
0 (w()) (w 12- 11-1@((wl-))) (wr(--)) )(
27
MB
Σ
ECNDE l' (enfwro(iiic)) Wnswio (Xic) (x (polylog(d))
Vw
ECNDE [(..swoo(X.c))]
n
iEV,...
21
((x)))((Xxc)) (iSwio(X..)) M3
2
BENDO
4
172
Vw
Σ
BenDO (itafwo(XX.)))
n
iEV,....
From the convexity of E(-).
Σ iEV..
BewDe
((viswo(XX:)) (X MB)
)
Σ EenDo (eLuiSwro - M3 kEV,...
Σ
ECnDe [Cyisweee (Xic))) ne
MB
In addition, by Lemma F.3,
V
Σ
EcaDe (
?
56

---

811²
p2 o
Vo.
Bew
n
$EV,*,
7
ECND
(Xx.))]
where the last inequality is due to (A8), and we have
(watt))- 2 7 Σ EEDD (ee -21ee" Mr
100 (w())) - ((w"))|-- ( -
n
iEV.-,0"
From telescoping summation, we have
T
Σ
EE (M.wwoo 0 (w(lemaou)) - Q (w*))l²
2 42
Cutoou iEV,-,K"
Finally, we can prove that the model cannot learn extremely rare features within T" iterations.
Lemma D.9. Suppose the event Emnt occurs. For any E [TCutout, Th we have 7/ (s" (s*,k*) k*)
Ö(a28 ( ) for each E {=1}.
Proof of Lemma D.9. For any T E [TCutouts T*), we have
T-1
(s" k²)) = 7 (Teutons (8",,²) + 7
Σ
BeNDE
(0) Di.0
m Φf ((rs!) vx-
t= Teatout iEV.
T-1
< 7 (Trttou))
(Teutows) (s", ,h)) +
EOnDO [i.c
Tooooo iE VE
T-1
(s", k²) +
Σ
EenDe [R (Vifwre (Xic))),
t Teatoat VEV..
where the first inequality is due to ø' S and the second inequality is due to - s E. From the result of Section D.2.3, 7/8
(Pentom)) ) (s", k*) < a²z-1 and by Lemma D.8 and Lemma D.6, we have
(T-1)
(T**
1
Σ
Σ
RENDE (yilww (X "
Σ
EENDO (Jifwio (X.fww(XX.))))
Tuutout iEVo-,.*
Teutour VEVe.,u-
Q (W Q(W,)) + 2n e Ma
S 8M PIVs 1op 2d + enT" Ma
Ō (a²3-)
2n/2T ). This finishes the proof. a=
The last line is due to (A6) and M = 48-1 log
What We Have So Far. Suppose the event Emit occurs. For any E [TCuoou:: T*), we have
(Learn common/rare features): 7 (s, + () k) = 2(1) for each s E {+1} and k
Kc U KKr
(Overfit augmented data with extremely rare features or no feature): For each i E [n], k E KE, C c
[P] with |C] C' such that (I) i E Vy, and pł & C or (2) i [n] and pt
Σ
( + 3p pi) = 2((1).
PECURPT}
57

---

(Cannot learn extreme features): (s.,)), o (c²332) for each E {+1) and h E Kg.
For any E {=1}, i E [n], and
[P] (pt < (i.p) 3 (s
D.2.5 Train and Test Accuracy
In this step, will prove that the model trained by Cutout has perfect training accuracy both augmented data and original data but has near-random guesses on test data with extremely rare data.
For any E Va, with {=1}. & E Ko U KR and C C [P] with [C] C and pj $ C.
Vif (Xi.c)
Σ Φ ( (1( ((00 (2(()))
- (mm=larr
PCC
(s, k) + By (s,
Σ
-((P -C)
1
polylog(d)
PECU(Nt)
1
2 (s, +
2(P -)
C..0 polylog(d)
2(11 polylog(d)
= 2(11,
for any [TCutout T. In addition, for any i E [n] and C c [P] correspond to the case above, by Lemma D.5 and Lemma B.4, have
with |C| = C' that does not
Yiswon (X.c)
Σ P&C
((w (00)aa(()) ((((w))
Σ
(0) (i,p) 30 (.(.)) 2(P -C
polylog(d)
pECU(NT)
1 polylog(d)
(())
((1),
for any [CCutout; ]r We conclude that Cutout with [Tuutont, T iterates achieve perfect training accuracy on augmented data.
Next, will show that Cutout achieves perfect training accuracy the original data. For any i [n], let us choose C C [P] with |C| = such that D E C. Then, from the result above, we have
yilwie (X:) = viSwoo (X..)((i..)) + Σ (o ((11)) (allaaaa()))) - ((w01)) ! {)))))
PEC
(1.)) +3 " (i.p) - CC. (potstog(as)
2 (aiiii/iiic +
Σ
pEC|(E))
2(11,,
for any E [Teutout; T*] and we conclude that Cutout with E [Teutont; T iterates achieve perfect training accuracy on original data.
Lastly, let us move on to the test accuracy part. Let (X,y) D be a test data with X E pdxP having feature patch p², dominant noise patch and feature vector Yy.k- We have (PP) ~ N(O,, ofA) for each E [P] \ {p", .p} and (F) av.,11 ~ N(0, AfA) for some {+1). Therefore, for all t [Teutout, T and p [P] {p*,p)
④ ((w0() ..(()))) (ww") 20(1)
58

---

w1 (1)
w -1. x012 (p)
(5 )
w1 (0)
w (0) 11 20110))1) +
E
(i, - o)
|
(((M)_0)(P1\\0))
(oold
+ + -a00 d
(28)
polylog(d)
with probability at least - o (police) poly(d)) due Lemma B.2, (A8), (8), and (9).. In addition, for any s' E {+1}, we have
(1) w (P) - cvss.))
(5/ x(00 ava.1) )
w o' x (P) ava1) )
(0)
Σ
p (i,
| l|
(ooadd + +
(29)
polylog(d)
with probability at least
poly(a]) due Lemma B.2, (A8), (8), and (9).
Case 1: Kc KR
By Lemma B.2, (A7), and (10),
④ w1 20()) )) 2 ((00)) (.00,,,000 x.)))))))))
(t)
w1 w "1, x0(1))
w (1) w -11 va.1) )
+ (0()) - x
x(1) - avssi)
0
S (1) ///(3 (s, 1) + [s, 1)) + ( w unI1) > + a (wo Un,1 ) to polylog(d)
< 00 + 5 (2o0) to
(polylog(d)
=o 1
(polylog(d)
(30)
with probability at least o (pobiaa) Suppose (28) and (30) holds. By Lemma B.4, we have
(X)
(0) (wwh)) vyxx)) ((10")) My))) myx)))
(0l (0(m0))) ,0(10))) @ (100 ((w))))))))))
7/ (t) (y. k) + "3 (y, k)
(ooyyog(d))
2(1) - (polslog())
59

---

> 0.
Therefore, we have
P(x (X) 0| x(0)) = uy ks E Ko KKu 21 (poly(c))
1
(31)
Case 2: ls E K
By triangular inequality and ø' S 1, we have
(( (!! xx(1)) )) o (( w (t) ( -
(( (!( .00,,11 )) (( wo arv.1))
(w!!) (o.()aa))))))
(0 ((((__))(())) o ((..1)
Φ 1.0.,11 ( 1 (t) 005,1) (
(t) x ( -v0s.1 ) - ( (w x - avs.1)
w
In addition,
④ ( ( (rvz.)))
(( -, (w0
00 an (s. 1) 1
(17
(-an
ann (1) 1) 1 (-o7 (s.
(u!)) Uo.1 (s, -a
w
- Us.1 +
(t)
(t.
(1. ( (s, + (s.
polylog(d)
= -(a))
where the second equality is due to Lemma B.4 and (A8). If (29) holds, we have
① ((w (10,",,11 ())) $ x ( ((w=
2(a) (polylog(d) ) Ma).
(32)
Note that
yfw (X)
= =0((u0) ((wo)) (0),))))))) & ((00")) uyyk) ((wug) .0000=000))) ((w")),
① ((10)) ,a(r)) )) $ ((w0)) 2(
pE(P) 5)
and
p (wo)) -..kk) - ((
2y.kk)) ((
+ Σ
(((108().2(1e) - (w
pEIP|MP- 20
( (w) (t) (() g. 0y,k)) + polylog(d)
60

---

s (g. kb) + 19.
(v. 1)) + (m00- w (0)
uyy +o
+0 (polylog(a))
s 0 2) ( to
polylog(d)
=o (polylog(()) (( ( a m0(0)))))))) )) @ ((1)))
where the first inequality is due (28), the second-to-last line is due (A8), (8), and (10), and the last inequality is due to (32). Therefore, we have y/w (X) > 0ff y = s. Otherwise, yfwce (x) < 0.
P(X.))~D yf > 0 x(x)) = Yykki K E Kg = poll(d))
(33)
Hence, combining (31) and (33) implies
P(X byf (X) > 0]
Σ
Pk +
Σ kEKCUKK
Pk to (poly(d)
2
REKO
1
Σ
Pk: +
1
pool(cc)
REKR
61

---

E Proof for CutMix
E.1 Proof of Lemma B.3 for CutMix
For each i,j E [n] and c Iet
S == p yel (Xir,s))
S]
-11-10111 Us fwrco (1)
[5]
For E {+1} and iterate
w (++1) (t)
(
= =-IV V=,, w, LoutMix
Σ Φ (wolo,z(")) x! + +E d' ((w!"), 2n50 )
7
Σ
EswDs
$gij.s
n² i.j[(n]
PES
PES
S7]
Σ
Σ
ESNDS
( piisstpees + I tpess d' ((wo!) ( Vo
n²
''E (EV
sn
Σ
(1) ESwDs Pisisppss + ( of ((w))) a!!!
n2
Hence, if we define 78 (s', (6',,) kt's and pe (1, p)'s recursively by using the rule
(5 (s', ss'n
Σ
(e) ESNDS pinistees + - d' (w)")...)))
n
VEV,
Pa 21 pb (i.p) +
ES-Ds
(1) 0ig.8 pes + " &' ((ws),a.")) ||
n
jE(m)
starting from 7/5 (s'k) Ps (i,p) = 0 for each s, s' E [=1], [K] E [n] and E [P] \ (pt). then we have
( Σ
(10) (s,
Σ
1/ k-s
kE(K]
RE(K)
(p)
Σ (i,p)
Σ
(1,
(p)
(((0))
JEV (E(P)((A
JEV (E(P)N(A
t Σ
syip! (1,
Us.1
Σ
SyaP (9 (i,
2 1-
|e(ai)
(((0,)
iEF
iEF
for each (+1).
E.2 Proof of Theorem 3.3
We will prove that the conclusion of Theorem 3.3 holds when the event Emit occurs. The proof of Theorem 3.3 is structured into the following six steps:
1. Introduce reparametrization of the CutMix loss LoatMix (W) to a convex function h(Z) for ease of analysis (Section 1.2
2. Characterize global minimum of h hZZ) (Section E.2.2).
3. Evaluate strong convexity constant in the region near the global minimum of h(2) (Section E.2.3).
4. Show that near stationary point of h(Z) close to global minimum (Section E.2.4).
5. Prove that gradient descent on the CutMix loss LCatMix (W) achieves near-stationary point of the reparametrized function i(Z) and perfect accuracy on original training data (Section E.2.5).
6. Evaluate the test accuracy of model in near-stationary point (Section E.2.6).
62

---

E.2.1 Reparametrization of CutMix Loss
It is complicated to characterize the stationary points of CutMix loss Liut (W) due to its non- convexity, We will overcome this problem by introducing reparameterization of the objective function. Let us define
(p) 2 = ((w))
Φ ((1001,00)) 1)
for E [m],pE E [P] and
2 o((wi, Us,t)) c((w-11 vo,k))
for each s {=1], k [K]. We can rewrite CutMix loss LoutMix (W) as function h(Z) of the defined variables Z == (2e,k (E U {2( (e(()) as follows.
h(Z) n2a
ESwDS
|
l
y/
2
(p)
Σ
(0)))
P
i.jE(n]
PES
PdS
1
[
l
yj
24
(p)
(p)
P
PES
where we write 2/ (pt) 2 if E Va,k- For notational simplicity, let us consider Z vectors in R2K+1(P-1) with the standard orthonormal basis (ea,K) (ea,)))((11))eE11) U
{ (p)
P(PM))))(PIMMtt)
which means
(p) Z (ZAA)e(()))AGRR) U {{
(p)
PEP
If there is no confusion, we will use e (x7)
to represent e, for i E Va
By the chain rule,
Vw CCutMix (W) J(W) where each column of Jacobian matrix J(W) E (R22x(((P-1))22K)) is
d' {
W 20! (p) w x
20.00
ve,k))usk ((, V W W = - d' ((w-1, (g,4)) Ua.k)
E 2d Vw (p) =
E 2d
x
Let us characterize the smallest singular value amin (J(W)) of the Jacobian matrix J (W). For any -2K 1), we have
unit vector c = {c,, U kE(n)
c
(m)
J(W) =
Σ
G,k W. +
Σ
(10))
V V (p)
(p)
E <E
Σ
Cas.ki Coa V WW
V Zog
(LL) AgE[K] (z)
Σ
(p) (Ww2sk V v
+2
(E(LI)
Σ
(4)
(w (p)
(PP gein)ge(PP(ve)) (1p))
63

---

For each 82,82 E {+1], k1, E [K] such that (11, & (52,
and i E [m], E [P] \ {p).
V W V VW
V w 2 V V = 0,
and if k >
(Vwzsndk Vwzz (012
- V Vwz, (0)) =0,
since (Us) Ua2,k2) = ( e(m) ) then
(u (((i)) = O. Also, for each s E {+1} and i E F,,.
2 (s,10f11) (Fw2zs1.ww:(..)
= 2 (ec1 (
(d((101, (wI) + 60((w_1, ((w_1,2f(i))
a²
I 4c2,1 ((101, + ( |a.00>11"
((()))( 00 ( a(fll)) + o ((w_1, ) le
+ 4
1
2n c, ((111, 0 (((w01,, 2),)))
(
) 0' (0 ((.)) 2 + 0 (w
2
| 1p
+ 4
where the last inequality holds since
- ( = aa² + 1
2 goåd w(na
where we apply the fact from the event Emit defined in Lemma B.2 and (A7). Also,
(Vwz-an Vw ( O.
Furthermore, for each i,j [n]. E [P] \ (ithge [P] {pj} with (i.p) + (1.9) satisfies
( ( (V (Vw=fm)) (r), /w
g (6' ((w).a!")) (( ( + (''(((ww ((w-n.-"")) o' ((w-1.a)))) (a())
((r)) (0' (( ((w1. )) +o (( (w_,, 1
$ 4Pm
(6))) 8' (1. 2))) ((-_))))))²² || |
4Pm
|=I + (c) (1))
4Pn
where the last inequality is due to AM-GM inequality and
| 2 2mP ( (0) x3)0) \
which we show through case analysis. For the case p p= pi and g pj. this inequality holds since
x
(9)
(p)
22. | 2nP (((E))) . + a²) z 2nP
(p)
where the second inequality is due to
1
1
(
|
2nP (et²) |.
1 |
|
> 22
which is implied by the fact from the event Emit defined in Lemma B.2, (A1). (A2), and (A7). In the remaining case,
(z)
(2)
|(
| > 2nP
2nP n ., (4)
x
x
64

---

where the second inequality is due to the fact from event Emit defined in Lemma B.2, (A1), and (A2).
For E {=1}.k [K] and [m]. [P] {pt}.
V 12 = & ((w1,, vo,k))² + d' 11(ww-1, us, 23²,
and
V 2 1|= -0000 0' ( + +0'
(( ) 1
2 8 oi
2 3
where the last inequality is due (8). By merging all inequalities together, have
||l))
E
1 V
Σ
(1)) (1
Vwzz
(p)
=
<E(LI),E((K]
KE PE
+ Σ
(V Vw (8.)
E
(P) (2/000)
+E(+I),EE,
JE(M)
(1.))
>
Σ
L V
(0)
VW (p)
SE <E
Σ
L2
1
2
V
1 (B.))
V
2n
4
NE(+I)iiF.
E
(
(d))) 2
V
+
4Pn
(1.))
>
Σ
2 2.
V 11
+7
1
Σ
(1)) 2
W
(p) 2 2
g²
4
(E(
(P())))))))\\))))
and conclude miin (J(W))
8 / for any W.
E.2.2 Characterization of a Global Minimum of CutMix Loss In this section, we will check that h(Z) is strictly convex and it has global minimum. For each i,j E [m] and c [P] us define ai.j.s E -B2K+n(P-1) as
ai.j.5 = Σ
(p)
e
j
PES
PBS
and then
M(Z)
1
Σ EsnDs
S P
(gr Z))
1
|S|
e e (ar..s 2i)
n² (.jE(n]
p
Since f(-) is convex. h( ()) also convex. Note that
Vh(Z) n t.jE(m)
Σ
ESnDs
(I 2)) (1-
[8] p
ys (arsss 2)1) ans.
and
V2h(Z)
65

---

1
Σ ESWDS
(16 (" ((viaaa,sss Z)) +
[
|S1
e" (1) 211 an..sahss
n²
P
ES [JEmm]
[ Z))a Z.)
n2
where the last equality holds since (z) = (-z) for any R. From the equation above, it suffices to show that (a..j.s). (CP1) spans p2k+n(P-1) to show strict convexity of h(Z),
(2) We define a function I : [P] - |n] such that for each E P7(p) = with x ((p) = V1 where
the existence is guaranteed by Lemma B.2 (but not necessarily unique). Then for any E [r|] and p E [p], we have
a1,i, +
alighifa) - (P- 1)
(E(P)\()
Σ
E
61,1+ E
e(t??)
- -PP-1)
61,1 e1,1+ +
E
e(o')
P'E[P]
dE(PT\(R}
p'E(P|N(a)
D'E(PIMR)
Σ
c
(n')
+
(P (P- 1)c(d) (p) (P -P 2)
Σ
-P-
ef0')
P'E[P]
P'E(PMMp)
Pe (p)
(34)
Hence, {aij.s) (JE()) spans R2K+x(P-1) and h (() is strictly convex. Thus, it can have at most one global minimum. We want to show the existence of the global minimum and characterize
n (2)
=
Σ
ESNDS
[S] [( (i Zi)+ + (1 p
Uz (ar,s, 2))) as.sss
iJE(m]
= 2 Σ EswDs [15 (1 2)) 2))+ + (1- |S|
yg V (a Zi) 1 pes e
(JE(N) PE[P]
We simplify terms
Σ ES-Ds
[ Ap Z)) + 11--+(110)
[
y, (vy 2i) 1PES
p
3E/m]
[1 Vi Z)) + (1 (1- |8|
Σ ESNDS
y ll (3, (ar,,s 2)) 1 pES
P
jEV;
+
ES-DS
[( (i Z)) )
1
S
y, (y zi)) A
P
jEV-v;
Σ ESNDE [e" (viiaanss Z)) Z)) pesl
y1
JEVn
(((vi(anss)))) 2)) + 1 (1-18) (1))
)) 1 pes
Σ ES-DS
+ Y/
JEV-M
1S] pes
= vı vi
ESSDD
+ Σ
ESwD (vi Z))
1 pes),
jEIm]
where the second equality holds since
(((2) + (((=) (=2)+8((=))
1. Also, for any p [P).
EsnDs
(1-15)
|S] 1
= P
1
Σ
ESnDS [11
S P
1 1,s5
vE(P)
66

---

1 p Bs
1 |5]
9ES
9ES
1 p
1 |S|
P -
ESWND
|S|
P
6P
Hence, if
Σ Es Da (y) [pEs) +
P-1 1
6P 1 =
jE(n]
for all i E [n]] and E [P], then we have Vh 0. Let us consider a specific Z parameterized by
21, 21, 2-1, of the form z!!)) y for all E [n] and p E [P]. We will find stationary point with this
specific form and then it should be the unique global minimum in the entire domain. Then for each
i [n] and p E [P), we have
Σ F (wi 2) jE(n]
Σ Es- Ds [e' (y: (ai,s.. Zi) ppes] +
Σ
ESNDs (y:((ar,, I))sp
jeVu
jEV-N
|Vail RSNDD [L' (Pzy, pEs] + IV- ESSWDg ((((S)2): - -(P (1-))))=-p) pps)
(uull ESNDS 1e' (P))))) + 1V- ESNDS (C(1 Zy:: (P - 1 ) LgEs!)
(E(P)
P |Vul -ESDDs (((2ys)) Σ 19E5
9ES
+/V-a.1 EESDDS e'(1S1zy - -PP Σ 1 ges
QES
(Dizl ESSDDD (SsE +1V=ull ESSDA [|8) (1S) - -P-1181)= P
1
Vul l' (P(z) + |V I' Es-Ds ([S (P -P-118)==
From Lemma F.,, there exists unique minimizer = 1 (e kE(K) U {((1)
PEPP)
of h (Z) and it satisfies så.. 2 O(1) for all k [K] and y:a(p) zng. (1) for all i [n]
and p [P] (xi) due (A1).
E.2.3 Strong Convexity Near Global Minimum
We will show that h b(Z) is strongly convex in set & containing global minimum 2 where G is defined as follows.
G = 2 E (22++(P-1)) : 1 211 < 1x
here 11-1100 is too norm. For any Z E G and unit vector [B with [x(+)))AE[ Ca + [E di e we have
Σ
ESNDS [f" ()) c)
n E.j
(2 (11 n²
Es
i.j
67

---

Note that for each i E [xl], E [P), from (34), we have
( = (c, (c.e = p (1..)
1
Σ (c, (c,
P-1 P
(c, amma))))
P
gE(PM(F)
where the notational convention (pt) Ca for E {=1], k [K] and i E Va,k- By Schwartz incquality and the fact that PSSDDS |S Ds.Ds (S {qHl 2 P(P41) for all
E [P],
(2)0)) 2
2 (c. (
p (c, a.1.))
1
1 Σ
(c,an))))))
P-1 P
=
(E(P](()
P-1
---)
P
)
(c, (c,a..i)) +
Σ
(e, (c.ariohdda)) + (c, (mmma)))))
+
p2
p2
(E(P]M(P)
P-1
P-1 P
P
1 2)
P(P+1)
Σ
ES-Ds (c,, (.,.s))
pz
p
< 22p
Σ
BSnDs [(e, (iss))
Hence, we have
8" (2(111 lxx) (4K + 2n(P - P2n2 (4K 2n(PP-11)
c. CVPM(Z))2
RSWDS [ce, (1sss)
(2
(c(o)²
Σ (E(+I).EE(K)
Eat
Σ
(4K + 2n 1)) p2n2
(2(211|)) lox)
(4K + (n 1)) P2n2
(2(
and we conclude h(Z) is p-strongly convex in G where μ = [4K and the fact that || (1), we have μ 2 poly(d)
Due to (A1), (A2).
E.2.4 Near Stationary Points are Close to Global Minimum
In this step, we want to show that near stationary points of lz))) are close to a global minimum 2.
||
Lemma E. Suppose Z (2Pk+((-1)) satisfies Vh Z)| < μee with some 0 <<< Then,
we have | 2 <E
Proof of Lemma E.I. If Z = 2, we immediately have our conclusion. We may assume Z + 2. Let us define function g ER + as g(t) (2+ (2). Then g is convex and
g'(1) 4h 2 + 1(2 21) z -2)).
(1) z 2) 42h 2 +11(( -
22) (=-1(()))
(2-
|2
Furthermore, for 0 < t < to where to == 2 2-1-2
u 2 Z|².
2 + 12 2) EG,
: ('' 2 /
68

---

We can conclude g is u Z - -|| -strongly convex in 00 fo]. From strong convexity in [0, fo] and convexity in IR, we have
(1a) - - (0))) (lo)) 2 p 1 2 2 ly
- 10) 2
40 < 1, we have
|V [|] 2 - --/12 (vh(Z), -- 2) 5((1) ((bb) 2 M
2
2
2/²²
to:
and
1 z 2
1
|V)(2)I 2 Z 2/ to
2 Z 7
2
this is contradictory. Thus, we have to 2 and Z E G. From the strong convexity of (ZZ) in G, we have
# z 2 - Vh(Z) 4A Vh( [V( < pe,
and we have our conclusion
z 2 <e
E.2.5 Gradient Descent Achieves Near Stationary Point
We will show that LCutMix (W) is smooth function.
Lemma E.2. Suppose the event Einit occurs. CutMix Loss LouuMix(W) is L-smooth with L 97 Po
Proof of Lemma E.2. Note that
Van LCutMix (W)
( (ne( + (1-15))
(S1)
ESWDS
us (1..s((Xessss))
n
p
Σ ø' ((we),efo))) x0 + Edd o' ((w1. (o)))) ) PES
PgS
Let W (w,, i
} and W-
[wi, w } be any parameters of the neural network fw. For any
j E [n] and c [P].
[S| p vi e. (n + (1- (1-16) (
u,e (x
Σ o' (("rr.e("))) (0 + E o' ((ūr, ago))
- -(15
[S) ni (wn.oo (1- (611 (N, (Xis.5))
Σ o' ((w112()))) a!! + Σ d' (( a.li))) ae!"))
PR3
-1s
S8 vi ( (X... + (1- (S1) v, ( (X11))))
Σ rl ((wn, 10
oz (( a(f"")))))) mpp
pes
- -(1s vil' (y (X1,,50)+
[5
(1- (5s)
v, (2 (x,,))0)
p
Σ d' (( x + Σ d' (ed(((,,.)) a( a!!)
PES
69

---

S +(
p ne (nntw ufnte (Xis,s)) (1- p) [ us (us (Xisss))
Σ d' ((Tr))()))) 2.!0 + +I (TTr..f"))) ag!o)
PCB
S8| - p (X.,o()
(1- ( (x
Σ d' ((m)a)())))
m. 10 + + o' ((ml. aqj!) PRS
x
PEB
Since |e"| < 1,
|S|
p will (XiIs) + (1-
|e] p
Usf (u)Sw
11, 1,
and since |00| s 1,
Σ PES
Φ' (1
(p)
x (p)
+ Ed'
0'
(T
(0) z
S P
max
x
(p)
DES
In addition, since o is r -smooth,
Σ Φ' (( (201, . (11)
x
(p)
+
Σ
(( (w)1)o(0)) (01) ))
20/0)
PES
PES
Σ Φ (T01. (((()))
x (p)
ø' ( ( )) 2/(1)
+
PES
PdS
[1i, (w)) ) 8'( ((T)) x (1)
1>
PES
Σ 05 ii, n (p) )) 08 ( (w) (0)) )|
PÉS
Sr-1> Σ
wi wi, xr! (?))) || |
+ +r-1 11 Σ
K (2 11, 20
(p))
|
PES
Sr-1p
max (E()),EE(P) (P)
(p)
||:0 -
and since 8' and @ are 1-Lipschitz, we have
( ss
p ve (XI.s( + (1 |8|
y, Uf (X.sss))
P
( vi (Wisw (X))i)))
(1
|S|
p
15 (Xij.s) fw (X (.)))))
(1<i0- - (p) ) + { [i-) - w x 113)
PES
(wi - w x ( ) ( ( w 1, x (p)
PgS
< P max
| (11ō, - -1,l || + || 11))
[P(N]E[[P]
< 22P
(p)
lww W
max
70

---

Therefore,
Vw, CcutMix W)
Vw, LoutMix W)
2
p
max (E(N),,E[P]
||00
wi + v2p²
max PE|P)
x |
W
W
< 2r
Pp
max (E(
W
w
where the last equality is due to (A1) and (A8). In the same way, we can obtain
()
Vu- CCutMix (W) Vw-, LoutMix W)
S 2pp
max iE(n).PE(P]
W
w
and
V CCuuMMixWW - CittMMii W)
max $ 1p (E(m),pE(1")
W W
S 9r
W 1
Pogd
W
where the last inequality holds since |
o and a² s fogd due (A7). Hence,
CouMMix(W) is L-smooth with L 9r Požd.
Since objective function LCutMix W) is I-smooth and 1 due (A8), descent lemma (see Lemma 3.4 in Bubeck et al. (2015)) implies
CuuMMxx (w(++!))
CoutMix (w(l)= S 1 VLCuMMix (w(*))l?
and by telescoping sum, have
(wrc))} S
2L (W(O))
O(1)
LCutMix
(35)
n/ n/
for any T > 0.
Choose
Then from (35), there exists TCutMix
I
poly(d) such that
polylog(d)
LCutMii (w
|| Scc.
From characterization of mmin (J(W)) in Section E.2.1,
2 V
LouMMix
(W(Tcmmmms)
|||
> Jmin (J (w (W((Commae)))
v/ (omntee) |
vh (CouMM)))
and thus
Vh Z (cussaa)
)||
2 2 lcc polylog(d)
For sufficiently large the RHS becomes smaller than μ in Section E.2.4,
| Then, by Lemma E. have seen
|| 2
oo
Z (Taastix)
2
4
and thus
((weff ((wffcuubii))
xr("))) $
(2)) (Tummma)))))
(ww (Toamin))
- e(1),
for all E [n]] and p [P], and therefore it reaches perfect training accuracy.
71

---

E.2.6 Test Accuracy of Solution Found by Gradient Descent
The final step is showing that (Tembiii)) reaches almost perfect test accuracy. From the results of Section E.2.5, have
(ww) ( (oooMMe Do.k (2)x - ((ui (Touthix)
(w= Vo,k) ((1)
Φ u TourMue) c(p) )) -0 ((
((
(PousMii))
<(())) O(1)
c(p)
18 for each E [+1}, k E i E [n] and p E [P] \ {p()-
For any u > by the mean value theorem, we have
8(u- - v) S (()) o(v) = (u - U) -))(() olu)
S (u u))
Hence, we have
① ((w (wsfcummnn) Vo.kk )) 1 (ww(Toussin) (aik) S 2e (Tooomse)) w
(Toasai)) Us.kk
w TcuuMin) w (Fouatii)) U2,kk S 3-1 (o) (( (ro0 (TouMin)) vask) - 1 (( (w (Touam)) -sskk ((1))ounn)))
and
2(1) S u0 (Tcostii))
u w. (Teustii)
(sskk S 1(
for each E {+1} and E [K]. Similarly, for all E [n] and P [P] {pī}.
Φ (( (w (Taaaax)) c(P) )) @ ((we (10_ (Toummii)))
((P)) S (0 (TeutMix)) w (Toabiii)
c(p))
w (Teumia) w -v
(Teuessiv)
(p) s 3-1 (o ((ro)) (TmmMii))
c(r) ) -
- ((w
(Toue)ix)
(())
-Bi
and
2(1) < (w! (Teumii)) w
(Tem c(1) 50(8-) M1
By Lemma B.3,
w (Temmie)
(TeotMix)
w (0) 1
w
(0)
Σ
k)osk
Σ
yipli,p)
(p)
=((=1),kE[A]
where for each s E {+1}.
(s, 1) ?1 (TonmMii)
(s, 1) + 7-1 (TouMMie) (s,
(Toussis) ) Σg yb (pl (Toustis)) (i,ps) + p- (1, (i. |s(00)] iEF
and
(ss k)) = 71 (Teamiix) (s, (s, + 7 (Tonmrix)) k)),
p(i, p) = Pi (Tousau)) (i.p) + p-1
(Tousuin) (i,p);
for each E (+1}, [K]] (1)iE [n] and p E [P] \ (x7). If we choose j E [m], E [P] {oj}
such that p(j.4) max p(i, p), then we have
(Teatiix)
(TeuMia)
(())
w g5
w -13 vj
(())) g())))
w (0)
w
(0) ( u₁
15
+(..gg) + +
Σ
Hip(i, p)
(p)
(EIN), (1.))
72

---

From the event Emit defined in Lemma B.2, (A8), and (8),
(w---"
(polylo(d) - w - =
(poolyyo 1
(Toomii)
(Tottii)) c(9)
w
W -ys
2
86
where the inequality holds since inequality, we have
( (w)) (Temaaii)
20
(Toumia))
c(A)
-[(1). In addition, by triangular
Uj
( -5/00)
(5500 -5,)))))))))
Σ (E)))) ((.))/(i.))
Hepli.p)
E
pli,p)
|
||<(0| |
PEPPNNt ((-))
p(j.9)
S p().))
S -/4)) - 3p(j.9)
2
where the last inequality is due to (9). Hence,
3 g((.. q) s ( (w (Tmmsii)
(TeatMix)
w -B
and we have p(j.9) - )
Let (X,y) D be test data with X (x.")...,, (P)) RdxP having feature patch p'. dominant noise patch p. and feature vector yy.k. We have (()) ~ N(0, AfA)) for each E [P] {p" .p) and (8) - cres,1 ~ o3 for some & E [+1]. Therefore, for all p E [P] {p" 5}
.....
w (Teumia)) xx(p)) )) Φ ((w0 (Toussa) x .z(()) ))
Φ
<
W
(TeatMix)
(Teussei)) x x0(1))
p(i.g) (5/ xx(1))
K 10 (0)
w 10)
)
Σ
=
| 12
(E(n),nE(P|N6)) (OPSpnP n 11p3-1000p- ld
s δ (oponot)
+ 6
polylog(d)
(36)
with probability at least
- poly(a)) due to Lemma B.2. In addition,
6 w .x(())
(
(TearMiv)
((
(TowMMie)
x())
w
mi (TullMi))
w (ToutMin))
se(01)
[ (IcorMix) w (2,1) > + w
(Teussei))
(ToarMi))
(TeutMiz) (1) - -cvs.1) |
< a
w
$ a,3 a,3-1/6 |0| ((ue (CouEMii)) vo..1) )ea1)) - ①
((w)
(Tommix)
, (vs2)) )
110
p(i,g) ((/
2 x00 av..)
+ <w0
w (0) (0) crvs.)) )|
Σ
11
((9) 2
PELPMM))
< ① (aB-1) δ (ooadd)) + + (0:0npp-oaae 10000
=o 1
polylog(d))
(37)
with probability at least 1-o (poly(a)) ) where the last equality due to (8), (9), (10), and (A8).
73

---

Suppose (36) and (37) holds. Then,
y Vfw(Toumm (X)
= ( ( w0 (Poeeree Vy.k) )) @ (nw0 (ousss)))) . (orkk)
E (o (0((w0) (ommmin)) xelo)) o ((w (1 x x(lo))
+
PE(PR(M
= 2(1 polylog(d)
0.
Hence, we have conclusion.
74

---

Technical Lemmas
In this section, we introduce technical lemmas that used for proving the main theorems. We present their proofs here for better readability.
The following lemma is used in Section C.2.4 and Section D.2.4:
Lemma E.1. For any 2, 6 I.
10(z) - (z +
16).
Proof of Lemma F.l.
2 1-0 --1-0 1-1
1
Φ(z) -00))2)(22)
1-8 22 + 82z
2r
- 2
+
2
2r
22
if0 if
(32 - B2 =0
if=<0
and we obtain
1- 8 2
lØ(z) - 0) 10(2) 20((2) (z)]
+ 16 Sr+
The following lemma is used in Section C.2.4. Lemma F.2. Suppose Fiuit occurs. Then, for any model parameter W = w0 1) we have
VW Σ ((Un/w(x:))
$ <8P2 Valal
Σ
Uyyisw(X) (X:)),
BEV.k
iEVe,
for each E {+1) and k E [K].
Proof of Lemma F.2. For each s E {+1} and i [n], we have
w (x:)II
Σ o' ((ws, ao.) 10 PE(P)
max S
2Po
p
where the inequality is due to the condition from the event Emit defined in Lemma B.2 and (A7).. Therefore, for each {=1], we have
V w.
Σ ((nff((X)) .EV.,
Σ l' (X.)
iEV..
2
Σ
E' (x)) fw
iEV
< 4P2
Σ (vnf((Xi))
iEVi,
<dP2
Σ
(E (X.))())))))
VEVeR
< <4Po
Σ (x.lw(X.))
VEV.,
The first inequality due triangular inequality, the third inequality is due to Cauchy-Schwarte inequality and the last inequality is due to 0 < -I" < 1, which can be used to show (E')² < El' < E. As result, we have our conclusion:
VW Σ ((iff
Vwe Σ ((rrf((Xi))
+ Vo- Σ ((rif((Xi))
=
iEVo,
LEV.N
75

---

S 8PPo2d(Vs. (Juff(X.)).
Σ ieVi,
The following lemma is used in Section D.2.4. Lemma F.3. Suppose Emit occurs. Then, for any model parameter W {(1,, w w-1), we have
(X Be (y (X
8P8 oPPooidVa.s
Σ
Be ([yv:fwo (X
SEVs,
iEV..
for each {+1) and k E [K].
Proof of Lemma F.3. For each & E {+1}, E [m] and c [P] with [C] C. we have
Ww..f((x.c))
Σ o' ((ws. x0!0) pPc
S
max PE[P
x
S
2Podd
where the inequality is due to the condition from the event Ena defined Lemma B.2 and (A7). Therefore, for any E {=1}, we have
V u.
Σ
(Xi,)))
LEV.,
EENDE (v:fw(X,.)) V Sw
iEV..
EenDe 1e (vifw(X Jw
VEV.n
2
S 44p2 od
ECNDD It' (Jifw(X,e)))
iEVi.k
<4p2
EenDe
[(e' (Xae))
ieV..k
S S4
Σ VEV..
EenDe (J.Sw (I.Sw(Xxc))],
The first inequality is due to triangular inequality, the third inequality is due to Cauchy-Schwartz Schwartz inequality and the last inequality is due to 0 v -f" < which can be used to show (E))2 < - 8f < f. As result, we have our conclusion:
VW Σ ECnDe (viff(Xi.o) ieVi.
EenDe (Xac))
+ Vw-n Σ ieV..
EewDe (eyff(((
iEVa.k
8/2 1220
EcnDe [(x,ff(Xx.)))...
76

---

The following lemma guarantees the existence and characterizes the minimum of the CutMix loss in Section E.2.2.
Lemma F.4. Suppose the event Einit occurs. Let 91,9-12 R x R + I be defined as
(0(21,2-1) [Vol [V-s] (Pzs) +
2 - p
P-1 1
PESWD ([S) ( -81))_]=-)] +
3P
for each 8 E {+1}. There exist unique 27, 22, > such that gı = 9-1(22;, = 0.
Furthermore, we have 2i, 2-= (1).
Proof of Lemma F.4. For each 21 > 0,
V-11
2 p
P-1
0-1
+
1
+
Ds (|P)(((((--1()a)))))
2
3P
[--1
P
+
+
< 0
[V]]
3P
since (z) < - for any x S 0 and we use
26 52"
S
Vil, |V-1 <
27 from the event Enit defined 52
Lemma B.2. In addition,
g (2), P21 + log
|-1l l' (((2 21 Plog 9) + ES [|S((((S)P |8| (P (P-[S])a]]] +
2
P-1 1
3P
V-11
+1) 8 (log 9) + P-1
[il
3P
0,
where we use
25 52"
< 111. V-11 <
27 from the event Emit defined in Lemma B.2 and (A1) for the
52
last inequality.
Since = + 9-1 g- 2) is strictly increasing and by intermediate value theorem, there exists S (0, 00) - oo) such that = S(=1) is unique solution of g=1
and S(21) Pzi + log 9. Note that S is strictly increasing since g-1(21, z-1) is strictly decreasing with respect to 2 and strictly increasing with respect to 2-1. Also, if S(z) is bounded above, i.c., there exists
some U > 0 such that S(z) S U for any > 0,
lim 9- g- S()))
(1/_al e' (PS(())) 2 |
P
lim
ESNDS [1S((())( (P- (81)=]]
2-000
3P
[V-1l l' (PU) ES [IS) (P-11[)=))
2
P-
lim
20000
[V]]
3P
2 ESnDS [[S] 1s
P-1 p -1 P-1
< p
P+1 1 + 3P
3P
<0
and it contradictory. Hence, we have lim S(2) oc.
Let us choose z > such that
3P 1+
14 Pi_1
z p
log
P-1
and thus
P-1
((Pz)
3P 1 +
Mil
|--1
We have
|V]
P-1
(1 S(x) =
8' (P2) + ESnDs | - -P- (S))((()())
+
[__
p
3P
77

---

Mil 1-11 +1 / ((2)) +
P-1
3P
= 0.
Next, we will prove the existence of 2" > 0 such that 91 (,",,(z"")) S(2))) > 0. Let us choose e >> 0 such that
3P(P+1)IVL)
1)
P(P P(P+1)IV21
c- max
(P-2)(++2))2)
+2
P-2
'2
1+
(P (P- (P-1)(P-2))00 2))p1]
12P
|-11]
12P(P 11)
(1+ [1]
1+
(38)
P-7
M (P - P) + 2)
V-11
and note that ((1) Since limm--2o S(z)
xi, can choose z² such that
L' (3 min (z*, S(²)))
3.- Then, for any 2 2. we have
-6 <<< (1) <0 and -1 < (-1) -1
(39)
From the definition of S and (39) with t = PS(=*) Y m ,((z"),, we have
P
[1-11 l' (PS(=)) + P-1)
ES-Ds [1S(((1))(())) - -P [8])=*]] - 2 [
3P
P- 1 +
PIV-11
(40)
2
If S(*)) - (P- 1)2² 2 0, then
PS(=") > (P 1)5(z²) - >'... 25.xx) - (P- 2)="
= + 8(²)) + S(2") - (P 1)
2 + 88()) 2 minf 2nn S{()))}
2
and we have
P-1 PIV-I
e <> ESNDS
- [[P(((())(()-(P-155
6
2
P
1
('(S(2)) - -(P - -1)2") + Σ
mL (mS(2²) (P- (+-m)22))) mm2²))
P+1
m=2
1
1
(P(P+1) -1)c) -)).)
P+1
2
2
where the last inequality is due to (39). This is contradictory to (38), especially the first term inside
the maximum, and we have S(z*) (P - 1)2² < 0. In addition, if (P - 1)5(=*)- x" < 0, then
P= > (P- - 5(x²) >
......22.. 22 - (P- -==)((²)
= -5²" + === - -))(2)²
2 + S(x") 2 2
"minfz" {{²")
and we have
P-1
PIV-11
6
2
< ESWDS
[[S] -PP))=
P-2
1
(PS((()))) +(P - (P-1))((2)) - x²) + Σ
ml (mS(=*)- - -P-- m)=²)) -P-m)==)
P+1
m=
1
1)(P - 2) (P- (PP
P - 1
[1 é)
P+1
2
2
78

---

where the last inequality is due to (39). This is contradictory to (38), especially the second term inside the maximum, and we have (P- 1)5((*) 2- 0. Note that we have
2/2 = ( min "ainf=",(="")) .((2)) 2 1
2
2P
and since c = (1) in (38), we have 2" 2PPlog (2 - = -
Thus, we have 5(=)) - (P (P 1)= <0 < -P- 1))((=))
P=((=)) One consider dividing the interval (=²=) - (P - PS())) into grid of length x" + S(²*). Then, the interval is
equally divided into p sub-intervals and 0 belongs to one of them. In other words, there exists k E [P 2] such that
k=(= (P - k)=² < 0 < (k + 1)5((z)) - (P - k ---k--1p 1)=",
and note that if P = 3. then k = 1. The rest of the proof is divided into two cases: (k 1)5(2*)
(P- - k- - 1)2² 2 (2 + -(=)) or (k- + 1)5("*) - (P- - k 1)2" < == + S(=")). ) In both cases,
show that 91 91(=" 5)=))) > 0.
Case 1: (k+ + 1)) - (P- - k 1)2² 2 2/22" + S(x)))
From (39), we have
-1 <
(--P2)) <
<... ........... ... < ([)x=))((=))) - -P- h 1))=") < <11+
and
- <<< + +))((²)) - (P- - k -- 1)=*) < ..... < <((P((=))) <0.
Thus, we have
BS-Ds [18)((())((2')) -(P- 181)=')\1|
1
kE(KS(=") - - -))) k(k kkk-1)
P
P+1
2
and we obtain k
P-1 since
1:k + 1)
2
k(k - 1)
+
2
P(P + 1)
6 1)B+ - (1S - (P--1)))=))
2
+
- +
P(P+1)
[-11
(P
1)(P+1) +1)
|+
6 +
2
M
6
P-1 P-1 2 +1)
where the second inequality is due to (40) and the fact that L' 1, and the last inequality is due to (38), especially the third term inside the maximum. Note that since k E N, k 2 2.
Note that from (39), we have
-1 -1 (<<E(-SSI PS(=))) <... <.)"="))<<<.<<..)) < k
k 1)2² (k+ 11++1)3 1)5(2))) <11+c
and
( k k+ 1)2" - (k - 1)2²) .... <.....<(0 <((2)') <0.
Hence, we obtain
ESwDs
[S]{([))=" - - -811((((()))
1
(P- k -P k)
1 (P- k) - -(P k + +
+P)c
P+1
2
2
79

---

(P- 2)2
1
1))
2(P + 1)
P+1
2
p2
P
1(P+1)
-
where we use h: 2 P. for the last inequality. Therefore, we have
2
= |
2 (1 +
P-1
1V-1 ((p=') +
p
3P
|-11 + +1) 6 4(P +1)
Vil
P P-1
2
3P
00
where the last inequality is due to (38), especially the fourth term inside the maximum. Case 2: (I + 1)5((²) - (P- k- 1)2* < 5== + 5(*))
In this case, we have k:5(z)) - (P - k)2² S -/= + +(=))) From (39), we have
-I<((--=='<< <... < < <1S((2))) - (P- - k)2²) < +c,
and
-E< +<<<(((+))(())) (P - k - 2-))2) < ... < (PS(())) <0. O.
Thus, we have
ESNDA (o((((((((((()((E))) (P- -(1) 1>|
1
(k (k+ ( 1)8(2") (P k - 1)2²)
k(k 11)
P
P+1
and we obtain k >
P-1 since
(k + 1)²
2 k:kk + 1)
+ ++1
2
2
P(P + 1)
- (P (P++11Bs-,(1(((((11555 - (P- [81)=*)
2
+ (k + +1))((( + +)S((=)) - -PP-)= 11) 1+1
2
1(P+1)
(1+
|-11
+ (P +1)
2
M
PP-1 + +1)² 2
2
where the second inequality is due (40) and the fact that (()) > -1 Vz and the last inequality is due to our (38), especially the third term inside the maximum. Note that since l E N.
we have 2 2
Note that from (39), we have
-1 -1< E (PP((2))) <...<< E ks - 2)²² (k: ( 2))((())) < <1
and
E < E k)2² k2*) < <... <...<<.. (((2") <0.
Hence, we obtain
ESnDs ()5))((((((())1 - (P- -0)s())((")]
1
(P- (P- k (P k) ((P - k) + + pP)
P+1
2
80

---

(P- k)(P- - 1-
P(P +
2(P +1)
P+1
2
(P- k)2
P(P+1)
2(P + 1)
P+1
2
p2
P
8(P +1)
2
where we use ho 2 P for the last inequality. Therefore, we have
Pil |V-1
2 ESSDD -PP-
P-1 3P
(===",((=))
((p=')
2 |--1 +1)
[11
P P-1
c-
4(P
3P
> 0,
where the last inequality is due to (38), especially the fourth term inside the maximum.
In both cases, have 91 ( S(=))) > 0. By intermediate value theorem, there exist unique
zi ==1 > such that gi (z x-11 = g-) x=1) = O. In addition, a S < S =" and we have
((1) since 21) and x² = O(1). By using a similar argument, we can show that
2-1 = (1), and we have our conclusion.
81

---

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 accurately reflect the paper's contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitation on our problem setting and theoretical framework in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
82

---

Justification:
We provide the full set of assumptions and a complete proof in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide detailed descriptions of the experimental setting in Section 5 and Appendix A.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
83

---

Answer: [No]
Justification: We do not provide open access to the data and code since our main focus is theory.
Guidelines:
The main focus of this paper is theory.
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: httppssccppplllc//ee Seeguddee/ooeeeeeeeeeee
ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
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: We provide detailed descriptions of the experimental setting in Section 5 and Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The main focus of this paper is theory.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
84

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
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: We provide the type of compute workers used (NVIDIA RTX A6000) in Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///eeur./eeeeeeeeeee cc/ hpppppic/ttiis//iiiiieepp
Answer: [Yes]
Justification: The research address to the NeurlPS Code of Ethics, ensuring ethical conduct throughout the study.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
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 mainly focuses on establishing a theoretical understanding of existing data augmentation techniques. Thus, there are no direct societal implications arising from the research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
85

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not involve the release of data models that pose high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
86

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
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 not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
87

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
88


Reviews:
[{"review_id": "yHDJdePkoz", "reviewer": "Reviewer_hATA", "summary": "This paper theoretically analyzed the benefits of two data augmentation techniques, Cutout and CutMix, for feature learning of two-layer and two-neuron convolutional neural networks. The authors considered an ideal data distribution in high dimension with one feature patch, one dominant noise patch, and some background noise patches, where the feature patch is generated by three different features in terms of the population: common, rare, and extremely rare features. This paper showed that classical training dynamic without data augmentation achieves perfect training accuracy but performs poorly on rare and extremely rare features, leading to low test accuracy; Cutout training achieves perfect training accuracy and learns rare features better than ERM, but still struggles with extremely rare features; and CutMix training achieves near-perfect performance by learning all features and noise vectors evenly, resulting in the highest test accuracy among the three methods. The paper validated the theoretical findings through extensive numerical experiments and real-world data experiments on CIFAR-10, showing that CutMix achieves the best performance in terms of test accuracy.", "questions": "1. In Section 1.2, it would be better to include more recent work on feature learning theory. For instance, some references are below.\n\n2. In Cutout training, based on your analysis of training, is there an optimal choice of hyperparameter $C$? Can we set $C=0$ in Theorem 3.2 to get Theorem 3.1?\n\n3. In Section 2.4, why do you assume the number of data points $n$ is much smaller than the feature dimension? Is it because of the over-parameterized model? And how about the large learning rate $\\eta$ case, for training dynamics? Many previous papers [Yang and Hu. 2020, Abbe, et al. 2022, Ba, et al. 2022] have shown the benefits of large learning rates to obtain feature learning. Moreover, how do you assume $K$, the number of orthogonal feature directions?\n\n4. In (4), a typo in $w^{(t+1)}_s$\n\n5. The proof strategy of CutMix training is to find the global minimizer directly. Does this strategy also work for ERM and Cutout? Can this method generalize to wider neural networks and more general datasets?\n\n6. In Lemma B.3, the statement is not complete. You define the $\\gamma_s^{(t)}$ and $\\rho_s^{(t)}$ later for different cases, separately.\n\n-------------------------------------------------------------------------------------\nYang and Hu. 2020. Feature learning in infinite-width neural networks\n\nAbbe, et al. 2022. The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks\n\nBa, et al. 2022. High-dimensional asymptotics of feature learning: How one gradient step improves the representation.\n\nBen Arous, et al. 2021. Online stochastic gradient descent on non-convex losses from high-dimensional inference.", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provided a novel theoretical framework for understanding the benefits of Cutout and CutMix, filling a gap in the literature where empirical success lacked a theoretical explanation. The presentation of the main theorems (Theorem 3.1, 3.2, and 3.3) is rigorous and clearly shows the differences in learning dynamics and performance between ERM, Cutout, and CutMix..", "weaknesses": "1. The use of a feature-noise data model to analyze the effectiveness of different training methods is restrictive. This feature noise patch data ideally separates the noise and feature orthogonally and enables us to consider the dynamics of the weights in feature and noise directions separately. However, in general data itself may contain some useful nonlinear features, which may not be characterized by this ideal model. It would be better to provide more motivations for this data assumption and present some real-world datasets exhibiting common, rare, and extremely rare features simultaneously. Besides this analysis only considered binary classification setting. \n\n2. The asymptotic choice of the hyperparameters in Section 2.4 is not natural. While analyzing high-dimensional limits is necessary for the theoretical analysis, the practical implications and sensitivity to these hyperparameters should be better addressed. Including a more detailed discussion or empirical validation of these assumptions would be better. Additionally, the paper could provide more guidance on how to choose the hyperparameters (or the scaling) in training and data augmentation for practitioners. \n\n3. There is limited discussion on the computational costs associated with implementing Cutout and CutMix compared with ERM. Including a theoretical analysis of memory usage, time complexity, or other computational costs would help in understanding the trade-offs involved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude for your time and valuable comments. We also thank you for bringing to our attention the typo in (4) and unclear statement in Lemma B.3 (we intended to claim the “existence” of such $\\gamma_s^{(t)}, \\rho_s^{(t)}$ for each training method). We will fix/clarify this in our next revision. In the following, we address the points raised by the reviewer.\n\n## **W1. Motivation for data**\n\nWe provide motivations with examples for our framework in our global response. We would appreciate it if you could refer to it.\n\n## **W2, Q2&3. Choice of hyperparameters**\n\nWe assume the number of data points $n$ is much smaller than the dimension $d$ which corresponds to the over-parameterization regime common in modern neural networks. This allows us to apply high-dimensional probability theory effectively, as you mentioned. \n\nThe assumptions on hyperparameters, such as the strength of noise and the frequencies of features, are designed to highlight the distinctions between the three training methods by satisfying the inequalities outlined below line 280. The choices for other hyperparameters are made to ensure convergence within our specific setting. These types of assumptions are also considered in several related works [1,2,3].\n\nAlso, we do not impose a strict condition on the total number of features. More important thing is the frequency of each feature rather than the total number of features. Any value of $K$ is possible as long as each $\\rho_k$ can satisfies given conditions.\n\nEven though most choices of hyperparameters arise from technical elements of our proof, we can provide intuition on choice of cutting size $C$ in cutout. Our intuition behind Cutout is that it outperforms by removing dominant noise, which do not generalize to unseen data. Thus, $C\\geq 1$ is necessary to ensure that the analysis of training dynamics differs from that with $C=0$. The proof strategy for Theorem 3.2 heavily relies on the condition $C\\geq1$. Hence, setting $C=0$ in Theorem 3.2 does not derive Theorem 3.1 directly. \n\nIn practice, image data contains features and noise across several patches. A larger cutting size can be effective in removing noise but may also remove important features that the model needs to learn. Thus, there is a trade-off in choosing the optimal cutting size. From this intuition, we believe that for images with a larger portion of background(noise), a larger cutting size is likely to be more effective.\n\n## **W3. The computational costs**\n\nSince our work does not focus on proposing novel algorithms, we believe that a discussion on computational and memory costs is not essential and should not be considered a weakness of our work. However, we address this concern here for the reviewer's benefit.\n\nIn the practical implementation of Cutout, a squared region is randomly sampled and this same region is cut from all images within a batch. Similarly, in the implementation of CutMix, a squared region is randomly sampled and then used to cut and paste parts of pairs of data batch and its random permutation. Consequently, the computational and memory costs involved in each iteration of both Cutout and CutMix are comparable to those of vanilla training, differing only by a constant factor. \n\nIn our theoretical setting, we consider training using full-batch gradient descent for ERM, and gradient descent on the expected loss for Cutout and CutMix. These idealized training methods involve higher computational and memory costs per epoch since they require more augmented data. For example, Cutout requires $\\binom{P}{C} n$ data points and CutMix requires $2^{P-1} n^2$ data points. However, we would like to emphasize that this setting is designed for a theoretical understanding; as outlined above, the practical versions are not computationally burdensome.\n\n## **Q1&3. Recent works on feature learning theory**\n\nThank you for suggesting recent works on feature learning theory and for raising questions related to comparisons with these literatures. We were not familiar with these works and have noted that they are somewhat orthogonal to our work due to differences in the definition of “features” compared to our approach and other related previous works. \n\nThe notion of features in our work refers to label-relevant information contained in the input that is useful for generalization to unseen data. In contrast, the notion of features in the works you suggested seems to be relate to the outputs of the last hidden layer (i.e., the representation of data point learned by the network). This distinction suggests that the concepts of \"features\" in these studies differ from those in our approach.\n\nWe believe that a large learning rate has less impact within our notion of feature learning since it does not affect trend in learning speed of features and noise which is essential as we described in Section 4.1.\n\n## **Q5. The proof strategy for CutMix**\n\nThe proof strategy for CutMix cannot be applied to ERM and Cutout because their training loss lacks a global minimum due to the exponential tail of the logistic loss ($\\lim_{z \\rightarrow \\infty} \\ell(z) = 0$). In contrast, CutMix loss has a global minimum due to its use of mixed labels ($\\lim_{z \\rightarrow \\infty } \\ell(z)+ \\ell(-z) = \\infty$).\n\nSince main idea of our strategy is considering the training loss as a composition of reparameterization and convex functions, we believe that this technique could be extended to a broader class of architectures, datasets, and training methods involving mixed labels. However, the exact characterization of the global minimum in different settings would require techniques beyond those we have used.\n\nThanks for your time and consideration.\n\nBest regards,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "udMF6vpwap", "reviewer": "Reviewer_mYpt", "summary": "The paper aims to provide a novel theoretical insight into the training dynamics of data augmentation methods such as Cutout and Cutmix. It also supports theoretically why Cutout and Cutmix perform better than ERM by showing that the ERM training is unable to learn rare and extremely rare features and that ERM can fit perfectly on the training data while being random on the extremely rare data. Thus the key contributions can be summarized as:\n\n**Comparative Analysis**: The paper reveals that Cutout outperforms ERM by facilitating the learning of rarer features, which ERM fails to do (Theorem 3.1 and Theorem 3.2). CutMix is shown to achieve nearly perfect performance by learning all features (Theorem 3.3).\n\n**ERM Limitations**: The authors propose that the negative results for ERM stem from its tendency to classify training samples by memorizing noise vectors instead of learning meaningful features, particularly when features do not appear frequently enough.\n\n**Cutout Benefits**: Cutout mitigates the challenge faced by ERM by removing some of the strong noise patches, thus enabling the learning of rare features to some extent.\n\n**CutMix Mechanism**: A novel technique to analyse the training dynamics of CutMix. This technique views the non-convex loss as a composition of a convex function and reparameterization, allowing characterization of the global minimum of the loss. It shows that CutMix forces the model to activate almost uniformly across every patch of inputs, facilitating the learning of all features.", "questions": "1. **Definitions**: The definitions of common, rare and extremely rare features are central to the story and contributions of the paper. However, they are not explicitly defined anywhere in the main draft.  I assume there must be some condition on probability $\\rho_k$ for a feature to be rare and extremely rare. Defining these in problem formulation will help improve the readability of the paper significantly. \n\n2. **Model Definition**: The current model definition is not 2-layered CNN in my opinion since it does not contain a hidden layer. I can summarize the model definition as $f(X)=\\[1, -1\\]^T\\phi(\\mathbf{W}\\mathbf{X})1_{P}$. Where $\\mathbf{W}=[w_{1},w_{-1}]$ and $\\mathbf{X}\\in\\mathbb{R}^{d\\times P}$, this is akin to a single-layer network. \n\n3. **Simulation Evaluation**: About the numerical simulations, the common features are defined as frequency 0.8, rare as 0.15 and extremely rare as 0.05. Is there any reasoning or theoretical justification to do so? What happens when we change the frequencies of these features to skew them further? Is the assumption that extremely rare feature frequency is rare only in the training and at test time there exists another distribution? Otherwise, why is the low performance of ERM on extremely rare features negative? Also, for Fig 1 (leftmost plot) it is not obvious why Cutmix is non-monotonic here. It rises and then plateaus, perhaps authors can change the plot scale to appropriately demonstrate this point.  \n\n4. **Real World Evaluation**: I find the real-world evaluation for the theory extremely lacking. It need not be extensive with many datasets but in the current CIFAR-10 experiments, there is no intuition from the perspective of common, rare and extremely rare features. A similar experiment to simulations on CIFAR-10 would support the point of the paper much better. \n\n5. **Visualisation of extremely rare features**: What would the visualisation of extremely rare and rare features in the case of CIFAR-10 look like? If possible can authors visualise the features learnt by ERM trained and CutOut and CutMix? This would show that extremely rare features learned by cutmix are indeed interpretable, thus important for generalisation as compared to random noise in the dataset.", "limitations": "The major limitations of the work are in its choice of definitions, namely model definition and definition of extremely rare features.\n1. Limitation of model definition: I am sceptical of the current conclusions generalising to networks with more layers since the current model definition is not really even 2 layered. \n2. Limitations of extremely rare features definition: Based alone on the frequency of a feature in the dataset, one can not distinguish noise from extremely rare features unless we have access to the data-generating process, which is often not the case in the real world.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "What I like about the paper:\n+ It addresses an important aspect of better understanding data-augmentation methods like Cutout and Cutmix. \n+ It is theoretically well-motivated.\n+ Provides a simple explanation of common features ≫dominant noises≫ rare features ≫background noise≫ extremely rare features for ERM training dynamics.", "weaknesses": "- I believe the writing of the current draft version can be further improved. (see questions)\n- The modelling assumptions about 2-layer CNN are questionable. (see questions for further discussion)\n- The theory needs further experimental evaluation (real-world experiment on CIFAR-10 is uninformative to the story, see questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude for your valuable comments.  In the following, we address the points raised by the reviewer.\n\n## **W1, Q1. The definitions of features**\n\nPlease refer to our global response. We describe these features in Section 2.4, but we acknowledge that discussion near Definition 2.1 would be helpful to readers. We plan to include a more detailed explanation of these notions in Definition 2.1 in our next revision.\n\n## **W2, Q2, L1. 2-layered CNN**\nWhether our network is 2-layer or 1-layer may depend on the perspective. Following existing works [1,2,3] in the literature, we regard it as a 2-layer CNN, where the weights in the second layer are fixed at 1 and -1, making only the first layer trainable. In addition, we agree that extension to a deeper neural network is not straightforward. However, we believe that our work sheds light on the benefits of patch-level augmentation, making it a valuable contribution. We will leave the extension to deeper networks as future work.\n\n## **Q3. Numerical simulations**\nOur choice of frequencies is intended to highlight the distinctions between the three methods. Our findings suggest that applying Cutout and CutMix lowers the “threshold” for the frequency of a feature’s occurrence required for learning it. When we reduce the frequency of a feature from 1 to 0, initially all three methods can learn the feature. As the frequency decreases, ERM may fail to learn the feature while Cutout and CutMix continue to succeed. At even lower frequencies, only CutMix can learn the feature whenever it appears in the training data.\n\n## **Q3, L2. Confusion regarding extremely rare features**\nWe believe there may be some confusion regarding extremely rare features. We have provided explanations with examples for our framework in our global response, and we encourage you to refer to it. We address remaining questions here:\n\n>**Is the assumption that .... extremely rare features negative?**\n\nOur training and test data distributions are identical. As detailed in our general response, learning more features generally improves performance. Although data with extremely rare features make up a small portion of the test distribution, learning these features can enhance test accuracy on that data, leading to overall test-time performance improvements. Thus, low performance of ERM on (extremely) rare features is negative for overall performance.\n\n>**Limitation. One can not distinguish noise from extremely rare features**\n\nWe think the reviewer may have confused. Extremely rare features are also label-dependent information that can appear nontrivially many times (albeit relatively rarer) across several data points, while similar or identical noise patches hardly reappear across different data points.\n\n## **Q3. Non-monotonicity of CutMix**\nIn Figure 1, the leftmost plot shows that the curve for CutMix initially rises, then slightly decreases before plateauing. This indicates a non-monotone behavior for CutMix, in contrast to the other methods. Let us clarify why: Due to the use of mixed labels, CutMix loss has global minimizers and they evenly learn all kinds of features. In the early stages of learning, the model tends to overshoot in learning common features because of their faster learning speed compared to other features. This initial overshooting leads to a temporary rise and subsequent decrease in the curve. This non-monotone behavior is precisely the reason why we had to devise a novel proof strategy different from ERM and Cutout.\n\n## **W3, Q4, Q5. Real world evaluation**\n\nWe experimented on CIFAR 10 to support our findings and address the reviewer’s concern.\n\nWe train ResNet18 using vanilla training without any augmentation, as well as with Cutout and CutMix, following the same experimental details described in Appendix A.1, except using only 10% of the training set. This data-hungry setting is intended to highlight the benefits of Cutout and CutMix. We then evaluated the trained models on the remaining 90% of the CIFAR training dataset. The reason for evaluating on the remaining training dataset is that we plan to analyze the misclassified data using C-score[4], which is publicly available only for the training dataset. \n\nC-score measures the structural regularity of data, with lower values indicating examples that are more difficult to classify correctly. In our framework, data with harder-to-learn features (corresponding to rarer features) would likely have lower C-scores. Since directly extracting and quantitatively evaluating features learned by the models is challenging, we use the C-score as a proxy to evaluate the misclassified data across models trained by ERM, Cutout, and CutMix.\n\nFigure 2 in our attached pdf in our global response illustrates that Cutout tends to misclassify data with lower C-scores compared to ERM, indicating that Cutout learns more hard-to-learn features than vanilla training. Furthermore, the data misclassified by CutMix has even lower C-scores than those misclassified by Cutout, suggesting that CutMix is effective at learning features that are the most challenging to classify. This observation aligns with our theoretical findings, demonstrating that CutMix captures even more difficult features compared to both ERM and Cutout.\n\nSince directly visualizing features learned by a model is challenging, we present data that was misclassified by the model trained with ERM but correctly classified by the model trained with Cutout instead. In Figure 3 in attached file, we show 7 samples per class with the lowest C-scores, which are considered to have rare features. Similarly, we also visualize data misclassified by the model trained with Cutout but correctly classified by the model trained with CutMix to represent data points with extremely rare features. This approach allows us to interpret some (extremely) rare features in CIFAR 10 ,such as frogs with unusual colors.\n\nThanks for your time and consideration.\n\nBest regards,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DzQxPFJ9oh", "reviewer": "Reviewer_pSne", "summary": "- This paper investigates the effectiveness of patch-level data augmentation techniques, specifically Cutout and CutMix, in training two-layer neural networks. \n- The study compares vanilla training, Cutout training, and CutMix training using a feature-noise data model. \n- The findings show that Cutout can learn low-frequency features missed by vanilla training, while CutMix can capture even rarer features, resulting in the highest test accuracy.\n- The analysis reveals that CutMix enables the network to learn features and noise vectors evenly, offering new insights into patch-level augmentation.", "questions": "- What insights can be gained from the theoretical analysis presented in the paper? Can this help in developing better patch-level data augmentation techniques compared to existing ones?\n- The paper specifies that the NN architecture used is a 2-layer CNN, but shouldn’t it be considered a 1-layer CNN?\n- Additionally, the weights W exist only for each class individually. Is it not possible to perform a more general analysis with C channels, as done by Shen et al.?", "limitations": "There is no specified section for limitations in this paper. The checklist includes a brief explanation, but the corresponding details are not found in the main paper.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- This paper provides a theoretical analysis of how Cutout and CutMix (i.e., patch-level data augmentation) \bimprove feature learning. \n- It specifically explains what features each method learns during the training process, offering deep insights beyond empirical results.", "weaknesses": "- While this paper provides a theoretical analysis of patch-level data augmentation methods, it only analyzes Cutout and CutMix, leaving other related methods for future work. \n- The theoretical analysis of this paper is expected to offer insights into practical applications and performance improvement, but it lacks detailed discussion in this regard. \n- It would be beneficial if the paper could provide more meaningful insights to the readers beyond providing a theoretical analysis, which is the most significant shortcoming of this work.\n- It is suggested to simplify the content of the “assumptions” summarized in Section 2.4 (with detailed explanations moved to the appendix) and add more experimental content in Section 5, particularly experiments related to CIFAR10.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our appreciation to the reviewer for your valuable and constructive comments. In the following, we address the points raised by the reviewer.\n\n## **W1. It only analyzes Cutout and CutMix**\n\nAs the reviewer would also agree, a complete theory is not built in a single day. We chose Cutout and CutMix as a starting point for understanding patch-level augmentation techniques, and even this first step required a considerable amount of efforts. Also, We would like to emphasize that there has been limited theory works even on CutMix, as we discussed in Section 1.2.\n\n## **W2&3, Q1. More insights beyond theoretical analysis**\n\nWe agree that exploring practical implications beyond the theoretical analysis of existing methods like Cutout and CutMix is valuable. We also believe that understanding the underlying mechanisms of these methods can lead to the development of even more effective techniques. With this in mind, we would like to discuss some potential directions for future applications.\n\nOne practical insight we can offer is related to the choice of cutting size $C$ in cutout. Our main intuition behind Cutout is that it outperforms by removing dominant noise patch, or “shortcuts,” which do not generalize to unseen data. Real-world image data contains features and noise across several patches. In practical scenarios, a larger cutting size can be effective in eliminating noise but may also remove important features that the model needs to learn. Thus, there is a trade-off in choosing the optimal cutting size. From this intuition, we believe that for images with a larger portion of background(noise), a larger cutting size is likely to be more effective.\n\nIn our theoretical analysis, we show that Cutout and CutMix can learn rare features even though still memorizing some noises. We believe that improving underlying mechanism we have demonstrated can lead to even more effective techniques. Below, we list a couple of potential directions that can not only enable effective feature learning, as Cutout and CutMix do, but also improve these methods by preventing the memorization of noise.\n\n- One limitation of Cutout is that it does not always effectively remove dominant noise. As a result, dominant noise can still persist in the augmented data, leading to potential noise memorization. Developing strategies that can more precisely detect and remove these noise components from the image input could enhance the effectiveness of these methods.\n- The main underlying mechanism of CutMix, as we have outlined in Section 4.2, is that it learns information almost uniformly from all patches in the training data, which allows it to capture even rarer features. However, this approach also involves the memorization of noise, which can potentially degrade performance in real-world scenarios. We believe that a more sophisticated cut and pasting strategy—one that considers the positional information of patches rather than using a uniform approach—could improve the model’s ability to learn more from patches containing label-relevant features and reduce the impact of label-irrelevant noise. Already some recent patch-level augmentation method, such as PuzzleMix[5] and Co-mixup[6], use these types of strategy.\n\n## **W4. Suggestion regarding paper organization**\n\nWe appreciate for your suggestion regarding the paper’s organization. We agree that moving some of the experimental results from the appendix to the main text could improve our draft. However, we also believe that fully presenting the assumptions in the main text is important for the completeness of our theoretical results.  We will carefully consider how to balance these aspects in the next revision, keeping the page limits in mind.\n\n## **Q2. The paper specifies that the NN architecture used is a 2-layer CNN, but shouldn’t it be considered a 1-layer CNN?**\n\nWhether our network is considered a 2-layer CNN or a 1-layer CNN depends on the perspective. Following the existing results in the literature, we regard it as a 2-layer CNN, where the weights in the second layer are fixed at 1 and -1, making only the first layer trainable. Many other works including [1,2,3] also consider neural networks similar to ours as 2-layer CNNs.  \n\n## **Q3. Is it not possible to perform a more general analysis with $C$ channels, as done by Shen et al.?**\n\nWe believe that a more general analysis with multiple neurons as done by Shen et al. 2022 is also possible, and we numerically validate this scenario in Appendix A.2, Figure 3. \n\nAs we discussed in line 144-151, using ReLU activation requires multiple neurons since neurons can be negatively initialized and remain unchanged throughout the training. In contrast, leaky ReLU activation always has positive slope, ensuring that a single neuron is often sufficient. Therefore, for mathematical simplicity, we focus on the case where the network has a single neuron for each output, and extension to multi-neuron case may require some additional techniques.  \n\n## **Limitation. There is no specified section for limitations in this paper**\n\nOur work has limitations related to the neural network architecture, specifically single-neuron leaky ReLU CNNs. We discussed this in lines 137-151, but we will add a Limitation section in the next revision to explicitly address these technical limitations.\n\nWe hope that our response clarifies your concerns. We would appreciate it if you could consider reassessing our submission.\n\nBest regards,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T7TKOAKBGG", "reviewer": "Reviewer_59hr", "summary": "This work theoretically investigates why patch-based data augmentation methods for image recognition, namely, CutOut and CutMix, improve performance based on the framework by [Zou+ICML23].\nSpecifically, they showed that when a CNN is trained with CutOut and CutMix, it can focus on rare and extremely rare features while ignoring noise. \nContrarily, the model trained with the standard ERM memorizes noise, which results in poorer performance.\nThese findings align with their numerical results.", "questions": "- If some features are extremely rare, I think they are less likely to appear in test data. Why learning it improves the performance? In practice, such features are likely to be attributed to systematic mislabeling.\nClearly defining common features, rare features, and extremely rare features may resolve this question.", "limitations": "- Although the checklist says the limitations are discussed in Section 2, I could not find the discussion of limitations in the section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work theoretically reveals why patch-based data augmentation, specifically CutOut and CutMix, improves the performance of CNNs.\nThese methods are so far powerful but ad-hoc heuristic, so research towards their theoretical understanding is important.\n- By comparing ERM, Cutout, and CutMix in a unified framework, the authors highlight the superior ability of CutMix that can exploit extremely rare features in data while effectively ignoring noises.\n- The theory well aligns with the numerical experiments on synthetic data.", "weaknesses": "- The important notions on features, i.e., common features, rare features, and extremely rare features, are not properly defined, making the manuscript difficult to read. I think improving the description in Section 2.1 would resolve this issue.\n- The technical contributions against [Zou et al. 23] are not clearly stated in the manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our appreciation to the reviewer for your valuable and constructive comments.  In the following, we address the points raised by the reviewer.\n\n## **W1. Confusion on the notions of features**\n\nWe have noticed that the notions of common features, rare features, and extremely rare features were not clearly explained in Definition 2.1. These features have significantly different frequencies, where common features appear much more frequently than rare features, and rare features appear more frequently than extremely rare features. While we describe this in the Assumptions (Section 2.4), we acknowledge that additional discussion near Definition 2.1 would be helpful to readers. We plan to include a more detailed explanation of these feature notions in Definition 2.1 in our next revision.\n\nIn global response, we provide clarification on the notions of features and more detailed motivation of our data model. We hope this resolves any confusion or misunderstanding. We will address the question raised due to this confusion.\n\n## **Q1. Why learning extremely rare features improves the performance?**\n\nAs we discussed in the global response, extremely rare features in our setting are still frequent enough to appear in a non-negligible fraction of the training set. These features also have a presence in the test distribution and provide valuable information for correct classification. Hence, learning these features contributes to improved performance.\n\n## **W2. The technical contributions against Zou et. al. 2023 are not clearly stated.**\n\nWe have discussed comparison to Zou et.al. 2023 in lines 123-130 and lines 313-318. While we believe this coverage is sufficient, we provide a more detailed comparison here.\n\n- Zou et.al. 2023 only consider two types of features (common features, rare features) while we consider three types of features(common features, rare features, extremely rare features). This is because Zou et.al.2023 investigate two training methods (vanilla, Mixup) while we study three training methods (ERM, Cutout, CutMix).\n- Zou et.al. 2023 consider quadratic activation, whereas we focus on smoothed leaky ReLU activation. While our analysis of ERM shares the same spirit as the analysis of vanilla training in Zou et.al. 2023, detailed proofs differ due to variants in the network architecture.\n- The main difference between the Mixup analysis in Zou et.al. 2023 and our CutMix analysis lies in the approach: Zou et.al. 2023 prove the benefit of Mixup by directly investigating its learning dynamics, while we show the benefit of CutMix by characterizing the global minimum of CutMix loss. Zou et.al. 2023 prove that Mixup can learn rare features in early phase since it is “boosted” by the learning of common features. In contrast, our analysis shows that global minimizers learn all kinds of features indicating that the benefit of CutMix arises as training approaches convergence. This distinction highlights the differences in the underlying mechanisms: Mixup has benefit in the early stage of training, while the benefits of CutMix arise from the later stages of training.\n\n## **Limitations. Could not find the discussion of limitations in the Section 2**\n\nOur work has limitations related to the neural network architecture, specifically single-neuron leaky ReLU CNNs. We discussed this in lines 137-151, but we will add a Limitation section in the next revision to explicitly address these technical limitations.\n\nThanks for your time and consideration.\n\nBest regards,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i0ebETxViz", "reviewer": "Reviewer_ZwXm", "summary": "This paper offers a theoretical explanation for the effectiveness of two practically useful algorithms—Cutout and Cutmix—by applying typical feature learning analysis to multi-patched feature and noise data. The authors present negative results for ERM as a comparison and demonstrate positive results for Cutout and Cutmix, including positive margins and near-optimal test error.", "questions": "1. Can the analysis be generalized to non-smooth neural networks? What technical difficulties will you encounter when generalizing the analysis to non-smooth activation functions like ReLU and leaky ReLU?\n\n2. Why is the near convergence result only presented for the Cutmix setting but not for the Cutout setting?\n\n3. Can you provide stronger results about the margin besides its positiveness? What is the order/magnitude of the margin?\n\n4. Why does the result for Cutout hold for any iteration T in an interval, while the result for Cutmix only guarantees the existence of an iteration that satisfies the properties?", "limitations": "Same as weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provides the first theoretical analysis of two practically useful data augmentation algorithms — Cutout and Cutmix.", "weaknesses": "This paper applies a smoothed leaky ReLU activation function in the neural network for technical reason, which differs from the model used in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our appreciation to the reviewer for your valuable and constructive comments.  In the following, we address the points raised by the reviewer.\n\n## **W1 & Q1. The use of smooth activation and generalization to non-smooth activation**\n\nWe note that our activation function differs from those typically used in practice. However, smooth activation functions are widely employed in theoretical studies to analyze the generalization performance of two-layer neural networks. Numerous works have explored theory of deep learning under similar settings as discussed in lines 59–71. Therefore, we believe that studying two-layer networks with smooth activations is a valuable approach for bridging the gap between practice and theory.\n\nOur theoretical analysis can be generalized to non-smooth activations, such as ReLU or Leaky ReLU, in the cases of ERM and Cutout. In fact, our proof did not rely on the smoothness of activations in these cases. However, the smoothness of activation plays a crucial role in the analysis of CutMix. The main difference between the analysis of ERM & Cutout and CutMix lies in our approach: for ERM and Cutout, we directly investigate learning dynamics, whereas for CutMix, we characterize the global minimum and demonstrate that CutMix training can achieve a near-stationary point. To show that the CutMix loss achieves a near-stationary point, we use the descent lemma (Lemma 3.4 in [7]), which is only applicable to smooth objective functions. This is why smoothness is necessary for the CutMix analysis.\n\n## **Q4. Why does the result for Cutmix only guarantee the existence of an iteration that satisfies the properties?**\n\nThe use of the descent lemma makes a distinction between the conditions on the iterations for ERM & Cutout and CutMix. The convergence of a smooth function $f(x)$ with optimizing variables $x$ is usually guaranteed by showing\n$\\frac{1}{T} \\sum_{t=0}^{T-1} \\lVert \\nabla f(x^{(t)}) \\rVert^2 \\leq \\frac{C}{T},$\nfor some constant $C$. Therefore, $\\min_{t =0,1, \\dots, T-1}\\lVert\\nabla f(x^{(t)})\\rVert^2 \\leq \\frac{C}{T}$ and it guarantees only the existence of an iteration that achieves a near-stationary point. We would like to emphasize that, even though our theory only guarantees this existence, our numerical validation (Section 5, Figure 1) shows consistent convergence behavior.\n\n## **Q2. Why is the near convergence result only presented for the Cutmix setting but not for the Cutout setting?**\n\nThe difference between ERM & Cutout and CutMix also results in different convergence criteria. We initially adopted training accuracy as the convergence criterion, following [1]. However, as discussed in lines 245–247, evaluating the training accuracy of augmented data is challenging because it uses augmented data with mixed labels. Therefore, we use the loss gradient as the convergence criterion, which can be guaranteed by the descent lemma. We note that we can also prove that ERM and Cutout achieve near convergence using the descent lemma. However, we adopted perfect training accuracy as the convergence criterion because it provides a more intuitive measure of how well the model fits all training data points. Moreover, due to the monotonic nature of ERM and Cutout training, we can show that the guarantees in our theorems hold for any sufficiently large polynomial time. \n\n## **Q3. Can you provide stronger results about the margin besides its positiveness? What is the order/magnitude of the margin?**\n\nIn our theoretical analysis, we proved that the model achieves an $\\Omega(1)$ margin for test data with learned features. If you are interested, you can check line 802 for ERM, line 996 for Cutout, and line 1155 for CutMix.\n\nThanks for your time and consideration.\n\nBest regards,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,

We express our gratitude for your time and valuable comments.

Before addressing concerns/questions raised by individual reviewers, we would like to re-emphasize the main intuition behind our theoretical framework and findings.

## **Motivation for feature and noise in our data distribution**

We would like to provide motivation for our data distribution and clarify each component of the distribution. The figure in the attached file illustrates the core ideas behind our feature noise data model, which we believe will help reviewers better understand our approach. 

The main characteristic of image data is that the input contains both information relevant to the image labels (which we refer to as "features," e.g., a cat’s face) and information irrelevant to the labels (which we refer to as "noise," e.g., the background). The key difference between these two components is that features can appear in other data points, while noise typically does not appear in other (unseen) data since it is independent of the label. This distinction motivates our approach, where features are sampled from a set of fixed vectors and noise is sampled from a Gaussian distribution. Both features and noise can be used to correctly classify training data, however, only features are useful for correctly classifying unseen test data. Thus, learning features are important for better generalization.

## **Clarification on difference between common, rare, and extremely rare features**

Next, we would like to clarify the notion of common, rare, and extremely rare features. Different features appear in data with different frequencies. For example, in a cat and dog classification task, the number of occurrence of cat’s face and cat’s tail in the dataset might differ significantly, yet both are relevant for the label "cat". The reason we separate features into these three categories is to highlight the distinctions between the three training methods we analyze. Additionally, we emphasize that “extremely rare” features are still likely to appear in a nontrivial fraction of the training data with high probability, as outlined in the second bullet point of Lemma B.2, given the assumptions on hyperparameters in Assumption B.1. We hope this clarification addresses any concerns or misunderstandings expressed by some reviewers.

We plan to include these discussions in the next revised version of our paper. 

Additionally, we provide references that will be addressed in individual rebuttals below.

We hope our response helps to resolve any concerns and confusion. 

Best regards,

Authors

Reference

[1] Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation. In ICML 2022

[2] Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv 2020

[3] Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. The benefits of mixup for feature learning. In ICML 2023

[4] Zihenrg Jiang, Chiyuan Zhang Kunal Talwar, and Michael C. Mozer. Characterizing structural regularities of labeled data in overparameterized models. In ICML 2021

[5] Jang-Hyun Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. In ICML 2020

[6] Jang-Hyun Kim, Wonho Choo, Hosan Jeong, and Hyun Oh Song. Co-mixup: Saliency guided joint mixup with supermodular diversity. In ICLR 2021

[7] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends®358 in Machine Learning 2015

Meta-review: The paper investigates the theoretical benefits of Cutout and CutMix for two-layer neural networks. 

The reviewers generally appreciate the theoretical insights of the widely used data augmentation methods. They unanimously voiced that the remaining concerns are adequately addressed by the rebuttal. 

I recommend accepting this paper as a spotlight, acknowledging the following values:
- Novel theoretical framework for connecting feature learning and data augmentation
- Inspiring potential future extensions for theoretical analysis or novel augmentation techniques
- Empirical support for the theoretical findings
Decision: Accept (spotlight)