HOW DOES MIXUP HELP WITH ROBUSTNESS AND GENERALIZATION?
Year: 2021

Abstract:
Mixup is a popular data augmentation technique based on taking convex combinations 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 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.

heading: 1 INTRODUCTION
text: Mixup was introduced by Zhang et al. (2018) as a data augmentation technique. It has been empirically shown to substantially improve test performance and robustness to adversarial noise of state-of-the-art neural network architectures (Zhang et al., 2018; Lamb et al., 2019; Thulasidasan et al., 2019; Zhang et al., 2018; Arazo et al., 2019). Despite the impressive empirical performance, it 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 we give an overview of our main contributions.
Adversarial robustness. Although neural networks have achieved remarkable success in many areas such as natural language processing (Devlin et al., 2018) and image recognition (He et al., 2016a), it has been observed that neural networks are very sensitive to adversarial examples — prediction can be easily flipped by human imperceptible perturbations (Goodfellow et al., 2014; Szegedy et al., 2013). Specifically, in Goodfellow et al. (2014), the authors use fast gradient sign method (FGSM) to generate adversarial examples, which makes an image of panda to be classified as gibbon with high confidence. Although various defense mechanisms have been proposed against adversarial attacks, those mechanisms typically sacrifice test accuracy in turn for robustness (Tsipras et al., 2018) and many of them require a significant amount of additional computation time. In contrast, Mixup training tends to improve test accuracy and at the same time also exhibits a certain degree of resistance to adversarial examples, such as those generated by FGSM (Lamb et al., 2019). Moreover, the corresponding training time is relatively modest. As an illustration, we compare the robust test
∗Equal contribution.
accuracy between a model trained with Mixup and a model trained with standard empirical risk minimization (ERM) under adversarial attacks generated by FGSM (Fig. 1a). The model trained with Mixup loss has much better robust accuracy. Robustness of Mixup under other attacks have also been empirically studied in Lamb et al. (2019).
Generalization. Generalization theory has been a central focus of learning theory (Vapnik, 1979; 2013; Bartlett et al., 2002; Bartlett & Mendelson, 2002; Bousquet & Elisseeff, 2002; Xu & Mannor, 2012), but it still remains a mystery for many modern deep learning algorithms (Zhang et al., 2016; Kawaguchi et al., 2017). For Mixup, from Fig. (1b), 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 are included in the appendix). While there have been many enlightening studies trying to establish generalization theory for modern machine learning algorithms (Sun et al., 2015; Neyshabur et al., 2015; Hardt et al., 2016; Bartlett et al., 2017; Kawaguchi et al., 2017; Arora et al., 2018; Neyshabur & 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 adversarial 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 regularization terms, we show that Mixup training minimizes an upper bound on the adversarial loss,which leads to the robustness against single-step adversarial attacks. For generalization, we show how the regularization terms can reduce over-fitting and lead to 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 2 introduces the notations and problem setup. In Section 3, we present our main theoretical results, including the regularization effect of Mixup and the subsequent analysis to show that such regularization improves adversarial robustness and generalization. Section 4 concludes with a discussion of future work. Proofs are deferred to the Appendix.

heading: 1.1 RELATED WORK
text: Since its advent, Mixup training (Zhang et al., 2018) has been shown to substantially improve generalization 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 (Berthelot 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 mechanism of why Mixup and its variants perform well on generalization and adversarial robustness is still limited.
Some of the theoretical tools we use in this paper are related to Wang & Manning (2013) and Wager et al. (2013), where the authors use second-order Taylor approximation to derive a 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 matrix factorization (Mianjy et al., 2018), and the implicit regularization in neural networks (Wei et al., 2020). This technique has been recently applied to Mixup in a parallel and independent work (Carratino et al., 2020) to derive regularization terms. Compared with the results in Carratino et al. (2020), our derived regularization enjoys a simpler form and therefore enables the subsequent analysis 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.

heading: 2 PRELIMINARIES
text: In this section, we state our notations and briefly recap the definition of Mixup.
Notations. We denote the general parameterized loss as l(θ, z), where θ ∈ Θ ⊆ Rd and z = (x, y) is the input and output pair. We consider a training dataset S = {(x1, y1), · · · , (xn, yn)}, where xi ∈ X ⊆ Rp and yi ∈ Y ⊆ Rm are i.i.d. drawn from a joint distribution Px,y . We further denote x̃i,j(λ) = λxi + (1 − λ)xj , ỹi,j(λ) = λyi + (1 − λ)yj for λ ∈ [0, 1] and let z̃i,j(λ) = (x̃i,j(λ), ỹi,j(λ)). Let L(θ) = Ez∼Px,y l(θ, z) denote the standard population loss and Lstdn (θ, S) = ∑n i=1 l(θ, zi)/n denote the standard empirical loss. For the two distributions D1 and D2, we use pD1 + (1− p)D2 for p ∈ (0, 1) to denote the mixture distribution such that a sample is drawn with probabilities p and (1 − p) from D1 and D2 respectively. For a parameterized function fθ(x), we use∇fθ(x) and∇θfθ(x) to respectively denote the gradient with respect to x and θ. For two vectors a and b, we use cos(x, y) to denote 〈x, y〉/(‖x‖ · ‖y‖).
Mixup. Generally, for classification cases, the output yi is the embedding of the class of xi, i.e. the one-hot encoding by taking m as the total number of classes and letting yi ∈ {0, 1}m be the binary vector with all entries equal to zero except for the one corresponding to the class of xi. In particular, if we take m = 1, it degenerates to the binary classification. For regression cases, yi can be any real number/vector. The Mixup loss is defined in the following form:
Lmixn (θ, S) = 1
n2 n∑ i,j=1 Eλ∼Dλ l(θ, z̃ij(λ)), (1)
where Dλ is a distribution supported on [0, 1]. Throughout the paper, we consider the most commonly used Dλ – Beta distribution Beta(α, β) for α, β > 0.

heading: 3 MAIN RESULTS
text: 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.

heading: 3.1 THE REGULARIZATION EFFECT OF MIXUP
text: As a starting point, we demonstrate how Mixup training is approximately equivalent to optimizing a regularized version of standard empirical loss Lstdn (θ, S). Throughout the paper, we consider the following class of loss functions for the prediction function fθ(x) and target y:
L = {l(θ, (x, y))|l(θ, (x, y)) = h(fθ(x))− yfθ(x) for some function h}. (2) 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 crossentropy for neural networks. In the following, we introduce a lemma stating that the Mixup training with λ ∼ Dλ = Beta(α, β) induces a regularized loss function with the weights of each regularization specified by a mixture of Beta distributions D̃λ = αα+βBeta(α+ 1, β) + β α+βBeta(β + 1, α).
Lemma 3.1. Consider the loss function l(θ, (x, y)) = h(fθ(x)) − yfθ(x), where h(·) and fθ(·) for all θ ∈ Θ are twice differentiable. We further denote D̃λ as a uniform mixture of two Beta distributions, i.e., αα+βBeta(α+ 1, β) + β α+βBeta(β+ 1, α), andDX as the empirical distribution of the training dataset S = (x1, · · · , xn), the corresponding Mixup loss Lmixn (θ, S), as defined in Eq. (1) with λ ∼ Dλ = Beta(α, β), can be rewritten as
Lmixn (θ, S) = L std n (θ, S) + 3∑ i=1 Ri(θ, S) + Eλ∼D̃λ [(1− λ) 2ϕ(1− λ)],
where lima→0 ϕ(a) = 0 and
R1(θ, S) = Eλ∼D̃λ [1− λ]
n
n∑ i=1 (h′(fθ(xi))− yi)∇fθ(xi)>Erx∼DX [rx − xi],
R2(θ, S) = Eλ∼D̃λ [(1− λ) 2]
2n
n∑ i=1 h′′(fθ(xi))∇fθ(xi)>Erx∼DX [(rx − xi)(rx − xi)>]∇fθ(xi),
R3(θ, S) = Eλ∼D̃λ [(1− λ) 2]
2n
n∑ i=1 (h′(fθ(xi))− yi)Erx∼DX [(rx − xi)∇2fθ(xi)(rx − xi)>].
By putting the higher order terms of approximation in ϕ(·), this result shows that Mixup is related to regularizing ∇fθ(xi) and ∇2fθ(xi), which are the first and second directional derivatives with respect to xi. Throughout the paper, our theory is mainly built upon analysis of the quadratic approximation of Lmixn (θ, S), which we further denote as
L̃mixn (θ, S) := L std n (θ, S) + 3∑ i=1 Ri(θ, S). (3)
Comparison with related work. The result in Lemma 3.1 relies on the second-order Taylor expansion of the loss function Eq. (1). Similar approximations have been proposed before to study the regularization effect of Dropout training, see Wang & Manning (2013); Wager et al. (2013); Mianjy et al. (2018); Wei et al. (2020). Recently, Carratino et al. (2020) independently used similar approximation to study the regularization effect of Mixup. However, the regularization terms derived in Carratino et al. (2020) is much more complicated than those in 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 3 in Carratino et 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 a Logistic Regression model (as one example of a GLM model, which we study later) and a two layer neural network with ReLU activations. We use the two-moons dataset (Buitinck et al., 2013). Fig. 2 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 of Mixup loss is quite close to the original Mixup loss.

heading: 3.2 MIXUP AND ADVERSARIAL ROBUSTNESS
text: Having introduced L̃mixn (θ, S) in Eq. (3), we are now ready to state our main theoretical results. In this subsection, we illustrate how Mixup helps adversarial robustness. We prove that minimizing L̃mixn (θ, S) is equivalent to minimizing an upper bound of the second order Taylor expansion of an adversarial loss.
Throughout this subsection, we study the logistic loss function
l(θ, z) = log(1 + exp(fθ(x)))− yfθ(x),
where y ∈ Y = {0, 1}. In addition, let g be the logistic function such that g(s) = es/(1 + es) and consider the case where θ is in the data-dependent space Θ, defined as
Θ = {θ ∈ Rd : yifθ(xi) + (yi − 1)fθ(xi) ≥ 0 for all i = 1, . . . , n}.
Notice that Θ contains the set of all θ with zero training errors:
Θ ⊇ {θ ∈ Rq : the label prediction ŷi = 1{fθ(xi) ≥ 0} is equal to yi for all i = 1, . . . , 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 θ ∈ Θ is satisfied in finite time in such practical cases with zero training errors.
Logistic regression. As a starting point, we study the logistic regression with fθ(x) = θ>x, in which case the number of parameters coincides with the data dimension, i.e. p = d. For a given ε > 0, we consider the adversarial loss with `2-attack of size ε √ d, that is, Ladvn (θ, S) =
1/n ∑n i=1 max‖δi‖2≤ε √ d l(θ, (xi + δi, yi)). We first present the following second order Taylor approximation of Ladvn (θ, S).
Lemma 3.2. The second order Taylor approximation of Ladvn (θ, S) is ∑n i=1 l̃adv(ε √ d, (xi, yi))/n, where for any η > 0, x ∈ Rp and y ∈ {0, 1},
l̃adv(η, (x, y)) = l(θ, (x, y)) + η|g(x>θ)− y| · ‖θ‖2 + η2
2 · g(x>θ)(1− g(x>θ)) · ‖θ‖22. (5)
By comparing l̃adv(δ, (x, y)) and L̃mixn (θ, S) applied to logistic regression, we prove the following. Theorem 3.1. Suppose that fθ(x) = x>θ and there exists a constant cx > 0 such that ‖xi‖2 ≥ cx √ d for all i ∈ {1, . . . , n}. Then, for any θ ∈ Θ, we have
L̃mixn (θ, S) ≥ 1
n n∑ i=1 l̃adv(εi √ d, (xi, yi)) ≥ 1 n n∑ i=1 l̃adv(εmix √ d, (xi, yi))
where εi = RicxEλ∼D̃λ [1 − λ] with Ri = | cos(θ, xi)|, and εmix = R · cxEλ∼D̃λ [1 − λ] with R = mini∈{1,...,n} | cos(θ, xi)|.
Theorem 3.1 suggests that L̃mixn (θ, S) is an upper bound of the second order Taylor expansion of the adversarial loss with `2-attack of size εmix √ d. Note that εmix depends on θ; one can think the final radius is taken at the minimizer of L̃mixn (θ, S). Therefore, minimizing the Mixup loss would result in a 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 to explore whether combining Mixup with adversarial training is able to provide robustness against larger and more sophisticated attacks such as iterative projected gradient descent and other multiple-step attacks.
Remark 3.1. Note that Theorem 3.1 also implies adversarial robustness against `∞ attacks with size ε since for any attack δ, ‖δ‖∞ ≤ ε implies ‖δ‖2 ≤ ε √ d, and therefore max‖δ‖∞≤ l(θ, (x+δ, y)) ≤ max‖δ‖26 √ d· l(θ, (x+ δ, y)).
In the following we provide more discussion about the range of R = mini∈{1,...,n} | cos(θ, xi)|. 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 a constant lower bound by adding some additional conditions.
Assumption 3.1. Let us denote Θ̂n ⊆ Θ as the set of minimizers of L̃mixn (θ, S). We assume there exists a set Θ∗ 1, such that for all n ≥ N , where N is a positive integer, Θ̂n ⊆ Θ∗ with probability at least 1− δn where δn → 0 as n→ 0. Moreover, there exists a τ ∈ (0, 1) such that
pτ = P ({x ∈ X : | cos(x, θ)| ≥ τ for all θ ∈ Θ∗}) ∈ (0, 1].
Such condition generally holds for regular optimization problems, where the minimizers are not located too dispersedly in the sense of solid angle (instead of Euclidean distance). More specifically, if we normalize all the minimizers’ `2 norm to 1, this assumption requires that the set of minimizers should not be located all over the sphere. In addition, Assumption 3.1 only requires that the probability pτ and the threshold τ to be non-zero. In particular, if the distribution of x has positive mass 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 a solid angle in X that is disjoint with the set of minimizers, the assumption still holds. Theorem 3.2. Under Assumption 3.1, for fθ(x) = x>θ, if there exists constants bx, cx > 0 such that cx √ d ≤ ‖xi‖2 ≤ bx √ d for all i ∈ {1, . . . , n}. Then, with probability at least 1 − δn − 2 exp(−np2τ/2), there exists constants κ > 0, κ2 > κ1 > 0, such that for any θ ∈ Θ̂n, we have
L̃mixn (θ, S) ≥ 1
n n∑ i=1 l̃adv(ε̃mix √ d, (xi, yi))
where ε̃mix = R̃cxEλ∼D̃λ [1− λ] and R̃ = min { pτκ1 2κ2−pτ (κ2−κ1) , √ 4κpτ 2−pτ+4κpτ } τ.
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-pooling. Specifically, we
1Under some well-separation and smoothness conditions, we would expect all elements in Θ̂n will fall into a neighborhood Nn of minimizers of ESL̃mixn (θ, S), and Nn will shrink as n increases, i.e. Nn+1 ⊂ Nn. One can think Θ∗ is a set containing allNn for n ≥ N .
consider the logistic loss, l(θ, z) = log(1 + exp(fθ(x))) − yfθ(x) with y ∈ {0, 1}, where fθ(x) represents a fully connected neural network with ReLU activation function or max-pooling:
fθ(x) = β >σ ( WN−1 · · · (W2σ(W1x) ) .
Here, σ represents nonlinearity via ReLU and max pooling, each Wi is a matrix, and β is a column vector: i.e., θ consists of {Wi}N−1i=1 and β. With the nonlinearity σ for ReLU and max-pooling, the function fθ satisfies that fθ(x) = ∇fθ(x)>x and ∇2fθ(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 ∑n i=1 max‖δi‖2≤ε √ d l(θ, (xi + δi, yi))/n can be written as
Lstdn (θ, S)+εmix √ d( 1
n n∑ i=1 |g(fθ(xi))−yi|‖∇fθ(xi)‖2)+ ε2mixd 2 ( 1 n n∑ i=1 |h′′(fθ(xi))|‖∇fθ(xi)‖22).
(6) With a little abuse of notations, we also denote
l̃adv(δ, (x, y)) = l(θ, (x, y)) + δ|g(fθ(x))− y|‖∇fθ(x)‖2 + δ2d
2 |h′′(fθ(x))|‖∇fθ(x)‖22.
The following theorem suggests that minimizing the Mixup loss in neural nets also lead to a small adversarial loss. Theorem 3.3. Assume that fθ(xi) = ∇fθ(xi)>xi, ∇2fθ(xi) = 0 (which are satisfied by the ReLU and max-pooling activation functions) and there exists a constant cx > 0 such that ‖xi‖2 ≥ cx √ d for all i ∈ {1, . . . , n}. Then, for any θ ∈ Θ, we have
L̃mixn (θ, S) ≥ 1
n n∑ i=1 l̃adv(εi √ d, (xi, yi)) ≥ 1 n n∑ i=1 l̃adv(εmix √ d, (xi, yi))
where εi = RicxEλ∼D̃λ [1 − λ], εmix = R · cxEλ∼D̃λ [1 − λ] and Ri = | cos(∇fθ(xi), xi)|, R = mini∈{1,...,n} | cos(∇fθ(xi), xi)|.
Similar constant lower bound can be derived to the setting of neural networsk. Due to limited space, please see the detailed discussion in the appendix.
On the value of R = miniRi via experiments. For both linear models and neural networks, after training accuracy reaches 100%, the logistic loss is further minimized when ‖fθ(xi)‖2 increases. Since ‖fθ(xi)‖2 = ‖∇fθ(xi)>xi‖2 = ‖∇fθ(xi)‖2‖xi‖2Ri, this suggests that Ri and R tend to increase after training accuracy reaches 100% (e.g., ∇fθ(xi) = θ 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 R was initially 2.27×10−5 but increased to 6.11×10−2 after training. Fig. 3 (c) and (d) also show thatRi for each i-th data point tends to increase during training and that the values of Ri for many points are much larger than the pessimistic lower bound R: e.g., whereas R = 6.11 × 10−2, we have Ri > 0.8 for several data points in Fig. 3 (d). For this experiment, we generated 100 data points as xi ∼ N (0, I) and yi = 1{x>i θ∗ > 0} where xi ∈ R10 and θ∗ ∼ N (0, I). 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 to 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 ‖∇fθ(xi)‖, which is a trivial case from the discussion above.

heading: 3.3 MIXUP AND GENERALIZATION
text: 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 generalization 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:
l(θ, (x, y)) = A(θ>x)− yθ>x,
where A(·) is the log-partition function, x ∈ Rp and y ∈ R. For instance, if we take A(θ>x) = log(1 + eθ
>x) and y ∈ {0, 1}, then the model corresponds to the logistic regression. In this paragraph, 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 ∑n i=1 xi = 0. and denote Σ̂X = 1 nxix > i . For a GLM, if A(·) is twice differentiable, then the regularization term obtained by the second-order approximation of L̃mixn (θ, S) is given by
1
2n [ n∑ i=1 A′′(θ>xi)] · Eλ∼D̃λ [ (1− λ)2 λ2 ]θ>Σ̂Xθ, (7)
where D̃λ = αα+βBeta(α+ 1, β) + α α+βBeta(β + 1, α).
Given the above regularization term, we are ready to investigate the corresponding generalization gap. Following similar approaches in Arora et al. (2020), we shed light upon the generalization problem by investigating the following function class that is closely related to the dual problem of Eq. (7): Wγ := {x→ θ>x, such that θ satisfying ExA′′(θ>x) · θ>ΣXθ 6 γ}, where α > 0 and ΣX = E[xix>i ]. Further, we assume that the distribution of x is ρ-retentive for some ρ ∈ (0, 1/2], that is, if for any non-zero vector v ∈ Rd, [ Ex[A′′(x>v)]
]2 ≥ ρ · min{1,Ex(v>x)2}. Such an assumption has been similarly assumed in Arora et al. (2020) and is satisfied by general GLMs when θ has bounded `2 norm. We then have the following theorem. Theorem 3.4. Assume that the distribution of xi is ρ-retentive, and let ΣX = E[xx>]. Then the empirical Rademacher complexity ofWγ satisfies
Rad(Wγ , S) ≤ max{( γ
ρ )1/4, (
γ ρ )1/2} ·
√ rank(ΣX)
n .
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 Θ are all bounded, then there exists constantsL,B > 0, such that for all θ satisfying ExA′′(θ>x)·θ>ΣXθ 6 γ (the regularization induced by Mixup), we have
L(θ) 6 Lstdn (θ, S) + 2L · LA ·
( max{(γ
ρ )1/4, (
γ ρ )1/2} ·
√ rank(ΣX)
n
) +B √ log(1/δ)
2n ,
with probability at least 1− δ. Remark 3.2. This result shows that the Mixup training would adapt to the intrinsic dimension of x and therefore has a smaller generalization error. Specifically, if we consider the general ridge penalty and consider the function class Wridgeγ := {x → θ>x, ‖θ‖2 6 γ}, then the similar technique would yield a Rademacher complexity bound Rad(Wγ , S) ≤ max{(γ/ρ)1/4, (γ/ρ)1/2} ·√ p/n, where p is the dimension of x. This bound is much larger than the result in Theorem 3.4 when the intrinsic dimension rank(ΣX) is small.
Non-linear cases. The above results on 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(θ, S) = 1n ∑n i=1(yi − fθ(xi))2, where y ∈ R and fθ(x) is a two-layer ReLU neural network, with the form of
fθ(x) = θ > 1 σ ( Wx ) + θ0.
where W ∈ Rp×d, θ1 ∈ Rd, and θ0 denotes the bias term. Here, θ consists of W , θ0 and θ1. If we perform Mixup on the second layer (i.e., mix neurons on the hidden layer as proposed by Verma et al. (2019a)), we then have the following result on the induced regularization.
Lemma 3.4. Denote Σ̂σX as the sample covariance matrix of {σ(Wxi)}ni=1, then the regularization term obtained by the second-order approximation of L̃mixn (θ, S) is given by
Eλ∼D̃λ [ (1− λ)2 λ2 ]θ>1 Σ̂ σ Xθ1, (8)
where D̃λ ∼ αα+βBeta(α+ 1, β) + β α+βBeta(β + 1, α).
To show the generalization property of this regularizer, similar to the last section, we consider the following distribution-dependent class of functions indexed by θ:
WNNγ := {x→ fθ(x), such that θ satisfying θ>1 ΣσXθ1 6 γ},
where ΣσX = E[Σ̂σX ] and α > 0. We then have the following result. Theorem 3.5. Let µσ = E[σ(Wx)] and denote the generalized inverse of ΣσX by Σ σ† X . Suppose X , Y and Θ are all bounded, then there exists constants L,B > 0, such that for all fθ inWNNγ (the regularization induced by Manifold Mixup), we have, with probability at least 1− δ,
L(θ) 6 Lstdn (θ, S) + 4L ·
√ γ · (rank(ΣσX) + ‖Σ σ†/2 X µσ‖2)
n +B
√ log(1/δ)
2n .

heading: 4 CONCLUSION AND FUTURE WORK
text: Mixup is a data augmentation technique that generates new samples by linear interpolation of multiple 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 a lack of rigorous theoretical understanding. In this paper, we prove that the Mixup training is approximately a regularized loss minimization. The derived regularization terms are then used to demonstrate why Mixup has improved generalization and robustness against onestep adversarial examples. One interesting future direction is to extend our analysis to other Mixup variants, for example, Puzzle Mix (Kim et 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.

heading: ACKNOWLEDGMENTS
text: The research of Linjun Zhang is 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 Foundation and the Chan-Zuckerberg Initiative. The research of Kenji Kawaguchi is partially supported by the Center of Mathematical Sciences and Applications at Harvard University. This work is also in part supported by NSF award 1763665.

heading: Appendix
text: In this appendix, we provide proofs of the main theorems and the corresponding technical lemmas. Additional discussion on the range of R in the case of neural nets, and some further numerical experiments are also provided.

heading: A TECHNIQUE PROOFS

heading: A.1 PROOF OF LEMMA 3.1
text: Consider the following problem with loss function lx,y(θ) := l(θ, (x, y)) = h(fθ(x))−yfθ(x), that is
Lstdn (θ, S) = 1
n n∑ i=1 [h(fθ(xi))− yifθ(xi)].
The corresponding Mixup version, as defined in Eq.(1), is
Lmixn (θ, S) = 1
n2 Eλ∼Beta(α,β) n∑ i,j=1 [h(fθ(x̃i,j(λ)))− (λyi + (1− λ)yj)fθ(x̃i,j(λ))],
where x̃i,j(λ) = λxi + (1− λ)xj . Further transformation leads to
Lmixn (θ, S) = 1
n2 Eλ∼Beta(α,β) n∑ i,j=1 { λh(fθ(x̃i,j(λ))))− λyifθ(x̃i,j(λ))
+ (1− λ)h(fθ(x̃i,j(λ)))− (1− λ)yjfθ(x̃i,j(λ)) }
= 1
n2 Eλ∼Beta(α,β)EB∼Bern(λ) n∑ i,j=1 { B[h(fθ(x̃i,j(λ)))− yifθ(x̃i,j(λ))]
+ (1−B)[h(fθ(x̃i,j(λ)))− yjfθ(x̃i,j(λ))] }
Note that λ ∼ Beta(α, β), B|λ ∼ Bern(λ), by conjugacy, we can exchange them in order and have
B ∼ Bern( α α+ β ), λ | B ∼ Beta(α+B, β + 1−B).
As a result,
Lmixn (θ, S) = 1
n2 n∑ i,j=1 { α α+ β Eλ∼Beta(α+1,β)[h(fθ(x̃i,j(λ)))− yifθ(x̃i,j(λ))]
+ β
α+ β Eλ∼Beta(α,β+1)[h(fθ(x̃i,j(λ)))− yjfθ(x̃i,j(λ))]
} .
Using the fact 1−Beta(α, β+1) andBeta(β+1, α) are of the same distribution and x̃ij(1−λ) = x̃ji(λ), we have ∑
i,j
Eλ∼Beta(α,β+1)[h(fθ(x̃i,j(λ)))− yjfθ(x̃i,j(λ))]
= ∑ i,j Eλ∼Beta(β+1,α)[h(fθ(x̃i,j(λ)))− yifθ(x̃i,j(λ))].
Thus, let D̃λ = αα+βBeta(α+ 1, β) + β α+βBeta(β + 1, α)
Lmixn (θ, S) = 1
n n∑ i=1 Eλ∼D̃λErx∼Dxh(f(θ, λxi + (1− λ)rx)))− yif(θ, λxi + (1− λ)rx)
= 1
n n∑ i=1 Eλ∼D̃λErx∼Dx lx̌i,yi(θ) (9)
where Dx is the empirical distribution induced by training samples, and x̌i = λxi + (1− λ)rx. In the following, denote Š = {(x̌i, yi)}ni=1, and let us analyze Lstdn (θ, Š) = 1n ∑n i=1 lx̌i,yi(θ), and compare it with Lstdn (θ, S). Let α = 1− λ and ψi(α) = lx̌i,yi(θ). Then, using the definition of the twice-differentiability of function ψi,
lx̌i,yi(θ) = ψi(α) = ψi(0) + ψ ′ i(0)α+
1 2 ψ′′i (0)α 2 + α2ϕi(α), (10)
where limz→0 ϕi(z) = 0. By linearity and chain rule,
ψ′i(α) = h ′(fθ(x̌i))
∂fθ(x̌i)
∂x̌i
∂x̌i ∂α − yi ∂fθ(x̌i)
∂x̌i
∂x̌i ∂α
= h′(fθ(x̌i)) ∂fθ(x̌i)
∂x̌i (rx − xi)− yi
∂fθ(x̌i)
∂x̌i (rx − xi)
where we used ∂x̌i∂α = (rx − xi). Since
∂
∂α
∂fθ(x̌i)
∂x̌i (rx−xi) =
∂
∂α (rx−xi)>[
∂fθ(x̌i)
∂x̌i ]> = (rx−xi)>∇2fθ(x̌i) ∂x̌i ∂α = (rx−xi)>∇2fθ(x̌i)(rx−xi),
we have
ψ′′i (α) =h ′(fθ(x̌i))(rx − xi)>∇2fθ(x̌i)(rx − xi)
+ h′′(fθ(x̌i))[ ∂fθ(x̌i)
∂x̌i (rx − xi)]2 − yi(rx − xi)>∇2fθ(x̌i)(rx − xi).
Thus,
ψ′i(0) = h ′(fθ(xi))∇fθ(xi)>(rx−xi)−yi∇fθ(xi)>(rx−xi) = (h′(fθ(xi))−yi)∇fθ(xi)>(rx−xi)
ψ′′i (0) =h ′(fθ(xi))(rx − xi)>∇2fθ(xi)(rx − xi) + h′′(fθ(xi))[∇fθ(xi)>(rx − xi)]2
− yi(rx − xi)>∇2fθ(xi)(rx − xi). =h′′(fθ(xi))∇fθ(xi)>(rx − xi)(rx − xi)>∇fθ(xi) + (h′(fθ(xi))− yi)(rx − xi)>∇2fθ(xi)(rx − xi)
By substituting these into equation 10 with ϕ(α) = 1n ∑n i=1 ϕi(α), we obtain the desired statement.

heading: A.2 PROOFS RELATED TO ADVERSARIAL ROBUSTNESS

heading: A.2.1 PROOF OF LEMMA 3.2
text: Recall that Ladvn (θ, S) = 1 n ∑n i=1 max‖δi‖2≤ε √ d l(θ, (xi + δi, yi)) and g(u) = 1/(1 + e
−u). Then the second-order Taylor expansion of l(θ, (x+ δ, t)) is given by
l(θ, (x+ δ, y)) = l(θ, (x, y)) + (g(θ>x)− y) · δ>θ + 1 2 g(x>θ)(1− g(x>θ)) · (δ>θ)2.
Consequently, for any given η > 0,
max ‖δ‖2≤η l(θ, (x+ δ, y)) = max ‖δ‖2≤η l(θ, (x, y)) + (g(θ>x)− y) · δ>θ + 1 2 g(x>θ)(1− g(x>θ)) · (δ>θ)2
=l(θ, (x, y)) + η|g(x>θ)− y| · ‖θ‖2 + η2
2 (g(x>θ)(1− g(x>θ))) · ‖θ‖2,
where the maximum is taken when δ = sgn(g(x>θ)− y) · θ‖θ‖ · η.

heading: A.2.2 PROOF OF THEOREM 3.1
text: Since fθ(x) = x>θ, we have ∇fθ(xi) = θ and ∇2fθ(xi) = 0. Since h(z) = log(1 + ez), we have h′(z) = e z
1+ez = g(z) ≥ 0 and h ′′(z) = e
z
(1+ez)2 = g(z)(1 − g(z)) ≥ 0. By substituting these into the equation of Lemma 3.1 with Erx [rx] = 0,
L̃mixn (θ, S) = L̃ mix n (θ, S) +R1(θ, S) +R2(θ, S), (11)
where
R1(θ, S) = Eλ[(1− λ)]
n
n∑ i=1 (yi − g(x>i θ))θ>xi
R2(θ, S) = Eλ[(1− λ)2]
2n
n∑ i=1 |g(x>i θ)(1− g(x>i θ))|θ>Erx [(rx − xi)(rx − xi)>]θ
≥ Eλ[(1− λ)] 2
2n
n∑ i=1 |g(x>i θ)(1− g(x>i θ))|θ>Erx [(rx − xi)(rx − xi)>]θ
where we used E[z2] = E[z]2 + Var(z) ≥ E[z]2 and θ>Erx [(rx − xi)(rx − xi)>]θ ≥ 0. Since Erx [(rx − xi)(rx − xi)>] = Erx [rxr>x − rxx>i − xir>x + xix>i ] = Erx [rxr>x ] + xix>i where Erx [rxr>x ] is positive semidefinite,
R2(θ, S) ≥ Eλ[(1− λ)]2
2n
n∑ i=1 |g(x>i θ)(1− g(x>i θ))|θ>(Erx [rxr>x ] + xix>i )θ.
≥ Eλ[(1− λ)] 2
2n
n∑ i=1 |g(x>i θ)(1− g(x>i θ))|(θ>xi)2
= Eλ[(1− λ)]2
2n
n∑ i=1 |g(x>i θ)(1− g(x>i θ))|‖θ‖22‖xi‖22(cos(θ, xi))2
≥ R 2c2xEλ[(1− λ)]2d
2n
n∑ i=1 |g(x>i θ)(1− g(x>i θ))|‖θ‖22
Now we bound E = Eλ[(1−λ)]n ∑n i=1(yi − g(x>i θ))(θ>xi) by using θ ∈ Θ. Since θ ∈ Θ, we have yifθ(xi) + (yi − 1)fθ(xi) ≥ 0, which implies that (θ>xi) ≥ 0 if yi = 1 and (θ>xi) ≤ 0 if yi = 0. Thus, if yi = 1, (yi − g(x>i θ))(θ>xi) = (1− g(x>i θ))(θ>xi) ≥ 0, since (θ>xi) ≥ 0 and (1− g(x>i θ)) ≥ 0 due to g(x>i θ) ∈ (0, 1). If yi = 0,
(yi − g(x>i θ))(θ>xi) = −g(x>i θ)(θ>xi) ≥ 0,
since (θ>xi) ≤ 0 and −g(x>i θ) < 0. Therefore, for all i = 1, . . . , n,
(yi − g(x>i θ))(θ>xi) ≥ 0,
which implies that, since Eλ[(1− λ)] ≥ 0,
R1(θ, S) = Eλ[(1− λ)]
n
n∑ i=1 |yi − g(x>i θ)||θ>xi|
= Eλ[(1− λ)]
n
n∑ i=1 |g(x>i θ)− yi|‖θ‖2‖xi‖2| cos(θ, xi)|
≥ RcxEλ[(1− λ)] √ d
n
n∑ i=1 |g(x>i θ)− yi|‖θ‖2
By substituting these lower bounds ofR1(θ, S) andR2(θ, S) into equation 11, we obtain the desired statement.

heading: A.2.3 PROOF OF THEOREM 3.2
text: Recall we assume that θ̂n will fall into the set Θ∗ with probability at least 1 − δn, and δn → 0 as n→∞. In addition, define the set
XΘ∗(τ) = {x ∈ X : | cos(x, θ)| > τ for all θ ∈ Θ∗},
there is τ ∈ (0, 1) such that XΘ∗(τ) 6= ∅, and
pτ := P(x ∈ XΘ∗(τ)) ∈ (0, 1).
Let us first study
1
n n∑ i=1 |g(x>i θ)(1− g(x>i θ))|(cos(θ, xi))2
Since we assume Θ∗ is bounded and cx √ d 6 ‖xi‖2 6 bx √ d for all i, there exists κ > 0, such that |g(x>i θ)(1− g(x>i θ))| > κ. If we denote p̂ = {number of x′is such that xi ∈ XΘ∗(τ)}/n. Then, it is easy to see
1 n ∑ xi∈X cΘ∗ (τ)
|g(x>i θ)(1− g(x>i θ))| 1 n ∑ xi∈XΘ∗ (τ) |g(x > i θ)(1− g(x>i θ))| 6 (1− p̂)/4 p̂κ
For η2 satisfying
η2(1 + (1− p̂)/4
p̂κ ) 6 τ2
we have
1
n n∑ i=1 |g(x>i θ)(1− g(x>i θ))|(cos(θ, xi))2 > 1 n ∑ xi∈XΘ∗ (τ) |g(x>i θ)(1− g(x>i θ))|τ2
> 1
n ∑ xi∈XΘ∗ (τ) |g(x>i θ)(1− g(x>i θ))|η2 + 1 n ∑ xi∈X cΘ∗ (τ) |g(x>i θ)(1− g(x>i θ))|η2.
Lastly by Hoeffding’s inequality, if we take ε = pτ/2
(1 + (1− p̂)/4
p̂κ ) 6 (1 + (1− pτ/2)/4 (pτ/2)κ )
with probability at least 1− 2 exp(−2nε2)
η 6 τ
√ 4κpτ
2− pτ + 4κpτ .
Similarly, if we study n∑ i=1 |g(x>i θ)− yi|| cos(θ, x)|
By boundedness of θ, x and y ∈ {0, 1}, we know there are constants κ1, κ2 > 0, such that
κ1 6 |g(fθ(xi))− yi| 6 κ2
Similarly, we know
η 6 pτκ1
2κ2 − pτ (κ2 − κ1) τ.
Combined together, we can obtain the result:
η 6 min{ pτκ1 2κ2 − pτ (κ2 − κ1) ,
√ 4κpτ
2− pτ + 4κpτ }τ

heading: A.2.4 PROOF OF THEOREM 3.3
text: From the assumption, we have fθ(xi) = ∇fθ(xi)>xi and∇2fθ(xi) = 0. Since h(z) = log(1+ez), we have h′(z) = e z
1+ez = g(z) ≥ 0 and h ′′(z) = e
z
(1+ez)2 = g(z)(1 − g(z)) ≥ 0. By substituting these into the equation of Lemma 3.1 with Erx [rx] = 0,
L̃mixn (θ, S) = L̃ mix n (θ, S) +R1(θ, S) +R2(θ, S), (12)
where
R1(θ, S) = Eλ[(1− λ)]
n
n∑ i=1 (yi − g(fθ(xi)))fθ(xi)
R2(θ, S) = Eλ[(1− λ)2]
2n
n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|∇fθ(xi)>Erx [(rx − xi)(rx − xi)>]∇fθ(xi)
≥ Eλ[(1− λ)] 2
2n
n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|∇fθ(xi)>Erx [(rx − xi)(rx − xi)>]∇fθ(xi)
where we used E[z2] = E[z]2 +Var(z) ≥ E[z]2 and∇fθ(xi)>Erx [(rx−xi)(rx−xi)>]∇fθ(xi) ≥ 0. Since Erx [(rx − xi)(rx − xi)>] = Erx [rxr>x − rxx>i − xir>x + xix>i ] = Erx [rxr>x ] + xix>i where Erx [rxr>x ] is positive semidefinite,
R2(θ, S) ≥ Eλ[(1− λ)]2
2n
n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|∇fθ(xi)>(Erx [rxr>x ] + xix>i )∇fθ(xi).
≥ Eλ[(1− λ)] 2
2n
n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|(∇fθ(xi)>xi)2
= Eλ[(1− λ)]2
2n
n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|‖∇fθ(xi)‖22‖xi‖22(cos(∇fθ(xi), xi))2
≥ R 2c2xEλ[(1− λ)]2d
2n
n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|‖∇fθ(xi)‖22
Now we bound E = Eλ[(1−λ)]n ∑n i=1(yi − g(fθ(xi)))fθ(xi) by using θ ∈ Θ. Since θ ∈ Θ, we have yifθ(xi) + (yi − 1)fθ(xi) ≥ 0, which implies that fθ(xi) ≥ 0 if yi = 1 and fθ(xi) ≤ 0 if yi = 0. Thus, if yi = 1,
(yi − g(fθ(xi)))(fθ(xi)) = (1− g(fθ(xi)))(fθ(xi)) ≥ 0,
since (fθ(xi)) ≥ 0 and (1− g(fθ(xi))) ≥ 0 due to g(fθ(xi)) ∈ (0, 1). If yi = 0,
(yi − g(fθ(xi)))(fθ(xi)) = −g(fθ(xi))(fθ(xi)) ≥ 0,
since (fθ(xi)) ≤ 0 and −g(fθ(xi)) < 0. Therefore, for all i = 1, . . . , n,
(yi − g(fθ(xi)))(fθ(xi)) ≥ 0,
which implies that, since Eλ[(1− λ)] ≥ 0,
R1(θ, S) = Eλ[(1− λ)]
n
n∑ i=1 |yi − g(fθ(xi))||fθ(xi)|
= Eλ[(1− λ)]
n
n∑ i=1 |g(fθ(xi))− yi|‖∇fθ(xi)‖2‖xi‖2| cos(∇fθ(xi), xi)|
≥ RcxEλ[(1− λ)] √ d
n
n∑ i=1 |g(fθ(xi))− yi|‖∇fθ(xi)‖2
By substituting these lower bounds of E and F into equation 12, we obtain the desired statement.

heading: A.3 PROOFS RELATED TO GENERALIZATION

heading: A.3.1 PROOF OF LEMMA 3.3 AND LEMMA 3.4
text: We first prove Lemma 3.3. The proof of Lemma 3.4 is similar.
By Eq. (9), we have Lmixn (θ, S) = L std n (θ, Š), where Š = {(x̌i, yi)}ni=1 with x̌i = λxi + (1− λ)rx and λ ∼ D̃λ = αα+βBeta(α + 1, β) + β
α+βBeta(β + 1, α). Since for Generalized Linear Model (GLM), the prediction is invariant to the scaling of the training data, so it suffices to consider S̃ = {(x̃i, yi)}ni=1 with x̃i = 1λ̄ (λxi + (1− λ)rx).
In the following, we analyze Lstdn (θ, S̃). For GLM the loss function is
Lstdn (θ, S̃) = 1
n n∑ i=1 lx̃i,yi(θ) = 1 n n∑ i=1 −(yix̃>i θ −A(x̃>i θ)),
where A(·) is the log-partition function in GLMs. Denote the randomness (of λ and rx) by ξ, then the second order Taylor expansion yields
Eξ[A(x̃>i θ)−A(x>i θ)] 2nd−order approx. = Eξ[A′(x>i θ)(x̃i − xi)>θ +A′′(x>i θ)V ar(x̃>i θ)]
Notice Eξ[x̃i − xi] = 0 and V arξ(x̃i) = 1n ∑n i=1 xix > i = Σ̂X , then we have the RHS of the last equation equal to
A′′(x>i θ)( E(1− λ)2
λ̄2 )θ>Σ̂Xθ.
As a result, the second-order Taylor approximation of the Mixup loss Lstdn (θ, S̃) is
n∑ i=1 −(yix>i θ −A(x>i θ)) + 1 2n [ n∑ i=1 A′′(x>i θ)]E( (1− λ)2 λ2 )θ>Σ̂Xθ
=Lstdn (θ, S) + 1
2n [ n∑ i=1 A′′(x>i θ)]E( (1− λ)2 λ2 )θ>Σ̂Xθ.
This completes the proof of Lemma 3.3. For Lemma 3.4, since the Mixup is performed on the final layer of the neural nets, the setting is the same as the least square with covariates σ(w>j x). Moreover, since we include both the linear coefficients vector θ1 and bias term θ0, the prediction is invariant to the shifting and scaling of σ(w>j x). Therefore, we can consider training θ1 and θ0 on the covariates {(σ(Wxi) − σ̄W ) + 1−λλ (σ(Wrx) − σ̄W )} n i=1, where σ̄W = 1 n ∑n i=1 σ(Wxi). Moreover, since we consider the least square loss, which is a special case of GLM loss with A(u) = 12u 2, we have A′′ = 1. Plugging these quantities into Lemma 3.3, we get the desired result of Lemma 3.4.

heading: A.3.2 PROOF OF THEOREM 3.4 AND COROLLARY 3.1
text: By definition, given n i.i.d. Rademacher rv. ξ1, ..., ξn, the empirical Rademacher complexity is
Rad(Wγ , S) = Eξ sup a(θ)·θ>ΣXθ≤γ
1
n n∑ i=1 ξiθ >xi
Let x̃i = Σ †/2 X xi, a(θ) = Ex[A′′(x>θ)] and v = Σ 1/2 X θ, then ρ-retentiveness condition implies a(θ)2 ≥ ρ ·min{1,Ex(θ>x)2} ≥ ρ ·min{1, θ>ΣXθ} and therefore a(θ) · θ>ΣXθ ≤ γ implies that ‖v‖2 = θ>ΣXθ ≤ max{(γρ ) 1/2, γρ}.
As a result,
Rad(Wγ , S) =Eξ sup a(θ)·θ>ΣXθ≤γ
1
n n∑ i=1 ξiθ >xi
=Eξ sup a(θ)·θ>ΣXθ≤γ
1
n n∑ i=1 ξiv >x̃i
≤Eξ sup ‖v‖2≤( γρ )1/2∨ γ ρ
1
n n∑ i=1 ξiv >x̃i
≤ 1 n · (γ ρ )1/4 ∨ (γ ρ )1/2 · Eξ‖ n∑ i=1 ξix̃i ‖
≤ 1 n · (γ ρ )1/4 ∨ (γ ρ )1/2 · √√√√Eξ‖ n∑ i=1 ξix̃i ‖2
≤ 1 n · (γ ρ )1/4 ∨ (γ ρ )1/2 · √√√√ n∑ i=1 x̃>i x̃i .
Consequently,
Rad(Wγ , S) = ES [Rad(Wγ , S)] ≤ 1 n · (γ ρ )1/4 ∨ (γ ρ )1/2 · √√√√ n∑ i=1 Exi [x̃>i x̃i]
≤ 1√ n · (γ ρ )1/4 ∨ (γ ρ )1/2 · rank(ΣX).
Based on this bound on 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 LLipchitz function ζ, for all φ ∈ Φ, with probability at least 1− δ,
Eζ(φ(xi)) ≤ 1
n n∑ i=1 ζ(φ(xi)) + 2LRad(Φ, S) +B
√ log(1/δ)
2n .

heading: A.3.3 PROOF OF THEOREM 3.5
text: To prove Theorem 3.5, by Lemma A.1, it suffices to show the following bound on Rademacher complexity.
Theorem A.1. The empirical Rademacher complexity ofWNNγ satisfies
Rad(WNNγ , S) ≤ 2
√ γ · (rank(ΣσX) + ‖Σ σ†/2 X µσ‖2)
n .
By definition, given n i.i.d. Rademacher rv. ξ1, ..., ξn, the empirical Rademacher complexity is
Rad(Wγ , S) =Eξ sup Wγ
1
n n∑ i=1 ξiθ > 1 σ(Wxi).
Let θ̃1 = Σ σ1/2 X θ1 and µσ = E[σ(Wx)], then
RS(WNNγ ) =Eξ sup WNNγ
1
n n∑ i=1 ξiθ̃ > 1 Σ σ†/2 X (σ(Wxi)− µσ) + Eξ sup WNNγ 1 n n∑ i=1 ξiθ̃ > 1 Σ σ†/2 X µσ
≤‖θ̃1‖2 · ‖Eξ[ 1
n n∑ i=1 ξiΣ σ†/2 X σ(Wxi)]‖+ ‖θ̃1‖ · 1√ n ‖Σσ†/2X µσ‖
≤2
√ γ · (rank(ΣσX) + ‖Σ σ†/2 X µσ‖2)
n ,
where the last inequality is obtained by using the same technique as in the proof of Lemma 3.4.
Combining all the pieces, we get Rad(Wγ , S) ≤ √ γ · rank(ΣσX)
n .

heading: B DISCUSSION OF R IN THE NEURAL NETWORK CASE
text: (B.1). On the value of R = miniRi via experiments for neural networks. After training accuracy reaches 100%, the loss is further minimized when ‖fθ(xi)‖2 increases. Since
‖fθ(xi)‖2 = ‖∇fθ(xi)>xi‖2 = ‖∇fθ(xi)‖2‖xi‖2Ri,
this suggests that Ri and R tend to increase after training accuracy reaches 100%. We confirm this phenomenon in Figure 3. In the figure,R is 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 × 10−5 but increased to 6.11 × 10−2 after training. Figure 3 (c) and (d) also show that Ri for each i-th data point tends to increase during training and that the values of Ri for many points are much larger than the pessimistic lower bound R: e.g., whereas R = 6.11× 10−2, we have Ri > 0.8 for several data points in Figure 3 (d). For this experiment, we generated 100 data points as xi ∼ N (0, I) and yi = 1{x>i θ∗ > 0} where xi ∈ R10 and θ∗ ∼ N (0, I). 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 to 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 ‖∇fθ(xi)‖, which is a trivial case from the above discussion. (B.2). A constant lower bound for neural networks. Similarly, we can obtain a constant lower bound by adding some additional conditions.
Assumption B.1. Let us denote Θ̂n ⊆ Θ as the set of minimizers of L̃mixn (θ, S). We assume there exists a set Θ∗, such that for all n ≥ N , where N is a positive integer, Θ̂n ⊆ Θ∗ with probability at least 1− δn and δn → 0 as n→ 0. Moreover, there exists τ, τ ′ ∈ (0, 1) such that
XΘ∗(τ, τ ′) = {x ∈ X : | cos(x,∇fθ(x))| > τ, ‖∇fθ(x)‖ > τ ′, for all θ ∈ Θ∗},
has probability pτ,τ ′ ∈ (0, 1). Theorem B.1. Define
FΘ := {fθ|fθ(xi) = ∇fθ(xi)>xi,∇2fθ(xi) = 0 almost everywhere, θ ∈ Θ}.
Under Assumption B.1, for any fθ(x) ∈ FΘ, if there exists constants bx, cx > 0 such that cx √ d ≤
‖xi‖2 ≤ bx √ d for all i ∈ {1, . . . , n}. Then, with probability at least 1 − δn − 2 exp(−np2τ,τ ′/2), there exist constants κ > 0, κ2 > κ1 > 0, if we further have θ ∈ Θ̂n, then
L̃mixn (θ, S) ≥ 1
n n∑ i=1 l̃adv(ε̃mix √ d, (xi, yi))
where ε̃mix = R̃cxEλ∼D̃λ [1−λ] and R̃ = min{ √
pτ,τ′κτ ′2
(2−pτ,τ′ )/4τ ′′2+pτ,τ′κτ ′2 ,
pτ,τ′κ1τ ′
pτ,τ′κ1τ ′+(2−pτ,τ′ )κ2τ ′′
}τ.

heading: B.1 PROOF OF THEOREM B.1
text: Notice if we assume for
XΘ∗(τ, τ ′) = {x ∈ X : | cos(x,∇fθ(x))| > τ, ‖∇fθ(x)‖ > τ ′, for all θ ∈ Θ∗},
there is τ, τ ′ ∈ (0, 1) such that XΘ∗(τ, τ ′) 6= ∅, and
pτ,τ ′ := P(x ∈ XΘ∗(τ, τ ′)) ∈ (0, 1).
Let us first study 1
n n∑ i=1 |g(fθ(xi))− yi|‖∇fθ(xi)‖2| cos(∇fθ(xi), xi)|
By boundedness of θ, x and y ∈ {0, 1}, we know there is κ1, κ2 > 0, such that
κ1 6 |g(fθ(xi))− yi| 6 κ2
If we denote p̂ = {number of x′is such that xi ∈ XΘ∗(τ, τ ′)}/n. Then, it is easy to see
1 n ∑ xi∈X cΘ∗ (τ,τ ′)
||g(fθ(xi))− yi|‖∇fθ(xi)‖2 1 n ∑ xi∈XΘ∗ (τ,τ ′) |g(fθ(xi))− yi|‖∇fθ(xi)‖2 6 (1− p̂)κ2τ ′′ p̂κ1τ ′
For η2 satisfying
η(1 + (1− p̂)κ2τ ′′
p̂κ1τ ′ ) 6 τ
we have
1
n n∑ i=1 |g(fθ(xi))− yi|‖∇fθ(xi)‖2 cos(∇fθ(xi), xi)| > 1 n n∑ i=1 |g(fθ(xi))− yi|‖∇fθ(xi)‖2η
Besides, if we consider n∑ i=1 |g(fθ(xi))(1− g(fθ(xi)))|‖∇fθ(xi)‖22(cos(∇fθ(xi), xi))2
Thus, we have
η2(1 + (1− p̂)/4τ ′′2
p̂κτ ′2 ) 6 τ2
With probability at least 1− 2 exp(−2nε2), for ε = pτ,τ ′/2, we have
η 6 min{
√ pτ,τ ′κτ ′2
(2− pτ,τ ′)/4τ ′′2 + pτ,τ ′κτ ′2 ,
pτ,τ ′κ1τ ′
pτ,τ ′κ1τ ′ + (2− pτ,τ ′)κ2τ ′′ }τ
B.2 PROOFS OF THE CLAIM fθ(x) = ∇fθ(x)>x AND ∇2fθ(x) = 0 FOR NN WITH RELU/MAX-POOLING
Consider the neural networks with ReLU and max-pooling:
fθ(x) = W [L]σ[L−1] ( z[L−1] ) , z[l](x, θ) = W [l]σ(l−1) ( z[l−1](x, θ) ) , l = 1, 2, . . . , L− 1,
with σ(0) ( z[0](x, θ) ) = x, where σ represents nonlinear function due to ReLU and/or max-pooling, and W [l] ∈ RNl×Nl−1 is a matrix of weight parameters connecting the (l − 1)-th layer to the lth layer. For the nonlinear function σ due to ReLU and/or max-pooling, we can define σ̇[l](x, θ)
such that σ̇[l](x, θ) is a diagonal matrix with each element being 0 or 1, and σ[l] ( z[l](x, θ) ) =
σ̇[l](x, θ)z[l](x, θ). Using this, we can rewrite the model as:
fθ(x) = W [L]σ̇[L−1](x, θ)W [L−1]σ̇[L−2](x, θ) · · ·W [2]σ̇[1](x, θ)W [1]x.
Since ∂σ̇ [l](x,θ) ∂x = 0 almost everywhere for all l, which will cancel all derivatives except for
d dxW [1]x, we then have that
∂fθ(x)
∂x = W [L]σ̇[L−1](x, θ)W [L−1]σ̇[L−2](x, θ) · · ·W [2]σ̇[1](x, θ)W [1]. (13)
Therefore,
∂fθ(x)
∂x x = W [L]σ̇[L−1](x, θ)W [L−1]σ̇[L−2](x, θ) · · ·W [2]σ̇[1](x, θ)W [1]x = fθ(x).
This proves that fθ(x) = ∇fθ(x)>x for deep neural networks with ReLU/Max-pooling. Moreover, from equation 13, we have that
∇2fθ(x) = ∇x(W [L]σ̇[L−1](x, θ)W [L−1]σ̇[L−2](x, θ) · · ·W [2]σ̇[1](x, θ)W [1]) = 0,
since ∂σ̇ [l](x,θ) ∂x = 0 almost everywhere for all l. This proves that ∇
2fθ(x) = 0 for deep neural networks with ReLU/Max-pooling.

heading: C MORE ABOUT EXPERIMENTS

heading: C.1 ADVERSARIAL ATTACK AND MIXUP
text: We demonstrate the comparison between Mixup and standard training against adversarial attacks created by FGSM. We train two WideResNet-16-8 (Zagoruyko & 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 one with Mixup loss (α = 5, β = 0.5). We create FGSM adversarial attacks (Goodfellow et al., 2014) for 1000 randomly selected test images. Fig. (1a) describes the results for the two models. It can be observed that the model trained with Mixup loss has better robustness.
C.2 VALIDITY OF THE APPROXIMATION OF ADVERSARIAL LOSS
In this subsection, we present numerical experiments to 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, we train a Logistic Regression model (as one example of a GLM model, which we study later) and a two layer neural network with ReLU activations. We use the two-moons dataset (Buitinck et al., 2013). Fig. 4, and compare the approximated adversarial loss and the original one along the iterations of computing the original adversarial loss against `2 attacks. The attack size is chosen such that √ d = 0.5, and both models had the same random initialization scheme. This experiment shows that using second order Taylor expansion yields a good approximation of the original adversarial loss.

heading: C.3 GENERALIZATION AND MIXUP

Review summaries:
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.