Year: 2022

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 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.

heading: 1 INTRODUCTION
text: Mixup (Zhang et al., 2018) is a modification to 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 et 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; 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 et al., 2019; Sohn et al., 2020), contrastive learning (Verma et al., 2021; Lee et al., 2020), privacy-preserving learning (Huang et al., 2021), and learning with fairness constraints (Chuang & Mroueh, 2021).
However, from a theoretical perspective, Mixup training is still mysterious even in the basic multiclass classfication setting – why should the output of a 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 et al., 2019; Carratino et al., 2020; Zhang et 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 to Muthu Chidambaram (muthu@cs.duke.edu).
model conditions under which this failure can provably happen when minimizing the Mixup loss. In Section 2 of this work, we provide a concrete classification dataset on which continuous approximateminimizers 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 et al. (2020) showed that Mixup training can be viewed as 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. In 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 to that of the aforementioned works, as we directly consider the properties exhibited by a Mixup-optimal classifier instead of considering what properties are encouraged by the regularization effects of the Mixup loss. In addition to our margin analysis, we also show that for the common setting of linear models trained on high-dimensional Gaussian features both Mixup (for a 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).

heading: 2 MIXUP AND EMPIRICAL RISK MINIMIZATION
text: The goal of this section is to understand when Mixup training can 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 a concrete example on which Mixup training does not 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.

heading: 2.1 SETUP
text: We consider the problem of k-class classification where the classes 1, ..., k correspond to compact disjoint sets X1, ..., Xk ⊂ Rn with an associated probability measure PX supported on X =⋃k i=1Xi. We use C to denote the set of all functions g : Rn → [0, 1]k satisfying the property that∑k i=1 g
i(x) = 1 for all x (where gi represents the i-th coordinate function of g). We refer to a function g ∈ C as a classifier, and say that g classifies x as class j if j = argmaxi gi(x). The cross-entropy loss associated with such a classifier g is then:
J(g,PX) = − k∑ i=1 ∫ Xi log gi(x)dPX(x)
The goal of standard training is to learn a classifier h ∈ argming∈C J(g,PX). Any such classifier h will necessarily satisfy hi(x) = 1 on Xi since the Xi are disjoint.
Mixup. In the Mixup version of our setup, we are interested in minimizing the cross-entropy of convex combinations of the original data and their classes. These convex combinations are determined according to a probability measure Pf whose support is [0, 1], and we assume this measure has a density f . For two points s, t ∈ X , we let zst(λ) = λs+(1−λ)t (and use zst when λ is understood) and define the Mixup cross-entropy on s, t with respect to a classifier g as:
`mix(g, s, t, λ) = { − log gi(zst) s, t ∈ Xi − ( λ log gi(zst) + (1− λ) log gj(zst) ) s ∈ Xi, t ∈ Xj
Having defined `mix as above, we may write the component of the full Mixup cross-entropy loss corresponding to mixing points from classes i and j as:
J i,jmix(g,PX ,Pf ) = ∫ Xi×Xj×[0,1] `mix(g, s, t, λ) d(PX × PX × Pf )(s, t, λ)
The final Mixup cross-entropy loss is then the sum of J i,jmix over all i, j ∈ {1, ..., k} (corresponding to all possible mixings between classes, including themselves):
Jmix(g,PX ,Pf ) = k∑ i=1 k∑ j=1 J i,jmix(g,PX ,Pf )
Relation to Prior Work. We have opted for a 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 [0, 1]. One obtains the original Mixup formulation of Zhang et al. (2018) for multi-class classification on a finite dataset by taking the Xi to be finite sets, and choosing PX to be the normalized counting measure (corresponding to a discrete uniform distribution). Additionally, Pf is chosen to have density Beta(α, α), where α is a hyperparameter.

heading: 2.2 MIXUP-OPTIMAL CLASSIFIER
text: Given our setup, we now wish to characterize the behavior of a Mixup-optimal classifier at a point x ∈ Rn. However, if the optimization of Jmix is considered over the class of functions C, this is intractable (to the best of our knowledge) due to the lack of regularity conditions imposed on functions in C. We thus wish to constrain the optimization of Jmix to a class of functions that is sufficiently powerful (so as 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:
Ai,jx, = {(s, t, λ) ∈ Xi ×Xj × [0, 1] : λs+ (1− λ)t ∈ B (x)}
Ai,jx, ,δ = {(s, t, λ) ∈ Xi ×Xj × [0, 1− δ] : λs+ (1− λ)t ∈ B (x)}
Xmix = x ∈ Rn : ⋃ i,j Ai,jx, has positive measure for every > 0  ξi,jx, = ∫ Ai,jx, d(PX × PX × Pf )(s, t, λ)
ξi,jx, ,λ = ∫ Ai,jx, λ d(PX × PX × Pf )(s, t, λ)
The set Ai,jx, represents all points in Xi × Xj that have lines between them intersecting an - neighborhood of x, while the set Ai,jx, ,δ represents the restriction of A i,j x, to only those points whose connecting line segments intersect an -neighborhood of x with λ values bounded by 1− δ (used in Section 3). The set Xmix corresponds to all points for which every neighborhood factors into Jmix. The ξi,jx, term represents the measure of the set A i,j x, while ξ i,j x, ,λ represents the expectation of λ over the same set. 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 Jmix.
Definition 2.1. Let C∗ to be the subset of C for which every h ∈ C∗ satisfies h(x) = lim →0 argminθ∈[0,1]k Jmix(θ)|B (x) for all x ∈ Xmix when the limit exists. Here Jmix(θ)|B (x) represents the Mixup loss for a constant function with value θ with the restriction of each term in Jmix to the set Ai,jx, .
We immediately justify this definition with the following proposition.
Proposition 2.2. Any function h ∈ argming∈C∗ Jmix(g,PX ,Pf ) satisfies Jmix(h) ≤ Jmix(g) for any continuous g ∈ C.
Proof Sketch. We can argue directly from definitions by considering points in Xmix for which h and g differ.
Proposition 2.2 demonstrates that optimizing over C∗ is at least as good as optimizing over 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 Xmix.
Lemma 2.3. For any point x ∈ Xmix and > 0, there exists a continuous function h satisfying:
hi (x) = ξi,ix, +
∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ) ) ∑k q=1 ( ξq,qx, + ∑ j 6=q ( ξq,jx, ,λ + (ξ j,q x, − ξj,qx, ,λ)
)) (1) With the property that lim →0 h (x) = h(x) for every h ∈ argming∈C∗ Jmix(g,PX ,Pf ) when the limit exists.
Proof Sketch. We set h = argminθ∈[0,1]k Jmix(θ)|B (x) and show that this is well-defined, continuous, 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 hi just represents the expected location of the point x on all lines between class i and other classes, normalized by the sum of the expected locations for all classes. It can be simplified significantly if Pf 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 h as defined in Lemma 2.3 is continuous for every > 0, its pointwise limit h need not be, which we demonstrate below.
Proposition 2.5. Let X1 = {(0, 1), (0,−1)} and let X2 = {(1, 0), (−1, 0)}, with PX being discrete uniform overX1∪X2 and Pf 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 h1(x) = h2(x) = 12 .
Proposition 2.5 illustrates our 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 a minimizer is constant on the class supports and not constrained elsewhere), whereas depending on the data the minimizer of Jmix can be discontinuous.

heading: 2.3 A MIXUP FAILURE CASE
text: With that in mind, several model classes popular in practical applications consist of continuous functions. For example, neural networks with ReLU activations are continuous, and several works have noted that they are Lipschitz continuous with shallow networks having approximately small Lipschitz constant (Scaman & Virmaux, 2019; Fazlyab et al., 2019; Latorre et al., 2020). Given the regularity of such models, we are motivated to consider the continuous approximations h in Lemma 2.3 and see if it is possible to construct a dataset on which h (for a fixed ) can fail to classify the original points correctly. We thus consider the following dataset:
Definition 2.6. [3-Point Alternating Line] We define X 23 to be the binary classification dataset consisting of the points {0, 1, 2} classified as {1, 2, 1}. In our setup, this corresponds to X1 = {0, 2} and X2 = {1} with PX = 131{0,1,2}.
Intuitively, the reason why Mixup can fail on X 23 is that, for choices of Pf that concentrate about 12 , we will have by Lemma 2.3 that the Mixup-optimal classification in a neighborhood of point 1 should skew towards class 1 instead of class 2 due to the sandwiching of point 1 between points 0 and 2. The canonical choice of Pf corresponding to a mixing density of Beta(α, α) is one such choice: Theorem 2.7. Let Pf have associated density Beta(α, α). Then for any classifier h on X 23 (as defined in Lemma 2.3), we may choose α such that h does not achieve 0 classification error on X 23 .
Proof Sketch. For any > 0, we can bound the ξ terms in Equation 1 using the fact that Beta(α, α) is strictly subgaussian (Marchal & Arbel, 2017), and then choose α appropriately.
Experiments. The result of Theorem 2.7 leads us to believe that the Mixup training of a continuous model should fail onX 23 for appropriately chosen α. To verify that the theory predicts the experiments, we train a two-layer feedforward neural network with 512 hidden units and ReLU activations on X 23 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 PyTorch (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 β1 = 0.9, β2 = 0.999 and a learning rate of 0.001 are shown in Figure 1. The class 1 probabilities for each point in the dataset outputted by the learned Mixup classifiers from Figure 1 are shown in Table 1 below:
We see from Figure 1 and Table 1 that Mixup training fails to correctly classify the points in X 23 for α = 32, and this misclassification becomes more exacerbated as we increase α. 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 23 for which Mixup training will fail even for the very mild choice of α = 1. We focus on the case of X 23 here to simplify the theory. The key takeaway is 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.

heading: 2.4 SUFFICIENT CONDITIONS FOR MINIMIZING THE ORIGINAL RISK
text: 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 X1, ..., Xk are finite and PX corresponds to the discrete uniform distribution. Then for every h ∈ argming∈C∗ Jmix(g,PX ,Pf ), we have that hi(x) = 1 on Xi.
Proof Sketch. Only the ξi,ix, term doesn’t vanish in hi (x) as → 0, as the mixing distribution is continuous and cannot assign positive measure to x alone when mixing two points that are not x.
Note that Proposition 2.8 holds for any continuous mixing distribution Pf supported on [0, 1] - we just need a rich enough model class.
In order to obtain the result of Proposition 2.8 with the added restriction of continuity of h on each of the Xi, we need to further assume that the collinearity of different class points that occurred in the previous section does not happen. Assumption 2.9. For any point x ∈ Xi, there do not exist u ∈ X and v ∈ Xj for j 6= i such that there is a λ > 0 for which x = λu+ (1− λ)v.
A visualization of Assumption 2.9 is provided in Section B of the appendix. With this assumption in hand, we obtain the following result as a 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 ∈ argming∈C∗ Jmix(g,PX ,Pf ), we have that hi(x) = 1 on Xi and that h is continuous on X .
Application of Sufficient Conditions. The practical take-away of Theorem 2.10 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 data when compared to ERM. We validate this by training ResNet-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 a batch size of 128 and otherwise identical settings to the previous subsection. For Mixup, we consider mixing using Beta(α, α) for α = 1, 32, 128, and 1024 to cover a wide band of mixing distributions. Our experimental results for the “worst case” of α = 1024 (the other choices are 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 a 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 to test data conflicting with mixed training points. Results are shown below in Table 2.
To interpret the estimated 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 & Virmaux, 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 an implication of Guo et al. (2019), which was that training/test performance on
the above benchmarks degrades with high values of α due to conflicts between original points and Mixup points.

heading: 2.5 THE RATE OF EMPIRICAL RISK MINIMIZATION USING MIXUP
text: 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 to do this - a simple calculation shows that Mixup training only sees one true data point per epoch in expectation (each pair of points is sampled with probability 1m2 and there are m true point pairs and m pairs seen per epoch, where m is the dataset size). The experimental results are even more surprising given that we are training using α = 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 a point and itself), and similar phenomena has indeed been observed in recent empirical work (Guo, 2021). We make this rigorous with the following result: Theorem 2.11. Suppose {x1, ..., xm} with m ≥ 6 are sampled from X according to PX , and that PX has a density. Then with probability 1, we can uniquely determine the points {x1, ..., xm} given only the ( m 2 ) midpoints {xi,j}1≤i<j≤m.
Proof Sketch. The idea is to represent the problem as a 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 information-theoretic sense, that it is possible to 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 it does. A full theoretical analysis of this phenomenon would necessarily require analyzing the training dynamics of neural networks (or another model of choice) when trained only on midpoints of the original data, which is outside the intended scope of this work. That being said, we hope that such analysis will be a fruitful line of investigation for future work.

heading: 3 GENERALIZATION PROPERTIES OF MIXUP CLASSIFIERS
text: Having discussed how Mixup training differs from standard empirical risk minimization with regards to the original training data, we now consider how a 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 one can move from a class support Xi while still being classified as class i.

heading: 3.1 THE MARGIN OF MIXUP CLASSIFIERS
text: Intuitively, if a point x falls only on line segments between Xi and some other classes Xj , ..., and if x always falls closer to Xi than the other classes, we can expect x to be classified according to class i by the Mixup-optimal classifier due to 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 a class i and a point x ∈ Xmix, suppose there exists an > 0 and a 0 < δ < 12 such that Ai,jx, ′,δ and A j,q x, ′ have measure zero for all
′ ≤ and j, q 6= i, and the measure of Ai,jx, is at least that of Aj,ix, .
Here the measure zero conditions are codifying the ideas that the point x falls closer to Xi than any other class on every line segment that intersects it, and there are no line segments between non-i classes that intersect x. The condition that the measure of Ai,jx, is at least that of A j,i x, handles asymmetric mixing distributions that concentrate on pathological values of λ. A visualization of Assumption 3.1 is provided in Section B of the Appendix. Now we can prove: Theorem 3.2. Consider k-class classification where the supports X1, ..., Xk are finite and PX corresponds to the discrete uniform distribution. If a point x satisfies Assumption 3.1 with respect to a class i, then for every h ∈ argming∈C∗ Jmix(g,PX ,Pf ), we have that h classifies x as class i and that h is continuous at x.
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 Ai,jx, ′,δ have measure zero.
Assumption 2.9 implies Assumption 3.1 with respect to each class, and hence we get Theorem 2.10 as a corollary of Theorem 3.2 as mentioned in Section 2. To use Theorem 3.2 to understand generalization, we make the observation that a point x can satisfy Assumption 3.1 while being a distance of up to minj d(Xi,Xj)2 from some class i. This distance can be significantly farther than, for example, the optimal linear separator in a linearly separable dataset.
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 et al. (2020) introduced an explicit regularizer to encourage a nonlinear decision boundary, we expect due to Theorem 3.2 that Mixup training will achieve a 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 a 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 al. (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 et 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 α are included in Section F of the Appendix.

heading: 3.2 WHEN MIXUP TRAINING LEARNS THE SAME CLASSIFIER
text: The experiments and theory of the previous sections have shown how a 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 a linear model θ>x on 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 n points in Rd distributed according to N (0, Id) with d > n (to be made more precise shortly). We also consider the mixing distribution to be any symmetric distribution supported on [0, 1] (thereby including as a special case Beta(α, α)). We let the labels of
points in X be ±1 (so that the sign of θ>x 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 θ) as the ERM classifier learned using gradient descent with high probability. To do so we need some additional definitions.
Definition 3.3. We say θ̂ is an interpolating solution, if there exists k > 0 such that
θ̂>xi = −θ̂>zj = k ∀xi ∈ X1, ∀zj ∈ X−1.
Definition 3.4. The maximum margin solution θ̃ is defined through:
θ̃ := argmax ‖θ‖2=1
{ min
xi∈X1,zj∈X−1
{ θ>xi,−θ>zj
}}
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 forX is also an interpolating solution forX , then any θ that lies in the span of X and minimizes the Mixup loss Jmix for a symmetric mixing distribution Pf is a rescaling of the maximum margin solution.
Proof Sketch. It can be shown that θ is an interpolating solution using a combination of the strict convexity of Jmix as a function of θ and the symmetry of the mixing distribution.
Remark 3.6. For every θ, we can decompose it as θ = θX + θX⊥ where θX is the projection of θ onto the subspace spanned by X . By definition we have that θX⊥ 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 θ lies in the span of X .
To characterize the conditions on X under which the maximum margin solution interpolates the data, we use a key result of Muthukumar et al. (2020), restated below. Note that Muthukumar et al. (2020) actually provide more settings in their paper, but we constrain ourselves to the one stated below for simplicity.
Lemma 3.7. [Theorem 1 in Muthukumar et al. (2020), Rephrased] Assuming d > 10n lnn+ 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 as 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.

heading: 4 CONCLUSION
text: The main contribution of our work has been to provide a 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 a 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.

heading: 5 ETHICS STATEMENT
text: 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 a 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 - we would just like to point it out for completeness.

heading: 6 REPRODUCIBILITY STATEMENT
text: 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 found at: https://github.com/2014mchidamb/Mixup-Data-Dependency. We have tried our best to organize the code to be easy to use and extend. Detailed instructions for how to run each type of experiment are provided in the README file included in the GitHub repository.

heading: ACKNOWLEDGEMENTS
text: Rong Ge, Muthu Chidambaram, Xiang Wang, and Chenwei Wu are supported in part by NSF Award DMS-2031849, CCF-1704656, CCF-1845171 (CAREER), CCF-1934964 (Tripods), a Sloan Research Fellowship, and a Google Faculty Research Award. Muthu would like to thank Michael Lin for helpful discussions during the early stages of this project.

heading: A REVIEW OF DEFINITIONS AND ASSUMPTIONS
text: For convenience, we first recall the definitions and assumptions stated throughout the paper below.
`mix(g, s, t, λ) = { − log gi(zst) s, t ∈ Xi − ( λ log gi(zst) + (1− λ) log gj(zst) ) s ∈ Xi, t ∈ Xj
J i,jmix(g,PX ,Pf ) = ∫ Xi×Xj×[0,1] `mix(g, s, t, λ) d(PX × PX × Pf )(s, t, λ)
Jmix(g,PX ,Pf ) = k∑ i=1 k∑ j=1 J i,jmix(g,PX ,Pf )
Ai,jx, = {(s, t, λ) ∈ Xi ×Xj × [0, 1] : λs+ (1− λ)t ∈ B (x)}
Ai,jx, ,δ = {(s, t, λ) ∈ Xi ×Xj × [0, 1− δ] : λs+ (1− λ)t ∈ B (x)}
Xmix = x ∈ Rn : ⋃ i,j Ai,jx, has positive measure for every > 0  ξi,jx, = ∫ Ai,jx, d(PX × PX × Pf )(s, t, λ)
ξi,jx, ,λ = ∫ Ai,jx, λ d(PX × PX × Pf )(s, t, λ)
Definition 2.1. Let C∗ to be the subset of C for which every h ∈ C∗ satisfies h(x) = lim →0 argminθ∈[0,1]k Jmix(θ)|B (x) for all x ∈ Xmix when the limit exists. Here Jmix(θ)|B (x) represents the Mixup loss for a constant function with value θ with the restriction of each term in Jmix to the set Ai,jx, .
Definition 2.6. [3-Point Alternating Line] We define X 23 to be the binary classification dataset consisting of the points {0, 1, 2} classified as {1, 2, 1}. In our setup, this corresponds to X1 = {0, 2} and X2 = {1} with PX = 131{0,1,2}. Assumption 2.9. For any point x ∈ Xi, there do not exist u ∈ X and v ∈ Xj for j 6= i such that there is a λ > 0 for which x = λu+ (1− λ)v. Assumption 3.1. For a class i and a point x ∈ Xmix, suppose there exists an > 0 and a 0 < δ < 12 such that Ai,jx, ′,δ and A j,q x, ′ have measure zero for all
′ ≤ and j, q 6= i, and the measure of Ai,jx, is at least that of Aj,ix, .
Definition 3.3. We say θ̂ is an interpolating solution, if there exists k > 0 such that
θ̂>xi = −θ̂>zj = k ∀xi ∈ X1, ∀zj ∈ X−1.
Definition 3.4. The maximum margin solution θ̃ is defined through:
θ̃ := argmax ‖θ‖2=1
{ min
xi∈X1,zj∈X−1
{ θ>xi,−θ>zj
}}
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 to help aid the reader’s intuition for our main results.

heading: C FULL PROOFS FOR SECTION 2
text: We now prove all results found in Section 2 of the main body of the paper in the order that they appear.
C.1 PROOFS FOR PROPOSITIONS, LEMMAS, AND THEOREMS 2.2 - 2.10
Proposition 2.2. Any function h ∈ argming∈C∗ Jmix(g,PX ,Pf ) satisfies Jmix(h) ≤ Jmix(g) for any continuous g ∈ C.
Proof. Intuitively, the idea is that when h and g differ at a point x ∈ Xmix, there must be a neighborhood of x for which the constant function that takes value h(x) has lower loss than g due to the continuity constraint on g. We formalize this below.
Let h be an arbitrary function in argming∈C∗ Jmix(g,PX ,Pf ) and let g be a continuous function in C. Consider a point x ∈ Xmix such that the limit in Definition 2.1 exists and that h(x) 6= g(x) (if such an x did not exist, we would be done). Now let θh and θg be the constant functions whose values are h(x) and g(x) (respectively) on all of Rn, and further let θhδ = argminθ∈[0,1]k Jmix(θ)|Bδ(x) (this is shown to be a single value in the proof of Lemma 2.3 below). Finally, as a convenient abuse of notation, we will use Jmix( ′)|Bδ(x) to indicate the result of replacing all log gi terms in the integrands of Jmix(g)|Bδ(x) with ′, as shown below (note that in doing so, we can combine the λ and 1−λ terms from mixing classes i and j; this simplifies the J i,jmix expression obtained in the proof of Lemma 2.3).
Jmix( ′)|Bδ(x) = − ′ k∑ i=1 k∑ j=1 ξi,jx,
Since θh 6= θg, we have that there exists a δ′ > 0 such that for δ ≤ δ′ we have |θhδ − θg| = > 0. From this we get that there exists ′ > 0 depending only on and θg such that:
Jmix(θg)|Bδ(x) − Jmix(θh)|Bδ(x) ≥ Jmix( ′)|Bδ(x)
Now by the continuity of g (and thus the continuity of log gi), we may choose δ ≤ δ′ such that Jmix(g)|Bδ(x) ∈ Jmix(θg)|Bδ(x) ± Jmix( ′)|Bδ(x). This implies Jmix(g)|Bδ(x) ≥ Jmix(θh)|Bδ(x), and since x was arbitrary (within the initially mentioned constraints, as outside of them h is unconstrained) we have the desired result.
Lemma 2.3. For any point x ∈ Xmix and > 0, there exists a continuous function h satisfying:
hi (x) = ξi,ix, +
∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ) ) ∑k q=1 ( ξq,qx, + ∑ j 6=q ( ξq,jx, ,λ + (ξ j,q x, − ξj,qx, ,λ)
)) (1) With the property that lim →0 h (x) = h(x) for every h ∈ argming∈C∗ Jmix(g,PX ,Pf ) when the limit exists. Proof. Firstly, the condition that x ∈ Xmix is necessary, since if ⋃ i,j A i,j x, has measure zero the LHS of Equation 1 is not even defined.
Now we simply take h (x) = argminθ∈[0,1]k Jmix(θ)|B (x) as in Definition 2.1 and show that h is well-defined.
Since the argmin is over constant functions, we may unpack the definition of Jmix|B (x) and pull each of the log θi(zst(λ)) terms out of the integrands and rewrite them simply as log θi. Doing so, we obtain:
J i,jmix = − ( ξi,jx, ,λ log θ i + (ξi,jx, − ξ i,j x, ,λ) log θ j )
Plugging the above back into Jmix and collecting the log θi terms as i = 1, ..., k we get:
Jmix(g,PX ,Pf )|B (x) = − k∑ i=1 ( ξi,ix, + ∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ) )) log θi
Where the first part of the summation above is from mixing Xi with itself, and the second part of the summation corresponds to the λ and (1 − λ) components of mixing Xi with Xj . Discarding the terms for which the coefficients above are 0 (the associated θi terms are taken to be 0, as anything else is suboptimal due to the summation constraint), we are left with a linear combination of − log θi1 ,− log θi2 , ...,− log θim , where the set {i1, i2, ..., im} is a subset of {1, ..., k}. If the aforementioned set consists of only a single index i, then the unique optimizer is of course θi = 1. On the other hand, if there are multiple θip , we cannot minimize Jmix|B (x) by choosing any of the θip to be 0, and as a consequence we also cannot choose any of the θip to be 1 since they are constrained to add to 1.
As such, we may consider each of the θip ∈ [δ, 1 − δ] for some δ > 0. With this consideration in mind, Jmix|B (x) is strictly convex in terms of the θip , since the Hessian of a linear combination of − log θip will be diagonal with positive entries when the arguments of the log terms are strictly greater than 0 and less than 1. Thus, as [δ, 1 − δ]m is compact, there exists a unique solution to h (x) = argminθ∈[0,1]k Jmix(θ)|B (x), justifying the use of equality. This unique solution is easily computed via Lagrange multipliers, and the solution is given in Equation 1.
We have thus far defined h on Xmix, and it remains to check that this construction of h corresponds to the restriction of a continuous function from Rn → [0, 1]k. To do so, we first note that Xmix is closed, since any limit point x′ of Xmix must necessarily either be contained in one of the supports Xi (due to compactness) or on a line segment between/within two supports (else it has positive distance from Xmix), and every ′-neighborhood of x′ contains points x for which ⋃ i,j A i,j x, has
positive measure for every (immediately implying that ⋃ i,j A i,j x′, ′ has positive measure).
Now we can check that h is continuous on Xmix as follows. Consider a sequence xm → x∗; we wish to show that h (xm) → h (x∗). Since the codomain of h is compact, the sequence h (xm) must have a limit point h∗. Furthermore, since each h (xm) is the unique minimizer of Jmix|B (xm), we must have that h∗ is the unique minimizer of Jmix|B (x∗), implying that h∗ = h (x∗). We have thus established the continuity of h on Xmix, and since Xmix is closed (in fact, compact), we have by the Tietze Extension Theorem that h can be extended to a continuous function on all of Rn.
Finally, if lim →0 h (x) exists, then it is by definition h(x) for any h ∈ C∗ and therefore for any h ∈ argming∈C∗ Jmix(g,PX ,Pf ).
Corollary C.1 (Symmetric Version). If Pf is symmetric, then we may simplify hi to be:
hi (x) = ξi,ix, + 2
∑ j 6=i ξ
i,j x, ,λ∑k
q=1
( ξq,qx, + 2 ∑ j 6=q ξ q,j x, ,λ ) Proof. In the symmetric case, we have ξi,jx, ,λ = ξ j,i x, − ξ j,i x, ,λ.
Proposition 2.5. Let X1 = {(0, 1), (0,−1)} and let X2 = {(1, 0), (−1, 0)}, with PX being discrete uniform overX1∪X2 and Pf being continuous uniform over [0, 1]. Then the Mixup-optimal classifier h is discontinuous at (0, 0).
Proof. Considering the point x = (0, 0), we note that only ξ1,1x, and ξ 2,2 x, are non-zero for all > 0. Furthermore, we have that ξ1,1x, = ξ 2,2 x, = 4 since the Pf -measure of B ( 1 2 ) is 2 and the sets A1,1x, , A 2,2 x, have PX -measure 18 . From this we have that the limit lim →0 h (x) = [ 1 2 1 2 ]> is the Mixup-optimal value at x.
On the other hand, every other point on the line segment connecting the points in X1 will have an -neighborhood disjoint from the line segment between the points in X2 (and vice versa), so we will have h1 ′(x) = 1 for all
′ ≤ . This implies that h ′(x) → [1 0] (and an identical result for points on the X2 line segment), so we have that the Mixup-optimal classifier is discontinuous at (0, 0) as desired.
Theorem 2.7. Let Pf have associated density Beta(α, α). Then for any classifier h on X 23 (as defined in Lemma 2.3), we may choose α such that h does not achieve 0 classification error on X 23 .
Proof. Fix a classifier h as defined in Lemma 2.3 on X 23 . Now for Y ∼ Beta(α, α) we have by the fact that Beta(α, α) is strictly subgaussian that P (∣∣Y − 12 ∣∣ ≤ ) ≥ 1− 2 exp (− 2/(2σ2)) where σ2 = 14α+2 is the variance of Beta(α, α). As a result, we can choose α > 1 2 ( log 4 2 − 1 ) to guarantee
that P (∣∣Y − 12 ∣∣ ≤ ) > 12 and therefore that ξ1,11, > 19 = ξ2,21, .
Now we have by Lemma 2.3 (or more precisely, Corollary C.1) that:
h1 (1) = ξ1,11, + 2ξ 1,2 1, ,λ
ξ1,11, + 4ξ 1,2 1, ,λ + ξ 2,2 1,
> 1
2
Thus, we have shown that h will classify the point 1 as class 1 despite it belonging to class 2.
Proposition 2.8. Consider k-class classification where the supports X1, ..., Xk are finite and PX corresponds to the discrete uniform distribution. Then for every h ∈ argming∈C∗ Jmix(g,PX ,Pf ), we have that hi(x) = 1 on Xi.
Proof. The full proof is not much more than the proof sketch in the main body. For x ∈ Xi, we have that ξj,qx, → 0 and ξ j,q x, ,λ → 0 as → 0 for every (j, q) 6= (i, i), while ξi,ix, → 1
|⋃iXi|2 and ξi,ix, ,λ → EPf [λ]
|⋃iXi|2 . As a result, we have lim →0 hi (x) = 1 as desired. 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 ∈ argming∈C∗ Jmix(g,PX ,Pf ), we have that hi(x) = 1 on Xi 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.11, we first introduce some additional notation as well as a lemma that will be necessary for the proof.
Notation: Throughout the following m corresponds to the number of data points being considered (as in Theorem 2.11), and as a 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 B to A. We use ei to denote the i-th basis vector in Rm, and use e′i to denote the i-th basis vector in R( m 2 ). Let A ∈ R( m 2 )×m be the “Mixup matrix” where each row has two 1s and the other entries are 0, representing a mixture of the two data points whose associated indices have a 1. The ( m 2 ) 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.
Lemma C.2. Assume m > 6, and P ∈ R( m 2 )×( m 2 ) is a permutation matrix. If PA is not a 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 {x1, ..., xm} with m ≥ 6 are sampled from X according to PX , and that PX has a density. Then with probability 1, we can uniquely determine the points {x1, ..., xm} given only the ( m 2 ) midpoints {xi,j}1≤i<j≤m.
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 to show this for the first entry (dimension) of the xi’s, as the result then follows for all dimensions. Let {x′i} be another sample of m points. For convenience, we group the first entries of the data points {xi}mi=1 into a vector w∗ ∈ Rm, and similarly obtain w ∈ Rm from {x′i}mi=1. Suppose w∗ ∈ Rm is not a permutation of w ∈ Rm but that they have the same set of Mixup points. We only need to show that the set of such w∗ has measure zero.
Suppose A is a Mixup matrix and P is a permutation matrix. Suppose PA is not a permutation of the columns in A. We would need Aw∗ = PAw, which is equivalent to [A,PA][(w∗)>,−w>]> = 0 (here [(w∗)>,−w>]> 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 at most m− 1. So fixing A and P , the set of non-recoverable w∗ has measure zero. There are only a finite number of combinations of A 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 ∈ R( m 2 )×( m 2 ) is a 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 i ∈ [m − 1], define ui = e1 + ei+1, and define um = e2 + e3. Note that these m vectors are all rows of A. The first (m− 1) vectors {ui}m−1i=1 are linearly independent because each ui has a unique direction ei+1 that is not a linear combination of any other vectors in {ui}m−1i=1 . Besides, we know that the span of {ui} m−1 i=1 is a
subspace of {v ∈ Rm : ∑m i=2 v(i) = v(1)} where v(i) is the i-th entry of v. Therefore, um doesn’t lie in the span of {ui}m−1i=1 , which implies that these n vectors {ui}ni=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, we only need to find a vector v that lies in the column span of A but is not in the column span of PA. To do this, we need the following claim:
Claim 1. There exists a row index subset I ⊆ [ ( m 2 ) ] with size (m − 1) such that the sub-matrix composed by the rows of A with indices in I 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.
Proof of Claim 1. By the definition of A, each column of A 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 I 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 I , there exist a column of the sub-matrix composed by the rows of PA with indices in I that is all-one vector. Then these m choices of I also correspond to the positions of all ones in a column of PA. This means that the columns of A and PA are the same up to permutations, which contradicts the assumption of our theorem. This finishes the proof of this claim.
Now define B1 as 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 I . Without loss of generality, suppose I = [m− 1], and suppose the first column of B1 is all-one vector. Let u = −e1 + ∑m i=2 ei ∈ Rm,
we know that Au = 2 ∑(m2 ) i=m e ′ i, i.e., the first (m− 1) entries of Au are 0, and the other entries are 2. Define v , 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. rank(C2) = m.
Proof of Claim 2. In this proof, we will consider each column of C2 as a 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 a simple undirected graph. Then we are going to show that we can select m “edges” from C2 which are linearly independent.
There are ( m 2 ) − (m − 1) edges in C2. From m > 6 we know that ( m 2 ) − (m − 1) > m 2
4 , so from Turán’s theorem, C2 contains at least one triangle. Assume this triangle is (i, j, k), then we select edges (i, j), (j, k) and (i, k) and define E3 = {i, j, k}. ∀r ∈ [m], r ≥ 3, we select an edge connecting Er with [m] \ Er. Assume that edge is (s, t) where s ∈ Er and t /∈ Er, we then add t to Er, i.e., Er+1 = Er ∪ {t}. In the next two paragraphs, we are going to show that there are always edges between Er and [m] \Er (so we can successfully select m edges in total), and the m edges we selected are linearly independent.
In matrix PA, there are r(m − r) edges between Er and [m] \ Er. Since C2 is constructed by deleting (m − 1) edges from PA, the number of edges left between Er and [m] \ Er is at least r(m− r)− (m− 1). When 3 ≤ r ≤ m− 2, we have r(m− r)− (m− 1) > 0. When r = m− 1, the only case where there is no edge between Er and [m] \Er is when all edges from vertex [m] \Er is in C1, which means that C1 has a column that is all-one vector and is a contradiction. Therefore, there are always edges between Er and [m] \ Er and we can successfully select m edges. Then we only need to show that these m selected edges are linearly independent. We use {ui}mi=1 to denote the vectors that correspond to these edges, i.e., u1 = ei+ ej , u2 = ej + ek, u3 = ei+ ek, · · · Assume by contradiction that they are linearly independent, then there exists x ∈ Rm, x 6= 0 such that ∑m i=1 x(i)ui = 0. By the selection process of the edges, we know that ∀r ≥ 4, ur has a unique direction, so x(r) = 0. Therefore, x(1)u1 + x(2)u2 + x(3)u3 = 0. Since {u1, u2, u3} are linearly independent, we have x = 0, which is a contradiction. Thus, these m selected edges are linearly independent, proving the claim.
Now assume by contradiction that v is in the column span of PA, then ∃w ∈ Rm such that v = PAw. Let v2 ∈ R( m 2 )−(m−1) be the bottom ( m 2 ) − (m− 1) entries of v, then v2 = C2w. Define w0 to be the all-one vector in Rm, we know that w0 is a valid solution to v2 = C2w. Since C2 has full column rank, w0 must be the unique solution to v2 = C2w. This implies that v = PAw0. However, we
know that PAw0 = 2 ∑(m2 ) i=1 e ′ i 6= v, which is a contradiction. Thus, v is not in the column span of A, which finishes the proof of the lemma.

heading: D ADDITIONAL EXPERIMENTS FOR SECTION 2
text: D.1 EXPERIMENTS FOR SECTION 2.3
As noted in the main paper, it is not difficult to extend Definition 2.6 to construct datasets on which Mixup training empirically fails for small values of α. The observation to make is that a major part of the proof of Theorem 2.7 is the fact that the same-point mixing probability of point 1 is small relative to the same-class mixing probability of class 0. As the former probability decreases quadratically with the dataset size m, we are motivated to consider extensions of X 23 consisting of more points and more classes. Towards that end, we consider the following generalization of X 23 : Definition D.1 (m-Point k-Class Alternating Line). We define X km to be the k-class classification dataset consisting of the points {0, 1, ...,m− 1} classified according to their value mod k incremented by 1. As before, PX is the normalized counting measure on X km.
We now consider training a two-layer feedforward network on X 210 and X 1010 using the same procedure and hyperparameters as in the main paper. The results are shown in Figure 8 below.
Here we see that even at α = 1, Mixup training fails to minimize the original empirical risk on X 210 and X 1010 , whereas in the main paper we noted that at α = 1 Mixup training had no issues minimizing the original risk on X 23 . Interestingly, we find that even standard training does not completely minimize the original empirical risk on X 210, once again perhaps a result of the regularity of the two-layer 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 we include the additional experiments mentioned in Section 2.4, namely the results of training ResNet-18 on MNIST, CIFAR-10, and CIFAR-100 with and without Mixup for α = 1, 32, and 128 (with the other hyperparameters being as described in Section 2.4). The results are shown in Figure 9.
As mentioned in the main body, these choices of α only lead to Mixup performing more similarly to ERM than α = 1024.

heading: E FULL PROOFS FOR SECTION 3
text: E.1 PROOF OF THEOREM 3.2
Theorem 3.2. Consider k-class classification where the supports X1, ..., Xk are finite and PX corresponds to the discrete uniform distribution. If a point x satisfies Assumption 3.1 with respect to a class i, then for every h ∈ argming∈C∗ Jmix(g,PX ,Pf ), we have that h classifies x as class i and that h is continuous at x.
Proof. For two points p, q in the supports X1, ..., Xk with a line segment between them intersecting x, let λ(p, q, x) denote the value of λ for which λp+ (1− λ)q = x. Since the supports are finite, we have that there exists 1 > 0 such that for all ≤ 1 we have that:
ξi,jx, = ∑ p ∑ q ∫ B (λ(p,q,x)) dPf
Where the summations are over all points p, q with line segments containing x. Now we have by the Lebesgue differentiation theorem applied to the integral term in the summations above (this
is possible because Pf has a density) that the following limit (as well as each limit for the other coordinate functions) exists:
lim →0 hi = lim →0
ξi,ix, + ∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ) ) ∑k q=1 ( ξq,qx, + ∑ j 6=q ( ξq,jx, ,λ + (ξ j,q x, − ξj,qx, ,λ)
)) = lim →0 1 ξ i,i x, + 1 ∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ) ) 1
∑k q=1 ( ξq,qx, + ∑ j 6=q ( ξq,jx, ,λ + (ξ j,q x, − ξj,qx, ,λ) )) Now by Assumption 3.1, we need only consider the ξi,ix, , ξ i,j x, , ξ i,j x, ,λ terms (as there are no other line segments that contain x). Furthermore, we have that there exists 2 > 0 such that for all ≤ 2 we have λ(p, q, x)− ≥ 12 for p ∈ Xi and q ∈ Xj , and that the measure of A i,j x, is at least that of A j,i x, . From this we get that for all ≤ min( 1, 2):
hi = ξi,ix, +
∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ) ) ξi,ix, + ∑ j 6=i ( ξi,jx, ,λ + ξ j,i x, ,λ + (ξ j,i x, − ξj,ix, ,λ) + (ξ i,j x, − ξi,jx, ,λ)
) ≥ ξi,ix, + ∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξ j,i x, ,λ)
) ξi,ix, + 2 ∑ j 6=i ( ξi,jx, ,λ + (ξ j,i x, − ξj,ix, ,λ) ) ≥ 1 2
Since the above also holds for a 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 a linear model θ>x on 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 n points in Rd distributed according to N (0, Id) with d > n (to be made more precise shortly). We let the labels of points in X be ±1 (so that the sign of θ>x is the classification), and use X1 and X−1 to denote the individual class points. Additionally, we let n1 = |X1| and n2 = |X−1|. 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 Jmix on Data Span] Suppose n1 = n2 = 1, i.e. there are two data points x, z with opposite labels. If x and z are linearly independent, then Jmix is strictly convex with respect to θ 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 sum over these cases. With this lemma, we may now prove Theorem 3.5. Before doing so, we point out that the version of Jmix considered here is after composition with the logistic loss (since we are considering binary classification with a linear classifier). Theorem 3.5. If the maximum margin solution forX is also an interpolating solution forX , then any θ that lies in the span of X and minimizes the Mixup loss Jmix for a symmetric mixing distribution Pf is a rescaling of the maximum margin solution.
Proof. Since d > n, we have that all of the points {xi}n1i=1, {zj} n2 j=1 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 Jmix (the terms corresponding to mixing points with themselves). Thus, in what follows, we disclude these ERM terms from Jmix to simplify the presentation.
Part I: n1 = n2 = 1. Denote θ>x1 = u and θ>z1 = −v, then
Jmix = Eλ [λ log(1 + exp(−λu+ (1− λ)v)) + (1− λ) log(1 + exp(λu− (1− λ)v))] . (2)
Where λ is distributed according to Pf which is symmetric and has full support on [0, 1]. Therefore, we can do the change of variables λ := 1− λ, and
Jmix = Eλ [λ log(1 + exp(−λv + (1− λ)u)) + (1− λ) log(1 + exp(λv − (1− λ)u))] . (3)
Combining Eq.(2) and Eq.(3), we know if (u,−v) is a global minimum of Jmix, then so is (v,−u). But the strict convexity in Lemma E.1 implies such a global minimum is unique, so we must have u = v = k(Pf ), where k(Pf ) is a constant that only depends on the density of Pf . Furthermore, ∀λ ∈ [0, 1], define
hλ(k) = λ log(1 + exp((1− 2λ)k)) + (1− λ) log(1 + exp((2λ− 1)k)), (4)
then ∀k > 0,
hλ(−k)− hλ(k) = (1− 2λ) log(1 + exp((1− 2λ)k)) + (2λ− 1) log(1 + exp((2λ− 1)k)) = (1− 2λ) log ( 1 + exp((1− 2λ)k) 1 + exp((2λ− 1)k) ) ≥ 0, (5)
and
h′λ(k)|k=0 = − 1
2 (1− 2λ)2 ≤ 0. (6)
Hence, we must have k(Pf ) > 0.
Part II: General n1 and n2. For the general case, we extend the observation we made prior to the proof of Part I. Namely, if we can show that an interpolating solution is optimal for mixing across the two classes, it follows immediately that the solution is optimal for all of Jmix (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 J i,jmix notation to indicate mixing of points xi and zj , so that we may write the loss in consideration as:
Jmix(θ) = 1
n1n2 n1∑ i=1 n2∑ j=1 J i,jmix(θ). (7)
By the proof in the previous part we know if J i,jmix is minimized, then we must have θ >xi = −θ>zj = k(Pf ) > 0. On the other hand, if J i,jmix(θ) are minimized simultaneously for all pairs (i, j), then clearly Jmix(θ) is also minimized. This is possible since the data points are linearly independent, so there exists θ ∈ Rd, such that
θ>xi = −θ>zj = k(Pf ) > 0 ∀i ∈ [n1], ∀j ∈ [n2]. (8)
Now we can conclude that any θ that minimizes the Mixup loss Jmix is an interpolating solution. Restricting θ to the span of X finishes the proof.
E.2.1 PROOF OF SUPPORTING LEMMA
Lemma E.1. [Strict Convexity of Jmix on Data Span] Suppose n1 = n2 = 1, i.e. there are two data points x, z with opposite labels. If x and z are linearly independent, then Jmix is strictly convex with respect to θ on the span of x and z.
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
f(λ) = λx+ (1− λ)z, (9)
then Jmix can be expressed as Jmix(θ) = Eλ [ λ log ( 1 + exp ( −θ>f(λ) )) + (1− λ) log ( 1 + exp { θ>f(λ) })] = Eλ [ log ( 1 + exp ( −θ>f(λ) )) + (1− λ)θ>f(λ) ] . (10)
Where again λ ∼ Pf . Note that the second term in Eq.(10) is linear in θ, hence the Hessian of Jmix can be written as
∇2Jmix(θ) = Eλ
[ exp ( −θ>f(λ) ) (1 + exp(−θ>f(λ)))2 f(λ)f(λ)> ] (11)
:= Eλg(λ).
Define B := Span{x, z}. To show Jmix is strictly convex on B, it suffices to show for every non-zero vector a ∈ B, we always have
a>∇2Jmix(θ)a > 0. (12)
Note that g(λ) is continuous w.r.t. λ and that Pf has full support on [0, 1], it suffices to show either
a>f(0)f(0)>a > 0 or a>f(1)f(1)>a > 0, (13)
which is equivalent to either
a>x 6= 0 or a>z 6= 0. (14)
This is obvious since a is a non-zero vector in B, and that x and z are linearly independent.

heading: F ADDITIONAL EXPERIMENTS FOR SECTION 3
text: In this section, we consider different class separations and choices of the mixing parameter α when training on the two moons dataset, with all other experimental settings being the same as in Section 3.1.
Upon decreasing the class separation to 0.1, we note that even standard training captures more of the nonlinear aspects of the data, as was observed in the prior work of Pezeshki et al. (2020).

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

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:  1. Constructing a dataset on which Mixup training fails to obtain the empirical risk minimization. 2. Providing sufficient conditions for minimizing the original risk and estimates of these sufficient condition measures on natural datasets. 3. An observation that the rate of empirical risk minimization using Mixup and a theorem about why this should happen. 4. A study on when the Mixup optimial classifier fails to generalize and a demonstration on a toy dataset. 5. An example for when Mixup training leads to the same classifier, obtained from standard training.  The main difference with related works is that the paper attempts to understand *why* Mixup works by studying *when* Mixup works with concrete examples.  

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.