Towards Understanding the Data Dependency of Mixup-style Training
Authors: Muthu Chidambaram
Xiang Wang
Yuzheng Hu
Chenwei Wu
Rong Ge
Venue: ICLR 2022 Spotlight (2022)
Keywords: mixup
deep learning
semi-supervised learning
empirical risk minimization
generalization
margin
counterexample

Abstract: In the Mixup training paradigm, a model is trained using convex combinations of data points and their associated labels. Despite seeing very few true data points during training, models trained using Mixup seem to still minimize the original empirical risk and exhibit better generalization and robustness on various tasks when compared to standard training. In this paper, we investigate how these benefits of Mixup training rely on properties of the data in the context of classification. For minimizing the original empirical risk, we compute a closed form for the Mixup-optimal classification, which allows us to construct a simple dataset on which minimizing the Mixup loss leads to learning a classifier that does not minimize the empirical loss on the data. On the other hand, we also give sufficient conditions for Mixup training to also minimize the original empirical risk. For generalization, we characterize the margin of a Mixup classifier, and use this to understand why the decision boundary of a Mixup classifier can adapt better to the full structure of the training data when compared to standard training. In contrast, we also show that, for a large class of linear models and linearly separable datasets, Mixup training leads to learning the same classifier as standard training.

Published as a conference paper at ICLR 2022
TOWARDS UNDERSTANDING THE DATA DEPENDENCY OF MIXUP-STYLE TRAINING
Muthu Chidambaram' Xiang Wang', Yuzheng Hu², Chenwei Wu', and Rong Ge 'Duke University, UUniversity of Illinois at Urbana-Channt chbana-Champaign
ABSTRACT
In the Mixup training paradigm, a model is trained using convex combinations of data points and their associated labels. Despite seeing very few true data points during training, models trained using Mixup seem to still minimize the original empirical risk and exhibit better generalization and robustness on various tasks when compared to standard training. In this paper, we investigate how these benefits of Mixup training rely on properties of the data in the context of classification. For minimizing the original empirical risk, we compute a closed form for the Mixup-optimal classification, which allows us to construct a simple dataset on which minimizing the Mixup loss can provably lead to learning classifier that does not minimize the empirical loss on the data. On the other hand, we also give sufficient conditions for Mixup training also minimize the original empirical risk. For generalization, we characterize the margin of a Mixup classifier, and use this understand why the decision boundary of Mixup classifier can adapt better to the full structure of the training data when compared to standard training. In contrast, we also show that, for large class of linear models and linearly separable datasets, Mixup training leads to learning the same classifier as standard training.
INTRODUCTION
Mixup (Zhang et al., 2018) a modification the standard supervised learning setup which involves training on convex combinations of pairs of data points and their labels instead of the original data itself. In the original paper, Zhang al. (2018) demonstrated that training deep neural networks using Mixup leads to better generalization performance, as well as greater robustness to adversarial attacks and label noise on image classification tasks. The empirical advantages of Mixup training have been affirmed by several follow-up works (He et al., 2019; Thulasidasan et al., 2019; 9; Lamb et al., 2019; Arazo et al., 2019; Guo, 2020). The idea of Mixup has also been extended beyond the supervised learning setting, and been applied to semi-supervised learning (Berthelot al., 2019; Sohn et al., 2020), contrastive learning (Verma et al., 2021; Lee et al., 2020), grivacy-preserve learning (Huang et al., 2021), and learning with faimess constraints (Chuang & Mroueh, 2021).
However, from a theoretical perspective, Mixup training is still mysterious even in the basic multi- class classfication setting why should the output of linear mixture of two training samples be the same linear mixture of their labels, especially when considering highly nonlinear models? Despite several recent theoretical results (Guo al., 2019; Carratino al., 2020; Zhang al., 2020; 2021), there is still not a complete understanding of why Mixup training actually works in practice. In this paper, we try to understand why Mixup works by first understanding when Mixup works: in particular, how the properties of Mixup training rely on the structure of the training data.
We consider two properties for classifiers trained with Mixup. First, even though Mixup training does not observe many original data points during training, it usually can still correctly classify all of the original data points (empirical risk minimization (ERM)). Second, the aforementioned empirical works have shown how classifiers trained with Mixup often have better adversarial robustness and generalization than standard training. In this work, we show that both of these properties can rely heavily on the data used for training, and that they need not hold in general.
Main Contributions and Related Work. The idea that Mixup can potentially fail to minimize the original risk is not new; Guo et al. (2019) provide examples of how Mixup labels can conflict with actual data point labels. However, their theoretical results do not characterize the data and
Correspondence Muthu Chidambaram (muthu8cs dduee.ed).

---

Published as a conference paper at ICLR 2022
model conditions under which this failure can provably happen when minimizing the Mixup loss. In Section of this work, we provide a concrete classification dataset on which continuous approximate- minimizers of the Mixup loss can fail to minimize the empirical risk. We also provide sufficient conditions for Mixup to minimize the original risk, and show that these conditions hold approximately on standard image classification benchmarks.
With regards to generalization and robustness, the parallel works of Carratino et al. (2020) and Zhang al. (2020) showed that Mixup training can be viewed minimizing the empirical loss along with a data-dependent regularization term. Zhang et al. (2020) further relate this term to the adversarial robustness and Rademacher complexity of certain function classes learned with Mixup. Section 3, we take an alternative approach to understanding generalization and robustness by analyzing the margin of Mixup classifiers. Our perspective can be viewed as complementary that of the aforementioned works, as we directly consider the properties exhibited by Mixup-optimal classifier instead of considering what properties are encouraged by the regularization effects of the Mixup loss. In addition to margin analysis, we also show that for the common setting of linear models trained on high- high-dimensional Gaussian features both Mixup (for large class of mixing distributions) and ERM with gradient descent learn the same classifier with high probability.
Finally, we note the related works that are beyond the scope of our paper; namely the many Mixup-like training procedures such as Manifold Mixup (Verma et al., 2019), Cut Mix (Yun et al., 2019), Puzzle Mix (Kim et al., 2020), and Co-Mixup (Kim et al., 2021).
MIXUP AND EMPIRICAL RISK MINIMIZATION
The goal of this section is to understand when Mixup training also minimize the empirical risk. Our main technique for doing so is to derive a closed-form for the Mixup-optimal classifier over a sufficiently powerful function class, which we do in Section 2.2 after introducing the basic setup in Section 2.1. We use this closed form to motivate concrete example on which Mixup training does minimize the empirical risk in Section 2.3, and show under mild nondegeneracy conditions that Mixup will minimize the emprical risk in Section 2.4.
2.1 SETUP
We consider the problem of k-class classification where the classes L,..., k correspond to compact disjoint sets Xi...,, Xa C IR" with an associated probability measure Px supported on X
Xi. We use C to denote the set of all functions g R [0, 1] satisfying the property that U U.
for all x (where g² represents the i-th coordinate function of g). We refer to function g C as classifier, and say that y classifies æ as class j if = argmax, of (z). The cross-entropy loss associated with such classifier y is then:
k
=
Σ 1=1
log (x)dPx(1)
X
The goal of standard training to learn a classifier argmingec [gg. Px). Any such classifier will necessarily satisfy h' (z) = 1 on X; since the X; are disjoint.
Mixup. In the Mixup version of our setup, convex combinations of the original data and their classes. These convex combinations are determined according probability measure PP whose support is [0, 1). and assume this measure has density f. For two points s, E X, we let zee (A) = As + (1 - A)t (and use 2et when À is understood) and define the Mixup cross-entropy on 8, with respect
interested in minimizing the cross-entropy of
classifier g as:
Emiz Ln, ( logg' (zst) () (Xlog (za:) + (1 X) log g (zse))
8 E X; s X t e X,
Having defined bmis as above, we may write the component of the full Mixup cross-entropy loss corresponding to mixing points from classes i and as:
JdH (g. Px, - min
- Lmtr (g. s,t, d(Px x Px x (P),
2

---

Published as a conference paper at ICLR 2022
The final Mixup cross-entropy loss is then the sum of Joh over all i,j E {1.... (corresponding to all possible mixings between classes, including themselves):
k
(g.
min pp,
1=1
Relation Prior Work. We have opted for more general definition of the Mixup loss (at least when constrained to multi-class classification) than prior works. This is not generality for generality's ' sake, but rather because many of our results apply to any mixing distribution supported on [o, I]. One obtains the original Mixup formulation of Zhang et al. (2018) for multi-class classification a finite dataset by taking the X; to be finite sets, and choosing Fx to be the normalized counting measure (corresponding Beta(o, o),, where a is a hyperparameter.
discrete uniform distribution). Additionally, Py is chosen to have density
2.2 MIXUP-OPTIMAL CLASSIFIER
Given our setup, we now wish to characterize the behavior of a Mixup-optimal classifier at a point E RR. However, if the optimization of Jmir is considered over the class of functions C, this intractable (to the best of our knowledge) due to the lack of regularity conditions imposed on functions in
Jmia to class of functions that is sufficiently powerful (so to include almost all practical settings) while still allowing for local analysis. To do so, we will need the following definitions, which will also be referenced throughout the results in this section and the next:
thus wish to constrain the optimization
A {s, E X, [0, Às + (1 A)t Be(x))
A 2,6,5
0. 1-1-66 8] As (1 A)t E Be(x)}
=
Xmii
x E EER:: U has positive measure for every
cid Sz,t
d(px x Px x (f)
Joy A d(Px x Px (s,
cid
A
The set A.d. represents all points in X, x Xj that have lines between them intersecting neighborhood of x, while the set A'd represents the restriction of A to only those points whose connecting line segments intersect an e-neighborhood of & with À values bounded by 1 (used in Section 3). The set Xmix corresponds all points for which every neighborhood factors into Jmiz- The ei-j term represents the measure the set A while ghd represents the expectation of À over the same To provide better intuition for these definitions, we provide visualizations in Section B of the appendix. We can now define the subset of C to which we will constrain our optimization of Jmia-
Definition 2.1. Let C* to be the subset of C for which every lim argmingggoo. [0,1]* (m)z for all E Xmir when the limit exists. Here Jmiz (0) (x) represents the Mixup loss for constant function with value 0 with the restriction of each term in Jmix to the set A
C satisfies h(x)
We immediately justify this definition with the following proposition.
Proposition 2.2. Any function h argmin Jmiz (g, P IPy) satisfies J (h) S Jmiz (g) for any continuous E C.
Proof Sketch. We can argue directly from definitions by considering points in Xmii for which and g differ.
3

---

Published as a conference paper at ICLR 2022
Proposition 2.2 demonstrates that optimizing over C* is at least good as optimizing the subset of C consisting of continuous functions, so we cover most cases of practical interest (i.e. optimizing deep neural networks). As such, the term "Mixup-optimal" is intended to mean optimal with respect to C* throughout the rest of the paper. We may now characterize the classification of a Mixup-optimal classifier on X mix-
Lemma 2.3. For any point E Xmtr and O, there exists continuous function he satisfying:
ct. Size
+
Σjti (Saie, + (S2i <(()))
hx(x)
Eq=1
c2. Σjjn jæht (Saie A + (E2 <i. <
With the property that lim,- he h(z) for every E argmingee- Jnsio Px,P,) when the limit exists.
Proof Sketch. We set he argmingggo, Il min (0) B, (w) and show that this is well-defined, contin- uous, and has the above form using the strict convexity of the minimization problem.
Remark 2.4. For the important case of finite datasets, it will be shown that the limit above always exists as part of the proof of Theorem 3.2.
The expression for hy just represents the expected location of the point x on all lines between class i and other classes, normalized by the of the expected locations for all classes. It can be simplified significantly if y is assumed to be symmetric: we give this as a corollary after the proof in Section C of the Appendix. Importantly, we note that while h2 defined in Lemma 2.3 is continuous for every E >> 0, its pointwise limit h need not be, which we demonstrate below.
Proposition 2.5. Let X, = ((0, 1), (0,- - and let X₂ = {(1, 0). (-1, 0)). with Px being discrete uniform over X X2 and yPy being continuous uniform over [0, 1). Then the Mixup-optimal classifier h is discontinuous at (0,0).
Proof Sketch. One may explicitly compute for x = (0,0) that (²(x) = 1²))
Proposition 2.5 illustrates first significant difference between Mixup training and standard training: there always exists a minimizer of the empirical cross-entropy J that can be extended to a continuous function (since minimizer is constant on the class supports and not constrained elsewhere), whereas depending on the data the minimizer of Jmiz can be discontinuous.
2.3 A MIXUP FAILURE CASE
With that in mind, several model classes popular in practical applications consist of continuous functions. For example, neural networks with ReLU activations continuous, and several works have noted that they are Lipschitz continuous with shallow networks having approximately small Lipschitz constant (Scaman & Virmaux, 2019; Fazlyab al., 2019; Latorre et al., 2020). Given the regularity of such models, we are motivated to consider the continuous approximations ht in Lemma 2.3 and see if it is possible to construct dataset which h, (for fixed c) can fail classify the original points correctly. We thus consider the following dataset:
Definition 2.6. [3-Point Alternating Line] We define X3 to be the binary classification dataset consisting of the points {0, 1, classified as 21, 1). In our setup, this corresponds to X; =00,2 2} and X2 {1} with Px- = 3 = 1u.
Intuitively, the reason why Mixup can fail on X3 is that, for choices of Py that concentrate about }. we will have by Lemma 2.3 that the Mixup-optimal classification a neighborhood of point should skew towards class instead of class 2 due the sandwiching of point I between points 0 and The canonical choice of IP, corresponding to a mixing density of Beta(a, a:) is one such choice:
Theorem 2.7. Let Py have associated density Beta a). Then for any classifier h. X3 (as defined in Lemma 2.3), we may choose a such that h. does not achieve 0 classification error on X²
Proof Sketch. For any e > O, we can bound the & terms in Equation I using the fact that Beta(a, a) strictly subgaussian (Marchal & Arbel, 2017), and then choose a: appropriately.
4

---

Published as a conference paper at ICLR 2022
1/100 CLEPNS AEMERATI L9en 10-800
Frer Daver Ateoeden tre AA BUEK
Patee Ateraa 1985
040
0355
035
6.5
200
200
2000
680
3083
2010
50.00
(a)
(b) 32
(c) 128
Figure I: Training error for Mixup and regular training on X3 Each curve corresponds to the mean of 10 training runs, and the around each curve represents region of one standard deviation.
Experiments. The result of Theorem 2.7 leads us believe that the Mixup training of continuous model should fail on X3 for appropriately chosen a. To verify that the theory predicts the experiments, train two-layer feedforward neural network with 512 hidden units and ReLU activations X² with and without Mixup. The implementation of Mixup training does not differ from the theoretical setup; we uniformly sample pairs of data points and train on their mixtures. Our implementation uses Py Torch (Paszke et al., 2019) and is based heavily on the open source implementation of Manifold Mixup (Verma et al., 2019) by Shivam Saboo. Results for training using (full-batch) Adam (Kingma & Ba, 2015) with the suggested (and common) hyperparameters of 33 0.9, B2 = 0.999 and learning rate of 0.001 are shown in Figure The class probabilities for each point the dataset outputted by the learned Mixup classifiers from Figure are shown in Table below:
h
0
2
α = 1
0.995
0.156
0.979
32
1.000
0.603
0.997
a = 128
1.000
0.650
0.997
Table I: Mixup model evaluations on X3 for different choices of a.
We see from Figure and Table I that Mixup training fails to correctly classify the points in X² for 32, and this misclassification becomes more exacerbated
increase a. The choice of for which misclassifications begin to happen is largely superficial; we show in Section D of the Appendix that it is straightforward to construct datasets in the style of X? for which Mixup training will fail even for the very mild choice of a 1. We focus on the case of X3 here to simplify the theory. The key takeaway that, for datasets that exhibit (approximately) collinear structure amongst points, it is possible for inappropriately chosen mixing distributions to cause Mixup training to fail to minimize the original empirical risk.
2.4 SUFFICIENT CONDITIONS FOR MINIMIZING THE ORIGINAL RISK
The natural follow-up question to the results of the previous subsection is: under what conditions on the data can this failure case be avoided? In other words, when can the Mixup-optimal classifier classify the original data points correctly while being continuous at those points?
Prior to answering that question, we first point out that if discontinuous functions are allowed, then Mixup training always minimizes the original risk on finite datasets:
Proposition 2.8. Consider k-class classification where the supports XI,.., Xs are finite and Px corresponds the discrete uniform distribution. Then for every h E argmin Jmiz (g, Px, Py)). we have that (x)))))))))))>( on X;
Proof Sketch. Only the gi.i term doesn't vanish in (x) as e - 0, as the mixing distribution is continuous and cannot assign positive measure to alone when mixing two points that not
Note that Proposition 2.8 holds for any continuous mixing distribution F, supported on [0, 1] we just need rich enough model class.
5

---

Published as a conference paper at ICLR 2022
ProE DaNvss MONT St 12265, NANM
PItre stes, CIPARIS jo 3924 NAF
Fror Carans CIAAR1081 1894. Pars
65
0.23-
0.15
The
0.65
U42
14C
0.08
12
13
(a) MNIST
(b) CIFAR-10
(c) CIFAR-100
Figure 2: Mean and single standard deviation of training runs for Mixup (a 1024) and ERM on
the original training data. Mixup achieves near-identical (within 1%) training accuracy to ERM.
In order to obtain the result of Proposition 2.8 with the added restriction of continuity of h on each of the X,, we need further assume that the collinearity of different class points that occurred in the previous section does not happen.
Assumption 2.9. For any point E X,, there do not exist u E X and e E X, for j * such that there is À > 0 for which Au + (1 A)e.
visualization of Assumption 2.9 is provided in Section B of the appendix. With this assumption in hand, we obtain the following result as corollary of Theorem 3.2 which is proved in the next section:
Theorem 2.10. We consider the same setting as Proposition 2.8 and further suppose that Assumption 2.9 is satisfied. Then for every h E argmingee- Jmin (g, Fx, Pr), we have that (x) - 1 on X; and that h is continuous on X.
Application of Sufficient Conditions. The practical take-away of Theorem 2. 2010 is that if a dataset does not exhibit approximate collinearity between points of different classes, then Mixup training should achieve near-identical training error on the original training daia when compared to ERM. We validate this by training ResNet-18 18 (He et al., 2015) (using the popular implementation of Kuang Liu) on MNIST (LeCun, 1998). CIFAR-10, and CIFAR-100 (Krizhevsky, 2009) with and without Mixup for 50 epochs with batch size of 128 and otherwise identical settings to the previous subsection. For Mixup, we consider mixing using Beta(a, a) for 1, 32, 128, and 1024 to cover wide band of mixing distributions. Our experimental results for the "worst case" of a = 1024 (the other choices strictly closer to ERM in training accuracy) are shown in Figure 2, while the other experiments can be found in Section D of the Appendix.
We now check that the theory can predict the results of our experiments by verifying Assumption 2.9 approximately (exact verification is too expensive). We sample one epoch's worth of Mixup points (to simulate training) from downsampled version of each train dataset, and then compute the minimum distances between each Mixup point and points from classes other than the two mixed classes. The minimum over these distances corresponds to an estimate of in Assumption 2.9. We compute the distances for both training and test data, to see whether good training but poor test performance can be attributed test data conflicting with mixed training points, Results are shown below in Table
Comparison Type
MNIST
CIFAR-10
CIFAR-100
Mixup/Train 11.433
17.716
12.936
Mixup/Test
11.897
23.133
15.076
Table 2: Minimum Euclidean distance results using our approximation procedure with Mixup
points generated using Beta 1024). We downsample all datasets 20%, to compare to the experiments of Guo et al. (2019).
To interpret the estimated e values in Table 2, we note that unless < 1/L (where L is the Lipschitz constant of the model being considered), a Mixup point cannot conflict with an original point (since the function has enough flexibility to fit both). Due to the estimated large Lipschitz constants of deep networks (Scaman & Vinmaux, 2019), our values certainly do not fall in this regime, explaining how the near-identical performance to ERM is possible on the original datasets. We remark that our results challenge implication of Guo et al. (2019), which was that training/test performance on

---

Published as a conference paper at ICLR 2022
the above benchmarks degrades with high values of due to conflicts between original points and Mixup points.
2.5 THE RATE OF EMPIRICAL RISK MINIMIZATION USING MIXUP
Another striking aspect of the experiments in Figure 2 is that Mixup training minimizes the original empirical risk at a very similar rate to that of direct empirical risk minimization. A priori, there is no reason to expect that Mixup should be able do this simple calculation shows that Mixup training only sees one true data point per epoch in expectation (each pair of points is sampled with probability = and there size). The experimental results are even more surprising given that we are training using a = 1024, which essentially corresponds to training using the midpoints of the original data points. This seems to imply that it is possible to recover the classifications of the original data points from the midpoints alone (not including the midpoint of point and itself), and similar phenomena has indeed been observed in recent empirical work (Guo, 2021). We make this rigorous with the following result:
true point pairs and m pairs seen per epoch, where is the dataset
Theorem 2.11. Suppose (11,,-.. Fin } with m 6 are sampled from X according to Xxx, and that Px has density. Then with probability 1, we can uniquely determine the points { Fm given only the (2) midpoints { h isicism"
Proof Sketch. The idea represent the problem linear system, and show using rank arguments that the sets of m points that cannot be uniquely determined are a measure zero set.
Theorem 2.11 shows, in an cetemaationtthhoreee sense, that is possible obtain the original data points (and therefore also their labels) from only their midpoints. While this gives more theoretical backing as to why it is possible for Mixup training using Beta(1024, 1024) to recover the original data point classifications with very low error, it does not explain why this actually happens in practice at the rate that does. A full theoretical analysis this phenomenon would necessarily require analyzing the training dynamics of neural networks (or another model of choice) when trained only on midpoints the original data, which is outside the intended scope of this work. That being said, we hope that such analysis will be fruitful line of investigation for future work.
3 GENERALIZATION PROPERTIES OF MIXUP CLASSIFIERS
Having discussed how Mixup training differs from standard empirical risk minimization with regards to the original training data, we now consider how learned Mixup classifier can differ from one learned through empirical risk minimization on unseen test data. To do so, we analyze the per-class margin of Mixup classifiers, i.e. the distance can move from class support X; while still being classified as class i.
3.1 THE MARGIN OF MIXUP CLASSIFIERS
Intuitively, if point falls only on line segments between X; and some other classes Xj,... and if & always falls closer to X, than the other classes, we can expect x to be classified according to class i by the Mixup-optimal classifier due Lemma 2.3. To make this rigorous, we introduce another assumption that generalizes Assumption 2.9 to points outside of the class supports:
Assumption 3.1. For class and a point Xmizs suppose there exists an 0 and 0 < 5 < such that A and Ad- have measure zero for all e' S E and j.q a i, and the measure A is at least that of A3.s
Here the measure conditions are codifying the ideas that the point ø falls closer to X, than any other class on every line segment that intersects it, and there are no line segments between non-i classes that intersect z. The condition that the measure of A is at least that of A handles asymmetric mixing distributions that concentrate on pathological values of X. A visualization of Assumption 3.1 is provided in Section of the Appendix. Now we can prove:
Theorem 3.2. Consider k-class classification where the supports XI...., X₂ are finite and Px corresponds to the discrete uniform distribution. If point x satisfies Assumption 3.1 with respect to a class i, then for every h E argmin Juin (g. g, Px P, f), we have that classifies x as class and that h is continuous at r..
7

---

Published as a conference paper at ICLR 2022
Model (alphe
Picap Modal (alpha 20241
Figure 3: Decision boundary plots for standard and Mixup training the two moons dataset of Pezeshki et al. (2020) with class separation of 0.5. Each boundary represents the average of 10 training runs of 1500 epochs.
Proof Sketch. The limit in Lemma 2.3 can be shown to exist using the Lebesgue differentiation theorem, and we can bound the limit below since the A 2,, have measure zero.
Assumption 2.9 implics Assumption 3.1 with respect to each class, and hence get Theorem 2.10 as a corollary of Theorem 3.2 as mentioned in Section 2. To use Theorem 3.2 to understand generalization,
make the observation that point can satisfy Assumption 3.1 while being distance of up to miny d(X..Xg) from some class i. This distance can significantly farther than, for example, the optimal linear separator in a linearly separable dataset.
2
Experiments. To illustrate that Mixup can lead to more separation between points than a linear decision boundary, we consider the two moons dataset (Buitinck et al., 2013), which consists of two classes of points supported on semicircles with added Gaussian noise. Our motivation for doing so comes from the work of Pezeshki et al. (2020), in which it was noted that neural network models trained on a separated version of the two moons dataset essentially learned a linear separator while ignoring the curvature of the class supports. While Pezeshki al. (2020) introduced an explicit regularizer to encourage a nonlinear decision boundary, we expect due to Theorem 3.2 that Mixup training will achieve similar result without any additional modifications.
To verify this empirically, we train a two-layer neural network with 500 hidden units with and without Mixup, to have a 1-to-1 comparison with the setting of Pezeshki et al. (2020). We use 1 and 1024 for Mixup to capture wide band of mixing densities. The version of the two moons dataset we use is also identical to that of the one used in the experiments of Pezeshki et (2020), and we are grateful to the authors for releasing their code under the MIT license. We do full-batch training with all other training, implementation, and compute details remaining the same as the previous section. Results are shown in Figure 3.
Our results affirm the observations of Pezeshki al. (2020) and previous work (des Combes et al., 2018) that neural network training dynamics may ignore salient features of the dataset; in this case the "Base Model" learns to differentiate the two classes essentially based on the x-coordinate alone. On the other hand, the models trained using Mixup have highly nonlinear decision boundaries. Further experiments for different class separations and values of a are included in Section F of the Appendix.
3.2
WHEN MIXUP TRAINING LEARNS THE SAME CLASSIFIER
The experiments and theory of the previous sections have shown how Mixup classifier can differ significantly from one learned through standard training. In this subsection, we now consider the opposing question when is the Mixup classifier the same as the one learned through standard training? Prior work (Archambault et al., 2019) has considered when Mixup training coincides with certain adversarial training, and our results complement this line of work. The motivation for our results comes from the fact that a practitioner need not spend compute on Mixup training in addition to standard training in settings where the performance will be provably the same.
We consider the case of binary classification using linear model 0 high-dimensional Gaussian data, which is a setting that arises naturally when training using Gaussian kernels. Specifically, we consider the dataset X to consist of points in dd distributed according N/ Ia) with d > (to be made more precise shortly). We also consider the mixing distribution to be any symmetric distribution supported on [0, 1] (thereby including as special case Beta(a, We let the labels of
8

---

Published as a conference paper at ICLR 2022
points in X be +1 (so that the sign of 0 is the classification), and use X1 and X-1 to denote the individual class points. We will show that in this setting, the optimal Mixup classifier is the same (up to rescaling of 0) as the ERM classifier learned using gradient descent with high probability. To do so we need some additional definitions.
Definition 3.3. We say 0 is an interpolating solution, if there exists & > 0 such that
@ x4 = - = Vx, E X1, Vej E X-1
Definition 3.4. The maximum margin solution i defined through:
= argmaax |0]|2=1
t0Tzs xi. -0 -0 =1 [x
min
When the maximum margin solution coincides with an interpolating solution for the dataset X (i.e. all the points are support vectors), we have that Mixup training leads to learning the max margin solution (up to rescaling).
Theorem 3.5. If the maximum margin solution for X is also an interpolating solution for X, then any 0 that lies in the span of X and minimizes the Mixup loss Jmix for a symmetric mixing distribution Fy is rescaling of the maximum margin solution.
Proof Sketch. It can be shown that 0 is an interpolating solution using a combination of the strict convexity of Jmir as a function of & and the symmetry of the mixing distribution.
Remark 3.6. For every 0, we can decompose it as 0 0x + 0x where 0x is the projection of onto the subspace spanned by X. By definition we have that 0x is orthogonal to all possible mixings of points in X. Hence, x does not affect the Mixup loss or the interpolating property, so for simplicity we may just assume 9 lies in the span of X.
To characterize the conditions on under which the maximum margin solution interpolates the data, use key result of Muthukumar al. (2020), restated below. Note that Muthukumar al. (2020) actually provide more settings in their paper, but we constrain ourselves to the one stated below for simplicity.
Lemma 3.7. [Theorem in Muthukumar al. (2020), Rephrased] Assuming d 10m In + n 1, then with probability at least 1 - 2/n, the maximum margin solution for X is also an interpolating solution.
To tie the optimal Mixup classifier back to the classifier learned through standard training, we appeal to the fact that minimizing the empirical cross-entropy of a linear model using gradient descent leads to learning the maximum margin solution on linearly separable data (Soudry et al., 2018: Ji & Telgarsky, 2018). From this we obtain the desired result of this subsection:
Corollary 3.8. Under the same conditions Lemma 3.7, the optimal Mixup classifier has the same direction as the classifier learned through minimizing the empirical cross-entropy using gradient descent with high probability.
4 CONCLUSION
The main contribution of our work has been to provide theoretical framework for analyzing how Mixup training can differ from empirical risk minimization. Our results characterize a practical failure case of Mixup, and also identify conditions under which Mixup can provably minimize the original risk. They also show in the sense of margin why the generalization of Mixup classifiers can be superior to those learned through empirical risk minimization, while again identifying model classes and datasets for which the generalization of Mixup classifier is no different (with high probability). We also emphasize that the generality of our theoretical framework allows most of our results to hold for any continuous mixing distribution. Our hope is that the tools developed in this work will see applications in future works concerned with analyzing the relationship between benefits obtained from Mixup training and properties of the training data.

---

Published as a conference paper at ICLR 2022
5 ETHICS STATEMENT
We do not anticipate any direct misuses of this work due to its theoretical nature. That being said, the failure case of Mixup discussed in Section 2 could serve as a way for an adversary to potentially exploit model trained using Mixup to classify data incorrectly. However, as this requires knowledge of the mixing distribution and other hyperparameters of the model, we do not flag this as a significant concern would just like to point it out for completeness.
REPRODUCIBILITY STATEMENT
Full proofs for all results in the main body of the paper can be found in Sections C and E of the Appendix. All of the code used to generate the plots and experimental results in this paper can be We have
found at: https:: //gi thub. com/2 201 1014mhhhi damb / /Mix/Mixuppp /iw.xppaaaaa-eeeeeeeeee tried our best organize the code to be easy use and extend. Detailed instructions for how to run each type of experiment are provided in the README file included in the GitHub repository.
ACKNOWLEDGEMENTS
Rong Ge, Muthu Chidambaram, Xiang Wang, and Chenwei Wu are supported in part by NSF Award DMS-2031 1849, CCF-1704656, CCF-1845171 (CAREER), CCF-1934964 (Tripods), Sloan Research Fellowship, and Google Faculty Research Award. Muthu would like to thank Michael Lin for helpful discussions during the early stages of this project.
REFERENCES
Eric Arazo, Diego Ortego, Paul Albert, Noel E O' O'Connor, and Kevin McGuinness. Unsupervised label noise modeling and loss correction. arXiv preprint arXiv:1904.11238, 2019.
Guillaume Archambault, Yongyi Mao, Hongyu Guo, and Richong Zhang. Mixup as directional adversarial training. CoRR, abs/ abs/1906.06875 2019. URL 06875.
1906.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach to semi-supervised learning. In H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: http://///oooeoocseeeeeee www.eeeiiinnnnnnnnnneeeeeeeeeeee weeiiis.cccpppeee wwtpc//pp/ppp////p//// /ile// 1cd138d04 99.68 wbw.f oag.a
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences from the scikit-learn project. CoRR, 0tt//330.022555 2013. URL http: / //arxiv.org/alttall...aaaaa..a.a abs/////ab/13399/ 0238.
Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On mixup regulariza- tion, 2020.
Ching- Yao Chuang and Youssef Mrouch. Fair mixup: Fairness via interpolation. 00s/2103.06503, 2021. URL http::::://.xii.oorgaa//////////
CoRR,
Remi Tachet des Combes, Mohammad Pezeshki, Samira Shabanian, Aaron C. Courville, and Yoshua Bengio. On the learning dynamics of deep neural networks. CoRR, abs/1809 809.06848, 2018. URL http:// /ttp:///axiv..// wwwg/bbsss.s..ooooooo.eee 818.80088888
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J. Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks, 2019.
10

---

Published as a conference paper at ICLR 2022
Hongyu Guo. Nonlinear mixup: Out-of-manifohd data augmentation for text classification. In The Thirty-Fourd Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Seconts Innovative Applications of Artificial Intelligence Conference. IAAI 2020, The Tenth AAAI Symposium Educatiinal Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 4044 4051. AAAI Press, 2020. URL https: http://aaai.oooo /ts////////////s// htts//idxx.ptti. AAAI/ hAA//articee/view/SSS
Hongyu Guo. Midpoint regularization: from high uncertainty training conservative classification, 2021.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Mixup as locally linear out-of-manifold regulariza- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3714-3722, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
Tong He, Zhi Zhang, Hang Zhang, Zhongyue Zhang, Junyuan Xie, and Mu Li. Bag of tricks for image classification with convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Yangsibo Huang, Zhao Song, Kai Li, and Sanjeev Arora. Instahide: Instance-hiding schemes for private distributed learning, 2021.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. CoRR, abs/1803.00 803.07300, 2018. URL http: arxiv. wtg./iioorr//oooooo
org/ abs/ 1803. 07300.
Jang-Hyun Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. In International Conference on Machine Learning, pp. 5275-5282 PMLR, 2020.
JangHyun Kim, Wonho Choo, Hosan Jeong, and Hyun Oh Song. Co-mixup: Saliency guided joint
mixup with supermodular diversity. In International Conference on Learning Representations, 2021. URL httph::t///oo/ /ttp::ess///pereiie...
net wtw.mooddowwwdodoooooooo
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun ), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: // //arxiiv.org. abs 1412.4 6980.
Alex Krizhevsky, Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Lamb, Vikas Verma, Juho Kannala, and Yoshua Bengio. Interpolated adversarial training: Achieving robust neural networks without sacrificing too much accuracy. In Proceedings of the 12th ACM Workshop Artificial Intelligence and Security, pp. 95-103, 2019.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization, 2020.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist// 1998.
Kibok Lee, Yian Zhu, Kihyuk Sohn, Chun-Liang Li, Jinwoo Shin, and Honglak Lee. i-mix: A strategy for regularizing contrastive representation learning. CoRR, abs/2010.08887, 2020. URL https: /ttpvv/rxvvvv/vva///vv org/ atwp//////////oo////./////aaa/// 2010 08887.
Olivier Marchal and Julyan Arbel. On the sub-gaussianity of the beta and dirichlet distributions. Electronic Communications in Probability, 22 Jan 2017. ISSN 1083-589X. doi: 10.1214/ 17-ecp92. URL http://///. dxx doi. 11t/1/...11117-EE..
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? arXiv preprint arXiv:2005.0800 2020.
11

---

Published as a conference paper at ICLR 2022
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32, pp. 8026-8037. Curran Associates, Inc., 2019.
Mohammad Pezeshki, Sékou-Oumar Kaba, Yoshua Bengio, Aaron C. Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: learning proclivity in neural networks. CoRR, abs/201 1. 1.0468, 2020. URL htt.ttt:::/aattt htt.:pp://axxi.orrrrr aaagg//aa/aaaa 2011. 09468.
Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation, 2019.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. In H. Larochelle, M. Ranzato. R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 596-608. Cur- ran Associates, Inc., 2020. URL file/069 628866644eee 64cce 9addbldddec wtt.abbcccccbaa6633333333333
ngs. neuri ps. cc/ cc/ppperr/2200 .a....a............p............
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2875 2018.
Sunil Thulasidasan, Gopinath Chennupati, Jeff A Bilmes, Tanmoy Bhattacharya, and Sarah Michalak. On mixup training: Improved calibration and predictive uncertainty for deep neural networks. Advances in Neural Information Processing Systems, 32: 13888-13889, 2019.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference Machine Learning, pp. 6438-6447, PMLR, 2019.
Vikas Verma, Minh-Thane Luong, Kenji Kawaguchi, Hieu Pham, and Quoc V. Le. Towards domain- agnostic contrastive learning, 2021.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.
Cutmix: Regularization strategy train strong classifiers with localizable features. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp.
2019.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou. How does mixup help with robustness and generalization?, 2020.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, and James Zou. When and how mixup improves calibration, 2021.
12

---

Published as a conference paper at ICLR 2022
A REVIEW OF DEFINITIONS AND ASSUMPTIONS
For convenience, we first recall the definitions and assumptions stated throughout the paper below.
log g' (Alogg ('sst) + (1 - g (zet))
s,t X;
mix 8,,,,
Jhd m min (g. 11,
lmte s, t, d(Px x Px x (y)(s,
Xxxxxxx0011
Umio (g, 1x,
Σ
J (g, Px.
i=1
A = ((), E X3 x [0, As + (1 -1-
A-d
((8,1,)) E X, X, 00, 1 5] As + (1 A)l E (x))
2,6,6
Xmiz
I TER::
U A has positive measure for every > 0
cij Sg.e
d(Px x x xx (8,
Abile
S A
c
=
dd x Px xx
Definition 2.1. Let C to be the subset of C for which every C satisfies h(x) lim,-+0 argmingejo..1y (0,11 (m)) (x) for all Xmix when the limit exists. Here Jmiz (0) (x)) represents the Mixup loss for constant function with value 9 with the restriction of each term in Jmix to the set A...
Definition 2.6. [3-Point Alternating Line] We define XG be the binary classification dataset consisting of the points {0, 1 classified as (1,2,1} In our setup, this corresponds to X, = [0,2) and X2 {1] with Px = 3 {0.12)))
X,, there do not exist X and v E X, for + such that there is a À > 0 for which x = Au + (1 - A)e.
Assumption 2.9. For any point
Assumption 3.1. For a class and a point 2 E Xmizz suppose there exists an é and a < < such that 2, and Ad- have measure zero for all é' S c and j. + and the measure of A is least that of A3.s Z,e"
Definition 3.3. We say Ô is an interpolating solution, if there exists à such that
Ø 2; - = Vr,, E X1, Vzy E X-1-
Definition 3.4. The maximum margin solution Ø is defined through:
θ argmax |d]|=
min [x,
{0T:; x,, TT 23}
B VISUALIZATIONS OF DEFINITIONS AND ASSUMPTIONS
Due to the technical nature of the definitions and assumptions above, we provide several visualizations in Figures 4 to 7 help aid the reader's intuition for our main results.
C FULL PROOFS FOR SECTION 2
We now prove all results found in Section 2 of the main body of the paper in the order that they appear.
13

---

Published as a conference paper at ICLR 2022
XI
X mix
Xj
A
Figure 4: A visualization of Xii and A
X2
X1
Figure 5: A visualization of the X3 dataset and how the Mixup sandwiching works.
14

---

Published as a conference paper at ICLR 2022
X
Xi
XJ
Figure 6: A visualization of Assumption 2.9, i.e. the "no collinearity" assumption.
X
Xi
Figure 7: A visualization of Assumption 3.1. Once again, the key idea is that falls at most 8 away from X, on every line between X; and X, that intersects it.
15

---

Published as a conference paper at ICLR 2022
C.1 PROOFS FOR PROPOSITIONS, LEMMAS, AND THEOREMS 2.10
Proposition 2.2. Any function E argmingeec. Imiz (g, Px, satisfies mix (h) S Jmiz (g) for any continuous g C.
Proof. Intuitively, the idea is that when h and differ at a point x: E X X there must be a neighborhood of for which the constant function that takes value ((x) has lower loss than g due to the continuity constraint on We formalize this below.
Let be arbitrary function in argmin gec- mmiz (g. 1y, and let g be a continuous function in C. Consider point X such that the limit in Definition 2.1 exists and that h(x) A g(ar) (if such an did not exist, we would be done). Now let 0n and 6g be the constant functions whose values are h(x) and ((x) (respectively) on all of R" and further let 0, orgming Smir (z))),()) (this is shown to be single value in the proof of Lemma 2.3 below). Finally, as a convenient abuse of notation, we will use (miz(())Bsse to indicate the result of replacing all log g terms in the integrands of Jmir (g)l (x) with c', shown below (note that doing so, we can combine the and À terms from mixing classes i and j; this simplifies the f&j of Lemma 2.3).
miz expression obtained in the proof
Jmiz (c)) =
cij SIyee
i j=1
Since On * fg. we have that there exists 8' such that for < 8' have 10hs 0g 0. From this we get that there exists é' >> O depending only on and Og such that:
Jmise (ansz(0g)) (9g)( Jmir 7m)ir(0)lmmmer 2 (m) (())))
Now by the continuity of g (and thus the continuity of log g') we may choose d S 8' such that Juin (g) Bs(x) E -min (0g) Bx(x) + "miz(ee)) [mir(e")lBsts)) This implies Jmiz (g) (5 2 Jmin (Ox)) Ba(a) (a())) and since x was arbitrary (within the initially mentioned constraints, as outside of them is uncon- strained) we have the desired result.
Lemma 2.3. For any point x E Xmix and > 0, there exists a continuous function he satisfying:
ST,e + Ejtt (Szie, + (E2i
(1(x) = E/=1
(I)
E9.0 Ejjto (Eg.) X + (5/.4
With the property that lim hx(x)) h(x)) for every argmin Jmii (g. Px,P,) when the limit exists.
Proof. Firstly, the condition that x Xmiz is necessary, since if U Add has measure zero the LHS of Equation 1 is not even defined.
Now we simply take hx(z) = argmingejo.11- Jmin (f) (x()) as in Definition 2.1 and show that he is well-defined.
Since the argmin is over constant functions, we may unpack the definition Jmii B. (x) and pull each of the log 0' (z,c(A)) terms out of the integrands and rewrite them simply as log 0', Doing so, we obtain:
J&s - log 0² (gh.
Eld log 0')
Plugging the above back into Jmii and collecting the log 0¹ terms as i 1,... I get:
&
Jmii (g. Px, PX)PPP))BBB)))) =
Σ
chu
+
(stil + (Etid - gdi <bh,ww)) log of
Sz,e
16

---

Published as a conference paper at ICLR 2022
Where the first part of the summation above is from mixing X, with itself, and the second part of the summation corresponds to the À and (1 A) components of mixing X; with Xy. Discarding the terms for which the coefficients above are 0 (the associated 0 terms are taken to be O, as anything else is suboptimal due to the summation constraint), of - log 0 log 0²=, ..... - log 0'm, where the set {61, i..... 2m) J is a subset of {l....,k) k). If the aforementioned set consists of only single index then the unique optimizer is of course f = 1. On the other hand, there are multiple 8²2, we cannot minimize Jmii (x(x)) by choosing any of the l to be O, and as a consequence we also cannot choose any of the 0'r to be since they are constrained add to
are left with linear combination
As such, we may consider each of the 0'r E [ō. 1 o] for some > O. With this consideration in mind, Jmiz (x) is strictly convex in terms of the f'r, since the Hessian of a linear combination of llg frr will be diagonal with positive entries when the arguments of the log terms are strictly greater than 0 and less than 1. Thus, as [6, 1 8)mH is compact, there exists unique solution to justifying the use of equality. This unique solution is easily
hz(z) = argming (0) (O)[BB(()) (u)) (x)).. computed via Lagrange multipliers, and the solution is given in Equation 1.
We have thus far defined he on Xmixx and it remains to check that this construction of he corresponds to the restriction of a continuous function from F. + [0, 1 To do so, we first note that X is closed, since any limit point x' of Xmii must necessarily either be contained in one of the supports X; (due compactness) or on line segment between/within two supports (else it has positive distance from X m, and every e'-neighborhood of x' contains points x for which UL a.e has positive measure for every e (immediately implying that U A' has positive measure).
Now we can check that he is continuous on Xmiz as follows. Consider sequence I'm - x=; we wish to show that h, (x)) + hx().. Since the codomain of h, is compact, the sequence h. (Tm) must have a limit point h²",." Furthermore, since each h, (Xm) the unique minimizer of Jmir B, (xm)) we must have that h is the unique minimizer of m B, (x*), implying that h h=(x)). We have thus established the continuity of ht on Xmiax and since Xmiz is closed (in fact, compact), we have by the Tietze Extension Theorem that he can be extended to a continuous function on all of IR..
Finally, if lim,-so (x)) exists, then it is by definition h(x) for any h E C and therefore for any E argmingec- Jmin Py).
Corollary C.1 (Symmetric Version). F is symmetric, then we may simplify hy to be:
cia + +2Enji S..eed S2,t
(x(x)
EE=1 (52:2 + Ejjty
jopy S2,e,>)
cid Proof. In the symmetric case, we have Sz,r,A
ehit $2,0,''
Sz,e
Proposition 2.5. Let X2 ((0, 1)) and let X² {(1, 0), (-1, 0)), with Px being discrete
uniform over X UX2, and y being continuous uniform over [0, 1]. Then the Mixup-optimal classifier is discontinuous at (0, 0).
Proof. Considering the point (0, 0), we note that only cl.1 and <2.2 are non-zero for all >> 0.
Furthermore, we have that fl.1 x2.2 since the meesurre of (²) is 2e and the sets
A 42.2 have IP measure $. From this we have that the limit lim (x( = [ 2
11
is the
Mixup-optimal value at x..
On the other hand, every other point on the line segment connecting the points in X, will have an e-neighborhood disjoint from the line segment between the points in X2 (and vice versa), we will have ht (x) = 1 for all < e. This implies that (x) + [1 0] (and an identical result for points on the X₂ line segment), so we have that the Mixup-optimal classifier is discontinuous at (0, 0) as desired.
Theorem 2.7. Let Py have associated density Beta(a, a). Then for any classifier h. on X3 (as defined in Lemma 2.3), we may choose a such that bt does not achieve O classification error X2
17

---

Published as a conference paper at ICLR 2022
Proof. Fix classifier h. defined in Lemma 2.3 on X3. Now for Y Beta(a, a) we have by the
fact that Beta(a, a)) is strictly subgaussian that P (
S r) 2 1 2exp (-e- =22((222) where
o² 20+2 is the variance of Beta(a, a). As result, we choose
l -1)
to guarantee
- c) > 1 and therefore that 51,c > $ = Si. Now we have by Lemma 2.3 (or more precisely, Corollary C.I) that:
that (|Y
1 (1) = 5 + 4 + 22,2 2
S1,e + 2
Thus, we have shown that he will classify the point 1 as class despite it belonging to class 2.
Proposition 2.8, Consider k-class classification where the supports XI...,,y, are finite and Fx corresponds to the discrete uniform distribution. Then for every h E argmin Jmiz (g. Px, IP) ppy) we have that h² (xx) on X₃.
Proof. The full proof is not much more than the proof sketch in the main body. For X have that cigg + and
ein Sz.c, + 0 as 0 for every (5,g) * (i, while Sz,
x. and
1A As a result, we have lim.-+o (z) as desired.
X.
Theorem 2.10. We consider the same setting as Proposition 2.8 and further suppose that Assumption 2.9 is satisfied. Then for every E argmin gEC- Jmia (9, Px,Py), we have that (z) = 1 on X; and that h is continuous on X.
Proof. Obtained as a corollary of Theorem 3.2.
C.2 PROOF FOR THEOREM 2.11
Prior to proving Theorem 2. 21, we first introduce some additional notation as well as a lemma that will be necessary for the proof.
Throughout the following m corresponds to the number of data points being considered (as in Theorem 2I1 and shorthand we use [m]] to indicate (1,..., m. Additionally, for two matrices A and B, we use the notation [A, B] to indicate the matrix formed by the concatenation of the columns of to A. We use e; denote the i-th basis vector in R" and use e to denote the i-th basis vector in R(T), Let A x be the "Mixup matrix" where each row has two 1s and the other entries are O, representing a mixture of the two data points whose associated indices have a 1. The (m)) rows enumerate all the possible mixings of the m data points. In this way, A is uniquely defined up to a permutation of rows. We can pick any representative as our A matrix, and prove the following lemma.
Notation:
Lemma C.2. Assume m 6, and P (T) is permutation matrix. If PA is not permutation of the columns of A, then the rank of [A, PA] is larger than m.
Using this lemma we can prove Theorem 2.11.
Theorem 2.11. Suppose (11,,..,, Fm } with m are sampled from X according to Ixx, and that Fx has density. Then with probability 1, we can uniquely determine the points {#1, Fm given only the (m) midpoints (xi. isicssm"
Proof. We only need to show that the set of samples that cannot be uniquely determined from their midpoints has Lebesgue measure zero, since Px is absolutely continuous with respect to the Lebesgue measure. It suffices show this for the first entry (dimension) of the x; 's, the result then follows for all dimensions. Let {a/} be another sample of m points. For convenience, we group the first entries of the data points {xx { 1 into vector w" E R and similarly obtain R from {a \m Suppose w" E R.T not a permutation
w E R but that they have the same set of Mixup points. We only need to show that the set of such w has measure zero
18

---

Published as a conference paper at ICLR 2022
Suppose A is Mixup matrix and P is permutation matrix. Suppose PA is not permutation of the columns in A. We would need Aw" = PAw, which is equivalent to [A, PA]](w") - =
(here [(w*) TT= - " indicates the vector resulting from concatenating -w to w*). According to Lemma C.2, we know the rank of [A, PA] is at least m + 1, which implies that the solution set of w
is most m7
So fixing A and P. the set of non-recoverable w" has measure zero. There are only a finite number of combinations of and P. Thus, considering all of these A and PA, the full set of non-recoverable w still has measure zero.
C.2.1 PROOF OF SUPPORTING LEMMA
Lemma C.2. Assume m > 6, and P E (T)) is permutation matrix. If PA is not a permutation of the columns of A, then the rank of [A, PA] is larger than m.
Proof. First, we show that both the ranks of A and PA are m. For all E [m- m 1], define u, = e1 + Es+1, and define um = e2 + Eg. Note that these vectors are all rows of A. The first (m - 1) vectors {u: J=r are linearly independent because each u, has a unique direction 6141 that is not linear combination of any other vectors in {ur) Besides, we know that the span of [= is subspace of {v E R" - - v(i)= = v(1) where vt) is the i-th entry of v. Therefore, um doesn't t lie in the span of {u, 1==1 which implies that these n vectors {u, 1==1 are linearly independent. This shows that A is at least rank m. Since A only has m columns, we know that the rank of A is m. The
matrix PA is also rank m because P is full rank.
Therefore, to show that the rank of [A, PA] is larger than m, only need to find vector that lies in the column span of A but is not in the column span of P.A. To do this, we need the following claim:
with size (m 1) such that the sub-matrix composed by the rows of A with indices in has a column that is all-one vector, but every column of the sub-matrix composed by the rows of PA with indices in I is not all-one vector.
Claim 1. There exists row index subset I C [[[]]
Proof of Claim 1. By the definition of A, each column of has only (m 1) ones and the other entries are zero. Therefore, the position of (m 1) ones in a column of A can uniquely determine that column vector. Besides, for an index set I with size (m - 1), the sub-matrix composed by the rows of A with indices in cannot have two columns that are both all-one vector. This is because otherwise A will have duplicate rows, which contradicts the definition of A. Therefore, there are m possible choices of I, each of which corresponds to the positions of all ones in a column of A.
Assume by contradiction that for these m choices of J, there exist a column of the sub-matrix composed by the rows of PA with indices in / that is all-one vector. Then these choices of I also correspond to the positions of all ones in a column of P.A. This means that the columns of A and P are the same up to permutations, which contradicts the assumption of our theorem. This finishes the proof of this claim.
Now define B1 the sub-matrix composed by the rows of A with indices in I, and C1 as the sub-matrix composed by the rows of PA with indices in J. Without loss of generality, suppose T= [m 1), and suppose the first column of B, is all-one vector. Let -1 Σmzer es E Rm
we know that Au = 2
im et,, i.c., the first (m 1) entries of Au are 0, and the other entries are 2. Define A Au, we are going to show that v is not in the column span of PA. Let C2 be the sub-matrix in PA consisting of the rows that are not in C1, then the following claim shows that C2 has full column rank.
Claim 2. ronk(C2) = m..
Proof of Claim 2. In this proof, we will consider each column of C2 as vertex. Since each row of C2 has only two 1s, we view each row as an edge connecting the two columns which correspond to the two 1s in that row. From the definition of A we know that the graph we constructed is simple undirected graph. Then we are going to show that we can select m "edges" from C2 which are linearly independent.
19

---

> m² so Published as a conference paper at ICLR 2022
There are (2) (m 1) edges in C2- From 6 we know that (2) (m 1)
1)>
from Turán's s theorem, C2 contains at least one triangle. Assume this triangle is (i, k), then we select edges j). (j. k) and ki, and define Σ = k.. Vr E [m], r 2 3. we select an edge E, and t Er, we then add to E,, i.e., E = E, U {t). In the next two paragraphs, we are going to show that there are always edges between E, and [m] E, (so we can successfully select edges in total), and the edges selected are linearly independent.
connecting E, with [m]] Er. Assume that edge is (s, t) where
In matrix PA, there r(m - r) edges between E, and [m] Er. Since C2 is constructed by deleting (m - 1) edges from PA, the number of edges left between E, and [m]] \ F, is at least m 1,
r(m -r) (m 1). When 3
m 2. we have r(m r) (m - 1) > 0. When the only case where there is no edge between E, and [m] \ E, is when all edges from vertex [m] Er
in C1, which means that C₁ has a column that is all-one vector and is a contradiction. Therefore, there are always edges between E, and [m] \ E, and we can successfully select m edges.
Then we only need to show that these m selected edges are linearly independent. We use {ur] to denote the vectors that correspond to these edges, i.e., Assume by contradiction that they are linearly independent, then there exists x E IRm x # 0 such that E (z))u; = 0. By the selection process of the edges, we know that Vr 2 4, u, has a unique direction, So (T) = 0. Therefore, x z())uz + x(2)uz + x33)u3 = O. Since {u,, u2 U3} are linearly independent, we have x 0, which is a contradiction. Thus, these selected edges are linearly independent, proving the claim.
E4 ey. 42 ej + cks Ug = + Ck.
Now assume by contradiction that is in the column span of PA, then 3w E I such that PAw.
Let 02 E (m-)) be the bottom (2) - (m - 1) entries of u, then U2 = C2w. Define wy to be the all-one vector in Rm we know that w/ is valid solution to 1/2 C2w. Since C2 has full column Crw. This implies that P PAwp- However, we i= et ن which is contradiction. Thus, is not in the column span of A.
rank, wo must be the unique solution to
mm)
know that PAwo 2
which finishes the proof of the lemma.
D ADDITIONAL EXPERIMENTS FOR SECTION 2
D.1 EXPERIMENTS FOR SECTION 2.3
As noted in the main paper. is not difficult extend Definition 2.6 to construct datasets on which Mixup training empirically fails for small values of a. The observation to make is that major part of the proof of Theorem 2.7 is the fact that the same-point mixing probability of point I small relative to the same-class mixing probability of class O. As the former probability decreases quadratically with the dataset size m, we are motivated to consider extensions of X2 consisting of more points and more classes. Towards that end, we consider the following generalization of X².
Definition D.1 (m-Point k-Class Alternating Line). We define X to be the k-class classification
dataset consisting of the points {0, 1.., m 1} classified according their value mod ls incremented by 1. As before. Px is the normalized counting measure on X=
We now consider training a two-layer feedforward network on X% and X using the same procedure and hyperparameters in the main paper. The results are shown in Figure 8 below.
Here we see that even at a = 1, Mixup training fails to minimize the original empirical risk on X% and 2/18 whereas in the main paper noted that at a = 1 Mixup training had no issues minimizing the original risk on X². Interestingly, we find that even standard training does not completely minimize the original empirical risk on X% once again perhaps result of the regularity of the twoel network model (although this is merely a hypothesis, and we do not analyze this phenomenon further here).
D.2 EXPERIMENTS FOR SECTION 2.4
Here include the additional experiments mentioned in Section 2.4, namely the results of training ResNet- 18 on MNIST, CIFAR-10, 10, and CIFAR- 100 with and without Mixup for a = 123 and 128 (with the other hyperparameters being described in Section 2.4). The results shown in Figure 9.
20

---

Published as a conference paper at ICLR 2022
Error Curves, Alternating Line 1.0, 10 Runs)
Error Curves, Alterneting Line (a 32.0, 10 Runs)
0.3
0.4
Tairring Ener
Tairinn Ererr
0.3
0.3-
02-
0.1-
ERM Mixup
ERM
Mixup
0.0
0.0
Epochs
(a) Lio
(b) X
32
Enror Curves, Alteraating Line 1.0. Runs)
Error Curves, Alternating Line la 32.0. 10 Runs)
0.8
0.7
0.7
Training Ennor
0.5
Training Enos
0.5-
0.1-
0.1
0.2
0.0
Mixup
0.0
Mixup
1000
2000
3000
4000
5000
1000
2000
3000
4000
3000
Epochs
Epochs
(c) 10
a =1
(d) X
32
Figure Training error plots for Mixup and regular training on X2 and X11 Each curve corresponds to the mean of 10 training runs, and the area around each curve represents a region of one standard deviation. Note that the ERM curves appear slightly different across values due to changes in y-axis scale.
As mentioned in the main body, these choices of a only lead to Mixup performing more similarly to ERM than 1024.
E FULL PROOFS FOR SECTION 3
E. PROOF OF THEOREM 3.2
Theorem 3.2. Consider k-class classification where the supports XI...,, are finite and Px
corresponds to the discrete uniform distribution. If a point æ satisfies Assumption 3.1 with respect to a class i, then for every h E argmin sec- Juii (g, 1x,, x Py), we have that classifies a as class and that h is continuous at r.
Proof. For two points q in the supports XI...., Xş with line segment between them intersecting x, A(p, q, .)) denote the value of for which Ap + (1 A)y = æ. Since the supports are finite, we have that there exists > 0 such that for all S we have that:
ΣΣ P B.((pga)))
dl,,
Where the summations are over all points 9 with line segments containing x. Now we have by the Lebesgue differentiation theorem applied the integral term in the summations above (this
21

---

Published as a conference paper at ICLR 2022
PITEE CaroN, MARST LF S.A BATTO
Fow Surves CHARTE oF 1.0. Bans
Friee On CRMATIN ja a M.Ree
60
0.23
64-
-5
0.22
0313
0.00
DKC
IACE
63
19
(a) MNIST (a= 1)
(b) CIFAR-IO (a = L)
(c) CIFAR-100 (a
Durves,
CHANTRE
0.355
0.330
0
0013
6.2
0.09
511
271
0.08
Steup
Spocks
Epeckt
Epodtt
(d) MNIST (a- 32)
(c) CIFAR-10 (a- 32)
(f) CIFAR-100 (a- 32)
Oreer Careeh, MISSTee 128.0
Curves CfAR2bie 126.3. huru
Capee CEARUO is 1225., 3amd
0.44
0.800
0.39
6015
Spocks
Epecks
Epccks
gg) MNIST (a = 128)
(h) CIFAR-10 (a = 128)
(i) CIFAR-100 (a = 128)
Figure 9: Mean and single standard deviation of training runs for Mixup (a 1,32, 128) and ERM on the original training data.
is possible because Fy has density) that the following limit (as well as each limit for the other coordinate functions) exists:
tid +
Eijts
(it.) (Sx.ed + (Eli <E..,))
lim h +0
lim
Sa,6
-0
Eg=1
<q. SR,e
Ejjty j
(5x,e,> + +E2:1 - cl.
1ehh 1
(Seiei + (chit edi -).,,)))
lim
k q=1 <x. +
Ejjt (5gg) + (ch.
<dle,)))
eda
Now by Assumption 3.1, we need only consider the Ereer Szy.A terms (as there no other line segments that contain x)) Furthermore, we have that there exists C2 0 such that for all S 02 1 for p E X, and q E X3, and that the measure of ALd is at least that of A have X(p, q. x) c 2 2 From this we get that for all e S min(E1. E2):
Chi2 + Ejtt (sth + (Shi
chit
M
$z,e
Σjje
(Eti + edi
S2,0, + (Eh (ehe.))
+ (522
eta S
ct,
Σjtt
(cع
+ (ct. chi shh,,)) 1
Sg.
i) G
+ 2 2 jzli Σjjt
(St + (ghit
<bica)) 2
dit
22

---

Published as a conference paper at ICLR 2022
Since the above also holds for sufficiently small neighborhood about x, we have the desired result.
E.2 PROOF OF THEOREM 3.5
Let us first recall the setting of Theorem 3.5, since it is more specialized than that of the previous results.
Setting. We consider the case of binary classification using linear model 0 on high-dimensional Gaussian data, which is a setting that arises naturally when training using Gaussian kernels. Specifi- cally, we consider the dataset X' to consist of n points in I= distributed according to (N fP) with d > n (to be made more precise shortly). We let the labels of points in X be =1 (so that the sign of 0 I is the classification), and use X1 and X-1 to denote the individual class points. Additionally, [ and n2 |X-1\-
we let
Before introducing the proof of Theorem 3.5, we first present a lemma that will be necessary in the proof.
Lemma E.1. [Strict Convexity of Jmie on Data Span] Suppose n1 = n2 = 1, i.c. there are two data points x, z with opposite labels. If and are linearly independent, then Jmiz strictly convex with respect to O on the span of x and z.
The reason this lemma focuses on the two data point case is that in the proof of Theorem 3.5 we will break up the Mixup loss into the over these cases. With this lemma, may now prove Theorem 3.5. Before doing so, we point out that the version of Jmiz considered here is after composition with the logistic loss (since we are considering binary classification with linear classifier).
Theorem 3.5. If the maximum margin solution for X is also an interpolating solution for X, then any that lies in the span of X and minimizes the Mixup loss Jmix for a symmetric mixing distribution Py is rescaling of the maximum margin solution.
Proof. Since d > n, we have that all of the points {-:) { are linearly independent with probability one. We will break the proof into two parts. In doing so, we make the following important observation: it suffices to prove the result for mixings of distinct points. This is because an interpolating solution (as given in Definition 3.3) is immediately seen to be optimal for the ERM part of Jmin (the terms corresponding to mixing points with themselves). Thus, in what follows, we disclude these ERM terms from Jmic to simplify the presentation.
Part I: 711 122 1. Denote 0 21 and 0 21 -2 then
Jmiz E, [X log(1 + exp(- -xu + (1 A)o)) + (1 - A) log(1 + exp(Auu - (1 - -))))]- (2)
Where À distributed according to P,, which symmetric and has full support on [0, 1]. Therefore, we can do the change of variables À == 1 X, and
Jmix Ex [A log(1 + exp(-xx Au + (1 - A)w) + (1 - A) log(1 + exp(Xc - (1 (1-A)=0)]
(3)
Combining E2) and E3),3), we know if (u, -v) is a global minimum of Jmias then so is (v, uu). But the strict convexity in Lemma E.1 implies such a global minimum is unique,
must have u = u = k(P,), f), where k((P,) is a constant that only depends on the density of Py. Furthermore,
AY E [0, 1], define
hx(k) Alog(1 + exp((1 - 2A)4)) - (1 - A) log(1 + exp((2A 1)k)),
(4)
then Vk > 0.
hx(-k) (k)) (1 22) + exp((1 -2))k)) + +(A 1) +cx(((2 -1)))
1 + exp(x((1 - 22)kk
= (1 1-22) log log
2 0,
(5)
1 1 exp((2X - 1)k)
and
(k))) - 1 (1 (12))² < O.
(6)
23

---

Published as a conference paper at ICLR 2022
Hence, must have k(P,) 0.
Part II: General n2 and 72.. For the general case, we extend the observation we made prior to the proof of Part L. Namely, if we show that an interpolating solution is optimal for mixing across the two classes, it follows immediately that the solution is optimal for all of Jmir (it is not hard to see that the calculation for mixing points from the same class is essentially no different from the ERM case in this context, as the À and 1 À terms can be combined). We thus focus only on mixing across classes, and overload the JJs the loss in consideration as:
miz notation to indicate mixing of points x; and æj. so that we may write
72
Juni (0)
Ju.
(0). miz
71
By the proof in the previous part we know if JhJJ is minimized, then we must have 0 22 = -0 -T=a = miz
k(P)) 0. On the other hand, if Jo (0) are minimized simultaneously for all pairs (i.j). then clearly Jmir (0) is also minimized. This is possible since the data points are linearly independent, so there exists IRd, such that
0 8 = 0 = = >0
Vi [ma], Vj E [m2].
Now conclude that any 0 that minimizes the Mixup loss Jmiz is interpolating solution. Restricting 9 to the span of finishes the proof.
E.2.1 PROOF OF SUPPORTING LEMMA
Lemma E.1. [Strict Convexity of Jmiz on Data Span] Suppose n1 = n2 = 1, i.e. there are two data points x, = with opposite labels. If x and are linearly independent, then Jmiz is strictly convex with respect on the span of x and
Proof. We note again that it suffices to prove the strict convexity with respect to only the mixings of different points, as the ERM part is clearly strictly convex and the sum of two strictly convex functions remains strictly convex. Denote
S(A) Ax + (1 - A)z.
(9)
then Jmiz can be expressed as
mmi (0) ΣΕ [olog(1 + exp(-0) (()))))((A))) + (1- A) exp f(a)))
Ex |log(1 1 + (x)()))((A)) + +(1 (1- A)eT f())]
(10)
Where again ~ py. Note that the second term in Eq.(10) is linear in 6, hence the Hessian of J be written
exp(-0T (())
22J (0) = EB
(1+ (1+exp(-0) exp(-00 (TT)()) S(A)(N))
(II)
IA)((AA)
Define B Span(z; 2). To show Jmnc is strictly convex on suffices to show for every non-zero vector a E B, we always have
222 Jmiz mix (0)a 0.
(12)
Note that g(A) is continuous w.z.t À and that P has full support [0, 1), it suffices show either a> a or a a 0.
a f(()
(13)
which is equivalent to either
a a 00
(14)
This is obvious since is non-zero vector in B, and that x and linearly independent.
n
24

---

Published as a conference paper at ICLR 2022
Base Model
(alihaa
Mixup (alpha 64)
)
Figure 10: Decision boundary plots for 32, 64 and class separation of 0.5.
Model
Mixup Model (alpha 128)
Model (alpha
 CD
Figure 11: Decision boundary plots for 128, 512 and class separation of 0.5.
25

---

Published as a conference paper at ICLR 2022
F ADDITIONAL EXPERIMENTS FOR SECTION 3
In this section, we consider different class separations and choices of the mixing parameter a when training on the two moons dataset, with all other experimental settings being the same as Section 3.1.
Upon decreasing the class separation 0.1, we that standard training captures more of the nonlinear aspects of the data, as was observed in the prior work of Pezeshki et al. (2020).
Base Model
Mixup Model (alpha 1)
Mixup Model (alpha 1024)
S
5
5
Figure 12: Decision boundary plots for a = 1, 1024 and a class separation of 0.1.
Base Model
Mixup Model (alpha 32)
Mixup Model (alpha 64)
5
5
Figure 13: Decision boundary plots for a = 32, 64 and class separation 0.1.
Base Model
Mixup Model (alpha 128)
Mixup Model (alpha 512)
Figure 14: Decision boundary plots for a = 128, 512 and a class separation of 0.1.
26


Reviews:
[{"review_id": "x0BV-f9GIBd", "reviewer": "Reviewer_NoVN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides an interesting  study, from the properties of the training data perspective, why and when Mixup help training better classifier in terms of model generalization and adversarial robustness. The papers show that both the model generalization and adversarial robustness brought by Mixup training heavily depends on the properties of the training data. Such observations have been empirically observed (such as by Guo et al. in (2019) as cited), but this paper provides a more formal theoretical analysis on that. I think this paper contribute an interesting analytical framework and useful insights regarding Mixup training to the community. Nevertheless, I have the following comments to the paper.\n\n1.\tThe paper did construct a case that Mixup failed to minimize the original empirical risk, and conjectured (at the end of section 2.3) that datasets with collinear structures amongst data points may cause Mixup to fail. I wonder if the authors could be more precise and specific on the conditions for such Mixup failure and formally prove that to some extent. \n2.\tFor figure 2, I wonder if the Mixup training errors are on the original training points or on the mixed points. It seems to me that Mixup obtained higher training error than the training without Mixup. Using these observations to support that “mixup training minimizes the empirical risk” (the first sentence of the last paragraph in Page6) is not very convincing to me. What training errors would you get if you train the models with a smaller \\alpha? \n3.\tI do not fully understand the argument in the last two sentences of Section2.4: “…This is in contrast to the fact that the test data points exhibit greater angular distance to the mixed training…”. To me, the reason for the test performance of Mixup at \\alpha =1024 is significantly worsening than ERM could be that the testing points are very different from the mixed points even though the training loss is low. Also, the manifold intrusion issue as discussed in Guo et al. (2019) seems to indicate the cases that mixed samples collide with the original training samples, not the test points. In your case, Mixup training with \\alpha = 1024 seems to not having such intrusion issue, but augmented samples generated by Mixup may have the affinity issue (i.e., far away from the training set). See “Tradeoffs in Data Augmentation: An Empirical Study” (Gontijo-Lopes et al., ICLR 2020).\n4.\tSection 2.5 is interesting to me, but also remind me of a recent paper “Midpoint Regularization: From High Uncertainty Training Labels to Conservative Classification Decisions” (Guo, ECML 2021). In that paper, mid-point samples (a special setting of Mixup) are generated for training. The empirical studies in that paper seems to be consistent to your theorem 2.11 here. In this sense, further discussion relating to the observations in that paper could be beneficial.\n5.\tThe paper could benefit from a more detailed related work section for the completeness of the paper. For example, Mixup has been applied to other settings such as natural text and graph data. Another missing work is “Mixup as Directional Adversarial Training” (Archambault et. al., 2019), which also attempts to provide a theoretically framework to understand why Mixup works, and their analysis seems to be related to section 3 in this paper. \n\n\nMinor question:\n\nThe theoretical analysis here is under the setting that the mixing ratio \\lambda is the same for mixing both the inputs and labels. Recent work on Mixup which uses different mixing ratios for the input and label mixing seems also working well (e.g., \"Nonlinear Mixup: Out-Of-Manifold Data Augmentation for Text Classification\", Guo, AAAI2020). I am curious to know if your theory in the paper still holds in that setting. \n", "summary_of_the_paper": "The paper provides a theoretical framework to enable analyzing Mixup training from a data dependency perspective, aiming to understand how the structure of the training data impacts the effectiveness of Mixup training. The paper first shows that the benefits of Mixup training, in terms of model generalization and adversarial robustness, heavily rely on the properties of the training data, and studies when Mixup training can fail to minimize the original empirical risk. In addition, the paper also theoretical characterizes the margin of a Mixup classifier, justifying why a Mixup classifier’s decision boundary is better than standard training and when such advantage disappear (i.e., in cases of training Mixup with linear models and linearly separable datasets). The paper contributes an interesting perspective for looking into Mixup training, which has been widely adopted by the community.   ", "summary_of_the_review": "The paper contributes to the understanding of Mixup training from a training data dependency perspective, which is novel and I think it would benefit the research community. On the other hand, the paper is not clear to me in some places as detailed in my reviews, and I would like the authors to comment on them.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "tst7V4nbYlz", "reviewer": "Reviewer_mn55", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the topic of this paper, but I have several concerns as below.\n\n1. Focus on extremely high \\alpha values\n    1. In the illustration of mixup examples, this paper considers \\alpha=32, 128, 1024, which is not even considered in the original mixup paper (standard one is \\alpha=1, and maybe variant the authors considered is \\alpha=2). My personal feeling is, no one will use such large alpha in real application of mixup; they will just use default value \\alpha=1. I think the authors are setting extremely large \\alpha values to exaggerate the effect they want to show. \n2. Theory results are limited to simple settings\n    1. Proposition 2.5 and Theorem 2.7 holds for only a certain dataset. I guess both are not deserved for proposition & theorem, just some “example”.\n    2. Results on Sec.3.2 are applicable for linear model with Gaussian data\n3. We cannot know whether the assumptions are realistic\n    1. Assumption 2.9 and 3.1 -> How can we know that this assumption holds in real datasets?\n4. Conclusion of Sec.2.5 is unclear\n    1. It seems like the Sec.2.5 should be about analyzing the convergence rate of original empirical risk when we use mixup training. Is Theorem 2.11 sufficient for showing that theoretically? I guess not. Moreover, the “midpoints” discussed here is mixing with \\lambda=0.5, which maps to an extremely large \\alpha value case, which is unrealistic.\n", "summary_of_the_paper": "This paper analyzes the empirical risk of mixup-style training methods. First, the authors provide an example where mixup training cannot minimize the empirical risk on the original data. Second, the authors provide sufficient conditions for mixup to minimize the empirical risk.\n", "summary_of_the_review": "This is an interesting paper trying to answer “why” and “when” mixup works. But it is neither a theory paper providing some meaningful theoretical results (that can be applicable for general scenarios), nor an empirical paper suggesting new scheme and providing extensive experimental results. I would say this is a toy theoretical attempt, which is not suitable for ICLR acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_Q0amTQuSAM", "reviewer": "Reviewer_eGEK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths:\n\n* The approach the paper takes in their study is a meaningful one, and the theory and experiments are well motivated.\n\n* The paper goes beyond the observations of related works to provide concrete conditions on which Mixup training can fail, and demonstrate it by constructing synthetic datasets and measures that could be estimated for natural datasets. This could be useful to practitioners as well for when they design their experiments on natural data.\n\n* The paper takes a complementary approach to existing works for understanding the generalization and robustness of the Mixup-optimal classifer.\n\n* Some interesting future work directions are underscored by the paper, such as the rate of convergence of Mixup training (Section 2.5).\n\n# Weaknesses:\n\n* `Mixup at our choice of $\\alpha=1024$`: could you report your experiments for better context? Furthermore, could you explain what the argument is in this paragraph? How does the observation that the test data points exhibit greater angular distance connect with your empirical observation? Do you mean to say that greater angular distance for the test set means less \"collision\" that is discussed in Guo et al. (2019)? I think clarification of this paragraph will improve the paper, because it is at the transition between studying the Mixup optimal classifier and its generalization properties.\n\n* I am curious what kind of applications of your Sufficient Conditions you envision for experiments. Could you elaborate on some interesting directions or limitations as you try to scale to larger and higher-dimensional raw data? \n\n* The Proof Sketch of Lemma 2.3. is unclear to me. Is it correct to say that you \"define\" $h_\\epsilon$ to be the argmin? Do you mean that you \"construct $h_\\epsilon$ and show it is the argmin\" instead?\n\n* The Proof Sketch of Proposition 2.8 is unclear to me. How do we know that the constant measure gives the empirical risk minimization?\n\n* Isn't $\\epsilon$ missing in your definition of $\\xi_{x,\\epsilon,\\lambda}^{i,j}$? \n\n* Not clear what you mean by \"recover\" in Theorem 2.11. Do you mean recover as a linear combination? Could you clarify it in the paper?\n\n* In Section 3.1. Paragraph \"Experiments\" exactly to what does *this* refer to in \"To illustrate this\"? Could you clarify the connection with the previous paragraph?\n\n* Not sure about the summation indices in the proof of Lemma 2.3. In the definition of $J_{mix}$ I think the summation goes only from $j=i+1$ to $k$. How does the summation (and the sign of the summation) change to indices $j=1$ to $i-1$ (and a negative sign) in the last summand in the equation at the end of page 15?  \n\n\n* Do you know of other papers that try to find examples for when the Mixup optimal classifier coincides with the empirical cross-entropy minimizer?\n\n\n## Minor.\n\n* Suggestion for the Introduction. Mixup has been used in contrastive learning settings. You could consider citing some of the works, e.g. [1,2].\n\n* Definition of J_mix on top of page 3. I would suggest to make the dependence on $g$ explicit in the RHS.\n\n* On page 3 you could mention that $A_{x,\\epsilon,\\delta}^{i,j}$ would be used later in the paper.\n\n* Lemma 2.3. Is it that $\\epsilon \\to 0$? You could clarify this.\n\n* Figure 1 and 8: ERM curves do not depend on $\\alpha$? Or am I missing something? Could you clarify this in the captions. What causes the difference between the blue (ERM) curves in Fig. 8(a) and (b)? \n\n* Figure 1's labeling is not clear. Please, enlarge the font.\n\n* Definition 8 is actually Figure 8 in Section D. Maybe a typo in the link? \n\n* The abuse of notation in Proposition 2.2. make it hard to understand the proof. \n\n* In the proof of Theorem 2.11, I am not sure what you mean by $Aw^*=PAw$ is equivalent to $[A, PA][(w^*)^\\top, w^\\top]^\\top$. Could you clarify?\n\n# References\n\n[1] Lee et al. 2021. i-Mix: A Domain-Agnostic Strategy for Contrastive Representation Learning. In ICLR.\n\n[2] Verma et al. 2021. Towards Domain-Agnostic Contrastive Learning. In ICML.\n", "summary_of_the_paper": "This paper provides interesting theoretical tools that help us study the relationship between empirical risk minimization/ empirical cross-entropy minimzation and Mixup minimization. The contributions of the paper consist of the following:\n\n1. Constructing a dataset on which Mixup training fails to obtain the empirical risk minimization.\n2. Providing sufficient conditions for minimizing the original risk and estimates of these sufficient condition measures on natural datasets.\n3. An observation that the rate of empirical risk minimization using Mixup and a theorem about why this should happen.\n4. A study on when the Mixup optimial classifier fails to generalize and a demonstration on a toy dataset.\n5. An example for when Mixup training leads to the same classifier, obtained from standard training.\n\nThe main difference with related works is that the paper attempts to understand *why* Mixup works by studying *when* Mixup works with concrete examples.\n\n", "summary_of_the_review": "I recommend 8: accept, good paper. In my opinion, this paper will be useful to the community both for theory and experiments. I have listed a few questions and suggestions in the Main Review. It is possible that I have missed some of the main arguments in the related works, but to me the contributions of the paper are novel and useful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting analysis of mixup, discussing when it works and when it fails. The theory is further illustrated with small but intuitive examples, which facilitates understanding the underlying phenomena and verifies correctness of the predictions made by the theory. The submission has received three reviews with high variance ranging from 3 to 8: mn55 favoring rejection while eGEK recommending accept. I read all the reviews and authors' response. Unfortunately, mn55 did not follow up to express how convinced they are with author's reply, but I do find the responses to mn55 very solid and convincing. In concordance with eGEK, I do find the provided analysis important and helpful, and the presentation of the theory through concrete examples very compelling.
Decision: Accept (Spotlight)