How Does Mixup Help With Robustness and Generalization?
Authors: Linjun Zhang
Zhun Deng
Kenji Kawaguchi
Amirata Ghorbani
James Zou
Venue: ICLR 2021 Spotlight (2021)
Keywords: Mixup
adversarial robustness
generalization

Abstract: Mixup is a popular data augmentation technique based on on convex combinations of pairs of examples and their labels. This simple technique has shown to substantially improve both the model's robustness as well as the generalization of the trained model. However,  it is not well-understood why such improvement occurs. In this paper, we provide theoretical analysis to demonstrate how using Mixup in training helps model robustness and generalization. For robustness, we show that minimizing the Mixup loss corresponds to approximately minimizing an upper bound of the adversarial loss. This explains why models obtained by Mixup training exhibits robustness to several kinds of adversarial attacks such as Fast Gradient Sign Method (FGSM). For generalization, we prove that Mixup augmentation corresponds to a specific type of data-adaptive regularization which reduces overfitting. Our analysis provides new insights and a framework to understand Mixup.


Published as a conference paper at ICLR 2021
How DOES MIXUP HELP WITH ROBUSTNESS AND GENERALIZATION?
Linjun Zhang
Zhun Deng'
Rutgers University
Harvard University
linjun. zhangjeru.gers.edd
zhundengēg harvard. edu
Kenji Kawaguchi*
Harvard University
kkawaguchi@fas www.aauuchffaae.aaaar.....o harvard. edu
Amirata Ghorbani
James Zou Stanford University jamesz@stanforee edu
Stanford University
ammrratagsstanforddeddu
ABSTRACT
Mixup is a popular data augmentation technique based on taking convex combina- tions of pairs of examples and their labels. This simple technique has been shown to substantially improve both the robustness and the generalization of the trained model. However, it is not well-understood why such improvement occurs. In this paper, we provide theoretical analysis to demonstrate how using Mixup in training helps model robustness and generalization. For robustness, we show that minimiz- ing the Mixup loss corresponds to approximately minimizing an upper bound of the adversarial loss. This explains why models obtained by Mixup training ex- hibits robustness to several kinds of adversarial attacks such as Fast Gradient Sign Method (FGSM). For generalization, we prove that Mixup augmentation corre- sponds to specific type of data-adaptive regularization which reduces overfitting. Our analysis provides new insights and a framework understand Mixup.
INTRODUCTION
Mixup was introduced by Zhang et al. (018)) as a data augmentation technique. It has been em- pirically shown to substantially improve test performance and robustness to adversarial noise of state-of-the-arr neural network architectures (Zhang et al.) 20188) Lamb et al. 2019 Thulasidasan al.] 2019: Zhang et al. 2018: Arazo et al. 2019). Despite the impressive empirical performance, is still not fully understood why Mixup leads to such improvement across the different aspects mentioned above. We first provide more background about robustness and generalization properties of deep networks and Mixup. Then give overview of main contributions.
Adversarial robustness. Although neural networks have achieved remarkable success in many areas such natural language processing (Devlin et al. 2018) and image recognition (He et al. 201 has been observed that neural networks are very sensitive to adversarial examples be easily flipped by human imperceptible perturbations (Goodfellow al. 2014 Szegedy al. 2013). Specifically, in Goodfellow et al. (2014), the authors use fast gradient sign method (FGSM) to generate adversarial examples, which makes an image panda high confidence. Although various defense mechanisms have been proposed against adversarial attacks, those mechanisms typically sacrifice test accuracy turn for robustness (Tsipras et al., 2018) and many of them require significant amount of additional computation time. In contrast, Mixup training tends improve test accuracy and at the same time also exhibits certain degree of resistance to adversarial examples, such as those generated by FGSM (Lamb al. 2019). Moreover, the corresponding training time is relatively modest. As an illustration, we compare the robust test
prediction
classified as gibbon with
Equual contribution.

---

Published as a conference paper at ICLR 2021
100
Mixup-lose loss
90
Test Accuracy
ERM
Generalization gap
80
mixup ERM
70
test loss
60
50
mixup
40
ERM
30
12
100
200
302
130
200
303
400
Attack Size
epoch
epoch
(a) Robustness
(b) Generalization
Figure I: Illustrative examples of the impact of Mixup on robustness and generalization. (a) Adver- sarial robustness on the SVHN data under FGSM attacks. (b) Generalization gap between test and train loss. More details regarding the experimental setup are included in Appendix C.I, C.2.
accuracy between model trained with Mixup and a model trained with standard empirical risk minimization (ERM) under adversarial attacks generated by FGSM (Fig. [aa.. The model trained with Mixup loss has much better robust accuracy. Robustness of Mixup under other attacks have also been empirically studied in Lamb al. (2019).
Generalization Generalization theory has been a central focus of learning theory [Vapnik 1979.
2013 Bartlett et al. 20022 Bartlett Mendelson 2002, Bousquet Elisseeff] 2002; Xu Mannor
2012). but it still remains mystery for many modern deep learning algorithms (Zhang et al. [0166] Kawaguchi et al. 2017). For Mixup, from Fig. (bb). we observe that Mixup training results in better test performance than the standard empirical risk minimization. That is mainly due to its good generalization property since the training errors are small for both Mixup training and empirical risk minimization (experiments with training error results
included in the appendix). While there have been many enlightening studies trying to establish generalization theory for modern machine learning algorithms (Sun al. [0155] Neyshabur et al.) 20155] Hardt et al. 2016 Bartlett et al., 2017 Kawaguchi et al., 2017; Arora et al. Neyssaayyyabuu & Li 2019), few existing studies have illustrated the generalization behavior of Mixup training in theory.
Our contributions. In this paper, we theoretically investigate how Mixup improves both adver- sarial robustness and generalization. We begin by relating the loss function induced by Mixup to the standard loss with additional adaptive regularization terms. Based on the derived regulariza- tion terms, we show that Mixup training minimizes an upper bound on the adversarial boss,which leads to the robustness against single-step adversarial attacks. For generalization, we show how the regularization terms can reduce over-fitting and lead better generalization behaviors than those of standard training. Our analyses provides insights and framework to understand the impact of Mixup.
Outline of the paper. Section introduces the notations and problem setup. In Section 3, we present our main theoretical results, including the regularization effect of Mixup and the subse- quent analysis to show that such regularization improves adversarial robustness and generalization. Section 4 concludes with discussion of future work. Proofs are deferred to the Appendix.
1.1 RELATED WORK
Since its advent, Mixup training (Zhang et al. 2018) has been shown to substantially improve gen- eralization and single-step adversarial robustness among a wide rage of tasks, on both supervised (Lamb et al. 2019 Verma et al.] 2019a] Guo et al.] 2019), and semi-supervised settings (Berth-) clot et al.] [2019] Verma et al. 2019b). This has motivated a recent line of work for developing a number of variants of Mixup, including Manifold Mixup (Verma et al. 2019a). Puzzle Mix (Kim) et al. 2020), CutMix (Yun et al. 2019), Adversarial Mixup Resynthesis (Beckham et al. 2019). and PatchUp (Faramarzi et al. 2020). However, theoretical understanding of the underlying mech- anism of why Mixup and its variants perform well on generalization and adversarial robustness is still limited.
2

---

Published as a conference paper at ICLR 2021
Some of the theoretical tools we use in this paper are related to Wang & Manning (2013) and Wager jet al. 2013)) where the authors use second-order Taylor approximation to derive regularized loss function for Dropout training. This technique is then extended to drive more properties of Dropout, including the inductive bias of Dropout (Helmbold & Long 2015), the regularization effect in ma- trix factorization (Mianjy et al. 2018)), and the implicit regularization arization in neural networks (Wei al., 2020). This technique has been recently applied to Mixup in a parallel and independent work (Car- ratino et al., 2020) to derive regularization terms. Compared with the results in Carrattio et al. (2020), our derived regularization enjoys simpler form and therefore enables the subsequent anal- ysis of adversarial robustness and generalization. We clarify the detailed differences in Section 3
To the best of our knowledge, our paper is the first to provide a theoretical treatment to connect the regularization, adversarial robustness, and generalization for Mixup training.
PRELIMINARIES
In this section, we state notations and briefly recap the definition of Mixup.
Notations. We denote the general parameterized loss as I(0, 2). where 0 E E Rd and 2 (a. y) is the input and output pair. We consider training dataset S = {(11, v1).... (Z Yn } where 2; E X C Re and E y C In are i.i.d. drawn from a joint distribution Pa... We further denote (A)
Λr; (1 A)my (A) Ay (1 A)yj for À E [] and let (A) = (A), (A)). Let L(0) = EEsP.,, (0, z) denote the standard population loss and (2, - 1(0, 2n)nn denote the standard empirical loss. For the two distributions DD and for E (0, 1) to denote the mixture distribution such that a sample is drawn with probabilities and (1 p) from D, and D2 respectively. For a parameterized function fo(),, we use fzx) and (z) to respectively denote the gradient with respect to x and A. For two vectors and b. we use cos y) to denote (z. y) /)/(([=]] 1|y/1)-
D2, we use pD1
Mixup. Generally, for classification cases, the output yi is the embedding of the class of r; i.e. the one-hot encoding by taking m as the total number of classes and letting y: {0, 11mh be the binary vector with all entries equal to zero except for the one corresponding to the class of æ;, In particular, if we take m 1, it degenerates to the binary classification. For regression cases, yı can be any real number/vector. The Mixup loss is defined in the following form:
n2
L (8, S)
Σ
E EAND 1(0, 2 (A)),
(1)
n
1-1=1
where DA distribution supported on [0, 1]. Throughout the paper. we consider the most com- monly used 'Dx- Beta distribution Beta(a, (3) for a, B 0.
3 MAIN RESULTS
In this section, we first introduce a lemma that characterizes the regularization effect of Mixup. Based on this lemma, we then derive our main theoretical results on adversarial robustness and generalization error bound in Sections 3.2 and 3.3 respectively.
3.1 THE
EFFECT OF MIXUP
As a starting point, we demonstrate how Mixup training is approximately equivalent to optimizing a regularized version of standard empirical loss (,, S). Throughout the paper, we consider the following class of loss functions for the prediction function fo(x) and target y:
L (10 (a, (0,, (x. v)) = h(fo())) - yfo( for some function h).
This function class L includes many commonly used losses, including the loss function induced by Generalized Linear Models (GLMs), such as linear regression and logistic regression, and also cross- entropy for neural networks. In the following, we introduce a lemma stating that the Mixup training with À ~ Dx Beta(a, 3) induces regularized loss function with the weights of each regulariza- tion specified by mixture of Beta distributions Dx
a+B Bela(a + 1,8) oh Bela 11, a))
3

---

Published as a conference paper at ICLR 2021
Lemma 3.1. Consider the loss function I[B, (2, = h(fo(z)) yfo(z)) where h(-) and fo(.)
for all 0 E @ twice differentiable.
We further denote DD uniform mixture of two Beta distributions, i.e, a+8 (, a+3 (Bt a,), and Dx the empirical distribution of the training dataset 5 = (I1, :.. ,Ja), the corresponding Mixup loss L (0, S), as defined in Eq. 7 with X Dx= Beta(a, 33,, can be rewritten
3
m (8, = L (0, Σ
R,(0, B EAND (11-) A)2 - -)),
t=1
where lim p(()) = and
E BAND A1
S) =
Σ - "B, Izl.
11.
E EA [11 --
n
R2(
h"" (((o(t)))VVoocz) (T "Bao::=))///xxxxx
x;)(r= -x;)
[V.)_- [V)
2n
Ex Ex~D
[(1 [11)
R)(
- -x) 2.)"1.
2n
By putting the higher order terms of approximation in sp-), this result shows that Mixup is related to regularizing (axz)) and fo(a), which are the first and second directional derivatives with respect to 24. Throughout the paper, our theory is mainly built upon analysis of the quadratic ap-
proximation of L (0, which we further denote as
Imix (0, = : (0,
Σ R.,0,))
(3)
Comparison with related work. The result in Lemma 3.1 relies on the second-order Taylor ex- pansion of the loss function Eq. [ Similar approximations have been proposed before study the regularization effect of Dropout training, see Wang & Manning 2013); Wager et al. (2013): Mianny al. 2018); Wei al. 22200). Recently, Carratino et al. (2020) independently used similar approx- imation to study the regularization effect of Mixup. However, the regularization terms derived in Carratino al. (020)) is much more complicated than those Lemma 3.1 For example, in GLM, our technique yields the regularization term as shown in Lemma 3.3] which is much simpler than those in Corollaries 2 and Carratino al. (2020). One technical step we use here to simplify the regularization expression is to equalize Mixup with input perturbation, see more details in the proof in the Appendix. This simpler expression enables us to study the robustness and generalization of Mixup in the subsequent sections.
Validity of the approximation. In the following, we present numerical experiments to support the approximation in Eq. (3). Following the setup of numerical validations in Wager et al. (2013); Carratino et al. (2020), we experimentally show that the quadratic approximation is generally very accurate. Specifically, we train Logistic Regression model (as example of GLM model, which we study later) and a two layer neural network with ReLU activations. We use the two-moons dataset (Buitinck al. 2013). Fig. [ shows the training and test data's loss functions for training two models with different loss functions: the original Mixup loss and the approximate Mixup loss. Both models had the same random initialization scheme. Throughout training, we compute the test and training loss of each model using its own loss function. The empirical results shows the approximation Mixup loss is quite close to the original Mixup loss.
3.2 MIXUP AND ADVERSARIAL ROBUSTNESS
ready state main theoretical results. In this subsection, we illustrate how Mixup helps adversarial robustness. We prove that minimizing I.iix (0, S) is equivalent to minimizing an upper bound of the second order Taylor expansion of an adversarial loss.
Having introduced (e, S) in Eq. (3)
4

---

Published as a conference paper at ICLR 2021
0.8
0-8
0.8
Mosup Approximace mixup
Micup
Approxinate mirup
0.0
Test fos
0.6
Tend liee
0.2
50
100 Epoch
150
200
0:2
100 Epoch
150
250
0.2
30
100
150
260
0.2
100 Spoch
150
200
Epoch
Logistic Regression
Two Layer ReLU Neural Network
Figure 2: Comparison of the original Mixup loss with the approximate Mixup loss function.
Throughout this subsection, we study the logistic loss function
1(0,)) =) log(1 + exp(ff(>))) vfo
where y E y' = 13. In addition, let be the logistic function such that g(8) = e0/(1 + E*) and consider the case where the data-dependent space θ, defined as
θ = (0 E Rd sofo(;;) + (y/ 1) (x:) 2 0 for all i 1,............ I....,
Notice that contains the set of all with zero training errors:
2 {0 E R the label prediction y: f(f (x;) 2 0} equal to yl for all i ......n..... (4)
In many practical cases, the training error (0-1 loss) becomes zero in finite time although the training loss does not. Equation (4) shows that the condition of f E θ is satisfied in finite time in such practical cases with zero training errors.
Logistic regression. As starting point, study the logistic regression with fa(x) 0 in which case the number parameters coincides with the data dimension, i.e. p = d. For a given E > O, we consider the adversarial loss with &2-attack of size evd, that is, I (6, S) = 1/n Ee= max (4, Saala (6, (x; + 6,, v:)). We first present the following second order Taylor ap- proximation of L.dv( (0,
Lemma 3.2. The second order Taylor approximation of Ladu (0,S) E ladu (xi, (w),::))// where for any 1 > 0, x E IR? and y E 10,
n² 2 1(x T) 9((= TO) 11113 (5) Tadu(1, (1), (I, n)) 1(0, (x, v)) 7lg(1 TO) yl -10112 +
By comparing (6, (x, v)) and [mi S) applied to logistic regression, we prove the following.
Theorem 3.1. Suppose that fo(x) = TTe and there exists a constant O₂ > such that |æ:l|e 2 ex cd for all i E ( (1....,n.. Then, for any 0 E O, we have
iimi i.mix (0, 2
1 n
Σ
"
indu /d, (24,
Σ
(adix (Emix Vd, (f4,
n2
where E; = R2c,E D. (1 A] with R; = cos(( xz)), and Emix
R Cz E.EEx-o C.EE - X] with
R = minge(1.....) cos (0, x.)L.
Theorem 3.1 suggests that mix (8, S) is an upper bound of the second order Taylor expansion of the adversarial loss with fg-attack of size mix dd. Note that mmix depends on 0; one can think the final radius is taken at the minimizer ī.mix (0, S). Therefore, minimizing the Mixup loss would result in small adversarial loss. Our analysis suggests that Mixup by itself can improve robustness against small attacks, which tend to be single-step attacks (Lamb et al. 2019). An interesting direction for future work is explore whether combining Mixup with adversarial training is able provide robustness against larger and more sophisticated attacks such as iterative projected gradient descent and other multiple-step attacks.
5

---

Published as a conference paper at ICLR 2021
Trainn arcurary
200
100
60-
60
Donsty
Density
10-
10.9
10-1
10
230
300
300
200
R
(a) Linear
(b) ANN
(c) ANN: epoch = 0 (d) ANN: epoch= 400
Figure 3: The behaviors of the values of R and R. during training for linear models and artificial neural network with ReLU (ANN), The subplots (c) and (d) show the histogram (R, Re,..., R,)
for ANN before and after training. R and Rg control the radii of adversarial attacks that Mixup training protects for.
Remark 3.1. Note that Theorem also implies adversarial robustness against & attacks with size since for any attack 8, ||ōl|c= S E implies ||ö1|2 S EVd, and therefore max L(6, (x+ y)) 2
max max16llaava. I(0, (ar + 5)))
In the following we provide more discussion about the range of Rt = millee(....... cos(O, x;).. We first show that under additional regularity conditions, we can obtain a high probability lower bound that does not depend on sample size. We then numerically demonstrate that R tends to increase during training for both cases of linear models and neural networks at the end of this subsection.
A constant lower bound for logistic regression. Now, we show how to obtain constant lower bound by adding some additional conditions.
Assumption 3.1. Let us denote Ô, C O as the set of minimizers of imms (0, We assume there exists a set Or I such that for all 2 N, where N is positive integer, O S O with probability at least - 8n where ōn + 0 as n + 0. Moreover, there exists a T (0, 1) such that
p- P e X cos(æ, 0) 2 for all 9 E (0*) 1).
Such condition generally holds for regular optimization problems, where the minimizers not lo- cated too dispersedly in the sense of solid angle (instead of Euclidean distance). More specifically, if we normalize all the minimizers' & norm to 1, this assumption requires that the set of minimizers should not be located all over the sphere. In addition. Assumption only requires that the proba- bility pr and the threshold in all solid angles, then when the set of minimizers is discrete, this assumption holds. For more complicated cases in which the set of minimizers consists of sub-manifolds, as long as there exists solid angle in X' that is disjoint with the set of minimizers, the assumption still holds.
be non-zero. In particular, if the distribution of æ has positive mass
Theorem 3.2. Under Assumption 3.1 for fe(z) = x 6. if there exists constants bas > 0 such that e₂ vd < ||ai||a S by d for all E {l,..., n). Then, with probability at least 8, 2 cexp(-np2/1) there exists constants 0, in O, such that for any On. we have
i (0. 2
Σ
(Emix Vd, (xi)
where Emix = Re, Bxc,E, A) and it min
4xpp
2n
2 p+ 44ppp
T.
Neural networks with ReLU Max-pooling. The results in the above subsection can be extended to the case of neural networks with ReLU activation functions and max- max-pooling. Specifically, we
Under some well-separation and smoothness conditions, we would expect all elements é,, will fall into neighborhood M,, of minimizers of F.g (0. (0.8), and Nr, will shrink as increases, i.c. Nn+1 C Nr. One think O* is containing all No, for 2 N.

---

Published as a conference paper at ICLR 2021
consider the logistic loss, (() log(1 + cxp(fo(x)) yfo(z) with y E {0, 1}, where fo(x) represents a fully connected neural network with ReLU activation function or max max-pooling:
fo(x) = 3T ((WWx--...WW.WWWW
...
Here, o represents nonlinearity via ReLU and max pooling, each W, is a matrix, and 3 a column vector: i.e., O consists of (W.) and B. With the nonlinearity for ReLU and max-pooling, the function fe satisfies that fa( ffa()) x and fo(x) 0 almost everywhere, where the gradient is taken with respect to input x. Under such conditions, similar to Lemma 3.2 the
adversarial loss function Σi=1 max 1o. (0, (2; + di, y:)) can be written
mix d 1
I, (0,5)+ vdl lo(fo(=))) ya [V
| [=((((=))IIV(((()))
2
n
(6)
With a little abuse of notations, we also denote
Tado (6, (2r, y)) = 1(0, (a,, v)) + (lg(S(()))) - vllV + 8dd 2 (
The following theorem suggests that minimizing the Mixup loss in neural nets also lead to a small adversarial loss.
Theorem 3.3. Assume that fa(x;) = [o(x;) 2i fo(x)) = 0 (which are satisfied by the Rel.U
and max-pooling activation functions) and there exists a constant Oz > 0 such that || 2 vd for all i .n.....n]. Then, for any 8 O we have
m [m, () 2 Σ 1=1
Jado (oaalE, v. (2,, v:)) 2 Σ Ladn (Emix vd, (I;, vi))
where = RiC, Exc D
D. 1 - \I.
Emix = R Cg BAND (1 A] and R:
R
(i..g( cos( V so (I:),,
Similar constant lower bound can be derived to the setting of neural networsk. Due to limited space, please the detailed discussion in the appendix.
On the value of R = min; Rs via experiments. For both linear models and neural networks, after training accuracy reaches 100%, the logistic loss is further minimized when for,) (Ix))ll increases. Since (z:))2 = V fe (x;) 2; 2|| || f (z; Illl this suggests that R& and R tend to increase after training accuracy reaches 100% (e.g.. ffe(x;) 0 in the case of linear models). We confirm this phenomenon in Fig. 3 In the figure. R is initially small but tends to increase after training accuracy reaches 100%, as expected. For example, for ANN, the value of was initially 2.27 x 10 but increased to 6.11 x 10 after training. Fig. (c) and (d) also show that R2 for each i-th data point tends to increase during training and that the values of R. for many points are much larger than the pessimistic lower bound R: e.g., whereas R = 6.11 x 10-2, we have R. > 0.8 for several data points in Fig. 3 (d). For this experiment, we generated 100 data points as x; ~ NO Z) and yi = [z 0 0} where z; E I. and 0 (O Z). We used SGD to train linear models and ANNs with ReLU activations and 50 neurons per each of two hidden layers. We set the learning rate be 0.1 and the momentum coefficient to be 0.9. We turned off weight decay so that R is not maximized as a result of bounding || fa;;))) which is a trivial case from the discussion above.
3.3 MIXUP AND GENERALIZATION
In this section, we show that the data-dependent regularization induced by Mixup directly controls the Rademacher complexity of the underlying function classes, and therefore yields concrete gener- alization error bounds. We study two models the Generalized Linear Model (GLM) and two-layer ReLU nets with squared loss.
Generalized linear model. A Generalized Linear Model is a flexible generalization of ordinary linear regression, where the corresponding loss takes the following form:
1(0, (5. v)) A(0 x)) y0 xr,
7

---

Published as a conference paper at ICLR 2021
where A(-) is the log- log-patiiion function, E IP and y E R. For instance, if we take A(0 x) log(1 e *) and y E (0, 1), then the model corresponds the logistic regression. In this para- graph, we consider the case where θ X and Y are all bounded.
By further taking advantage of the property of shift and scaling invariance of GLM, we can further simplify the regularization terms in Lemma 3.1 and obtain the following results.
Lemma 3.3. Consider the centralized dataset S, that is, 1/n Ei= 2; 0. and denote Σx - For GLM, if A(-) is twice differentiable, then the regularization term obtained by the second-order approximation of L
(0, () is given by
1
(1 A)2 A2
A .B)l.BAAs BAND
T ΣxO.
(7)
2n
where Dx = a+B Beta(a + 1,8) +
a a+3
Beta + 1x).)
Given the above regularization term, we are ready to investigate the corresponding generalization gap. Following similar approaches in Arora al. (2020), shed light upon the generalization problem by investigating the following function class that is closely related to the dual problem of Eq.
Wy == {o oT x, such that 0 satisfying Aa x) 0 Ex0 < {
where 0 and Σx [. Further, assume that the distribution of x is p-retentive for some E (0, 1/2]. that is, if for any non-zero vector v E R4, [A"xx" [v) >
E,, (v (v))))) Such assumption has been similarly assumed in Arora et al. 2020) and
satisfied by general GLMs when has bounded la norm. We then have the following theorem.
Theorem 3.4. Assume that the distribution of x4 is p-retentive, and let Σx empirical Rademacher complexity of Wiy satisfies
E E[rx''
Then the
Rod(W,, 8) ( (2)12
rank(Ex (Ex)
The above bound on Rademacher complexity directly implies the following generalization gap of Mixup training.
Corollary 3.1. Suppose A(.) is La-Lipchitz continuous, X, y and O are all bounded, then there exists constants L, B > O, such that for all 9 satisfying (A Exx < (the regularization induced by Mixup), we have
L(0) < L sld (0, + 2L La
(maxx(
( 22yr
rank(Ex)
B
log (1/0)
2n
with probability al least 1 --
Remark 3.2. This result shows that the Mixup training would adapt to the intrinsic dimension of and therefore has a smaller generalization error. Specifically, if we consider the general ridge penalty and consider the function class Wridge := {r - 0 QTa x, [|0 < 7. then the similar tech- nique would yield a Rademacher complexity bound Rad(W,, S) S max((>/p) (/2
/p/n, where is the dimension of This bound is much larger than the result in Theorem 3.4 when the intrinsic dimension vank(Ex) small.
Non-linear cases. The above results GLM can be extended to the non-linear neural network case with Manifold Mixup (Verma et al. 2019a). In this section, we consider the two-layer ReLU neural networks with the squared loss L(U, S) Ei fo(x:))², where y R and fo(x)) is a two-layer ReLU neural network, with the form of
fo(z) 0. (Wx) + 0o
where W Rxd 0, Rd, and denotes the bias term. Here, consists of W, 9g and 0,.
we perform Mixup on the second layer (i.e., mix neurons on the hidden layer as proposed by Verma et al. 2.19a)), then have the following result the induced regularization.
8

---

Published as a conference paper at ICLR 2021
Lemma 3.4. Denote Ex as the sample covariance matrix of (o(WW;;))))) (= then the regularization term obtained by the second-order approximation of mi (0, )) is given by
ENDD (1 (1-1)2
(8)
A2
# where D2 af ofg 1,3) + a+p (3 + 1,))
To show the generalization property of this regularizer, similar to the last section, we consider the following distribution-depeneee dependent class of functions indexed by 0:
WAy {ar fa)), such that 0 satisfying 0, 0x < <7},
where MX = B|E and O. We then have the following result.
Theorem 3.5. Let Po = [Wx) and denote the generalized inverse of Σ by Ed Suppose X, y and θ are all bounded, then there exists constants L,B > O, such that for all fo in W.y (the regularization induced by Manifold Mixup), have, with probability least 1 8,
L(0) < 1.t (0,5) 7. (r(annk(zg)) |/ Mo 12)
log (1
BV
71
2n
CONCLUSION AND FUTURE WORK
Mixup is data augmentation technique that generates new samples by linear interpolation multi- ple samples and their labels. The Mixup training method has been empirically shown to have better generalization and robustness against attacks with adversarial examples than the traditional training method, but there is lack of rigorous theoretical understanding. In this paper, prove that the Mixup training is approximately a regularized loss minimization. The derived regularization terms then used to demonstrate why Mixup has improved generalization and robustness against one- step adversarial examples. One interesting future direction is to extend our analysis to other Mixup variants, for example, Puzzle Mix (Kim al., 2020) and Adversarial Mixup Resynthesis (Beckham et al., 2019). and investigate if the generalization performance and adversarial robustness can be further improved by these newly developed Mixup methods.
ACKNOWLEDGMENTS
The research of Linjun Zhang supported by NSF DMS-2015378. The research of James Zou is supported by NSF CCF 1763191, NSF CAREER 1942926 and grants from the Silicon Valley Foun- dation and the Chan-Zuckerberrs Initiative. The research of Kenji Kawaguchi is partially supported by the Center of Mathematical Sciences and Applications at Harvard University. This work is also part supported by NSF award 1763665.
REFERENCES
Eric Arazo, Diego Ortego, Paul Albert, Noel E O'Connor, and Kevin McGuinness. Unsupervised label noise modeling and loss correction. arXiv preprint 1.04:/1944.12338 2019.
Raman Arora, Peter Bartlett, Poorya Mianjy, and Nathan Srebro. Dropout: Explicit forms and capacity control. arXiv preprint wwXiv:2003.0339) 2020.
Sanjeev Arora, R Ge, B Neyshabur, and Y Zhang. Stronger generalization bounds for deep nets via compression approach. In 35th International Conference on Machine Learning, ICML 2018, 2018.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Localized rademacher complexities. In International Conference Computational Learning Theory, pp. 44 44-58. Springer, 2002.

---

Published as a conference paper at ICLR 2021
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally normalizee margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 2017.
Christopher Beckham, Sina Honari, Vikas Verma, Alex M Lamb, Farnoosh Ghadiri, R Devon Hjelm, Yoshua Bengio, and Chris Pal. On adversarial mixup resynthesis. In Advances in neural informa- fion processing systems, pp. 4346-4357, 2019.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach semi-supervised learning. In Advances in Neural Information Processing Systems, pp. 5049-5059, 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526 2002.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer. Alexandre Gramfort, Jaques Grobler. Robert Layton, Jake Van- derPlas, Arnaud Joly, Brian Holt, and Gaäl Varoquaux, API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Min- ing and Machine Learning, pp. 108-122, 2013.
Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On mixup regular- ization. arXiv preprint arXiv:2006.06049 2020.
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. NeurIPS Creativity Workshop 2019, 2019.
Jacob Devlin, Ming-Wer Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: /1Xiv:/810.04805, 2018.
Mojtaba Faramarzi, Mohammad Amini, Akilesh Badrinaaraayanan, Vikas Verma, and Sarath Chan- dar. Patchup: regularization technique for convolutional neural networks. arXiv preprint arXiv:2006.07794 2020.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6577 2014.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Mixup as locally linear out-of-manifold regulariza- tion. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 3714-3722, 2019.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1234-1234, PMLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings deep residual networks. In European Conference Computer Vision, pp. 630-645. Springer, 2016b.
David P Helmbold and Philip M Long. On the inductive bias of dropout. The Journal of Machine Learning Research,
2015.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint 1700v:1710.05468, 2017.
Jang-Hyun Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. International Conference on Machine Learning, 2020.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
10

---

Published as a conference paper at ICLR 2021
Alex Lamb, Vikas Verma, Juho Kannala, and Yoshua Bengio. Interpolated adversarial training: Achieving robust neural networks without sacrificing too much accuracy. In Proceedings of the 12th ACM Workshop Artificial Intelligence and Security, pp. 95-103 2019.
Poorya Mianjy, Raman Arora, and Rene Vidal. On the implicit bias of dropout. In International Conference on Machine Learning, pp. 3540-3548, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Behnam Neyshabur and Zhiyuan Li. Towards understanding the role of over-parametrriztion in gen- eralization of neural networks. In International Conference on Learning Representations (ICLR), 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in neural information processing systems, pp- 8026-8037, 2019.
Shizhao Sun, Wei Chen, Liwei Wang, Xiaoguang Liu, and Tin-Yan Liu. On the depth of deep neural networks: theoretical view. arXiv preprint (rXiv::506.05232.. 2015.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint 13Xiv:1312.619 2013.
Sunil Thulasidasan, Gopinath Chennupati, Jeff A Bilmes, Tanmoy Bhattacharya, and Sarah Micha- lak. On mixup training: Improved calibration and predictive uncertainty for deep neural networks. In Advances in Neural Information Processing Systems, pp. 18888-13899, 2019.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint
2018.
V Vapnik. Estimation of dependences based empirical data nauka, 1979.
Vladimir Vapnik. The nature of statistical learning theory. Springer science business media, 2013.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438-6447. PMLR, 2019a.
Vikas Verma, Alex Lamb, Juho Kannala, Yoshua Bengio, and David Lopez-Paz. Interpolation con- sistency training for semi-supervised learning. Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3635-3641. AAAI Press, 2019b.
Stefan Wager, Sida Wang, and Percy S Liang. Dropout training adaptive regularization. In Advances in neural information processing systems, pp. 351-359, 2013.
Sida Wang and Christopher Manning. Fast dropout training. In international conference machine learning, pp. 118-126, 2013.
Colin Wei, Sham Kakade, and Tengyu Ma. The implicit and explicit regularization effects of dropout. arXiv preprint arXiv:2002. /2915, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmin mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint
2017..
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-47) 2012.

---

Published as a conference paper at ICLR 2021
Sangdoo Yun, Dongyoon Han, Scong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. Proceed- ings of the IEEE International Conference Computer Vision, pp. 6023-6032, 2019.
Sergey Zagoruyko and Nikos Komodakis.
Wide residual networks.
arXiv preprint
arXiv:1605.07146, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint /61 2016.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference Learning Representations, 2018.
12

---

Published as a conference paper at ICLR 2021
Appendix
In this appendix, we provide proofs of the main theorems and the corresponding technical lemmas. Additional discussion the range of R in the case of neural nets, and some further numerical experiments are also provided.
A TECHNIQUE PROOFS
A.1 PROOF OF LEMMA 3.1
Consider the following problem with loss function (0) = 1(0, (z, 3)) = -((f(()))-)))) - -ff(x)) that
(0, 1 Σ ( -,,soxx))
The corresponding Mixup version, as defined in iq is
(m, n12
BxxBeta(a,
Σ [b(s((E,,(A)) - (Nys (1 (1)))((
1-=1
where Zej (A) Ax; (1 Alay.
Further transformation leads to
1
1 (0,
E (xxBela(a,3))
Σ { Ay.fo(Ess ++==1
n2
+ (1 ())(f - -( N)urfo(Ens(A1)
1 n2 Be Σ -V))
+ (1 - (L)-B) fo
Note that x ~ Betala, (), BJd ~ (Arn(A), by conjugacy, we can exchange them in order and have
B N Bern
a+ a+ B ~ Beta(a B, + 11 B)-
As result,
n
m.mi (0
Σ
a
n²
1 a B
f,1=1
B
+
E -
+
B
Using the fact 1- Be, 3 11 and Beta(3+1,c) are of the same distribution and ø.g (1 A) (A), we have
-
Σ (xx (
Thus, let DA = a
Betala + 1,8) + at3 Beta + 1,a)
3
a-3
L mixx (0, (0, S)
E ExwD h( Aeạ + (1- A)ra))) v.f(0, Az; (1 A)ra)
n
1
E EAND, E, EnaDD (0)
(9)
13

---

Published as a conference paper at ICLR 2021
where D2 is the empirical distribution induced by training samples, and ã; Ax; + (1 A)rz-
In the following, denote $ = { 1))) and let us analyze I (0. = Σ L...v. (f), and
compare it with (0, Let 1 - À and vha(a) = 12..1 (0). Then, using the definition of the twice-differentiabiltyy of function <);.
1 (0) = ()(()) = (0) + 10 + (0)a² + p;)()a)
(10)
2
where limz-0 (2) = 0. By linearity and chain rule,
va((a) = h)()) (3,) 0ē;
Ö (f{( dā:
Vi 0z, da
ai, da
(z.) (ā.)
0 f (ix)
(Tz - xz) - yi
(ra - xi)
az:
where we used
02, 8a
(rx Zz.). Since
① (fs da dā;
θ (rx -z,) [f((zt)
0i:
(rx 22,) da
TT = x2;) 42 fo(;))
= (r (tr
da
we have
(o) -
2za)
+1"(F((E:))] (50(3s) 2100(1))))1100(1) (rz 2z)]² yo (r T fo()))(2 24)-
0z,
Thus,
(0(0)) (((f((z 2.)22:).VV (ro-z,) (((6)))))
(ra-x:))
W/ (0) = -1((o((z)) - 2,) V2 (0; - m.) + +1(((((2)))V(((((=) - xx:)]
vilre 22) = fo(x)))) =x)--
foo T (r- 2T)(T= n.:) T fo(x)) + (N((f(())) v-) - T T fo(a)(r(>> - -x,)
By substituting these into equation 10 with pl() 1 n E (a)), we obtain the desired statement.
A.2 PROOFS RELATED TO ADVERSARIAL ROBUSTNESS
A.2.1 PROOF OF LEMMA 3.2
Recall that Ladx0(e (8, a
à E max 1o. 1(0, (æ; + v:)) and g(u) 11/(1 + =e"). Then
the second-order Taylor expansion of I(0, (r 6, t)) is given by
1
1(0, (I + 6, 6)) = 1(0, (x, v)) + (g(0 x) - 9) 8T 0 + 70(x To)( 100ggg(x000 0)
Consequently, for any given 17 0.
o max I(A, (x + 8,)) = max 1(0, (I. v)) + (g(0 x)) - v) .T ,0(x TT((1 9(x 0)) T()) (8TØy² 0)2 |
n (g(2 0)(1 g(x g(xTT)) [T)) 110112.
=(( (z. v)) glg T 0) yl ||0| 2
where the maximum is taken when 8 = sgn(g (x [0) y) Tee n
A.2.2 PROOF OF THEOREM 3.1
Since fo(x) x 0, we have V fe(;)) = 0 and fo = 0. Since h(2) = log(1 + e²), we have e
M((z) T+c== g(() 2 0 and h²)))) = (1+e+z g(=)(1 g(=)) > 0. By substituting these into
the equation of Lemma 3.1 with E,, [rz] = 0,
i.nii (0, i. S) + (1, (2,
(11)
14

---

Published as a conference paper at ICLR 2021
where
(1, = Ex((1 - ))
Σ i=1
(vr g(x, 0))0 x4
n
R2, = Ex[(1 2)91
Σ
19(22) (o(x]0)(1- ((,;0))10' Er. 1(r xz)(Tr - -xx)
2n
2=1
Ex[(1 2)12
n
2
19(x; (o(x]0)] 0)(1 g( 0))10 SAIOTEE, Er, 1(ra - xz)(T' - -xx)
2n
i=1
where we used E[=²] = E[ + Var(z) 2 E|a and Er, (r - xi)(ra Iz) T 2 0. Since
E,, IT's 2T)(T= - 2;4 = E., (T2r r rrT + 2,0,] Br, (roT 1 + 2 where
E,, [r=r]] I] is positive semidefinite,
(2) 2 EA[(1 2I22 n
1g(x,00(L ((xT0))e (rrrl + 2,2, )0
2n
Ex((1 2)]²
19(21 () .(x) (0) xx)²
2n
Ex1(1 - 2)1?
19(2, 0) g( 000000001000001110000
2n
1=1
R22 1E 2
m
19(0 0)(1 - g( [(=T00))) 00
2n
Now we bound E' Ex((1 Ch g(x (0) x.) by using 0 E O Since 0 + we have
" ys Jo [x(;)) + (y: (x,) 2 O, which implies that (0 x,) 2 0 y and (0 xx) S if y: = O. Thus, if = 1.
(14 - g( ()) x,) = (1 g 0)) xx,) 2 0, g(x 0)) 2 0 due g(x) 0) E (0, 1). If y 0. (y: - [z ()) x;) g(x () x,) 2 0, since (0Tx;) < 0 and -g(x; 0) < 0. Therefore, for all i = ,,...,n.
since (0T x;) 2 0 and
(ys g( () x2) 2
which implies that, since Ex[(1 - A)] 2 0,
(1, Ex1(1- A)
n
Σ
|y g [=TT0)]000000a 0)100 x11
n
Exl(1 - X)
Σ 19(xT O) vill
sr:)
n
RC,.ExI(1 v)l
Σ
lg(x 0) y: ||0||2
n
1=1
By substituting these lower bounds of (6, S) and R2(0, S) into equation 11 we obtain the desired statement.
A.2.3 PROOF OF THEOREM 3.2
Recall we assume that Ú,, will fall into the set O* with probability at least 1 1- -n. and 8, + 0 as n + co. In addition, define the set
X (r) (x E 2:: cos 0)l > for all 0 O*),
15

---

Published as a conference paper at ICLR 2021
there is (0, 1) such that Xe- (T) + 0, and
pr = P(x Xg-((T) E (0,1).
Let us first study
la 0)(1 - -6x2] (cos(0,,:)))
Since we assume @* is bounded and Co c < ||::|2 & by v for all i, there exists & >> 0, such that (a(x;) (1 - g( 0)) >
we denote p = (number of z/s such that x; E Xe- (T))/n. /n. Then, is easy to see
L..xxg (r) (0 () y(0 0))
(1 - (1-4)/4
=m (r) (0(2)] () g(xg 0))
pi
7
For r72 satisfying
(1 p)/4
17 (1 +
< 72
pr
we have
(0(=)T)(11 0)(1 ((oos0)) 19(xT0)(1 - g(0, 0))(1)²
Σ
19(2, (((TT0(11 0)(1 g(x, g(xT0))) 0))
(T)
|a(x:T 0)(1 1))
(T)
a. (r)
Lastly by Hoeffding's inequality, if we take e = p2/2
(1 + (1 D)/4
< (1 + (1 Pr 12/2)/4
pn
(pr 2)-
with probability at least
2 eexp(-2nE)
4xpp
17 E T(
Pr + 4xpr
Similarly, if we study
10(2, 0) wall (0,s)),z)
By boundedness of 0, x and y E {0, 1}. we know there are constants Ki, K2 > 0, such that
K1 < (g(So(z))) yil < K2
Similarly, we know
P1R1
1) &
26²
Pr (R2 - k1))
Combined together, we can obtain the result:
Pr11
4xp,
< min
}
2x² Pr (N -xi)'
2 Pr 4xp,
16

---

Published as a conference paper at ICLR 2021
A.2.4 PROOF OF THEOREM 3.3
From the assumption, we have fo(zi) V.fo(a;) T xj and V fo(x)) 0. Since h(z) log(1+
we have (2) I+f= g(2) 2 and (2) (1+e=)= = g(2) g(2)) 2 0. By substituting
these into the equation of Lemma 3.1 with _r, = 0.
_ (0, L (0, S) + [)
(12)
where
Ex A) (1,
(y =(fo(((())))
n
Ex 1
R2)
1ra -2)((r (x:() [i) [[)( Σ -(ol)))))) Br,
2n
Ex[(1- 2)1²
2
Σ
(e(S((a)))(
Er ((r - x;)(rz - x:)) [ \
2n
1=1
where we used E[2²] = E[=]² + Var(2) E|z} and V((( Er, (r - -ra) -2i) [ fo(z))
Since E,, [Tr xz) - x;) 2x) E,, 1 T IsY + 2,,0, E,, [r + T
where E,, [rar positive semidefinite.
[1 2)1² n
R2(0,
(B,,, x V fo(zz)
2n
Ex - 2)1²
(o(To(=a)) (V Tx:)²
2n
Ex1(1- - 2)12
Σ
le(fo(x)) //t00///000///01////////31//1110
2n
i=1
R² R²,gE, Ex[( (1 2
(1- [abblc))(((-
2n
Now bound E = ()) Ei_ -V (x)))) by using 0 E O. Since 0 E O, we have fo (xx) + (y 1).f (z:) 2 O, which implies that fz.),) 2 of and fx( S 0 if ys = 0.
Thus, y/ 1,
(u= ((fo(x:)))((((())) = (1 ((0((())))))))((( 20,
since (Jo(x:)) 2 0 and (1 - ((((((())))) 2 0 due to E (0, 1). If =0
(v. (
20,
since (fo(z;)) < 0 and -((f((x)) < Therefore, for all ,..
(y: o(fo(=:))(ff(zz)) 2 0,
which implies that, since Ex - X)] 2 0.
R1 Exi(1 - A]]
y o(f((=))]l16(
n
Ex[(1= - 2)]
Σ
(o(fo(z))) w (otpaa/))///l/////cc///////l////
n
1=
Ro, Ex V "
n
By substituting these lower bounds of F. and F into equation 12 obtain the desired statement.
17

---

Published as a conference paper at ICLR 2021
A.3 PROOFS RELATED TO GENERALIZATION
A.3.1 PROOF LEMMA
AND LEMMA 3.4
We first prove Lemma 3.3 The proof of Lemma 3.4 is similar.
By Eq. (9). we have mix (0, S) = L Lidd(0, (0, 5), where & = {( y)) with é; = Az; + (1 A)r=
and À ~ D a Bela(a + 1, + a+B Bela(B + 1, 1,) Since for Generalized Linear Model (GLM), the prediction is invariant to the scaling of the training data, so it suffices to consider 5 = { y=) with E, (Az, + (1 (1-A)ra) >)ra).
In the following, we analyze (0, 5). For GLM the loss function
1 (0,5) -) Σ La (0)
(y 0 - A()T))). 8)).
where A(-) is the log-partition function in GLMs.
Denote the randomness (of À and r.)) by ç, then the second order Taylor expansion yields
Eg [A( 0) A(xx, 0)] 2nd order approx. E L& (x; xx) 0 + A"x VV
()(;
Notice Eg [ .r.] = 0 and Varç(#;) = 1 E T.p. Σx, then we have the RHS of the last
equation equal to
A² E(1 2)2
X² ) Σxσ.
As result, the second-order Taylor approximation of the Mixup loss (atd(0, S) is
(1 (1-X) X)2
(yror TO
A 0))
A" (x 0)
)0 E xx
2n
X2
(1
A)2
= - -.
(0,
+
A 0)
00 T5x0
2n
X2
This completes the proof of Lemma 3.3 For Lemma 3.4 since the Mixup is performed the final layer of the neural nets, the setting is the same as the least square with covariates a (w) z). Moreover, since we include both the linear coefficients vector 0, and bias term Oo. the prediction is invariant to the shifting and scaling of [w æ). Therefore, we can consider training 0, and 0g on the covariates ((o(W,;) σw) (oWr)) ow)) where ow - (Wa:;) x;)) Moreover, since we consider the least square loss, which special case GLM loss with A(u) Juu we have A" = 1. Plugging these quantities into Lemma 3.3 we get the desired result of Lemma 3.4
A.3.2 PROOF OF THEOREM 3.4 4.4 AND COROLLARY 3.1
By definition, given i.i.d. Rademacher rv. & En, the empirical Rademacher complexity is
Rad(W,, S) = Ee sup U5
00 xt
1=1
Let 8; X122,, x, al)) = [z 0) and 1//20, then prretentiveness condition implies
a(0)² > p. min E, (0 (0xx)) p. m-min(1, T Σx0} and therefore a(0) 00 ΣxO 7 implies that
||a||2 = -xx0 max ma) 3.
18

---

Published as a conference paper at ICLR 2021
As result,
Rad(Wy, S) -Egg
sup
5. Di
a ( xx05>" n
= =I& sup
Erul T 74
a(0)-0-Ex057
t=1
< sup
5,0' T 3;
|| |
$ (2)1/4 v (2)12 Ecll Σ
E ||
1=1
s_ (2/// 22)1/2
Eg ll
Σ
f 11?
i=1
x p
(2)1/4 v (2)1/2
Σ
i=1
Consequently,
n Exg [o] Td!
Rad(W,, Es[Rad(Wy, S)] n
(2)1/ ( Va (2)1 22112 rank(Ex))
1
Based on this bound Rademacher complexity, Corollary 3.1 can be proved by directly applying the following theorem.
Lemma A.1 (Result from Bartlett & Mendelson (2002), ) For any B-uniformly bounded and L- sipchitz,uunction S, for all @ E 4 with probability at least 1 6,
log(1/8)
E((((x;)) <
((((x;)) + 2LRad S) + B
2n
A.3.3
PROOF THEOREM 3.5
To prove Theorem 3.5 by Lemma A.I suffices show the following bound on Rademacher complexity.
Theorem A.1. The empirical Rademacher complexity of W satisfies
Rad(WANN ,S) < 21 7 (rank((2))) + 11 02/ Mo 112)
By definition, given n i.i.d. Rademacher rv. E1,..., En, the empirical Rademacher complexity is
Rad(W,, =Ig sup Wy i=
EOT (WWx)).
19

---

Published as a conference paper at ICLR 2021
Let 0, Ex Ex1/20 and po E(o((w))) then
Rs(Mi =Bgg sup
1
E 1 (o vo) ) E sup
1
Σ
Eg
/x//
Me
WNN n
war
n2
<1101112 |B&e
x / 12
o (Wax))l + 11:11
- |
1
Ha!
$21 7. (rank(E3) + |E 12
M4 113)
n
where the last inequality is obtained by using the same technique in the proof of Lemma 3.4 Combining all the pieces, we get
Rad(Wy, S 7 7.rank
12
B DISCUSSION OF R IN THE NEURAL NETWORK CASE
(B.1). On the value of R = min; R₂ via experiments for neural networks. After training accuracy reaches 100%, the loss is further minimized when (zff(z)))l2 increases. Since
V fo(a;) T., = (
this suggests that R3 and R tend to increase after training accuracy reaches 100%. We confirm this phenomenon in Figure3] In the figure, R initially small but tend to increase after training accuracy reaches 100%, as expected. For example, for ANN, the values of R were initially 2.27 x 10-5 but increased to 6.11 x 10-2 after training. Figure 3 (c) and (d) also show that R2 for each i-th data point tends to increase during training and that the values of R, for many points are much larger than the pessimistic lower bound R: e.g., whereas R 6.11 x 10 2, have R > 0.8 for several data points in 3 (d). For this experiment, we generated 100 data points as T2 ~ No0. 7) and Vi [ 8" 0} where i; R 10 and 0 (O 7). We used SGD to train linear models and ANNs with ReLU activations and 50 neurons per each of two hidden layers. We set the learning rate be 0.1 and the momentum coefficient to be 0.9. We turned off weight decay so that R is not maximized as a result of bounding (/V which is a trivial case from the above discussion.
(B.2). A constant lower bound for neural networks. Similarly, we can obtain constant lower bound by adding some additional conditions.
Assumption B.1. Let us denote θ, C ④ as the set of minimizers of im (0, We assume there exists a set @", such that for all n 2 N, where N is a positive integer, θ, C O with probubility at least 1 - 8n and on -> 0 as -> O. Moreover, there exists r' E (0, 1) such that
Xo- (e, T") fxr Ex cos(æz, Vfo(z)) > [o(x)] > t', for all 0 E
has probability Pr,r' E (0, 1).
Theorem B.1. Define
Fe = (Folo((a.)) = ( De, Vo 0 almost everywhere, 0 E O}.
Under Assumption B.1 for any fo(x) E Fe, if there exists constants bz, C2 > 0 such that cy v d S ||æi|| & by / for all E {1....,n) Then, with probability at least 1 - 8n - 2 exp(ppppppp 2mp /2) /2), there exist constants K 0,K₂ > Kn O. if we further have 0 E ①,,, then
m (0,S)
Tad (Emix Vdd (xt,
where Emix = R.wD, [1-X) and R. minty
(2-p,,,) 15.2
Po Pni (2- (N27" lT.
20

---

Published as a conference paper at ICLR 2021
B.1
PROOF OF THEOREM B.1
Notice if we assume for
Xe- (T, {a E X: cos(2, Vfo(z)) 3 T, Vf((=)] > r', for all 0 E )*),
there is T, 10 such that Xex (T, + 0, and
Prr P( E X (T, +)) (0,1).
Let us first study
1
(o(o()))) y VIll cos (xx;))) m;)
By boundedness of 8, x and y E {0, 1}. we know there is K1, Aig > 0, such that K1 & lo(fe(x:)) Vil & K2
we denote ý = (number of z/s such that x; E No- (T, r')}/// /n. Then, is easy to see
Enjxy (F.77 [(([)(()) vs (x))
(1 1-D))2T"
1 Z. (F,t9) [ff((())) - Voll
For n7 satisfying
111 (1 D)R2T"
E
DKIT'
have
n
n Ig(fo(zz)) v vIlll
- wi ool
Besides, if we consider
Σ
Thus, we have
11 + (1 42/4T"1
E
With probability at least 1 - 2exp( 2n for E = PT.-' /2, we have
Pr.T
K1T'
E minty (2 - pr, 4/47 PT.T' ProcKKT' + (2 Pr. Dreg )rez)
}T
B.2 PROOFS OF THE CLAIM fo(x) (.fo()) AND fe 0 FOR NN WITH RELU/MAX-POOLING
Consider the neural networks with ReLU and max-pooling:
fe(x)= ((t-11(2!!!!))) (1, 0) (1- (2K-11 01). 1, 1.....,
with o (2 (2,, (z,, 0)) = where represents nonlinear function due to ReLU and/or max-pooling,
and Will - matrix of weight parameters connecting the (2 1)-th layer to the I- th layer. For the nonlinear function due ReLU and/or max-pooling, define aill (I. 0)
21

---

Published as a conference paper at ICLR 2021
such that al (x. 0) is diagonal matrix with each element being 0 and old (210
( 0) (x, 0). Using this, we can rewrite the model as:
(z) w W glt ( 0) (1 (z/0)/ilzz
Since (z.0) 0 almost everywhere for all I, which will cancel derivatives except for 8e
dir W we then have that
0fo()) w - w oww Ōx
(13)
Therefore,
0f(()) dr 1 W ( - ... w 0)wllls fo(x).
This proves that fo(x) V fex) T for deep neural networks with ReLU/Max-pooling Moreover, from equation
we have that
V2 fo( V. ( (I 0) W1ig( (x, 0)w(l))) = 0,
since (a.0) 0 almost everywhere for all L. This proves that V2 = 0 for deep neural Or,
networks with MeLU/Max-pooling
C MORE ABOUT EXPERIMENTS
C.I ADVERSARIAL ATTACK AND MIXUP
We demonstrate the comparison between Mixup and standard training against adversarial attacks created by FGSM. We train two WideResNet-166 16-8 (Zagorukko & Komodakis 2016) architectures on the Street View House Numbers SVHN (Netzer et al. 2011)) dataset; one model with regular empirical risk minimization and the other with Mixup loss adversarial attacks (Goodfellow et al. 2014) for 1000 randomly selected test images. Fig. (lab describes the results for the two models. can be observed that the model trained with Mixup loss has better robustness.
5, B 0.5). We create FGSM
C.2 VALIDITY OF THE APPROXIMATION OF ADVERSARIAL LOSS
In this subsection, present numerical experiments support the approximation in Eq. 5 and (6) Under the same setup of our numerical experiments of Figure 2 we experimentally show that the quadratic approximation of the adversarial loss is valid. Specifically, model (as one example of a GLM model, which we study later) and two layer neural network with ReLU activations. We the two-moons dataset (Buitinck al. 2013). Fig. 4 and compare the approximated adversarial loss and the original one along the iterations of computing the original adversarial loss against f attacks. The attack size is chosen such that e ev = 0.5, and both models had the same random initialization scheme. This experiment shows that using second order Taylor expansion yields good approximation of the original adversarial loss.
train Logistic Regression
Adversarial
Approsimate
0.6
0.65
g
0.50
0.000
100
150
200
0.6
150 Esech
300
0.755
100
150
200
25,
180
150
200
Epoch
Epoch
Epoch
Logistc Regression
Two Layer ReLu Neural Network
Figure 4: Comparison of the original adversarial loss with the approximate adversarial loss function.
22

---

Published as a conference paper at ICLR 2021
C.3 GENERALIZATION AND MIXUP
Figures 5H8 show the results of experiments for generalization with various datasets that moti- vated us mathematically study Mixup. We followed the standard experimental setups without any modification as follows. We adopted the standard image datasets, CIFAR-10 (Krizhevsky & Hinton 2009), CIFAR-I00 (Krizhevsky & Hinton 2009). Washion-MNISS (Xiao al. 2017). and Kuzushii- (Clanuwat et al., 2019). For each dataset, we consider two cases: with and with- out standard additional data augmentation for each dataset. We used the standard pre-activation ResNet with 18 layers (He et al.) (016b)) Stochastic gradient descent (SGD) was used to train the models with mini-batch size 64, the momentum coefficient = 0.9, and the learning rate 0.1. All experiments were implemented in PyTorch (Paszke et al. 2019).
Lesk enor
mixup
test loss
mixup
ERM
00-30
epoch
epech
opoch
opach
trinn error
train loss
epech
epoch
epoch
gener comeraliziion gaip (1o5-5)
peveerolittoon pap terror)
genera al Eotion gap (ooss)
goneralizion
224
2/
150
300
125
203
350
100
250
epoch
epoch
epoch
epach
(a) without extra data augmentation
(b) With extra data augmentation
Figure 5: Generalization: CIFAR-10
mibup
Test crros
test loss
ERM
1-300-
6.:00
epech
221
103
100
15
epoch
2/8 14
epoch
opoch
train enror
train loss
train error
train loss
25
14
A+
opoch
opoch
epoch
epoch
reneraaationn gap (loss)
generaliztion gap (enror) 1
lettonn gao (loss)
generaliztion gap
epoch
epoch
epoch
(a) Without extra data augmentation
(b) With extra data augmentation
Figure 6: Generalization: CIFAR-100
23

---

Published as a conference paper at ICLR 2021
10:1 crror
ERM
test loss
ERM
mixup
320
260
360
206
283
epoch
epoch
epoch
epoch
arror
train enor
train loss
125
opoch
epoch
opoch
opoch
generaliziio gap (erro))
gemerall cnnerrlltiioon gap (loss))
pemeraliztion gap (error)
generalliztioon enterrllittion gap (1oss)
epoch
epoch
opoch
epach
Without data augmentation
(b) With data augmentation
Figure 7: Generalization: Fashion-MNIST
test crror
mixup ERM
test loss
mixup ERM
loss
210
299
spoch
train loss
train onor
3
train loss
brin
epoch
epoch
epoch
epoch
generaliztion gap (emor)
genera lzztoon gap (loss)
genera liztion gap (10ss)
peneraliztion
spoch
opoch
epoch
opach
Without extra data augmentation
(b) With data augmentation
Figure 8: Generalization: KuzushijiMMNIST
24


Reviews:
[{"review_id": "yoeffoJjX5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows that Mixup training is approximately certain kind of regularized loss minimization. Based on this, it provides some theoretical analysis on the advantages of Mixup training for the generalization and adversarial robustness over one-step attacks. \n\nThis paper provides many insights on why Mixup works: e.g. connecting its 2nd order approximation with l2 adversarial loss; and shows that the Radmacher complexity of mixup adaptively characterize the intrinsic dimension of empirical data distribution. Though the techniques used in the paper were already developed by other works, the new results and insights on mixup in this work are worthy of being known by the community, particularly for that Mixup is such a popular data augmentation trick in deep learning. \n\nSome questions:\n1.\tCould you provide any comments on Mixup and adversarial training, e.g. one-step and multi-step ones?\n2.\tWhat about the generality of the analysis on L_infinity attacks? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gdZ6Sfy8zkC", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Paper summary**\nThe paper gives theoretical proof showing that the recently proposed data augmentation technique Mixup can indeed improve generalization and help in robustness. The theorems cover GLMs and certain classes of neural networks. The paper also contains numerical experiments supporting some aspects of the theory.\n\n**Strengths**\n1. Currently, there is only a limited theoretical understanding of why Mixup works. This paper shows that Mixup is essentially equal to regularizing the first and second derivatives (with respect to the input $x$). Intuitively, this means that changing the training samples slightly shouldn't change the output of the model much. Further, the paper proves that the mixup loss is an upper bound on the $2^{nd}$ order Taylor approximation of the adversarial loss, and hence reducing mixup loss reduces adversarial loss. Finally, the paper proves that mixup helps in reducing the Rademacher complexity and hence improves generalization.\n2. The results seem fairly general and apply to many models such as GLMs and neural networks.\n3. The paper supports its approximations and claims by numerical experiments.\n\n**Concerns**\n1. The regularizing term $\\mathcal{R}_3$ looks like it is minimizing $z^T\\nabla f_\\theta(x_i) z$ (for some $z$). This promotes the Hessian (wrt $x$) to have negative eigenvalues in the direction of $z$. Ideally, we would want the Hessian (and also the gradient) to be 0 around the training samples so that perturbing the input doesn't change the output much. Thus, I don't see how the $\\mathcal{R}_3$ term helps regularize the Hessian properly.\n2. The paper claims that Assumption 3.1 holds when the minimizers are not too dispersed. Does it still hold for practical neural networks where the minimizers can possible be fairly far apart?\n\n\n**Comments**\nAlthough the paper seems well written, I have a few suggestions:\n1. The notation $cos(\\theta, x)$ which refers to $\\frac{\\langle \\theta, x \\rangle}{\\|\\theta\\|\\|x\\|}$ should be explained in the preliminary section.\n2. On page 6, the statement $f_\\theta(x)=\\nabla f_\\theta(x)^Tx$ should be proven. It will save the reader some time if the proof is provided.\n3. In Remark 3.1, I think Theorem 3.2 should actually be Theorem 3.4\n\n**Score justification**\nThere isn't much prior work on the theoretical understanding of Mixup. This paper provides theoretical guarantees for Mixup on two fronts - robustness and generalization; for both GLMs and ReLUs. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "eQTKN4T0F5-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper theoretically studies the beneficial effect of mixup on robustness and generalization of machine models. The mixup loss is  rewritten to be the sum of the original empirical loss and a regularization term (plus a high order term). For robustness, the regularization term is proven to be upper bound of first and second order terms of the adversarial loss's Taylor expansion. Hence, the mixup loss can upper bound the approximate adversarial loss. For generalization, the regularization term is used to control the hypothesis to have small Rademacher complexity. The paper is clearly written and well organized.\n\npros:\n1. Rigorous theoretical analysis are conducted on non-linear models, specifically the neural network model. \n2. The theoretical results are clean and insightful. \n\ncons:\n1. When studying robustness, an approximated adversarial loss is considered. The approximated loss is the truncation of the Taylor expansion of the original loss. The quality of the approximation is not explored in the paper. It is better to provide numerical evidence that whether the bounds in Thm 3.1 and 3.3 still hold for original adversarial loss, and how tight the bounds are. \n2. In the generalization part, only an indirect connection is built between mixup loss and the generalization gap. no result is provided concerning the generalization error of the solution found by minimizing the mixup loss. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "CkhBlB-AuE5", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper has extensive analysis on mixup augmentation, which focus on the effect of adversarial robustness and generalization. In adversarial robustness, They try to make a connection between mixup loss and adversarial loss, On the other hand of generalization,  they argue that mixup is a kind of data-apdaptive regularization.\n\nComment \n1. Good contribution about author's careful analysis on connecting between mixup loss and adversarial loss. It seems to be the first theoretical analysis on discussing their connection, since the past works just report the number to show how mixup and their variants to be robust to single-step adversarial attack.\n\n2. Good to community about having a connection between Mixup and Rademacher complexity, I think it can make some impact to discuss the high-level connection between data augmentation and model generalization.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides theoretical justifications on why the data augmentation technique, Mixup (convex combinations of pairs of data examples) , can help in improving robustness and generalization of GLMs and ReLUs. The authors rewrote a Mixup loss function as the summation of a standard empirical loss and some regularization terms regularizing gradient, Hessian and some higher order terms. Using the quadratic approximation of the Mixup loss (ignoring the higher order terms), the authors proved that the quadratic approximation of the Mixup loss was equivalent to an upper bound of the second order Taylor expansion of an adversarial loss, providing justifications for why Mixup loss training could improve robustness against small attacks. Using the same quadratic approximation of the Mixup loss, the regularization term controlled the hypothesis class to have a smaller Rademacher complexity.

Overall, the paper provides insightful theoretical interpretations for a commonly used data augmentation technique in DL. The paper also supports its claims by numerical experiments. Although there is some minor concerns on using the quadratic approximation of the Mixup loss, as well as R3 term's regularization effect on a broader family of models, the paper provides unique and novel insights on Mixup.; all reviewers acknowledge the authors applying the existing proof techniques to analyze Mixup's effect on robustness and generalization.

Therefore, I recommend accepting this paper.
Decision: Accept (Spotlight)