Year: 2020

Abstract:
Data augmentation is a widely used training trick in deep learning to improve the network generalization ability. Despite many encouraging results, several recent studies did point out limitations of the conventional data augmentation scheme in certain scenarios, calling for a better theoretical understanding of data augmentation. In this work, we develop a comprehensive analysis that reveals pros and cons of data augmentation. The main limitation of data augmentation arises from the data bias, i.e. the augmented data distribution can be quite different from the original one. This data bias leads to a suboptimal performance of existing data augmentation methods. To this end, we develop two novel algorithms, termed “AugDrop” and “MixLoss”, to correct the data bias in the data augmentation. Our theoretical analysis shows that both algorithms are guaranteed to improve the effect of data augmentation through the bias correction, which is further validated by our empirical studies. Finally, we propose a generic algorithm “WeMix” by combining AugDrop and MixLoss, whose effectiveness is observed from extensive empirical evaluations.

heading: 1 INTRODUCTION
text: Data augmentation (Baird, 1992; Schmidhuber, 2015) has been a key to the success of deep learning in image classification (He et al., 2019), and is becoming increasingly common in other tasks such as natural language processing (Zhang et al., 2015) and object detection (Zoph et al., 2019). The data augmentation expands training set by generating virtual instances through random augmentation to the original ones. This alleviates the overfitting (Shorten & Khoshgoftaar, 2019) problem when training large deep neural networks. Despite many encouraging results, it is not the case that data augmentation will always improve generalization errors (Min et al., 2020; Raghunathan et al., 2020). In particular, Raghunathan et al. (2020) showed that training by augmented data will lead to a smaller robust error but potentially a larger standard error. Therefore, it is critical to answer the following two questions before applying data augmentation in deep learning:
• When will the deep models benefit from data augmentation? • How to better leverage augmented data during training?
Several previous works (Raghunathan et al., 2020; Wu et al., 2020; Min et al., 2020) tried to address the questions. Their analysis is limited to specific problems such as linear ridge regression therefore may not be applicable to deep learning. In this work, we aim to answer the two questions from a theoretical perspective under a more general non-convex setting. We address the first question in a more general form covering applications in deep learning. For the second question, we develop new approaches that are provably more effective than the conventional data augmentation approaches.
Most data augmentation operations alter the data distribution during the training progress. This imposes a data distribution bias (we simply use “data bias” in the rest of this paper) between the augmented data and the original data, which may make it difficult to fully leverage the augmented data. To be more concrete, let us consider label-mixing augmentation (e.g., mixup (Zhang et al., 2018; Tokozume et al., 2018)). Suppose we have n original data D = {(xi,yi), i = 1, . . . , n}, where the input-label pair (xi,yi) follows a distribution Pxy = (Px,Py(·|x)), Px is the marginal distribution of the inputs and Py(·|x) is the conditional distribution of the labels given inputs; we generate m augmented data D̃ = {(x̃i, ỹi), i = 1, . . . ,m}, where (x̃i, ỹi) ∼ Px̃ỹ = (Px̃,Pỹ(·|x̃)),
and Px = Px̃ but Py(·|x) 6= Pỹ(·|x̃). Given x ∼ Px, the data bias is defined as δy = maxy,ỹ ‖y − ỹ‖. We will show that when the bias between D and D̃ is large, directly training on the augmented data will not be as effective as training on the original data.
Given the fact that augmented data may hurt the performance, the next question is how to design better learning algorithms to leash out the power of augmented data. To this end, we develop two novel algorithms to alleviate the data bias. The first algorithm, termed AugDrop, corrects the data bias by introducing a constrained optimization problem. The second algorithm, termed MixLoss, corrects the data bias by introducing a modified loss function. We show that, both theoretically and empirically, even with a large data bias, the proposed algorithms can still improve the generalization performance by effectively leveraging the combination of augmented data and original data. We summarize the main contributions of this work as follows:
• We prove that in a conventional training scheme, a deep model can benefit from augmented data when the data bias is small.
• We design two algorithms termed AugDrop and MixLoss that can better leverage augmented data even when the data bias is large with theoretical guarantees.
• Based on our theoretical findings, we empirically propose a new efficient algorithm WeMix by combining AugDrop and MixLoss , which has better performances without extra training cost.

heading: 2 RELATED WORK
text: A series of empirical works (Cubuk et al., 2019; Ho et al., 2019; Lim et al., 2019; Lin et al., 2019a; Cubuk et al., 2020; Hataya et al., 2019) on how to learn a good policy of using different data augmentations have been proposed without theoretical guarantees. In this section, we mainly focus on reviewing theoretical studies on data augmentation. For a survey of data augmentation, we refer readers to (Shorten & Khoshgoftaar, 2019) and references therein for a comprehensive overview.
Several works have attempted to establish theoretical understandings of data augmentation from different perspectives (Dao et al., 2019; Chen et al., 2019; Rajput et al., 2019). Min et al. (2020) shown that, with more training data, weak augmentation can improve performance while strong augmentation always hurts the performance. Later on, Chen et al. (2020) study the gap between the generalization error (please see the formal definition in (Chen et al., 2020)) of adversarially-trained models and standard models. Both of their theoretical analyses were built on special linear binary classification model or linear regression model for label-preserving augmentation.
Recently, Raghunathan et al. (2020) studied label-preserving transformation in data augmentation, which is identical to the first case in this paper. Their analysis is restricted to linear least square regression under noiseless setting, which is not applicable to training deep neural networks. Besides, their analysis requires infinite unlabeled data. By contrast, we do not require the original data to be unlimited. Wu et al. (2020) considered linear data augmentations. There are several major differences between their work and ours. First, they focus on the ridge linear regression problem which is strongly convex, while we consider non-convex optimization problems, which is more applicable in deep learning. Second, we study more general data augmentations beyond linear transformation.

heading: 3 PRELIMINARIES AND NOTATIONS
text: We study a learning problem for finding a classifier to map an input x ∈ X onto a label y ∈ Y ⊂ RK , where K is the number of classes. We assume the input-label pair (x,y) is drawn from a distribution Pxy = (Px,Py(·|x)). Since every augmented example (x̃, ỹ) is generated by applying a certain transformation to either one or multiple examples, we will assume that (x̃, ỹ) is drawn from a slightly different distribution Px̃ỹ = (Px̃,Pỹ(·|x̃)), where Px̃ is the marginal distribution on the inputs x̃ and Pỹ(·|x̃)) (we can write it as Pỹ for simplicity) is the conditional distribution of the labels ỹ given inputs x̃. We sample n training examples (xi,yi), i = 1, . . . , n from distribution Pxy and m training examples (x̃i, ỹi), i = 1, . . . ,m from Px̃ỹ. We assume that m n due to the data augmentation. We denote by D = {(xi,yi), i = 1, . . . , n} and D̃ = (x̃i, ỹi), i = 1, . . . ,m} the dataset sampled from Pxy and Px̃ỹ, respectively. We denote by T (x) the set of augmented data transformed from x. We use the notation E(x,y)∼Pxy [·] to stand for the expectation that takes over a random variable (x,y) following a distribution Pxy. We denote by ∇wh(w) the gradient of a function h(w) in terms of variable w. When the variable to be taken a gradient is obvious, we use
the notation ∇h(w) for simplicity. Let use ‖ · ‖ as the Euclidean norm for a vector or the Spectral norm for a matrix.
The augmented data D̃ can be different from the original data D in two cases, according to (Raghunathan et al., 2020). In the first case, often referred to as label-preserving, we consider
Py(·|x) = Pỹ(·|x̃), ∀x̃ ∈ T (x) but Px 6= Px̃. (1)
In the second case, often referred to as label-mixing, we consider
Px = Px̃ but Py(·|x) 6= Pỹ(·|x̃),∃x̃ ∈ T (x). (2)
Examples of label-preserving augmentation include translation, adding noises, small rotation, and brightness or contrast changes (Krizhevsky et al., 2012; Raghunathan et al., 2020). One important example of label-mixing augmentation is mixup (Zhang et al., 2018; Tokozume et al., 2018). Due to the space limitation, we will focus on the label-mixing case, and the related studies and analysis for the label-preserving case can be found in Appendix A. To further quantify the difference between original data and augmented data when Px = Px̃ and Py 6= Pỹ, we introduce the data bias δy given x ∼ Px as following:
δy := max y,ỹ ‖y − ỹ‖. (3)
The equation in (3) measures the difference between the label from original data and the label from augmented data given input x. We aim to learn a prediction function f(x;w) : RD × X → RK that is as close as possible to y, where w ∈ RD is the parameter and RD is a closed convex set. We respectively define two objective functions for optimization problems over the original data and the augmented data as
L(w) = E(x,y) [` (y, f(x;w))] , L̃(w) = E(x̃,ỹ) [` (ỹ, f(x̃;w))] , (4)
where ` is a cross-entropy loss function which is given by
`(y, f(x;w)) = K∑ i=1 yipi(x;w), where pi(x;w) = − log ( exp(fi(x;w))∑K j=1 exp(fj(x;w)) ) . (5)
We denote by w∗ and w̃∗ the optimal solutions to minw L(w) and minw L̃(w) respectively,
w∗ ∈ arg min w∈RD L(w), w̃∗ ∈ arg min w∈RD L̃(w). (6)
Taking L(w) as an example, we introduce some function properties used in our analysis. Definition 1. The stochastic gradients of the objective functions L(w) is unbiased and bounded, if we have E(x,y) [∇w` (y, f(x;w))] = ∇L(w), and there exists a constant G > 0, such that ‖∇wp(x;w)‖ ≤ G,∀x ∈ X ,∀w ∈ RD, where p(x;w) = (p1(x;w), . . . , pK(x;w)) is a vector. Definition 2. L(w) is smooth with an L-Lipchitz continuous gradient, if there exists a constant L > 0 such that ‖∇L(w)−∇L(u)‖ ≤ L‖w− u‖,∀w,u ∈ RD, or equivalently, L(w)−L(u) ≤ 〈∇L(u),w − u〉+ L2 ‖w − u‖
2,∀w,u ∈ RD. The above properties are standard and widely used in the literature of non-convex optimization (Ghadimi & Lan, 2013; Yan et al., 2018; Yuan et al., 2019; Wang et al., 2019; Li et al., 2020). We introduce an important property termed Polyak-Łojasiewicz (PL) condition (Polyak, 1963) on the objective function L(w). Definition 3. (PL condition) L(w) satisfies the PL condition, if there exists a constant µ > 0 such that 2µ(L(w)− L(w∗)) ≤ ‖∇L(w)‖2,∀w ∈ RD, where w∗ is defined in (6). The PL condition has been observed in training deep and shallow neural networks (Allen-Zhu et al., 2019; Xie et al., 2017), and is widely used in many non-convex optimization studies (Karimi et al., 2016; Li & Li, 2018; Charles & Papailiopoulos, 2018; Yuan et al., 2019; Li et al., 2020). It is also theoretically verified in (Allen-Zhu et al., 2019) and empirically estimated in (Yuan et al., 2019) for deep neural networks. It is worth noting that PL condition is weaker than many conditions such as strong convexity, restricted strong convexity and weak strong convexity (Karimi et al., 2016).
Finally, we will refer to κ = Lµ as condition number throughout this study.

heading: 4 MAIN RESULTS
text: In this section, we present the main results for label-mixing augmentation satisfying (2). Due to the space limitation, we present the results of label-preserving augmentation satisfying (1) in Appendix A. Since we have access to m n augmented data, it is natural to fully leverage the augmented data D̃ during training. But on the other hand, due to the data bias δy , the prediction model learned from augmented data D̃ could be even worse than training the prediction model directly from the original data D, as revealed by Lemma 1 (its proof can be found in Appendix C) and its remark. Throughout this section, suppose that a mini-batch SGD is used for optimization, i.e. to optimize L(w), we have
wt+1 = wt − η
m0 m0∑ k=1 ∇w` (yk,t, f(xk,t;wt)) , (7)
where η is the step size, m0 is the batch size, and (xk,t,yk,t), k = 1, . . . ,m0 are sampled from D. A similar mini-batch SGD algorithm can be developed for the augmented data.
Lemma 1. Assume that L and L̃ satisfy properties in Definition 1, 2 and 3, by setting η = 1/L and m0 ≥ 8δ2y , when t ≥ L µ log 4(L(w1)−L(w∗))µ δ2yG 2 , we have
E[L(wt+1)− L(w∗)] ≤ δ2yG2/µ ≤ O(δ2y/µ), (8)
where wt+1 is output of mini-batch SGD trained on D̃, δy is defined in (3).
Remark: It is easy to verify (see the details of proof in Appendix D) that if we simply train the learning model by the original data D, we have
E [L(wn+1)− L(w∗)] ≤ O ( L log(n)/(nµ2) ) . (9)
Comparing the result in (9) with the result of (8) in Lemma 1, it is easy to show that, when the data bias is too large, i.e., δ2y ≥ Ω(L log(n)/(nµ)), we have O ( L log(n)/(nµ2) ) ≤ O(δ2y/µ). This implies that training the deep model directly on the original data D is more effective than on the augmented data D̃. Hence, in order to better leverage the augmented data in the presence of large data bias (δ2y ≥ Ω(κ log(n)/n), where κ = L/µ), we need to come up with approaches that automatically correct the data bias. Below, we develop two approaches to correct the data bias. The first approach, termed “AugDrop”, corrects the data bias by introducing a constrained optimization approach, and the second approach, termed “MixLoss”, addresses the problem by introducing a modified loss function.
4.1 AugDrop: CORRECTING DATA BIAS BY CONSTRAINED OPTIMIZATION To address this challenge, we propose a constrained optimization problem, i.e.
min w∈RD
L(w) s.t. L̃(w)− L̃(w̃∗) ≤ γ, (10)
where γ > 0 is a positive constant, w̃∗ is defined in (6). The key idea is that by utilizing the augmented data to constrain the solution in a small region, we will be able to enjoy a smaller condition number, leading to a better performance in optimizing L(w). To make it concrete, we first define three important terms:
γ0 := δ 2 yG 2/(2µ), A(γ) = { w : L̃(w)− L̃(w̃∗) ≤ γ } , (11)
µ(γ) = max µ′
{ L(w)− L(w∗) ≤ ‖∇L(w)‖2/(2µ′),w ∈ A(γ) } . (12)
We then present a proposition about A(γ) and µ(γ), whose proof is included in Appendix E. Proposition 1. If γ ∈ [γ0, 8γ0], we have w∗ ∈ A(γ) and µ(γ) ≥ µ.
According to Proposition 1, by restricting our solutions inA(γ), we have a smaller condition number (since µ(γ) ≥ µ) and consequentially a smaller optimization error. It is worth mentioning that the restriction of solutions in A(γ) is reasonable due to the optimal solution w∗ ∈ A(γ). The idea of using augmentation transformation to restrict the candidate solution was recognized by several
earlier studies, e.g. (Raghunathan et al., 2020). But none of these studies cast it into a constrained optimization problem, a key contribution of our work.
The next question is how to solve the constrained optimization problem in (10). It is worth noting that neither L(w) nor L̃(w) is convex. Although multiple approaches can be used to solve nonconvex constrained optimization problems (Cartis et al., 2011; Lin et al., 2019b; Birgin & Martı́nez, 2020; Grapiglia & Yuan, 2019; Wright, 2001; O’Neill & Wright, 2020; Boob et al., 2019; Ma et al., 2019), they are too complicated to be implemented in deep learning. Instead, we present a simple approach that divides the optimization into two stages, which is referred to as AugDrop (Please see the details of update steps from Algorithm 2 in Appendix F).
• Stage I. We minimize L̃(w) over the augmented data D̃. It runs a mini-batch SGD against D̃ at least T1 iterations with the size of mini-batch beingm1. We denote by wT1+1 the final output solution of this stage.
• Stage II. We minimize L(w) using the original data D. It initializes the solution wT1+1 and runs a mini-batch SGD against D in n/m2 iterations with mini-batch size being m2.
We notice that AugDrop is closely related to TSLA by (Xu et al., 2020) where the first stage trains the data with label smoothing and the second stage trains the data without label smoothing. However, they study the problem how to reduce the variance of stochastic gradient in using label smoothing, while we study how to correct bias in data augmentation by solving a constrained optimization problem. The following theorem states that if we run this two stage optimization algorithm, we could achieve a better performance since µ(8γ0) is larger than µ. We include its proof in Appendix F.
Theorem 1. Define µc = µ(8γ0). Assume that L and L̃ satisfy properties in Definition 1, 2 and 3, set learing rate η1 = 1/L in Stage I and learning rate η2 = 12nµc log
( 8nµ2c(L(w1)−L(w∗))
G2L
) in Stage
II for AugDrop. Let w1 be the initial solution in Stage I of AugDrop and wT1+2, . . . ,wT1+n/m2+1 be the intermediate solutions obtained by the mini-batch SGD in Stage II of AugDrop. Choose
T1 = 1 η1µ log 2(L̃(w1)−L̃(w̃∗))µδ2yG2 , m1 =
( 1 + √ 3 log 2T1δ )2 8 δ2y and m2 = ( 1 + √ 3 log 2nδ )2 4 δ2y ,
with a probability 1− δ, we have wt ∈ A(8γ0),∀t ∈ {T1 + 2, . . . , T1 + n/m2 + 1} and
E [L(ŵ)− L(w∗)] ≤ G2L
4nµ2c
( 1 + log ( 4nµ2c(L(w1)− L(w∗))
G2L
)) ≤ O ( L log(n)
nµ2c
) , (13)
where ŵ = wT1+n/m2+1 and δy is defined in in (3).
Remark. Theorem 1 shows that all intermediate solutions wt obtained in Stage II of AugDrop satisfy the constraint L̃(wt) − L̃(w̃∗) ≤ 8γ0, that is to say, wt ∈ A(8γ0). Based on Proposition 1, we will enjoy a larger µc than µ. Comparing the result of (13) in Theorem 1 with (9), training by using AugDrop will result in a better performance than directly training on D due to µc ≥ µ. Besides, when the data bias is large, i.e., δ2y ≥ Ω(L log(n)/(nµ)), we know O(L log(n)/(nµ2c)) ≤ O(µδ2y/µ2c) ≤ O(δ2y/µ), where the last inequality holds due to µc ≥ µ. By comparing (13) with the result of (8) in Lemma 1, we know that training by using AugDrop has a better performance than directly training on D̃ when the data bias is large. By solving a constrained problem, the AugDrop algorithm can correct the data bias and thus can enjoy an better performance.
4.2 MixLoss: CORRECTING DATA BIAS BY MODIFIED LOSS FUNCTION Without loss of generality, we set L(w∗) = 0, a common property observed in training deep neural networks (Zhang et al., 2016; Allen-Zhu et al., 2019; Du et al., 2018; 2019; Arora et al., 2019; Chizat et al., 2019; Hastie et al., 2019; Yun et al., 2019; Zou et al., 2020). Since ‖y − ỹ‖ ≤ δy for any y and ỹ and given x, we define a new loss function `a(ỹ, f(x̃;w)) as
`a(ỹ, f(x̃;w)) = min ‖z−ỹ‖≤δy `(z, f(x̃;w)). (14)
It has been shown that since the cross-entropy loss `(z, ·) is convex in terms of z ∈ Y , then the minimization problem (14) is a convex optimization problem and has a closed form solution (Boyd & Vandenberghe, 2004). Using this new loss, we define a new objective function La(w)
La(w) = E(x̃,ỹ) [`a(ỹ, f(x̃;w))] = E(x̃,ỹ) [
min ‖z−ỹ‖≤δy `(z, f(x̃;w))
] . (15)
Algorithm 1 WeMix 1: Input: T1, T2, stochastic algorithms A1, A2 (e.g., momentum SGD, SGD) 2: Initialize: w1 ∈ RD, λ ∈ (0, 1), η1, η2 > 0
// First stage: Weighted Mixed Losses 3: for t = 1, 2, . . . , T1 do 4: draw examples (xit ,yit) at random from training data construct stochastic gradient of L 5: generate augmented examples (x̃jt , ỹjt) construct stochastic gradient of La 6: compute stochastic gradient ĝt = λ∇`(yit , f(xit ;wt)) + (1− λ)∇`a(ỹit , f(x̃it ;wt)) 7: wt+1 = A1(wt; ĝt, η1) update one step of A1 8: end for
// Second stage: Augmentation Dropping 9: for t = T1 + 1, T1 + 2, . . . , T1 + T2 do
10: draw examples (xit ,yit) at random from training data construct stochastic gradient of L 11: compute stochastic gradient ĝt = ∇`(yit , f(xit ;wt)) 12: wt+1 = A2(wt; ĝt, η2) update one step of A2 13: end for 14: Output: wT1+T2+1.
It is easy to verify that La(w∗) = 0 and therefore w∗ also minimizes La(w) (see Appendix G). In contrast, w̃∗, the minimizer of L̃(w), can be very different from w∗. Hence, we can correct the data bias arising from the augmented data by replacing L̃(w) with La(w), leading to the following optimization problem:
min w∈RD
Lc(w) = λL(w) + (1− λ)La(w), (16)
where λ ∈ (0, 1). Since Lc(w) shares the same minimizer with L(w) (see Appendix G), it is sufficient to optimize Lc(w), instead of optimizing L(w). The main advantage of minimizing Lc(w) over L(w) is that by introducing a small λ, we will be able to reduce the variance in computing the gradient of Lc(w), and therefore improve the overall convergence. More specifically, our SGD method is given as follows: at each iteration t, we compute the approximate gradient as ĝt = λ∇`(yt, f(xt;wt)) + (1− λ) 1m0 ∑m0 i=1∇`a(ỹt,i, f(x̃t,i;wt)), where (xt,yt) is an example sampled from D at iteration t. We refer to this approach as MixLoss (Please see the details of update steps from Algorithm 3 in Appendix H). We then give the convergence result in the following theorem, whose proof is included in Appendix H.
Theorem 2. Assume that L, L̃ and La satisfy properties in Definition 1, 2 and 3, by setting m0 ≥ 72(1−λ)2
λ2 and η = 1 µn log nµ2L(w1) λ2LG2 ≤ 1 2L in MixLoss, we have
E [L(wn+1)− L(w∗)] ≤ λLG2
nµ2
( 1 + 5 log
nµ2L(w1) λ2LG2
) ≤ O ( λL log(n/λ2)
nµ2
) . (17)
Remark. According to the results in (17) and (9), we know that O ( λL log(n/λ2)/(nµ2) ) ≤
O ( L log(n)/(nµ2) ) when an appropriate λ ∈ (0, 1) is selected, leading to a better performance by using MixLoss compared with the performance trained on the original data D. For example, one can simply use λ = O(µ/L). On the other hand, when the data bias is large where δ2y satisfying δ 2 y ≥ Ω(L log(n)/(nµ))), we know O(L log(n)/(nµ2)) ≤ O(δ2y/µ). Based on
previous discussion, by choosing an appropriate λ ∈ (0, 1) (e.g., λ = O(µ/L)), we will have O ( λL log(n/λ2)/(nµ2) ) ≤ O(δ2y/µ). Then by comparing (17) with (8), we know that training by using MixLoss has a better performance than directly training on D̃ when the data bias is large. Therefore, by solving the problem with a modified loss function, the MixLoss algorithm can enjoy a better performance by correcting the data bias.
4.3 WeMix: A GENERIC WEIGHTED MIXED LOSSES WITH AUGMENTATION DROPPING ALGORITHM
Inspired by previous theoretical analysis of using augmented data, we propose a generic framework of weighted mixed losses with augmentation dropping that builds upon two algorithms, AugDrop and MixLoss. Algorithm 1 describes our procedure in detail, which is referred to as WeMix. It consists of two stages, wherein the first stage it runs a stochastic algorithm A1 (e.g., momentum SGD, SGD) for solving weighted mixed losses (16) and the second stage it runs another/same
stochastic algorithm A2 (e.g., momentum SGD, SGD) for solving the problem over original data. The notation A(·; ·, η) is one update step of a stochastic algorithm A with learning rate η. For example, if we select SGD as algorithmA, then SGD(wt; ĝt, η) = wt−ηĝt. The proposed WeMix is a generic strategy where the subroutine algorithm A1/A2 can be replaced by any stochastic algorithms such as stochastic versions of momentum methods (Polyak, 1964; Nesterov, 1983; Yan et al., 2018) and adaptive methods (Duchi et al., 2011; Hinton et al., 2012; Zeiler, 2012; Kingma & Ba, 2015; Dozat, 2016; Reddi et al., 2018). We can also replace `a by ` to avoid solving a minimization problem. The last solution of the first stage will be used as the initial solution of the second stage. If λ = 0 and `a = `, then WeMix reduces to the AugDrop; while if T2 = 0, WeMix becomes to MixLoss. For label-preserving case, we only need to simply use `a = ` (i.e, δf = 0) in WeMix.

heading: 5 EXPERIMENTS
text: To evaluate the performance of the proposed methods, we trained deep neural networks on two benchmark data sets, CIFAR-10 and CIFAR-1001 (Krizhevsky & Hinton, 2009) for the image classification task. Both CIFAR-10 and CIFAR-100 have 50,000 training images and 10,000 testing images of 32×32 resolutions. CIFAR-10 has 10 classes containing 6000 images each, while CIFAR100 has 100 classes. We use mixup (Zhang et al., 2018) as an example of lable-mixing augmentation and Contrast as an example of lable-preserving augmentation and. For the choice of backbone, we use ResNet-18 model (He et al., 2016) in mixup, and Wide-ResNet-28-10 model (Zagoruyko & Komodakis, 2016) is applied in the Contrast experiment following by (Cubuk et al., 2019; 2020). To verify our theoretical results, we compare the proposed AugDrop and MixLoss with two baselines, SGD with mixup/Contrast and SGD without mixup/Contrast (baseline). We also include WeMix in the comparison. The mini-batch size of training instances for all methods is 256 as suggested by He et al. (2019) and He et al. (2016). The momentum parameter of 0.9 is used. The weight decay with the parameter value is set to be 5 × 10−4. The total epochs of training progress is fixed as 200. Followed by (He et al., 2016; Zagoruyko & Komodakis, 2016), we use 0.1 as the initial learning rates for all algorithms and divide them by 10 every 60 epochs.
For AugDrop, we drop off the augmentation after s-th epoch, where s ∈ {150, 160, 170, 180, 190} is tuned. For example, if s = 160, then it means that we run the first stage of AugDrop 160 epochs and the second stage 40 epochs. For MixLoss, we tune the parameter δy from {0.5, 0.05, 0.005, 0.0005} and the best performance is reported. For WeMix, we use the value of δy with the best performance in MixLoss, and we tune the dropping off epochs s same as AugDrop. We fix the convex combination parameter λ = 0.1 both for MixLoss and WeMix. We use top-1 accuracy to evaluate the performance. All top-1 accuracy on the testing data set are averaged over 5 independent random trails with their standard deviations.

heading: 5.1 MIXUP
text: Given two examples (xi,yi) and (xj ,yj) that are drawn at random from the training data, mixup creates a virtual training example as follows x′ = βxi + (1− β)xj ,y′ = βyi + (1− β)yj , where β ∈ [0, 1] is sampled from a Beta distribution β(α, α). We useα = 1 in the experiments as suggested in (Zhang et al., 2018). In this subsection, we want to empirically verify that our theoretical findings for label-mixing augmentation in Section 4. The experimental results conducted on CIFAR-10 and CIFAR-100 are listed in Table 1. We can see from the results that both AugDrop and MixLoss are
1https://www.cs.toronto.edu/˜kriz/cifar.html
better than two baselines, with and without mixup, which matches the theory found in Section 4. The performance of MixLoss is slightly worse than that of AugDrop, but they are comparable. Besides, the proposed WeMix enjoys both improvements, leading to the best performance among all algorithms although its convergence theoretical guarantee is unclear.
Next, we implement MixLoss and WeMix with δy = 0 (i.e., use `a = `), which are denoted by MixLoss-s and WeMix-s, respectively. We summarize the results in Table 1, showing that both MixLoss-s and WeMix-s drop performance, comparing with MixLoss and WeMix, respectively.
Besides, we use more than two images in mixup such as three and ten images and the results are shown in Table 2. Although the top-1 accuracy of mixup reduces dramatically, we find that the proposed WeMix can still improve the performance when it comparing with mixup itself, showing the robustness of WeMix.

heading: 5.2 CONTRAST
text: As a simple label-preserving augmentation, Contrast controls the contrast of the image. Its transformation magnitude is randomly selected from a uniform distribution [0.1, 1.9] following by (Cubuk et al., 2019). Despite its simplicity, we choose it to demonstrate our theory for the considered case in Appendix A. The results of highest top-1 accuracy on the testing data sets for different methods are presented in Table 3. We find that by directly training on data with Contrast, it will drop the performance a little bit. Even so, the result shows that AugDrop has better performance than two baselines, which is consistent with the theoretical findings for label-preserving augmentation in Appendix A that we need use the data augmentation at the early training stage but drop it at the end of training. Although there is no theoretical guarantee for the label-preserving transformation case, we implement MixLoss and WeMix by setting δf = 0, i.e., using `a = ` in (14). The results show that MixLoss and WeMix are better than two baselines but are slightly worse than AugDrop.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: In this paper, we have studied how to better utilize data augmentation in training deep neural networks by designing two training schemes with the first one switches augmented data to original data during the training progress and the second one training on a convex combination of original loss and augmented loss. We have provided theoretical analyses of these two training schemes in non-convex smooth optimization setting. With the insights of theoretical results, we have designed a generic algorithm WeMix that can well leverage data augmentation in practice. We have verified our theoretical finding throughout extensive experimental evaluations on training ResNet and WideResNet models over benchmark data sets. Despite the effectiveness of WeMix, its theoretical guarantee is still not fully understand. We would like to leave this open problem as future work.

heading: A MAIN RESULTS FOR LABEL-PRESERVING AUGMENTATION
text: We consider label-preserving augmentation case (1), that is,
Py(·|x) = Pỹ(·|x̃), ∀x̃ ∈ T (x) but Px 6= Px̃. It covers many image data augmentations including translation, adding noises, small rotation, and brightness or contrast changes (Krizhevsky et al., 2012; Raghunathan et al., 2020). It is worth mentioning that the compositions of label-preserving augmentation could also be label-preserving. Similar to the case of label-mixing augmentation, we measure the following difference between Px and Px̃ by a KL divergence:
δP := DKL(Px‖Px̃) = Ex∼Px [ log
Px(x) Px̃(x)
] . (18)
Due to the data bias δP , the prediction model learned from augmented data D̃ could be even worse than training the prediction model directly from the original data D, as revealed by the following lemma and its remark. Lemma 2. (label-preserving augmentation) Assume that L and L̃ satisfy properties in Definition 1, 2 and 3, by setting η = 1/L and m0 ≥ 4ηδP , when t ≥ t0 = L µ log (L(w1)−L(w∗))µ 2δPG2 , we have
E(x̃t,ỹt)[L(wt+1)− L(w∗)] ≤ 4δPG
2
µ ≤ O ( δP µ ) , (19)
where wt+1 is output of mini-batch SGD trained on D̃, δP is defined in (18).
Proof. See Appendix I.1.
Remark: Comparing the result in (9) with the result of (19) in Lemma 2, it is easy to show that, when the data bias is too large, i.e., δP ≥ Ω(L log(n)/(nµ)), we have O ( L log(n)/(nµ2) ) ≤ O(δP /µ). This implies that training the deep model directly on the original data D is more effective than on the augmented data D̃. Hence, in order to better leverage the augmented data in the presence of large data bias (δP ≥ Ω(κ log(n)/n), where κ = L/µ), we need to come up with an approach that automatically correct the data bias in D̃. Below, we use AugDrop to correct the data bias by solving a constrained optimization problem.
A.1 AugDrop: CORRECTING DATA BIAS BY CONSTRAINED OPTIMIZATION
To correct data bias, we consider to solve the constrained optimization problem (10). The key idea is to shrink the solution in a small region by using utilize augmented data to enjoy a smaller condition number, leading to an improved convergence in optimizing L(w). By introducing a term that
γ1 := δPG 2/µ,
we can present a proposition aboutA(γ) and µ(γ), showing that we have a smaller condition number and consequentially a smaller optimization error by restricting our solutions to A(γ). Proposition 2. If γ ∈ [γ1, 4γ1], we have w∗ ∈ A(γ) and µ(γ) ≥ µ, where A(γ) and µ(γ) are defined in (11) and (12), respectively.
Proof. See Appendix I.2.
The following theorem shows the convergence result of AugDrop for label-preserving augmentation.
Theorem 3. Define γ = 4γ1, µe = µ(4γ1). Assume that L and L̃ satisfy properties in Definition 1, 2 and 3, set learning rate η1 = 1/L in Stage I and learning rate η2 =
1 2nµe
log (
8nµ2e(L(w1)−L(w∗)) G2L ) in Stage II for AugDrop. Let w1 be the initial solution in Stage I
of AugDrop and wT1+2, . . . ,wT1+n/m2+1 be the intermediate solutions obtained by the mini-batch
SGD in Stage II of AugDrop. Choose T1 = Lµ log 2(L̃(w1)−L̃(w̃∗))µ δPG2 , m1 =
( 1 + √ 3 log 2T1δ )2 8 δP
and m2 = ( 1 + √ 3 log 2nδ )2 8 δP
, with a probability 1 − δ, we have wt ∈ A(4γ1),∀t ∈ {T1 + 2, . . . , T1 + n/m2 + 1} and
E [L(ŵ)− L(w∗)] ≤ G2L 8nµ2e + G2L 8nµ2e log
( 8nµ2e(L(w1)− L(w∗))
G2L
) ≤ O ( L log(n)
nµ2e
) , (20)
where ŵ = wT1+n/m2+1 and δP is defined in (18).
Proof. See Appendix I.3.
Remark. Theorem 3 shows that all intermediate solutions wt obtained in Stage II of AugDrop satisfy the constraint L̃(wt) − L̃(w̃∗) ≤ 4γ1, that is to say, wt ∈ A(4γ1). Based on Proposition 2, we will enjoy a larger µe than µ. Comparing the result of (20) in Theorem 3 with (9), training by using AugDrop will result in a better performance than directly training on D due to µe ≥ µ. Besides, when the data bias is large, i.e., δP ≥ Ω(L log(n)/(nµ)), we know O(L log(n)/(nµ2e)) ≤ O(µδP /µ2e) ≤ O(δP /µ), where the last inequality holds due to µe ≥ µ. By comparing (20) with the result of (19) in Lemma 2, we know that training by using AugDrop has a better performance than directly training on D̃ when the data bias is large. By solving a constrained problem, the AugDrop algorithm can correct the data bias and thus enjoy an better performance.

heading: B TECHNICAL RESULTS FOR CROSS-ENTROPY LOSS
text: Lemma 3. Assume that L(w) = E[`(y, f(x;w))] satisfies property in Definition 1, where ` is a cross-entropy loss, then we have
‖∇w`(y, f(x;w))−∇w`(ỹ, f(x;w))‖ ≤ G‖y − ỹ‖, (21) and
‖∇w`(y, f(x;w))‖ ≤ G. (22)
Proof. The objective function is
L(w) = E(x,y) [`(y, f(x;w))] , (23) where the cross-entropy loss function ` is given by
`(y, f(x;w)) = K∑ i=1 −yi log ( exp(fi(x;w))∑K j=1 exp(fj(x;w)) ) . (24)
Let set
p(x;w) = (p1(x;w), . . . , pK(x;w)), pi(x;w) = − log ( exp(fi(x;w))∑K j=1 exp(fj(x;w)) ) , (25)
then the gradient of ` with respective to w is
∇`(y, f(x;w)) = 〈y,∇p(x;w)〉. (26)
Therefore, ∀x ∈ X and w ∈ RD we have ‖∇w`(y, f(x;w))−∇w`(ỹ, f(x;w))‖
= ‖〈y − ỹ,∇p(x;w)〉‖ ≤‖∇p(x;w)‖ ‖y − ỹ‖ ≤G‖y − ỹ‖, (27)
and
‖∇w`(y, f(x;w))‖ = ‖〈y,∇p(x;w)〉‖ ≤ ‖∇p(x;w)‖ ‖y‖ ≤ G, (28) where uses the facts that ‖∇p(x;w)‖ ≤ G and ‖y‖ ≤ ‖y‖1 = 1, here ‖ · ‖ is a Euclidean norm (`2 norm) and ‖ · ‖1 is `1 norm.

heading: C PROOF OF LEMMA 1
text: Proof. Recall that the update of mini-batch SGD is given by wt+1 = wt − ηg̃t.
Let set the averaged mini-batch stochastic gradients of L̃(wt) as
g̃t := 1
m0 m0∑ i=1 ∇` (ỹt,i, f(x̃t,i;wt)) ,
then by the Assumption of L̃ satisfying the property in Definition 1, we know that E(x̃t,i,ỹt,i) [∇` (ỹt,i, f(x̃t,i;wt))] = ∇L̃(wt), ∀i ∈ {1, . . . ,m0} (29) and thus E(x̃t,ỹt)[g̃t] = ∇L̃(wt), (30)
where we write E(x̃t,ỹt)[g̃t] as E(x̃t,1,ỹt,1)[. . .E(x̃t,m0 ,ỹt,m0 )[g̃t]] for simplicity. Then the norm variance of g̃t is given by
E(x̃t,ỹt)[‖g̃t −∇L̃(wt)‖ 2]
=E(x̃t,ỹt) ∥∥∥∥∥ 1m0 m0∑ i=1 ∇` (ỹt,i, f(x̃t,i;wt))−∇L̃(wt) ∥∥∥∥∥ 2 
(a) =
1
m20 m0∑ i=1 E(x̃t,i,ỹt,i) [∥∥∥∇` (ỹt,i, f(x̃t,i;wt))−∇L̃(wt)∥∥∥2] (b)
≤ 4G 2
m0 , (31)
where (a) is due to (29) and the pairs (x̃t,1, ỹt,1), . . . , (x̃t,m0 , ỹt,m0) are independently sampled from D̃; (b) is due to the facts that the Assumption of L̃ satisfying the property in Definition 1 and Lemma 3, and then by Jensen’s inequality, we also have ‖∇wL̃(w)‖ ≤ G, implying that∥∥∥∇`(ỹ, f(x̃;w))−∇L̃(w)∥∥∥2 ≤ 4G2. On the other hand, by the Assumption of L satisfying the property in Definition 2, we have
E(x̃t,ỹt)[L(wt+1)− L(wt)] ≤E(x̃t,ỹt) [ 〈∇L(wt),wt+1 −wt〉+ L
2 ‖wt+1 −wt‖2 ] (a) = η
2 E(x̃t,ỹt)
[ ‖∇L(wt)− g̃t‖2 − ‖∇L(wt)‖2 − (1− ηL) ‖g̃t‖2 ] (b) = η
2
( ‖∇L(wt)−∇L̃(wt)‖2 + E(x̃t,ỹt) [ ‖∇L̃(wt)− g̃t‖2 ] − ‖∇L(wt)‖2
− (1− ηL) E(x̃t,ỹt)[‖g̃t‖ 2] )
(c) ≤ η 2
( ‖∇L(wt)−∇L̃(wt)‖2 + 4G2
m0 − ‖∇L(wt)‖2
) (32)
where the (a) is due to the update of wt+1 = wt− ηg̃t; (b) is due to (30); (c) is due to η = 1/L and (31). By using the Assumption of L̃ and L satisfying the property in Definition 1 and Px = Px̃, we have
‖∇L(wt)−∇L̃(wt)‖ =‖E(x,y)[∇w`(y, f(x;wt))]− E(x̃,ỹ)[∇w`(ỹ, f(x̃;wt))]‖ (a)
≤E(x,y,ỹ)[‖∇w`(y, f(x;wt))−∇w`(ỹ, f(x;wt))‖] (21)
≤ GE(y,ỹ)[‖y − ỹ‖] (b)
≤Gδy, (33)
where (a) uses Jensen’s inequality; (b) is due to (3). By using the Assumption of L satisfying the property in Definition 3 and (33), inequality (32) becomes
E(x̃t,ỹt)[L(wt+1)− L(wt)]
≤ ηG2δ2y
2 +
2ηG2
m0 − η 2 ‖∇L(wt)‖2
≤ ηG2δ2y
2 +
2ηG2
m0 − ηµ (L(wt)− L(w∗)) ,
which implies E(x̃t,ỹt)[L(wt+1)− L(w∗)]
≤ (1− ηµ) (L(wt)− L(w∗)) + ηG2δ2y
2 +
2ηG2
m0
≤ (1− ηµ)t (L(w1)− L(w∗)) +
( ηG2δ2y
2 +
2ηG2
m0 ) t−1∑ i=0 (1− ηµ)i.
Due to (1− ηµ)t ≤ exp(−tηµ) and ∑t−1 i=0(1− ηµ)i ≤ 1 ηµ , when
m0 ≥ 8
δ2y
and
t ≥ L µ log 4(L(w1)− L(w∗))µ
δ2yG 2
,
we know
E(x̃t,ỹt)[L(wt+1)− L(w∗)] ≤ δ2yG 2
µ .

heading: D PROOF OF (9)
text: We first put the full statement of (9) in the following lemma. Lemma 4. Assume that L satisfies the properties in Definition 1, 2 and 3, by setting η = 12nµ log ( 8nµ2(L(w1)−L(w∗)) G2L ) , we have E(xn,yn) [L(wn+1)− L(w∗)] ≤ G 2L 8nµ2 +
G2L 8nµ2 log
( 8nµ2(L(w1)−L(w∗))
G2L
) , where wn+1 is output of SGD trained on D.
Proof. By the Assumption of L satisfying the property in Definition 2, we have E(xn,yn)[L(wn+1)− L(wn)]
≤E(xn,yn)[〈∇L(wn),wn+1 −wn〉] + L
2 E(xn,yn)
[ ‖wt+n −wn‖2 ] (a) = − ηE(xn,yn)[〈∇L(wn),∇` (yn, f(xn;wn))〉] + L
2 E(xn,yn)
[ ‖∇` (yn, f(xn;wn)) ‖2 ] (b) = − η‖∇L(wn)‖2 + η2L
2 E(xn,yn)[‖∇` (yn, f(xn;wn)) ‖ 2],
where (a) is due to the update of wn+1 = wn− η∇` (yn, f(xn;wn)); (b) is due to the Assumption of L satisfying the property in Definition 1 that E(x,y) [∇w` (y, f(x;w))] = ∇L(w). By using the Assumption of L satisfying the property in Definition 1 that ‖∇w`(y, f(x;w))‖ ≤ G and the Assumption of L satisfying the property in Definition 3, we have
E(xn,yn)[L(wn+1)− L(wn)]
≤η 2LG2
2 − η‖∇L(wn)‖2
≤η 2LG2
2 − 2ηµ (L(wn)− L(w∗)) ,
which implies
E(xn,yn)[L(wn+1)− L(w∗)]
≤ (1− 2ηµ) E(xn−1,yn−1) [L(wn)− L(w∗)] + η2LG2
2
≤ (1− 2ηµ)n (L(w1)− L(w∗)) + η2LG2
2 n−1∑ i=0 (1− 2ηµ)i.
Due to (1− 2ηµ)n ≤ exp(−2ηµn) and ∑n−1 i=0 (1− 2ηµ)i ≤ 1 2ηµ , then by using the setting of
η = 1
2nµ log
( 8nµ2(L(w1)− L(w∗))
G2L
) ,
we have
E(xn,yn) [L(wn+1)− L(w∗)]
≤ exp (−2ηµn) (L(w1)− L(w∗)) + ηG2L
4µ
= G2L 8nµ2 + G2L 8nµ2 log
( 8nµ2(L(w1)− L(w∗))
G2L ) ≤O ( L
nµ2 log(n)
) .

heading: E PROOF OF PROPOSITION 1
text: Proof. By using the Assumption of L̃ satisfying the property in Definition 3, we have
L̃(w∗)− L̃(w̃∗)
≤‖∇L̃(w∗)‖ 2
2µ
(a) = ‖∇L̃(w∗)−∇L(w∗)‖2
2µ
(b) ≤ δ2yG 2
2µ
where (a) is due to the definition of w∗ in (6) so that ∇L(w∗) = 0; (b) follows the same analysis of (33) in Lemma 1. Thus we know w∗ ∈ A(γ) when γ ≥ γ0 := δ2yG 2
2µ . On the other hand, by the definition of µ(γ) in (12) and the Assumption of L satisfying the property in Definition 3, we know µ(γ) ≥ µ when γ ≤ 8µ0.

heading: F ALGORITHM AUGDROP AND PROOF OF THEOREM 1
text: We present the details of update steps for AugDrop and its convergence analysis in this section.
Algorithm 2 AugDrop 1: Input: T1 2: Initialize: w1 ∈ RD, η1, η2 > 0
// Stage I: Train Augmented Data 3: for t = 1, 2, . . . , T1 do 4: draw m1 examples (x̃t,1, ỹt,1), . . . , (x̃t,m1 , ỹt,m1) at random from augmented data 5: update wt+1 = wt − η1m1 ∑m1 i=1∇w` (ỹt,i, f(x̃t,i;wt)) 6: end for // Stage II: Train Original Data 7: for t = T1 + 1, T1 + 2, . . . , T1 + n/m2 do 8: drawm2 examples (xt,1,yt,1), . . . , (xt,m2 ,yt,m2) without replacement at random from original data 9: update wt+1 = wt − η2m2 ∑m2 i=1∇w` (yt,i, f(xt,i;wt))
10: end for 11: Output: wT1+n/m2+1.
Proof. In the first stage of the proposed algorithm, we run a mini-batch SGD over the augmented data D̃ with m1 as the size of mini-batch. Let (x̃t,i, ỹt,i), i = 1, . . . ,m1 be the m1 examples sampled in the tth iteration. Let g̃t be the average gradient for the t iteration, i.e.
g̃t = 1
m1 m1∑ i=1 ∇w`(ỹt,i, f(x̃t,i;wt))
We then update the solution by mini-batch SGD: wt+1 = wt−η1g̃t. By using Lemma 4 of (Ghadimi et al., 2016), with a probability 1− δ′, we have∥∥∥g̃t −∇L̃(wt)∥∥∥ ≤ (1 +√3 log 1
δ′
)√ 8G2
m1 . (34)
By the Assumption of L̃ satisfying the property in Definition 2 and the update of wt+1 = wt−η1g̃t, we have
L̃(wt+1)− L̃(wt)
≤− η1〈∇L̃(wt), g̃t〉+ η21L
2 ‖g̃t‖2
= η1 2 ‖∇L̃(wt)− g̃t‖2 − η1 2 ‖∇L̃(wt)‖2 − η1(1− η1L) 2 ‖g̃t‖2
(a) ≤ η1 2
( 1 + √ 3 log 1
δ′
)2 8G2
m1 − η1µ(L̃(wt)− L̃(w̃∗)),
where (a) uses the facts that (34), η1 = 1/L and the Assumption of L̃ satisfying the property in Definition 3. Thus, with a probability (1− δ′)t, using the recurrence relation, we have
L̃(wt+1)− L̃(w̃∗)
≤(1− η1µ)(L̃(wt)− L̃(w̃∗)) + η1 2
( 1 + √ 3 log 1
δ′
)2 8G2
m1
≤ (1− η1µ)t ( L̃(w1)− L̃(w̃∗) ) + η1 2 ( 1 + √ 3 log 1 δ′ )2 8G2
m1 t−1∑ i=0 (1− η1µ)i. (35)
Due to (1− η1µ)t ≤ exp(−tη1µ) and ∑t−1 i=0(1− η1µ)i ≤ 1 η1µ , when
t ≥ T1 := 1
η1µ log 2(L̃(w1)− L̃(w̃∗))µ δ2yG 2 ,
we have L̃(wt+1)− L̃(w̃∗)
≤ exp(−tη1µ) ( L̃(w1)− L̃(w̃∗) ) + ( 1 + √ 3 log 1
δ′
)2 4G2
µm1
≤ δ2yG 2
2µ +
( 1 + √ 3 log 1
δ′
)2 4G2
µm1 . (36)
Let δ′ = δ2T1 , if we choose m1 such that
m1 =
( 1 + √ 3 log
2T1 δ
)2 8
δ2y ,
then for any t ≥ T1, then with a probability 1− δ/2 we have
L̃(wt+1)− L̃(w̃∗) ≤ δ2yG 2
µ . (37)
In the second stage of the proposed algorithm, we run a mini-batch SGD over the original data D with m2 as the size of mini-batch. Let (xt,i,yt,i), i = 1, . . . ,m2 be the m2 examples sampled in the tth iteration. Let ĝt be the average gradient for the t iteration, i.e.
ĝt = 1
m2 m2∑ i=1 ∇w`(yt,i, f(xt,i;wt))
We then update the solution wt+1 = wt − η2ĝt. By using Lemma 4 of (Ghadimi et al., 2016), with a probability 1− δ′′, we have
‖ĝt −∇L(wt)‖ ≤ ( 1 + √ 3 log 1
δ′′
)√ 8G2
m2 . (38)
By the smoothness of L̃(w) and the update of wt+1 = wt − η2ĝt, we have L̃(wt+1)− L̃(wt)
≤− η2〈∇L̃(wt), ĝt〉+ η22L
2 ‖ĝt‖2
= η2 2 ‖∇L̃(wt)− ĝt‖2 − η2 2 ‖∇L̃(wt)‖2 − η2(1− η2L) 2 ‖ĝt‖2
(a) ≤η2‖∇L̃(wt)−∇L(wt)‖2 + η2‖ĝt −∇L(wt)‖2 − η2µ(L̃(wt)− L̃(w̃∗))
(b) ≤η2 2δ2yG2 + ( 1 + √ 3 log 1
δ′′
)2 8G2
m2 − η2µ(L̃(wt)− L̃(w̃∗)), (39) where (a) uses the facts that Young’s inequality, η2 ≤ 1/L and the Assumption of L̃ satisfying the property in Definition 3; (b) uses inequality (38) and the same analysis of (33) in Lemma 1. It is easy to verify that for any t ∈ {T1 + 1, . . . , T1 +n/m2}, we have, with a probability (1− δ′′)n/m2 , we have L̃(wt+1)− L̃(w̃∗)
≤ (1− η2µ) ( L̃(wt)− L̃(w̃∗) ) + η2 G2δ2y + ( 1 + √ 3 log 1
δ′′
)2 8G2
m2  ≤ (1− η2µ)t ( L̃(wT1+1)− L̃(w̃∗) ) + η2 G2δ2y + ( 1 + √ 3 log 1
δ′′
)2 8G2
m2  t−1∑ i=0 (1− η2µ)i
≤ δ2yG 2
µ +
1
µ
G2δ2y + ( 1 + √ 3 log 1
δ′′
)2 8G2
m2
 ,
where the last inequality is due to (1 − η2µ)t ≤ 1, ∑t−1 i=0(1 − η2µ)i ≤ 1 η2µ , and (37). Let δ′′ =
δ 2n/m2
, if we choose m2 such that m2 ≥ ( 1 + √
3 log 2nm2δ )2 4 δ2y , for example,
m2 =
( 1 + √ 3 log 2n
δ
)2 4
δ2y ,
then with a probability 1− δ, for any t ∈ {T1 + 1, . . . , T1 + n/m2} we have
L̃(wt+1)− L̃(w̃∗) ≤ 4δ2yG 2
µ .
Therefore, wt ∈ A(8γ0) for any t ∈ {T1 +2, . . . , T1 +n/m2 +1}. Following the standard analysis in Appendix D, we have
E [ L(wT1+n/m2+1)− L(w∗) ] ≤ G 2L
4nµ2c + G2L 4nµ2c log
( 4nµ2c(L(w1)− L(w∗))
G2L
) ,
where µc = µ(8γ0).
G OPTIMAL SOLUTIONS OF La(w) AND Lc(w)
By the definition of `a in (14) and Px = Px̃, we know
`a(ỹ, f(x̃;w))
= min ‖z−ỹ‖≤δy `(z, f(x;w))
≤`(y, f(x;w)) (40)
since ‖y − ỹ‖ ≤ δy . Therefore, by (15), (40) and Px = Px̃ we have
La(w) =Ey[La(w)] =E(x,ỹ,y) [`a(ỹ, f(x;w))]
≤E(x,ỹ,y) [`(y, f(x;w))] =E(x,y) [`(y, f(x;w))]
=L(w). (41)
Since ` is a non-negative loss function, then we know
0 ≤ La(w∗) ≤ L(w∗) = 0,
which implies that
La(w∗) = 0,
and thus
La(w∗) ≤ La(w), ∀w.
Therefore, w∗ also minimizes La(w). On the other hand, by (16) we know
Lc(w∗) = λL(w∗) + (1− λ)La(w∗) = 0.
Therefore,
Lc(w∗) ≤ Lc(w), ∀w,
i.e, w∗ also minimizes Lc(w), indicating that Lc(w) shares the same minimizer as L(w).

heading: H ALGORITHM MIXLOSS AND PROOF OF THEOREM 2
text: We present the details of update steps for MixLoss and its convergence analysis in this section.
Algorithm 3 MixLoss 1: Input: λ 2: Initialize: w1 ∈ RD, η > 0 3: for t = 1, 2, . . . , n do 4: draw an example (xt,yt) without replacement at random from original data 5: draw m0 examples (x̃t,1, ỹt,1), . . . , (x̃t,m0 , ỹt,m0) at random from augmented data 6: compute ĝt = λ∇`(yt, f(xt;wt)) + (1− λ) 1m0 ∑m0 i=1∇`a(ỹt,i, f(x̃t,i;wt))
7: update wt+1 = wt − ηĝt 8: end for 9: Output: wn+1.
Proof. Recall that
Lc(w) = λL(w) + (1− λ)La(w), (42)
where La(w) = E(x̃,ỹ) [`a(ỹ, f(x̃;w))] = E(x̃,ỹ) [
min ‖z−ỹ‖≤δy `(z, f(x̃;w))
] and
ĝt = λ∇`(yt, f(xt;wt)) + (1− λ) 1
m0 m0∑ i=1 ∇`a(ỹt,i, f(x̃t,i;wt)). (43)
By the update of wt+1 = wt − ηĝt and by the Assumption of Lc satisfying the property in Definition 2, we have (Nesterov, 2004)
Et [Lc(wt+1)− Lc(wt)]
≤− ηEt [〈∇Lc(wt), ĝt〉] + η2L 2 Et [ ‖ĝt‖2 ] (a)
≤ − η(1− ηL)Et [ ‖∇Lc(wt)‖2 ] + η2LEt [ ‖ĝt −∇Lc(wt)‖2 ] (b)
≤ − η(1− ηL)Et [ ‖∇Lc(wt)‖2 ] + 9
8 λ2η2LEt
[ ‖∇`(yt, f(xt;wt))−∇L(wt)‖2 ] + 9(1− λ)2η2LEt
∥∥∥∥∥ 1m0 m0∑ i=1 ∇`a(ỹt,i, f(x̃t,i;wt))−∇La(wt) ∥∥∥∥∥ 2 
(c) ≤ − η(1− ηL)Et [ ‖∇Lc(wt)‖2 ] + 9
2 λ2η2LG2 +
36(1− λ)2η2LG2
m0 (d) ≤ − η(1− ηL)Et [ ‖∇Lc(wt)‖2 ] + 5λ2η2LG2, (44)
where Et[·] is taken over random variables (xt,yt), (x̃t,1, ỹt,1), . . . , (x̃t,m0 , ỹt,m0); (a) uses the facts that Young’s inequality ‖a − b‖2 ≤ 2‖a‖2 + 2‖b‖2 and E[ĝt] = ∇Lc(wt); (b) uses the facts that (42) (43) and Young’s inequality ‖a + b‖2 ≤ (1 + 1/c)‖a‖2 + (1 + c)‖b‖2 with a = 8; (c) use the same analysis in (31) from the proof of Lemma 1, the facts that the Assumption of L satisfying the property in Definition 1 and by Jensen’s inequality, we also have ‖∇L(w)‖ ≤ G, implying that ‖∇`(y, f(x;w))−∇L(w)‖2 ≤ 4G2; (d) holds by setting m0 ≥ 72(1−λ) 2
λ2 since we have sufficiently large number of augmented examples. Thus, since η ≤ 12L and by using the Assumption of Lc satisfying the property in Definition 3, we have
Et [Lc(wt+1)− Lc(wt)] ≤− ηµEt [Lc(wt)] + 5λ2η2LG2,
and therefore
En [Lc(wn+1)]
≤ exp (−ηµn)Lc(w1) + 5λ2ηLG2
µ
≤ exp (−ηµn)L(w1) + 5λ2ηLG2
µ , (45)
where last inequality is due to the fact that Lc(w) ≤ L(w). In (45), by choosing
η = 1
µn log nµ2L(w1) λ2LG2 ,
we have
En [Lc(wn+1)] ≤ λ2LG2
nµ2 +
5λ2LG2
nµ2 log nµ2L(w1) λ2LG2 . (46)
Since L(w) = 1λLc(w)− 1−λ λ La(w), then (46) becomes
En [L(wn+1)]
≤λLG 2
nµ2 +
5λLG2
nµ2 log nµ2L(w1) λ2LG2 − 1− λ λ E [La(wn+1)]
≤λLG 2
nµ2 +
5λLG2
nµ2 log nµ2L(w1) λ2LG2 , (47)
where the last inequality is due to λ ∈ (0, 1) and La(wn+1) ≥ La(w∗) = 0.

heading: I PROOFS IN APPENDIX A
text: We include the proofs for Appendix section “Main Results for label-preserving Augmentation”.
I.1 PROOF OF LEMMA 2
The analysis is similar to that for Lemma 1. For completeness, we include it here.
Proof. Following the same analysis in Lemma 1, we can have the same result as in (32). That is to say, we have
E(x̃t,ỹt)[L(wt+1)− L(wt)] ≤ η
2
( ‖∇L(wt)−∇L̃(wt)‖2 + 4G2
m0 − ‖∇L(wt)‖2
) . (48)
We have
‖∇L(wt)−∇L̃(wt)‖ ≤ ∫ dxy‖Px(x)− Px̃(x)‖‖∇`(y, f(x;wt))‖
(a) ≤G ∫ dx‖Px(x)− Px̃(x)‖
(b) ≤G √
2DKL(Px‖Px̃) (c) =G √ 2δP , (49)
where (a) is due to the Assumption of L satisfying the property in Definition 1; (b) uses Pinsker’s inequality (Csiszar & Körner, 2011; Tsybakov, 2008); (c) is due to (18). With inequality (49),
by using the facts that η = 1/L and the Assumption of L satisfying the property in Definition 3, inequality (48) becomes
E(x̃t,ỹt)[L(wt+1)− L(wt)]
≤ηδPG2 + 4G2 m0 − η 2 ‖∇L(wt)‖2 ≤ηδPG2 + 4G2
m0 − ηµ (L(wt)− L(w∗))
≤2ηδPG2 − ηµ (L(wt)− L(w∗)) ,
where the last inequality is due to the selection of m0 ≥ 4ηδP . Then we have
E(x̃t,ỹt)[L(wt+1)− L(w∗)] ≤ (1− ηµ) E(x̃t−1,ỹt−1)[L(wt)− L(w∗)] + 2ηδPG 2
≤ (1− ηµ)t (L(w1)− L(w∗)) + 2ηδPG2 t−1∑ i=0 (1− ηµ)i.
Due to (1− ηµ)t ≤ exp(−tηµ) and ∑t−1 i=0(1− ηµ)i ≤ 1 ηµ , when
t ≥ L µ log (L(w1)− L(w∗))µ 2δPG2 ,
we know
E(x̃t,ỹt)[L(wt+1)− L(w∗)] ≤ 4δPG
2
µ .
I.2 PROOF OF PROPOSITION 2
Proof. By using the Assumption of L̃ satisfying the property in Definition 3, we have
L̃(w∗)− L̃(w̃∗)
≤‖∇L̃(w∗)‖ 2
2µ
(a) = ‖∇L̃(w∗)−∇L(w∗)‖2 2µ (b)
≤ δPG 2
µ
where (a) is due to the definition of w∗ in (6) so that ∇L(w∗) = 0; (b) follows the same analysis of (49) in Lemma 2. Thus we know w∗ ∈ A(γ) when γ ≥ γ1 := δPG 2
µ . On the other hand, by the definition of µ(γ) in (12) and the Assumption of L satisfying the property in Definition 3, we know µ(γ) ≥ µ when γ ≤ 4µ1.
I.3 PROOF OF THEOREM 3
This proof is similar to the proof of Theorem 1. For completeness, we include it here.
Proof. In the first stage of the proposed algorithm, we run a mini-batch SGD over the augmented data D̃ with m1 as the size of mini-batch. Using the similar analysis in (35) from Theorem 1, we have, with a probability (1− δ′)t, L̃(wt+1)− L̃(w̃∗) ≤ (1− η1µ)t ( L̃(w1)− L̃(w̃∗) ) + η1 2 ( 1 + √ 3 log 1 δ′ )2 8G2
m1 t−1∑ i=0 (1− η1µ)i.
Due to (1− η1µ)t ≤ exp(−tη1µ) and ∑t−1 i=0(1− η1µ)i ≤ 1 η1µ , when
t ≥ T1 := L
µ log 2(L̃(w1)− L̃(w̃∗))µ δPG2 ,
we have
L̃(wt+1)− L̃(w̃∗) ≤ δPG
2
2µ +
( 1 + √ 3 log 1
δ′
)2 8G2
2µm1 . (50)
Let δ′ = δ2T1 , if we choose m1 such that
m1 =
( 1 + √ 3 log
2T1 δ
)2 8
δP ,
then for any t ≥ T1, we have
L̃(wt+1)− L̃(w̃∗) ≤ δPG
2
µ . (51)
In the second stage of the proposed algorithm, we run a mini-batch SGD over the original data D with m2 as the size of mini-batch. Using the same analysis in (39) from Theorem 1, we have
L̃(wt+1)− L̃(wt) ≤η2‖∇L̃(wt)−∇L(wt)‖2 + η2‖ĝt −∇L(wt)‖2 − η2µ(L̃(wt)− L̃(w̃∗)). Then by (38) in the proof of Theorem 1 and (49) in the proof of Lemma 2, we have, with a probability 1− δ′′,
L̃(wt+1)− L̃(wt) ≤2η2δPG2 + η2 ( 1 + √ 3 log 1
δ′′
)2 8G2
m2 − η2µ(L̃(wt)− L̃(w̃∗)).
It is easy to verify that for any t ∈ {T1 + 1, . . . , T1 + n/m2}, we have, with a probability (1 − δ′′)n/m2 , we have
L̃(wt+1)− L̃(w̃∗)
≤ (1− η2µ) ( L̃(wt)− L̃(w̃∗) ) + η2 2δPG2 +(1 +√3 log 1 δ′′ )2 8G2
m2  ≤ (1− η2µ)n/m2 ( L̃(wT1+1)− L̃(w̃∗) ) + η2 2δPG2 +(1 +√3 log 1 δ′′ )2 8G2
m2  n/m2−1∑ i=0 (1− η2µ)i
≤δPG 2
µ +
1
µ 2δPG2 +(1 +√3 log 1 δ′′ )2 8G2
m2  , where the last inequality is due to (1 − η2µ)t ≤ 1, ∑t−1 i=0(1 − η2µ)i ≤ 1 η2µ , and (51). Let δ′′ =
δ 2n/m2
, if we choose m2 such that m2 ≥ ( 1 + √
3 log 2nm2δ )2 8 δP , for example,
m2 =
( 1 + √ 3 log 2n
δ
)2 8
δP ,
then with a probability 1− δ, for any t ∈ {T1 + 1, . . . , T1 + n/m2} we have
L̃(wt+1)− L̃(w̃∗) ≤ 4δPG
2
µ .
Therefore, wt ∈ A(4γ1) for any t ∈ {T1 + 2, . . . , T1 + n/m2 + 1}. Following the similar analysis in Appendix D, we have
E [ L(wT1+n/m2+1)− L(w∗) ] ≤ G 2L
4nµ2e + G2L 4nµ2e log
( 4nµ2e(L(w1)− L(w∗))
G2L
) ,
where µe = µ(4γ1).

Review summaries:
This paper proposes a method to improve the generalization of deep networks when the input is applied strong augmentations, i.e. mixup, resulting in large data bias. The authors proposes theoretical foundation behind their two methods, AugDrop and MixLoss and show their effectiveness on CIFAR10/CIFAR100 datasets. Although the paper has technical novelty and it only provides incremental gains on relatively small-size dataset. Below, you can find some of my comments/questions about the paper.

In this work, the authors first prove a deep model can benefit from augmented data when the data bias is small. Then they propose two methods, namely "AugDrop" that corrects  and "MixLoss", that correct data bias by "constrained optimisation" and "modified loss function" respectively. Finally they show that these two methods can be combined and further improve the performance.