$k$-Mixup Regularization for Deep Learning via Optimal Transport
Authors: Kristjan Greenewald
Anming Gu
Mikhail Yurochkin
Justin Solomon
Edward Chien
Venue: ICLR 2022 Submitted (2022)
Keywords: Neural networks
Classification
Data augmentation
Optimal Transport

Abstract: Mixup is a popular regularization technique for training deep neural networks that can improve generalization  and increase adversarial robustness. It perturbs input training data in the direction of other randomly-chosen instances in the training set. To better leverage the structure of the data, we extend mixup to $k$-mixup by perturbing $k$-batches of training points in the direction of other $k$-batches using displacement interpolation, i.e. interpolation under the Wasserstein metric. We demonstrate theoretically and in simulations that $k$-mixup preserves cluster and manifold structures, and we extend theory studying the efficacy of standard mixup to the $k$-mixup case. Our empirical results show that training with $k$-mixup further improves generalization and robustness across several network architectures and benchmark datasets of differing modalities.

Under review as a conference paper at ICLR 2022
- M-XUU REGULARIZATION FOR DEEP LEARNING VIA OPTIMAL TRANSPORT
Anonymous authors Paper under double-blind review
ABSTRACT
Mixup is a popular regularization technique for training deep neural networks that can improve generalization and increase adversarial robustness. It perturbs input training data in the direction of other randomly-chosee set. To better leverage the structure of the data, we extend mixup k-mixup by perturbing k--bacches of training points in the direction of other k-batches using displacement interpolation, i.e. interpolation under the Wasserstein metric. We demonstrate theoretically and in simulations that k-mixup preserves cluster and manifold structures, and we extend theory studying the efficacy of standard mixup to the k-mixup case. Our empirical results show that training with h-mixup further improves generalization and robustness across several network architectures and benchmark datasets of differing modalities.
instances in the training
Standard mixup Zhang et al. 2018 a data augmentation approach that trains models on weighted averages of random pairs of training points. Averaging weights typically drawn from beta distribution ((,, o),, with parameter a such that the generated training set is vicinal, i.e., it does not stray too far from the original dataset. Perturbations generated mixup may be in the direction of any other datapoint instead of being informed by local distributional structure. As shown in Figure [ this is key weakness of mixup that can lead poor regularization when distributions are clustered or supported on an embedded manifold. With larger a. the procedure can result in averaged training points with incorrect labels in other clusters or in locations that stray far from the data manifold.
mixup
(1-mmixup
4-mixup
32.mixup
Figure 1: We train fully-com culle-coneected network three synthetic datasets for binary classification, with 1-mixup through 32-mixup regularization (a = 1). The plotted functions show the network output and demonstrate that higher k-mixup better captures local structure (visible through less blur, increased contrast) while retaining reasonable, even smoothing between the classes.
To address these issues, we present k-mixup, which averages random pairs sets samples from the training dataset. This averaging is done using optimal transport, with displacement interpolation. The sets of k samples are viewed as discrete distributions and are averaged as distributions in geometric sense. If 1 1, we recover standard mixup regularization. Figures and iillustrate how k-mixup produces perturbed training datasets that better match the global cluster or manifold support structure of the original training dataset. Note that the constraints of optimal transport are crucial,
NEW

---

Under review as a conference paper at ICLR 2022
as for instance nearest-neighbor approach would avoid the cross-cluster matches necessary for smoothing. In Section 4 we provide empirical results that justify the above intuition.
Our contributions are as follows.
Empirical results:
We show improved generalization results on standard benchmark datasets showing k-mixup with k >> 1 often improves on standard mixup and at worst does no harm
We show that k-mixup further improves robustness adversarial attacks.
Theoretical characterizations that speak to the claims above in a more precise manner:
We argue that as & increases, one is more and more likely to remain within the data manifold (Section 2.1).
In the clustered setting, we provide an argument that shows intercluster regularization interpolates nearest points and better smooths interpolation of labels (Section (2.2).
We extend the theoretical analysis of Zhang al. (2020) and Carratino et al. (020)) our
k-mixup setting, showing that it leverages local training distribution structure to make more informed regularizations (Section 3)
Related works. We tackle issues noted in the papers adaptive mixup (Guo al. 2019) and manifold mixup (Verma et al.] 2018). The first refers to the problem as "manifold intrusion" and seeks to fix it by training datapoint-specific weights a and considering convex combinations of more than 2 points. This requires additional networks to detect the data manifold and to assign weight combinations, adding substantial complexity to their approach. Manifold mixup deals with the problem by relying on the network to parametrize the data manifold, interpolating in hidden layers of the network. We show in Section 4 that k-mixup can be performed in hidden layers to boost performance of manifold mixup. A related approach is that of GAN-mixup (Sohn et al.) (020a) which trains conditional GAN and uses to generate data points between different data manifolds. As with the other approaches above, the need for training of an additional GAN results in far greater complexity than our k-mixup method.
NEW
PuzzleMix (Kim et al. 2020) also combines optimal transport ideas with mixup, extending CutMix (Yun et al. 2019) to combine pairs images. PuzzleMix uses transport to shift saliency regions of images, producing meaningful combinations of input training data. Their use of OT is fundamentally different from ours and does not generalize to non-image data. A recent follow-on work CoMix (Kim) al. 2021 ,, considers similar approach based sub/supermodular optimization.
Performing optimal transport between empirical samples of distributions has been considered in
NEW
studies of the sample complexity of Wasserstein distance (e.g- Weed & Bach (2019)). Ours is the first application where the underlying source and target distribution are the same, and a theoretical investigation of the generalized notion of k-variance is in [Solomon al. (2000). In other works, transport between empirical samples has been dubbed minibatch optimal transport and has been used in generative models (Genevay et al. 2018 Fatras et al., (220)) and domain adaptation (Damodaran
et al. 2018 Fatras et al. 2021).
GENERALIZING MIXUP
Standard mixup. Mixup uses a training dataset of feature- pairs {(r,, y/) M the target yi is a one-hot vector for classification. Weighted averages of training points construct vicinal dataset:
( v == (Az; + (1 A)zy, Ays + (1 A)1;).
X is sampled from beta distribution, ,(a, a), with parameter > 0 usually small so that the averages are near an endpoint. Using this vicinal dataset, empirical risk minimization (ERM) becomes:
Emir (f) = BiJ.A [E (# [G)] i,j ~ M(j_u(1.....) N), A
a),
(1)
where / is proposed feature-target map and é is loss function. Effectively, one trains on datasets formed by averaging random pairs of training points. As the training points are randomly selected,
Where a is optimized for both methods.
2

---

Under review as a conference paper at ICLR 2022
this construction makes it likely that the vicinal datapoints may not reflect the local structure of the dataset, as in the clustered or manifold-supee setting.
m-mixup. To generalize mixup, sample two random subsets of l: training points {(0? M }
and {( ) For compactness, let x² := {=?]== and y² := {u? Jx-1 denote the feature and target sets (and likewise for {). A weighted average of these subsets is formed with displacement interpolation and used as a vicinal training set. This concept is from optimal transport (see, e.g., (Santambrogio) 2015) and considers (t) and (xr, yy) as uniform discrete distributions ji", juf over their support. In this setting, the optimal transport problem becomes linear assignment problem (Peyré & Cuturi 2019). The optimal map is described by permutation Sy minimizing the cost:
W2 AA)
1 K
E ||
Here, can be found efficiently using the Hungarian algorithm (Bertsimas & Tsitsiklis 1997p. Figure 2 gives intuition for this identification. When compared to the random matching used by standard mixup, pairing is more likely match nearby points and make matchings that better respect local structure-especially by having cross-cluster matches between nearby points on the two clusters.
h: = 1: (1-)mixup
k = 32: k-mixup
Figure 2: Optimal transport couplings and vicinal datasets for A: (left) and A: = 32 (right) in 3 simple datasets. In the bottom row, a was used to generate vicinal datasets of size 512. Given permutation and weight A, the displacement interpolation between (x",3")) and (r5 vf) is:
DIx(<> V) (2 v) = Aax7 vi) + (1 A) (1) s 1=1"
As in standard mixup, we draw X ~ B(a, a). For the loss function, we consider all random samples, i.e. [[(=7, 27) (N).
(N) subsets
Ek
emix (f) E.,. [C[(DI wf),, DTA )f 7.8 ~ T.E=U(,....W),... ((a,
The localized nature of the matchings makes it more likely that the averaged labels will smoothly interpolate over the decision boundaries. A consequence is that k-mixup is robust to higher values of a, since it is no longer necessary to keep À close to 0 or to avoid erroneous labels. This can be seen in our empirical results in Section and theoretical analysis appears in Section
Pseudocode and Computational Complexity We would like to emphasize the speed and simplicity of our method (cspecially relative to other mixup variants). We have included a brief Py PyTch pseudocode in supplement Section[A] and note that with CIFAR-10 and k 32 the use of k-mixup added 8-9 seconds per epoch. Also in that section a more extended analysis of computational cost, showing that there is little computational downside to generalizing 1-mixup to 1--miuu.
NEW
2 MANIFOLD AND CLUSTER STRUCTURE PRESERVATION
The use of an optimal coupling for producing vicinal data points makes it likely that vicinal datapoints reflect the local structure of the dataset. Below we argue that as increases, the vicinal couplings will preserve manifold support, preserve cluster structure, and interpolate labels between clusters.
3

---

Under review as a conference paper at ICLR 2022
2.1 MANIFOLD SUPPORT
Suppose our training data is drawn from a distribution on a d-dimensional embedded submanifold S in X' y C. RR,, where X and Y denote feature and target spaces. We define an injectivity radius: Definition (Injectivity radius). Let (S) = ty X x y d(p. S) <e denote the e-neighborhood S S where d(p, S) is the Euclidean distance from to S. Define the injectivity radius Rs of S to be the infimum of the e's for which (S) is not homotopy equivalent to S.
As S is embedded, (S) is homotopy equivalent to S for small enough e, Rs O. Essentially, Definition I grross an e neighhorhood until the boundary intersects itself. We have the following:
Proposition 1. For training distribution μ supported on an embedded submanifold S with injectivity radius Rg, with high probability any constant fraction 1 - ô (for any fixed 0 E (0, 1) of the couplings induced by k-mixup will remain within (S) for h large enough.
The proof of this proposition is in supplement Section Hence, for large enough k, the interpolation induced by optimal transport will approximately preserve the manifold support structure. While the theory requires low dimension d and high k to achieve a tight bound, our empirical evaluations show good performance in the small-k regime. Some schematic examples are shown in Figures I and 2
2.2 CLUSTERED DISTRIBUTIONS
With clustered training distribution we preserve global structure in two ways: by mostly match- ing points within clusters and by matching (approximately) nearest points across clusters. These characterizations are only true approximately, but are achieved exactly as l + co, argued below.
To refine the definition of a clustered distribution, we adopt the (m, A)-clutterable definition used in Weed & Bach (2019; Solomon al. (2020). In particular, a distribution yı is (m, A--clusterable supp(μu) lies in the union of m balls of radius at most A. Now, our training samples (I;, Vi) are sampled from such distribution, where the clusters are sufficiently separated, then intracluster matchings will be prioritized over cross-cluster matchings under optimal transport.
Lemma 1. Draw two batches of samples {p. V and { from a (m, A) A--ccssterable distribution, where the distance between any pair of covering balls least 2A. If and st denote the number of samples in cluster in batch I and 2, respectively, then the optimal transport matching will have Errr 8s] cross-cluster matchings.
The proof of the above (supplement Section C) involves the pigeonhole principle and basic geometry. We also argue that the fraction of cross-cluster identifications approaches zero as k + so and characterize the rate of decrease. The proof (supplement Section D follows via Jensen's inequality:
Theorem 1. Given the setting of Lemma [ with probability masses Pi...,, Pmo and two batches of size k matched with optimal transport, the expected fraction of cross-cluster identifications is O ((2k) 1/2 Σmhh VDi(1 p.)).
NEW
Note that the absolute number of cross-cluster matches still increases k: increases providing more information in the voids between clusters. We emphasize that the (m, A) assumption is designed to create "worst-case scenario" ie. setting where clusters are well-separated such that cross- cluster identifications are as unlikely as possible. Hence in real datasets the fraction of cross-cluster identifications will be larger than indicated in Theorem [] Finally, we show that these cross-cluster matches are of length close to the distance between the clusters with high probability (proved in supplement Section D i.e., the endpoints of the match lie the parts of each cluster closest to the other cluster. This rests upon the fact that we are considering the W2 cost, for which small improvements to long distance matchings yield large cost reductions in squared Euclidean distance.
NEW
Theorem 2. Suppose density p has support on disjoint compact sets (clusters) A, B whose boundaries are smooth, where p > O throughout A and B. Let D be the Euclidean distance between A and B, and let R,, Rg be the radii of A, B respectively. Define A, to be the subset of set A that is less than D(1 + E) distance from B. and define B. similarly. Consider two batches of size k drawn from p and matched with optimal transport. Then, for k large enough, with high probability all cross-cluster
matches will have an endpoint each in A and B,, where max(RA.
4

---

Under review as a conference paper at ICLR 2022
Theorem 2 implies for large k that the vicinal distribution created by sampling along the cross-cluster matches will almost entirely lie in the voids between the clusters. If the clusters correspond to different classes, this will directly encourage the learned model to smoothly interpolate between the class labels as one transitions across the void between clusters. This is in contrast to the randomized matches of 1-mixup, which create vicinal distributions that can span a line crossing any part of the space without regard for intervening clusters. The behavior noted by Theorems [] and 2 are visualized in Figures and showing that k-mixup provides smooth interpolation between clusters, and strengthens label preservation within clusters.
3 REGULARIZZTTON EXPANSIONS
Two recent works analyze the efficacy of 1-mixup perturbatively (Zhang et al.) 2020 Carratino al. 2020p. Both consider quadratic Taylor series expansions about the training set or a simple transformation of it, and they characterize the regularization terms that arise in terms of label and Lipschitz smoothing. We adapt these expansions k-mixup and show that the resulting regularization is more locally informed via the optimal transport coupling.
In both works, perturbations are sampled from a globally informed distribution, based upon all other samples in the training distribution. In k-mixup, these distributions are defined by the optimal transport couplings. Given a training point zi, we consider all k-samplings 7 that might contain it, and all possible k-samplings & that it may couple to. A locally-informed distribution is the following:
D. I
where σng denotes the optimal coupling between k- k-samplings y and &. This distribution will be more heavily weighted points that is often matched with. We use "locally-infomme upweighting of points closer to the point of interest that are likely to be matched to it by k-mixup.
in this sense of
Zhang et al. (0200) expand about the features in the training dataset Dx (x1,.... .......... J. and the perturbations in the regularization terms are sampled from D. We generalize their characterization to k-mixup, with D replaced by D. We assume loss of the form {(f y) h(f(z)) y f(z) for some twice differentiable and f- This broad class of losses includes the cross-entropy for neural networks and all losses arising from Generalized Linear Models.
Theorem 3. Assuming loss e as above, the k-mixup loss can be written as:
Em (f) = Esttd -,- R3 + Bx-s(a+Laj((11 (1-))) 2)
where lim 6(a)= 0, Eatd denotes the standard ERM loss, and the three R2 regularization terms are:
R1 Ex-p(a+1.o) A1
Σn (k(((zz)) v.) v.) E,wD, xx,]
E Am [[1
2
R2
["(((z;)) EAND [(r - 2;)(r - x;) vv)())((
2n
R3
E BA-
2)21
Σx (M(((((()))))
Σ 1=1
vz) -,), -()))(=
2n
proof is given in Section of the supplement and follows from some algebraic rearrangement and Taylor expansion in terms of X. The higher-order terms are captured by Exw A) - A)]. gotd represents the constant term in this expansion, while the regularization terms R. represent the linear and quadratic terms. These effectively regularize V ff(:)) and f²f(x;) with respect to local perturbations
x; sampled from D., ensuring that our regularizations are locally- informed. In other words, the regularization terms vary over the support of the dataset, at each point penalizing the characteristics of the locally-ifforme This allows the regularization to adapt better to local data (e.g. manifold) structure. For example, R2 and R3 penalize having large gradients and Hessian respectively along the directions of significant variance of the distribution D. of points I3 is likely be matched to. When as k 1, this D, will
NEW
distribution rather than a global distribution.
5

---

Under review as a conference paper at ICLR 2022
not be locally informed, and will instead effectively be a global variance measure. As k increases, the Dj will instead be dominated by matches to nearby clusters, better capturing the smoothing needs in the immediate vicinity of z,, Notably, the expansion is in the feature space alone, yielding theoretical results in the case of 1-mixup on generalization and adversarial robustness.
An alternate approach by Carratino et al. (2020) characterizes mixup as combination of reversion to mean followed by random perturbation. In supplement Section G k-mixup via a locally-informed mean and covariance.
we generalize their result to
EMPIRICAL RESULTS
We empirically test the efficacy of k-mixup with toy datasets, UCI datasets, image, and speech datasets employing variety of neural network architectures. Across these experiments we find that k-mixup for k > 1 tends to improve upon (1-)mixup for fixed a, and if not remains comparable. Additional experiments with CIFAR-10 10 compare k-mixup with manifold mixup, explore the combination of the two methods, and demonstrate improvements in adversarial robustness from k-mixup. Experiments were performed in various laptop, cluster, and cloud environments using PyTorch. Unless otherwise stated, a standard SGD optimizer was used, with learning rate 0.1 decreased at epochs 100 and 1 150, momentum 0.9, and weight decay 10-1
Toy datasets. Results for the toy datasets of Figures] 1 and 2 (denoted "One Ring." "Four Bars," and "Swiss Roll") are shown in Figure R We used fully-connected 3-layer neural network (130 and 120 hidden units). As the datasets are very clustered and have no noise, smoothing is not needed for generalization and performance without mixup typically 100%. Applying mixup to these datasets thus provides view to the propensity of each variant to oversmooth, damaging performance. For each dataset and each a; higher k- m-mixup outperforms (1-)mixup. For larger a, the performance gap between the baseline (1-)mixup and k >> 1 mixup becomes quite significant, reaching 8%, 50%, and 40% respectively for = 16 and a = 64. These results quantitatively confirm the intuition built in Figures and]] 2 that --mixup regularization more effectively preserves these structures in data,
NEW
limiting losses from oversmoothing.
o
16
a 64
25
0
16
64
.25
64
1
94.487
90,930
86.527
86.467
86.899
100
100
100
50.110
50.017
99.708
99.670
67.942
61.633
59.573
2
95.230
93.197
50.653
90.043
90.027
100
100
100
60.725
50.107
99.653
99.667
81.696
69.327
64.397
4
96.190
91.
92.633
92. 191
91. 807
100
97.477
99.703
99.717
99.721
50.064
73.773
96.547
93.714
94.377
807
93.463
100
920
99.853
5990093
99..09
99 69.64661
99.710
98.897
16
96.717
95.961
98.097 95.017
95.193
100
100
100
99.997
99.987
99.760
99.707
99.692
99,787
99.761
(a) One Ring
(b) Four Bars
(c) Swiss Roll
Figure 3: Test accuracy on toy datasets, averaged over 5 Monte Carlo trials.
UCI datasets. Scaling up from the toy datasets, we tried k-mixup on UCI datasets (Dua & Graff 2017) of varying size and dimension: Iris (150 instances, dim. 4), Breast Cancer Wisconsin- Diagnostic (569 instances, dim. 30), Abalone (4177 instances, dim. 8), Arrhythmia (452 instances, dim. 279), HTRU2 (17898 instances, dim. 9), and Phishing (1 1055 instances, dim. 30). For Iris, we used a 3-layer network with 120 and 84 hidden units; for Breast Cancer, Abalone, and Phishing, we used a 4-layer network with 120, 120, and 84 hidden units; for Arrhythmia we used 5-layer network with 120, 120, 36, and 84 hidden units; and lastly, for HTRU2, we used a 5 layer network with 120, 120, 84, 132 hidden units. Each entry is averaged over 20 Monte Carlo trials. Test classification performance is shown in Figure 4 k-mixup improves over (1-)mixup in each case, although for Arrhythmia no mixup outperforms both, and for Phishing, no mixup statistically matches the performance of k-mixup. In these small datasets, the best (or at least good) performance seems to be achieved with relatively small a = 0.1 and moderate l (4 or 8).
Data Set
None
2
=
16
A:
1
1
Abalome
27.68
28.00
27.99
28.12
27.93
27.75
27.50
27.51
27.43
28,59
28.12
27.08
27.47
27.38
27.66
27.93
Anhythmia
57.07
52.12
56.41
53.86
54.73
34.73
33.04
55.16
52.12
35.11
$4.40
55.05
53.37
53.70
54,46
56.38
Cancer
92.81
92.10
92.91
93.79
91.95
91.99
91.76
90.82
89.96
89.26
87.70
91.72
92.27
92.32
91.58
91.10
HTRU2
97.50
97.47
97.65
97.52
97.49
97.37
97.51
97.42
97.32
97.42
97.51
97.42
Tris
95.9
96.2
94.8
96.4
96.9
96.5
91.9
92
88.8
89.
86
87.4
81
79.5
77.1
76.6
Phishing
96.57
96.26
96.39
96.44
96.56
96.30
95.89
95.89
95.99
96.01
96.33
94.73
95.06
94.90
95.56
96.00
(x)
0.1
a
(c)
10.0
Figure 4: Test accuracy on UCI datasets using fully connected networks.

---

Under review as a conference paper at ICLR 2022
.06
-5
OX 10
= TO0
A
o= .06
mm
0
100
1
99.09
99.09
99.05
99.03
98.98
98.79
98.64
0.068
0.148
0.239
0.436
0.617
1.347
1.732
99.11
99.12
99.07
99.02
98.99
98.88
98.25
0.070
0.129
0.214
0.388
0.586
1.238
1.585
99.13
99.11
99.05
99,06
99.04
96.91
98.85
0.049
0.111
0.191
0.358
0.542
1,078
1.399
8
99.12
99.12
99.09
99.06
99.01
99.00
98.99
88
0.037
0.092
0.149
0.305
0.449
0.930
1,191
16
99.18
99.13
99.14
59,08
99.09
99.08
99.12
16
0.035
0.070
0.122
0.241
0.341
0.719
0.938
32
99.18
99.15
99.17
99.
10
99.11
99.16
99.18
32
0.029
0.039
0.076
0.152
0.221
0.456
0.586
(a) Performance (test accuracy)
(h) Average squared distance of vicinal distribution from training set
Figure 5: Results for MNIST with LeNet architecture (no mixup performance: 99.0%), averaged
over 20 Monte Carlo trials (#.002 confidence on test performance). Note that k-mixup doubles the
improvement of 1-mixup over ERM.
05
.1.100 0==
55
0=1
10
100
k
05
a= 1
a=
a=
0=
10
100
94.785
95.025
95.27
95.645
95.63
94.82
94.085
29.5
58.2
107.1
198.1
280.3
624.1
803.1
94.8
94,92
95,285
95.645
95.79
95.105
94.14
27.0
54.0
192.6
276.8
564,9
721.2
94.76
94.99
95.3
95.65
95.745
95.205
94.315
22.3
58.6
87.3
163.0
240.6
494.3
657.6
8
94.79
94,925
95.255
95.625
95.815
95,285
94.61
8
24.1
43.1
78.4
141.7
199.5
431.3
$54.8
94.68
94.98
95.215
95.595
95.735
95.33
94.92
16
16.8
32.6
70.7
114.3
186.6
365.2
468.7
32
94.74
94.905
95.11
9554465
695675
95.375
95.165
32
14.9
28.4
50.4
96.9
142.4
288.6
371.7
(a) Performance (test accuracy)
(b) Average squared distance of vicinal distribution from training set.
Figure 6: Results for CIFAR-10 with Resnet 8 architecture (no mixup performance: 94.4%), averaged over 20 Monte Carlo trials (+.03 confidence on test performance). Difference between best k-mixup and best 1-mixup is 0. 0.17% for fixed high a (a = 100), the improvement increases to 1.2%.
Image datasets. Results for MNIST (LeCun & Cortes 2010) using a convolutional neural network, i.., LeNet modified slightly to accommodate grayscale images, are in Figure [ with a joint sweep over k and a. Each table entry is averaged over 20 Monte Carlo trials. For each generated point in the vicinal distribution, we compute its closest squared distance to the matched pair from which it was generated. The results are averaged over the vicinal dataset and reported in part (b) of the figure. It shows that k-mixup yields significantly closer matches as k increases, causing the generated vicinal distribution to deviate less (in terms of squared distance) from the original training set. This is empirical evidence of our method respecting manifold support and cluster structure, as noted in Section 2 In spite of this lower variation, for each a the best generalization performance is for some k >>> 1, with a = 100 yielding 98% accuracy for k = 32 compared to 98.64% accuracy for k = 1. Generally, for fixed a, increasing & improves performance for this dataset.
Figure O analogous results for CIFAR- 10, using the PreAct R8snet-18 architecture as in Zhang et al.) (2018). Again k-mixup succeeds in finding matches that lie signifi- cantly closer together as k increases. For each a except the small = .1, the best generalization performance is still for some k > 1, with a = 100 yielding 95.16%%6.6 accu- racy for k= = 32 compared to 94.085% accuracy for A = 1. The best performance overall is achieved at & = 8 with parameter = 1. While the best k- k-mixup performance exceeds that of the best 1-mixup by only 0.17%, recall that in this setting 1-mixup outperforms ERM by 1.4% (Zhang let al., 2018). so when combined with the low overall error rate, small gains are not surprising. Tables of results for DenseNet and WideResnet architectures can be found in Figure 9 with the best m-mixup outperforming the best 1 1-mixup by 0.44% and 0.28% respectively. Note that in the case of Densenet, &- = 16 outperforms or (statistically) matches k- = 1 for all values of a.
k
a=
1
a=
2
a=
5
0
1
0 10
1
76.54
77.22
77.88
77.76
74.88
2
76.54
77.38
78.19
78.41
76.09
4
76.55
77.36
77.94
78.25
76.51
8
76.51
77.18
77.82
78.03
76.69
16
76.43
77.08
11.37
77.87
76.86
32
76.29
76.93
77.51
77.54
76.90
CIFAR-100
performance (= 0b connicance
k
o==1
2
a=
10
1
97.13
97.12
97.14
97.17
96.76
2
97.16
97.14
97.19
97.29
96.81
4
97.11
97.13
97.16
97.24
96.87
8
97.16
97.11
97.14
97.23
96.94
16
97.09
97.11
97.08
97.16
96.93
32
97.16
97.10
97.05
97.08
96.94
(b)
SVHN performance (4.02 confidence)
Figure 8: Test accuracy on CIFAR-100 and SVHN, averaged over 20 Monte Carlo trials (+.03 confidence).
For both MNIST and CIFAR-10 datasets, with coupling distances reported, one could compare settings with similar average squared distances. For example, a close inspection of Figures [ and ssow that higher & again tends to have the advantage, indicating that performance gains are not simply due to having a closer vicinal distribution.
NEW
Additionally, we show training curves (performance as a function of epoch) for Resnet-18 18 on CIFAR- 10 in Figure 7. averaged over 20 random trials. The training speed (test accuracy in terms of epoch) for 1-mixup and 32-mixup shows no loss of convergence speed with A = 32 mixup, with (if anything) k 32 showing slight edge. The discontinuity epoch 100 is due to our reduction of the learning
7

---

Under review as a conference paper at ICLR 2022
70-
90-
Commect claolfiactonn
70
89-
600
50
20-
8
50
100
150
250
5
50
100
150
20n
50
150
150
200
50 100
150
250
Esech
Escch
Eooch
Epach
(a) Test acc.,
1.
(b) Train acc., a
1.
(c) Test acc.,
10.
(d) Train acc.,
10.
Figure 7: Training convergence of i: = 1 and k = 32 mixup on CIFAR-10, averaged over 20 random trials. Note that both train at roughly the same rate (k 32 slightly faster), the train accuracy discrepancy is due to the more class-accurate vicinal training distribution created by higher k-mixup.
A
<
5
0
88.46
88.47
88,38
88.22
87.75
87.01
96.71
96.58
88.64
88.53
88.73
88.59
88.41
87.84
16
96.62
97.02
97.15
97.08
16
88.47
88.41
88.75
88.06
88.02
88.20
(a) DenseNet-BC BC-190 architecture
(b) WideResnet 101 architecture
(#:03 confidence, no mixup performance: 96.3%)
(d:009 confidence, no mixup performance: 88.4%)
Figure 9: CIFAR-10 test accuracy for DenseNet-BC-190 and WideResnet-101 architectures. For DenseNet, the difference between best k-mixup and best I-mixup is 0.44%, for fixed high a (a = 4), the improvement increases 0.65%. For WideResnet, the difference between best k-mixup and best 1-mixu is 0.28%, for fixed high a (a- = 4), the improvement increases to 1.25%.
rate at epochs 100 and 150 to aid convergence (used throughout our image experiments). The train accuracy shows similar convergence profile between 1- and 32-mixup; the difference in absolute accuracy here (and the reason it is less than the test accuracy) is because the training distribution is the mixup-modifeed because the induced vicinal distribution and labels are more consistent with the true distribution, due to the better matches from optimal transport. The large improvement in train accuracy is remarkable given the high dimension of the CIFAR-10 data space, since it indicates that A = 32 mixup is able to find significantly more consistent matches than k = mixup.
vicinal distribution. The curve for &- = 32 is higher, especially for a = 10,
Figure 8 shows results for CIFAR-100 and SVHN, with a Resnet-18 18 architecture. As before, for fixed a, the best performance is achieved for some k > 1. The improvement of the best k-mixup over the best 1-mixup 0.53% for CIFAR-100 and 0.12% for SVHN. For fixed high a 10, the k-mixup improvement over 1- 1-mixup rises to 2.02% for CIFAR- 100, possibly indicating that the OT matches yield better interpolation between classes, aiding generalization.
Speech dataset. Performance is tested on speech dataset: Google Speech Commands (Warden 2018) using LeNet architecture are in Figure 10 Each table entry is averaged over 20 Monte Carlo trials (+-011 confidence on test per- formance). We augmented the data in the same way Zhang et al. (2018). The difference between best k-mixup and best 1-mixup 0.4%.
a =
a
2
2
a 10
89.05
89.03
89.42
88.28
2
89.17
89.12
89.40
89.43
88.67
1
89.07
89.06
89.82
89.61
89.13
88.98
89.05
89.73
89.50
16
88.97
88.96
89.55
89.68
89.74
Figure 10: Google Speech Commands test accuracy using LeNet architecture, averaged over 20 Monte Carlo trials (Verma et al. 2018), which helps in settings like those (t.014 confidence).
Manifold mixup. We compare to Manifold Mixup
in Figure 1 by making interpolations more meaningful. It performs mixup at random layers (random per minibatch), not only in the input space. This extends "manifold k-mixup:" k-mixup in the hidden layers as well as the input layers. We use settings in Verma et al. (2018), i.e., for PreAct Resnet18, the mixup layer is randomized (coin flip) between the input space and the output of the first residual block F
Results for CIFAR-10 with Resnet18 architecture are in Figure II Numbers in this experiment are averaged over 20 Monte Carlo trials (#.03 confidence on test performance). While manifold 1-mixup outperforms the standard 1-mixup from Figure 6 it is matched by manifold k-mixups with 4 and outperformed by standard k-mixup (Figure h- = 8). We also tried randomizing over (a) the
"See https://ggiie con/vi kaaverma 077 / fold mi xup
8

---

Under review as a conference paper at ICLR 2022
outputs of all residual blocks and (b) the outputs of (lower-dimensional) deep residual blocks only, but found that performance of both 1-mixup and k-mixup degrades in these cases. This underscores that mixup in hidden layer manifolds is not guaranteed to be effective and can require tuning.
.2
10
95.00
95.27
95.59
95.74
95
Adversarial robustness. Figure T2 shows results white-box adversarial attacks generated by the FGSM method (implementation of Kim (220 3 for various val- ues of maximum adversarial perturbation. As in Verma al. (2018). J we used FGSM over PGD, since the iterative PGD attacks are significantly more effective, making any performance improvements seem less relevant practice. Additionally, we expect simple gradient attacks to be par- ticularly meaningful for evaluating the success of mixup, whose goal is to approximately linearly interpolate between classes. We show CIFAR-IO accuracy on white-box FGSM adversarial data (10000 points), where the maximum adversarial perturbation is set to c/255; performance is averaged over 30 Monte Carlo trials (+0.66 confidence). All performances are without adversarial training. Note that h = 2 outperforms & = 1 uniformly by as much as 8.64%, and the k mixups all outperform & = mixup on larger attacks. Similar results for MNIST are in Figure| 12 b), with the FGSM attacks being somewhat less effective. Here k = 8 is best for smaller attacks, and k is best for larger attacks.
2
94,91
95.22
95.56
95.69
95.29
94.99
95.22
95.55
95.75
94.98
8
94.92
95.22
95.58
95.72
95.39
16
94.86
93.18
95.38
95.69
95.47
32
94.86
95.09
95.42
95.53
95.46
Figure 11: Manifold mixup test accuracy on (IFAR-10 using Resnet18 architec- ture, averaged over 20 Monte Carlo trials (+.03 confidence).
NEW
The improved robustness shown by k-mixup speaks to a key goal of mixup, that of smoothing the predictions in the parts of the data space where no/few labels are available. This smoothness should make adversarial attacks require greater magnitude to successfully "break" the model.
===J
5
==
E
2
4
8=
E = 16
1: <==5
6=1
=
6
=
=
10
72.07
66.02
59.72
4861
23.71
98.26
97.36
96.03
92.97
86.89
77.14
79.48
74.22
70.18
66.58
57.25
26.23
98.32
97.45
96.15
93.16
87.34
78.24
4
78.82
72.71
67.82
63.60
54.80
27.32
4. 98.30
97.30
95.81
92.34
84.89
72.48
8
78.00
70.45
64.224
59.01
50.32
26.24
8 98.36
97.46
95.96
92.33
83.70
69.33
[a) CIFAR-
10 confidence)
(b) MNIST
(2:0.1
confidence)
Figure 12: Adversarial robustness: accuracy on white-box FGSM adversarial attacks.
CONCLUSIONS AND FUTURE WORK
The experiments above demonstrate that k-mixup often improves the generalization and robustness gains achieved by (1- (1-)mixup, and at least does no harm. This is seen across a diverse range of datasets and network architectures. It is simple to implement, adds little computational overhead to conventional (1-)mixup training, and may also be combined with related mixup variants. As k increases, the regularization induced more accurately reflects the local structure of the training data, especially in the manifold support and clustered settings, seen in Sections 2ndd 3 Empirical results show that performance is robust to variations in k, ensuring that extensive tuning is not required.
Our experiments show the greatest improvement from using k-mixup on low-dimensional datasets, while the improvement on high-dimensional datasets remains positive but is smaller (recall that classic mixup also has somewhat small gains over mixup in these settings). This difference could be due to the diminishing value of Euclidean distance for characterizing dataset geometry in high dimensions (Aggarwal al., 200T), but intriguingly this effect was not remedied by doing OT in the possibly dimensiiaai manifolds created by the higher layers in our manifold mixup experiments. To remedy this issue, in future work we will consider alternative metric learning strategies, with the goal of identifying effective high-dimension
metrics for displacement interpolation of data points.
Mixup has been incorporated into a broad range of learning applications, many of which we have not empirically investigated here. The original work demonstrated robustness to label corruption and improved GAN training stability, which could easily benefit from k-mixup as well. Additionally, mixup has been used for augmentation in semi-supervised learning (Berthelot et al., 2019 Sohn ct al. 2020b). Given its simplicity, a k-mixup augmentation may be able to generate more informed shifts of labelled and unlabelled training points. This same philosophy applies to recent method for generalizing fair classifiers (Chuang & Mrouch 202T), which already leverages manifold mixup.
Software has MIT License

---

Under review as a conference paper at ICLR 2022
Ethics Statement The k- k-mixup regularization procedure we propose and our experimentation it do not bring up additional ethical concerns outside of general concerns associated with machine learning field, and the of neural network models. Standard benchmark datasets and tasks were used, with the assumption that dataset originators have done their due diligence with respect to concerns IRBs, privacy, faimess, and the like.
Reproducibility Statement With regards to reproducibility, we note that k-mixup is exceedingly simple, and may be easily incorporated into almost any neural network as data perturbation step. For our experiments, publicly available benchmark datasets have been used and are clearly stated in Section 4 Additionally, the models used and the relevant training parameters are described for each task considered. Upon acceptance, we would be glad to make full implementation of our experiments available on Github under an open source MIT license. Lastly, for theoretical results, full proofs of our statements are provided in the appendices following the references.
REFERENCES
Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. On the surprising behavior of distance metrics in high dimensional space. In International conference on database theory, pp. 420-434.
Springer, 2001.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel MixMatch: A Holistic Approach to Seni-Supervised Learning. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d texquutessinge Alché-Buc, F. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: / http:///coccceeeeeeeeeeeeeecescs hnw.eeeeeddinnn..nnnesseeeseeeee cc cc/ppaper//119//1eee.. lcd138d049 4bw.aao4446770eeeeeeeee---0----- http:/sssswssssseeeeeee////////e
Dimitris Bertsimas and John Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1st edition, 1997. ISBN 1886529191.
Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On Mixup Regulariza- tion. arXiv:2006.0000 06049 [cs, stat], June 2020. UBLL/ttee//aaxxvv..rrr/aa////000 06049 arXiv: 2006.06049.
Ching- Yao Chuang and Youssef Mrouch. Fair mixup: Fairness via interpolation. In International Conference Learning Representations, 2021.
id Cd=DN15s5BXe5
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Computer Vision - -ECCV 2018, pp. 467-483, Cham, 2018. Springer International Publishing. ISBN 978-3-030- 01225-0.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
Kilian Fatras, Younes Zine, Rémi Flamary, Remi Gribonval, and Nicolas Courty. Learning with mini- batch Wasserstein: asymptotic and gradient properties. In Proceedings of the Twenty Third Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2131-2141. PMLR, June 2020. URL ht atttps:/ppoceeednngs
.ml...smm..rr........ www.ssrsspee...... / vl http///////aaaaaaaaaaaaaaa html
ISSN: 2640-3498.
Kilian Fatras, Thibault Sejourne, Rémi Flamary, and Nicolas Courty. Unbalanced minibatch Optimal Transport; applications to Domain Adaptation. In Proceedings of the 38th International Conference mlr
Machine Learning, pp. 31 31-6-1197 PMLR, July 2021. URL
arress/v13/fatras222 html
ISSN: 2640-3498.
Aude Genevay, Gabriel Peyre, and Marco Cuturi. Learning Generative Models with Sinkhorn Divergences. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, pp. 1608-161 1617. PMLR, March 2018. URL httpp::/pproeeeiinss..tt mir
press//88/gennvaal 8a html ISSN: 2640-3498.
10

---

Under review as a conference paper at ICLR 2022
Hongyu Guo, Yongyi Mao, and Richong Zhang. MixUp Locally Linear Out-of-Manifoll Regularization. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):3714 3722. July 2019. ISSN 2374-3468. //ojs. aaai...aai.... www.aaaa..rrginnnnoo org/index.
doi:
URL https:
Number: 01.
S. K. Katti. Moments of the Absolute Difference and Absolute Deviation of Discrete Distributions.
The Annals of Mathematical Statistics, (1()):78855, 1960. ISSN 0003-4851. URL https
www. jstor www./orgg/aaa... 2237495
Publisher: Institute of Mathematical Statistics.
Hoki Kim. Torchattacks: A pytorch repository for adversarial attacks. arXiv:2010.01950, 2020.
arXiv preprint
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- 5285. PMLR, November 2020. URLhttp: http:tt:://ppoocdigg....stt mlr...ssm.r..oo http://........ar///1111/////m html
ISSN: 2640-3498.
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
net/ wwwp::.nee/foouummeeeeee wwr.mmiiimimiiiooooo..o wwt.:/iddvvxxxxxxkkk.. ottp://www........./oooooo//////
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL /ictp://yan
lecun. wwtp/////////nttt.////o//m
Gabriel Peyré and Marco Cuturi. Computational Optimal Transport: With Applications to Data Science. Foundations and Trends@ in Machine Learning. 1 1(5-6):355-607, February 2019. ISSN 1935-8237, 1935-8245. doi: 10. 10115/20000000073. URL // /wwww nowpub isserrs Publisher: Now Publishers, Inc.
com/ hatmm//riicieeetaaall/////// MMA--077
Filippo Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling. Progress in Nonlinear Differential Equations and Their Applications.
Birkhäuser Basel, 2015. ISBN 319---3-99-2082-55. doi: 10. 10007998-33331-208222 https://wwwt spr pepringgr.. com/ /ttp//ocok////3122222222
URL
Jy Yong Sohn, Jackyun Moon, Kangwook Lee, and Dimitris Papailiopoulos. Gan-mixup: Augmenting across data manifolds for improved robustness. ICML Workshop on Uncertainity and Robustness in Deep Learning, 2020a.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A. Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence. Advances in Neural Information Processing Systems, 33:596-600 608, 2020b. (1964dce9addba 3 Abst
neurips. cc/ wttpccpppp/p////////e/p
Justin Solomon, Kristjan Greenewald, and Haikady N Nagaraja. k-variance: A clustered notion of variance. arXiv preprint arXiv:2012.06955. 2020.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Aaron Courville, Ioannis Mitliagkas, and Yoshua Bengio. Manifold Mixup: Learning Better Representations by Interpolating Hidden States. September 2018. URL URLattps:
hitps: http::/::////peeeveieeee net http://wwww.etttoooooooooror.//
Pete Warden. Speech commands: A dataset for limited-vocabulary speech recognition. arXiv preprint arXiv:1804.03209, 2018
Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(44):2620-2666 2019.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. CutMix: Regularization Strategy to Train Strong Classifiers With Localizable Features.
pp. 6023 6032, 2019. URL https: htttp:://opeaaccess
theevf. wwtpeeeeccoooceooooooooomooooeee cttpo//coteett_tcooo 2019 2019/htm1// Yun CutMix Bat.aaiweeeaaaaaaaattoooaaaaaaaa wtw.:laariraaioooStttttttee to Train Sttp__ttro____ Classi fiers wiles__WWte with Lac_athhahaaaaae___eeee zab w httpoccvooo_pppp_p___eee paper.htm

---

Under review as a conference paper at ICLR 2022
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond Em- pirical Risk Minimization. February 2018. URL bELpo://ppeneeeiii.eeeeffooommo
riDap1-Rb
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou. How Does Mixup Help With Robustness and Generalization? September 2020. URL
12

---

Under review as a conference paper at ICLR 2022
A k-MIXUP PSEUDOCODE & COMPUTATIONAL COST
NEW
Below is code for one epoch of k-mixup training, in the style of Figure 1 of Zhang et al. (2018).
yl, y2 should be one-hot vectors
for (xl, yl), (x2, y2) in zip (loader1, loader2):
cost numpy. inf [x1 shape x1 x1. shape [0]]
for i in range (x1. shapeha // k);
cost [i (i+1) k,
k: (i+1) k] scipy. spatial.
distance_matrix [x] * k: (i+1) k], x2 k: (i+1) * k])
idx ceippy.ottiiin petrimmiee.iiearr...m wer__iinerr_ssuee ltt___sss_sssssmsssssese
(cost)
x2 (i+1) k] x2 i k: (i+1) * k]
y2[i (i+1)) * k] yi i (i+1) * k]
aam www.oo..ranmmm.oom
(alpha, alpha)
x = Variable (1am * x1 (1 lam) * x2)
y Variable (1am yl (1 lam) y2)
@etimizeer.zero_ge
()
loss (net (x), y) (backardd
optimizer.step ()
Computational cost. While the cost of the Hungarian algorithm is (k))), it provides k data points for regularization, yielding an amortized ((k2) complexity per data point. For the smaller values of k that we empirically consider, approximate Sinkhorn-based methods (Cuturi 2013) are slower in practice, and the Hungarian cost remains small relative to that of gradient computation (e.g. for CIFAR-10 and it 32, the Hungarian algorithm costs 0.69 seconds per epoch in total). Computing the distance matrix input to the OT matching costs O(k2d) d) where d is dimension, yielding an amortized (kd) complexity per data point. With the high dimensionality of CIFAR, naive CPU implementation of this step of the computation adds about 8 seconds per epoch 4 Moreover, training convergence speed is unaffected, unlike manifold mixup /Verma et al. 2018). which in our experience converges slower and has larger computational overhead. Overall, there is little computational downside to generalizing 1-mixup k-mixup.
B PROOF OF PROPOSITION 1
NEW
Finite-sampa sample convergence of empirical measures implies that for an arbitrary sampling of l points fu.. we have 3 (e. (ix) < ( with high probability (e.g.. 1 1/k² probability, from Theorem 9.1 of Solomon al. (0200) when combined with results from Weed Bach (2019)). The triangle inequality then implies that the Wasserstein-2 distance between our batches of k samples will tend to
O at the same asymptotic rate: W2 A I O(k-2/d) with high probability.
Recalling that by the definition of the optimal coupling permutation (i), we have & E || a. 11 W ( < -k2d2/d with high probability. Hence, for any I C [1, k] with ||
"a(i)ll
20)12 1-1 for all I. П < O(K'-1/d) < ōk for k large enough and any d (0. 1]. In essence, long-distance identifications are rare, and their fraction is bounded for large enough k. Therefore, for & large enough, again with high probability there exists a subset I with |Z] 2 (1 - 5)kk such that | x5 ll2 Rs for all i I. Since x? and ( lie in S, the proposition results.
C PROOF OF LEMMA
We argue by contradiction and prove the result for m first. Suppose that the number of cross- cluster matchings exceeds Irı s1l. Then by the pigeonhole principle, there must be at least two such matchings, which we II say are between p; and q. and pi+1 and 4++1. WLOG. As the cost of the cross-cluster matchings is > (2 and the cost of intra-cluster matchings is (2A)2, more
'It is possible to accelerate this computation with parallelization/GPU usage, but as this cost is small portion of the overall training cost did not optimize it.
13

---

Under review as a conference paper at ICLR 2022
optimal matching would pair ps and 9++1, and P4+1 and 9s- This contradicts optimality of the initial pairing.
In the scenario with m clusters, analogous argument works. As above, |r; is the number of cluster elements that must be matched in a cross-cluster fashion, and half the sum of these quantities is the minimum number of cross-cluster matchings overall. If this number is exceeded, by the pigeonhole principle, there must be additional cross-cluster matches that form a cycle the graph over clusters. As above, the cost would be reduced by matching points within the same clusters, so this contradicts optimality.
D PROOF OF THEOREM
We first prove the result for two clusters of weight and 1 With our clustered assumption, we may assume that all identifications that can be intracluster will be intracluster. Thus, if 81 and 82 denote the number of points in cluster from batch I and 2, then the resulting number of cross-cluster matches |s 52/- As the samples for our batches are i.i.d., these random variables follow simple binomial distribution Bkk, p). We can bound the expectation of this quantity with Jensen's 's inequality:
[Ells) s2 < Blss1 s2| 2Var(s1) 2kp(1 -p
With some algebraic manipulation, desired rate bound results. It is also possible to get exact rate with some hypergeometric identities (Katti) 1960), but these simply differ by a constant factor, we omit the exact expressions here.
For the general case, our clustered assumption again allows us to assume that OT will prioritize intracluster identifications. Thus, if we let r; and 8; denote the number of samples in cluster in batch I and 2, respectively. then the number of cross-cluster matchings will be _ >; rr - sil. Ultimately, r and 9; are sampled from a binomial distribution (kk, pt), so may repeat the argument above and note that (r. 8i] (1 - pt). Simple algebraic manipulations lead the desired result.
E PROOF OF THEOREM 2
By the smooth boundary and positive density assumptions, we know that P(As) > 0 and P(Bs) for any 5 >> O. Hence, for fixed 5 and l large enough, we know that with high probability the sets As and Bg each contain more points than the number of cross-cluster identifications.
Now consider A, and B, for 25 + (max (RA. RB (2DD)). All cross-cluster matches need to be assigned. The cost of assigning a cross-cluster match to point As and point B, is at most D² 20)a (since we are using W2). Furthermore, the cost of assigning cross-cluster match that contains a point in A outside A, and an arbitrary point in B is at least D² + e)2. Consider the difference between these two costs:
D2(L+e)--D D2 +2) D2 20) + - -62)) 2D2 Max(RA, RB)² Z R
2D2
Since this difference and we have shown As contains sufficient points for handling all assign- ments, this assignment outside of A, will only occur if there is within-cluster pair which benefits from using the available point in A, more than is lost by not giving to the cross-cluster pair (> R& ). The maximum possible benefit gained by the within-cluster pair is the squared radius of A. i.c. R Since we have shown that the lost cost for the cross-cluster pair is bigger than R², we have arrived at contradiction. The proof is similar for the B side.
We have thus shown that for l large enough (depending on 8). with high probability all cross-cluster matches have endpoint each in A and B. where = 26 (max (RA, Ry R2)))/(2D2). Setting 5 (max(Ra RA, / //DD²) completes the proof.
F PROOF OF THEOREM 3
We mostly follow the notation and argument of Zhang et al. (2020) (c.f. Lemma 3.1), modifying it for setting. There they consider sampling X Beta(o, B) from asymmetric Dirichlet
14

---

Under review as a conference paper at ICLR 2022
distribution. Here, assume symmetric Dirichlet distribution, such that B, simplifying most of the expressions. The analogous results hold in the asymmetric case with simple modifications.
Consider the probability distribution Dx with probability distribution: B(aa + 1,a). Note that this distribution is more heavily weighted towards across all a, and for 1, there is asymptote as you approach 1.
Let us adopt the shorthand notation ( (A) == Auς + (1 2) for an interpolated feature point. The manipulations below are abbreviated, as they do not differ much for our generalization.
Ek Ex (f)
2 B Ba
Σ
Σ
+ + ->7?
Aw (10))
{x))²
7:5=1==1
k
k: xx)) 2 ExNDla B Bern(A)
Σ
(5)
M==1i=1 (1.,
+ (1
k
Σ
Ex (ā (A))) - V7 (
xx)) 7:5=1 iml
For the third equality above, the ordering of sampling for À and B has been swapped via conjugacy: ~ B(ax, a). BJλ ~ Bern(A) is equivalent to ~ (0, },. A/B ~ B(a + B, a + B). This is combined with the fact that ())) A) (0,)((
get the last line above.
Now we can swap the sums, grouping over the initial point to express this as the following:
emix ( N Σ Eo + (1 (1-))r)) - 1/ s(x;; + (1 - -Arr),
where the probability distribution D; is as described in the text.
The remainder of the argument performs a Taylor expansion of the loss term h(f(Ar; + (1- -)r))) (1-))r)
v f (Az; + (1 X)r) in terms of 1 X, and is not specific to our setting, so we refer the reader to
Appendix A.1 of (Zhang et 2020). for the argument.
G MMMI AS MEAN REVERSION FOLLOWED BY REGULARIZATION
Theorem 4. Define (z) as
a7 a 000 xf)
97 07 + f v.). (1) and Vž = (2) x= v y
where 27 1/2 E x
(i) are expectations under the matchings
(2) and 0 ~ 9/11/2.1(0,000 a). Further, denote the zero mean perturbations
8 1) + (1 8)
(() - -(1 -1-
? = (0- 00=0 + (1 - 0)v - -0)0?
Then the k-mixup loss can be written as
&
OTmirup (f)
Egge
e(0) +0772
The mean 27 being shifted toward exactly the mean of the locally-infoman distribution D;- Moreover, the covariance structure of the perturbations is detailed in the proof (simplified in Section G.I. and is now also derived from the local structure the distribution, inferred from the optimal transport matchings.
15

---

Under review as a conference paper at ICLR 2022
Proof. This argument is modelled a proof of Carratino al. (2020), adopt analogous
notation and highlight the differences our setting and refer the reader to Appendix B. of that paper for any omitted details. First, let shorthand notation for the interpolated loss function:
m (A) = {(S(xa + (1 A)a (00)))) Anp + - 2)
Then the mixup objective may be written as:
k (A).
E (f) k(x) 7-E=1i=1
Σ
Σ
Exm?
As X B(a,, at), may leverage the symmetry of the sampling function and parameter 0 ~ (11 to write the objective as:
h
& (
Li
where &
B 7 (0)
To obtain the form of the theorem in the text, we introduce auxiliary variables #7, 02 to represent the mean-reverted training points:
/ = Eo.e Ox? + (1 0)ze (c()
07 Eo.s Oyy + (1 0)v
and E7 to denote the zero mean perturbations about these points:
87 p.r7 + (1 () - -Bo.g [xx] + (1 - 0) x(c(
7 0u? (1 0)y O) Eo,s
Ou? + - +
These reduce to the simplified expressions given in the theorem if we recall that 0 and are indepen- dent random variables. Note that both the mean-reverted points and the perturbations are informed by the local distribution DD
G.1 COVARIANCE STRUCTURE
As in Carratino et al. structure of the local perturbations, very similar, we omit it.
2020). it's possible to come up with some simple expressions for the covariance write out the analogous result below. As the argument is
Lemma 2. Let o² denote the variance of B1,2,1 a). and v² := o² - (1 - 0)2. Then the following expressions hold for the covariance of the zero mean perturbations:
02 =/) - =T7) +
Eo,55,(87)T
8727
82
0² (0) DT)T 1 12 -
Eg Eg (
02
0² (07 +/)(? V!)T
12 2
E
Es Es
87 (ET)
g2
where Egpz?. Dg. Egps denote empirical covariance matrices.
Note again, that the covariances above are locally-infornet rather than globally determined. Lastly, there is also a quadratic expansion performed about the mean-reverted points V," y with terms that regularize f. but omit this result as the regularization of Theorem is more intuitive (c.f. Theorem 2 of (Carratino et al. 2020
16


Reviews:
[{"review_id": "j9fncwOstn7", "reviewer": "Reviewer_iZL9", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Major comments:\n\n-- Proposition 1 and Theorem 1's implications are unclear. Does this mean that k-mixup with large k is closer to \"on-manifold mixup\" such as SMOTE?  For instance, see \"[Chawla et al. (2002)] that proposed to augment the rare class in an imbalanced dataset by interpolating the nearest neighbors and [DeVries & Taylor (2017)] that showed that interpolation and extrapolation the nearest neighbors of the same class in feature space can improve generalization\". (The description of these papers are excerpted from the original mixup paper -- the authors may want to refer to Sec. 4 of the original paper.)\n\n-- \"The localized nature of the matchings makes it more likely that the averaged labels will smoothly interpolate over the decision boundaries. A consequence is that k-mixup is robust to higher values of α, since it is no longer necessary to keep λ close to 0 or 1 to avoid erroneous labels.\" => For high-dimensional data, even with higher values of alpha, it is unclear if erroneous labels (aka manifold intrusion) will occur with high probability. This questions the practical gain of the proposed method on high-dimensional data. \n\n-- The proposed idea seems relevant to [\"GAN-mixup: Augmenting Across Data Manifolds for Improved Robustness\", Sohn et al.].  The authors may want to clarify the difference between the proposed approach and the one introduced in this prior work. \n\n-- Performance comparisons with baseline algorithms are missing.  \n--- Guo et al.'s AdaMixup\n-- [\"On Adversarial Mixup Resynthesis\", Beckham et al.]\n\n-- Some performance gains (compared to k = 1) on real datasets look too marginal; See Figure 10, Figure 11 \n\n-- By looking at Figure 5 and Figure 6, the performance seems to be highly correlated with the average squared distance of vicinal distribution from training set, regardless of the choice of k.  For instance, in Figure 6, (k=1, alpha=0.5) and (k=8, alpha=1) have almost the same distance as well as the test accuracy. \n\nThis makes it unclear whether or not the performance gain actually comes from the benefits of k-mixup. Instead, this might be an artifact of decreasing distance intervals as k increases. For instance, in Figure 5, even though the same values of alpha's are tested, k=1's average squared distance ranges from 0.068 to 1.732, while k=32's those ranges from 0.029 to 0.586. This allows the latter to try out more reasonable values of the squared distances. \n\nTo show that this is not the case, the authors may want to rerun the experiments while adaptively setting the range of alpha values for a different choice of k such that the same (or similar) alpha values can be tested. \n\n-- The confidence on test performance seems surprisingly too low to me. What are the random factors across different Monte Carlo runs?  Random initializations and random shuffling usually alone usually give a much higher confidence interval than the reported values such as 0.02 or 0.05. \n(See Table 1 in this for instance -- https://arxiv.org/abs/2109.08203)\n\n-- Adversarial robustness: robust accuracy against FGSM (or any simple gradient-based attack) can be highly misleading. Please use AutoAttack by Croce and Hein instead to see whether there exists an actual robustness gain.\n\n\nMinor comments:\n\n-- \"Averaging weights are typically drawn from a beta distribution β(α, α), with parameter α ≪ 1 such that the generated training set is vicinal\" -> Not true.  See Table 1 and Table 2 in the original mixup paper for the choice of large alpha values.  Also, the original paper says \"For example, in CIFAR-10 classification we can get very low training error on real data even when α → ∞ (i.e., training only on averages of pairs of real examples)\".", "summary_of_the_paper": "The paper proposes an optimal transport-based mixup algorithm, theoretically analyzes the algorithm, and empirically evaluates its performance.", "summary_of_the_review": "The theoretical claims look solid, but their implications are unclear.  The experimental settings and results could be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gpYQ3sOw_Pd", "reviewer": "Reviewer_K2Mi", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros: \n- This work is well-motivated and well-written.\n- Theoretical study supports the claim of the paper (as k increases, the vicinal samples better reflect the local structure of the dataset).\n- Experimental protocol seems sound and varied.\n\nCons:\n- There are two hyper-parameters, k and alpha, whose choice is not completely clear to me (see below).\n\nQuestions and remarks: \n- It could be useful to the reader to elaborate on the advantage of the Hungarian algorithm over Sinkhorn w.r.t k.\n- Do you really need to compare the cost of the regularization to the cost of computing gradients? Isn't k-mixup regularization a pre-processing step with \"fixed cost\"? \n- Do you have an idea why increasing k does not always improve your results? This seems to be opposed to the intuition that higher k better reflects the structure of the dataset. More generally, it could be great to have a discussion on how to choose k and alpha for your method.\n- Could this technique be useful in the context of transfer learning (I am not asking for more experiments here)?", "summary_of_the_paper": "This work proposes an improvement on the Mixup regularization for training deep neural networks. Instead of performing weighted averages of randomly chosen pairs of samples, an optimal transport map between two k-batches is computed. Then, \"new\" samples are constructed by interpolating between *coupled* pairs of samples (according to the optimal transport plan). This enables to better reflect the local structure of the dataset. A theoretical study supports this intuition, and extensive experiments are conducted.", "summary_of_the_review": "This work seems well-motivated, clearly explained with globally convincing experiments. My only concern is on how to choose the hyper-parameters k and alpha, which do not seem to always have the intended effect. Overall, I tend to recommend acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SMxT3JMYgEB", "reviewer": "Reviewer_P7xo", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Description: The paper explains well the method and it can be reproduced easily in my opinion. However, I find it hard to fully understand how they build the entire minibatches of data they use (see questions below). There are some details I am not sure to understand for now and I feel the paper lacks a bit of clarity. May be adding some concrete examples might help readers to get the picture of the creation of the full minibatch used in training or may be adding the pseudo code of their algorithm. Regarding theoretical results, the paper discusses their results properly, however I have some concerns about the validity of the results due to the fact that authors use in practice minibatch optimal transport instead of exact OT (see questions and remarks below). Thus, I am not convinced of the pertinence of some claims.\n\n\nEvaluation: The evaluation of the methods seems complete experimentally. The method has been used on classification problems on a different datasets of different dimensions. It has also been compared to other mixup variants (manifold mixup) and on adversarial attacks. The results show a small increase in the performance. I think the empirical comparison is complete. However, I have some concerns regarding the theory as stated above. Indeed using minibatch OT as you do, creates non optimal connections between samples including connections between different examples [3]. Thus a longer discussion on minibatch OT is required.\n\n\nSignificance: The idea is interesting but is not too novel as the idea of coupling close samples has already been explored in the original mixup paper through k-nearest neighbourh. The difference is the use of optimal transport to determine how to connect samples instead of doing it randomly as done in the original mixup.\n\nRelated Work and Discussion: The strength of the methods are discuted but the aspect of minibatch OT is lacking and as such, the discussion is not complete in my opinion. The limitations of the methods is not discussed enough in my opinion. Authors could have empirically experimented the percentage of connections between different clusters of data to show that their method respects the manifold of data. Regarding related work, there are missing discussions which I think are important with previous methods (k nearest neighbourh from original mixup for instance).\n\nClarity: A reader not familiar with the mixup regularization could understand previous work as well as the presented method. The paper is easy to read and correctly written. The objective is clearly stated and I have not seen typos in the main text. I think that, from the text, one could reproduce the proposed methods. However, I also think that a discussion on how they create the full minibatch of data used during training should be included in the paper. Maybe adding examples or pseudo code is a good way to improve the clarity on these details.\n\nQuestions and remarks:\n\n1. You do not really use optimal transport but minibatch optimal transport[1,2] and you should discuss the differences. As such, it is known from [3,4,5] that it creates non optimal connections between clusters of data due to the sampling of minibatches. Following your intuition to preserve the manifold structure, I wonder why all your best scores are not for the biggest k, as the biggest k would more preserve the structure. This is contradictory with the initial prediction. Finally, if k grows to infinity, the proposed method would just mixup samples between themselves, thus no doing any mixup at all... This is also a concerning point, a study focused on minibatch OT (what authors do in practice) might alleviate this problem.\n\n2. Even if the connections between far away data are rare, it is noted in [5] that they happen and can harm the neural networks on some applications. I wonder their impact on the training. (see point 8 for a related point)\n\n3. Furthermore, due to the possible imbalanced classes, the data structure you are looking for, might not be possible in practice even for big k and even with OT between the full distributions. How does your method work for highly imbalanced case ? May be using partial OT or unbalanced OT with your minibatch formulation might help.\n\n4. I have some concerns with Section 3.1 and Section 3.2. You have applied your theory to exact OT, or minibatch OT with only one batch couple, while you are doing minibatch OT which is an expectation of optimal transport terms over minibatches of data. The latter favorises the creations of non optimal connections and is different of the former. You consider the case where the number of data grows to infinity but in practice you only use really small k. As such the theory is not in concordance with the practice and I am not convinced. \n\n5. While the use of Optimal Transport is appeling and increases the scores, it is not the first time that doing miwup between similar data is used. Indeed, in the original mix up paper, authors tried to used a k-nearest neighbourh and did not see improvement over original mixup. A discussion between k-nearest neighbourh is thus lacking.\n\n6. What is the full batch size you used for your training ? Was it k ?\n\n7. Could you please share a pseudo algorithm of your method ? It could be in appendix and help to understand some details of your training.\n\n8. As the motivation of your method is to respect the manifold of data, an interesting experiment, in my opinion, would be to measure the average percentage of connections between data which belong to different clusters. \n\n[1] DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation, Damadoran et al.\n\n[2] Learning Generative Models with Sinkhorn Divergences, Genevay et al.\n\n[3] Learning with minibatch Wasserstein: asymptotic and gradient properties, Fatras et al.\n\n[4] Minibatch Optimal Transport distances; analysis and applications, Fatras et al.\n\n[5] Unbalanced minibatch Optimal Transport; applications to Domain Adaptation, Fatras et al.\n\n\n----------------------------------------------------------------------------------------------------------------------------------------------------------------\n############################################ UPDATE ############################################\n----------------------------------------------------------------------------------------------------------------------------------------------------------------\nI have read your answers. While I think some elements have greatly improved, I still think that there are some problems. I think the discussion on the minibatch transport plan should be better discussed at least in supplementary. I have also a concern of the manifold structure preservation in high dimension. Most reviewers also think that the use of theorems in practice is unclear. For all these reasons I keep my score unchanged.", "summary_of_the_paper": "Goals: The paper presents a new manner of mixing up training samples to create new training distributions like mix up. It uses optimal transport between minibatches of data of size k. Then they perform mixup between transported data and uses these new data in the training of their neural networks. The intuition is that their method is more able to respect the manifold of data contrary to original mixup which mix samples uniformly at random.\n", "summary_of_the_review": "Recommendation: Reject. While I agree the idea is appealing, it is not too novel and some missing discussions would lead to a huge change in the original paper in my opinion.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9gt8HBLSiQM", "reviewer": "Reviewer_EGaJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper shows some nice improvements on low-dimensional toy datasets from using optimal transport to select examples from two different batches to interpolate.  The improvements on larger datasets are more marginal, but are still significant when the mixing rate alpha is large.  This is decent work and it may have some impact, but the small improvements may make the impact fairly limited.  Additionally what it achieves does overlap some with Manifold Mixup, although the paper does explain that Manifold Mixup has other drawbacks.  \n\nOther comments: \n  -First paragraph of intro is really boilerplate that could be removed.  \n\n  -Figure 1 is a bit weaker of a result than could be possible - since the solution inside the spiral is still somewhat but only partially blurred after using k-mixup.  Nonetheless it is better than the baseline.  \n\n  -Figure 2 is pretty convincing that more points are being interpolated onto the same manifold when using a larger K.  \n\n  -How is the algorithm different from mixing with nearest neighbors from a limited pool of examples?  Perhaps it's the requirement of an optimal transport (so that the same point can't be picked twice as a neighbor)?  \n\n  -The insight in Theorem 1 is nice, especially that cross-cluster mixes will still be selected more as K grows, but as a decreasing fraction of K.  \n\n  -The classification results (Figure 8) are a bit discouraging, and somewhat contradict the introduction which claims that the k-mixup technique doesn't hurt results, when several results are 0.1-0.3 basis points below the baseline.  Still, where improvements occur they are often of larger magnitude than the deteriorations.  \n\n  -The improvement with large alpha is impressive.  \n\n  -FGSM is a very weak attack, so the improvements in Figure 12 are of questionable significance, although it is nice to see slightly better robustness.  \n\n", "summary_of_the_paper": "This paper proposes to select pairs of points to mix between two batches of K examples by using the hungarian algorithm to find an L2 optimal matching.  This substantially improves performance on non-linear low-dimensional classification tasks where mixup underfits and it also improves results on moderate-scale classification tasks (like CIFAR-100) and especially helps when the mixing rate alpha is large.  There is also theory analyzing how often mixing will interpolate between different clusters when using k-mixup.  \n\nDetailed Notes from reading the paper: \n\n  -Modification of mixup where batches of k points are perturbed in the direction of k other points using interpolation under a Wasserstein metric.  \n\n  -Proof with experiments and theory showing this k-mixup preserves cluster and manifold structure.  \n\n  -K-mixup improves results (or keeps same) and improves adversarial robustness.  \n\n  -Increasing K makes interpolated points more likely to be on data manifold.  \n\n  -Use Hungarian algorithm to find L2 optimal permutation.  \n\n", "summary_of_the_review": "This paper achieves small improvements on large datasets and significant improvements on either low dimensional data or where the mixing rate alpha is very large.  The improvements are small but the idea is simple and logical, so I weakly recommend 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": "12deyrN2gTG", "reviewer": "Reviewer_8N9h", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "-Strengths:\n\n1. This paper is generally well-written and well-organized, making it easy to understand.\n\n2. The authors did many experiments in various settings. They used neural networks with different sizes (small MLP to DenseNet) on different datasets (both synthetic and real-world datasets) from different modalities (image and audio). Each experiment is also repeated multiple times.\n\n3. The authors provided very detailed settings, e.g., network structures and hyperparameters, for their experiments. This makes their experiments quite reproducible.\n\n-Concerns:\n\n1. The justification for the proposed k-mixup method might be unclear, and this is my major concern for this paper. I will explain my concern in detail in the following paragraphs:\n\n1.1 The authors claimed that $k$-mixup preserves the local structures of the training data, but this alone is not enough to explain why $k$-mixup could help. Imagine the extreme case where we take $k$ to infinity, and this will essentially be equivalent to having no mixup at all because every data point will mix up with itself. Therefore, there might be deeper reasons why $k$-mixup could work, and this could be related to how the labels are interpolated during mixup. Since $k$-mixup encourages closer points to mix, the mixup between points from different classes will have a sharper label transition compared to the normal mixup. The authors proved in Theorem 2 that $k$-mixup can help the model with smooth interpolation between the clusters, but this model seems somewhat specific and the authors did not talk much about this smoothing effect in this paper.\n\n1.2 Both smaller $\\alpha$ and larger $k$ can make the training set become more vicinal, and intuitively it could be unclear which has a better regularization effect. For instance, setting both $k$ and $\\alpha$ to be large and setting both to be small should both result in a vicinal dataset. In this case, the two regimes might have a similar local structure for the training data, and it seems confusing why this extra parameter $k$ could help because we can always choose a smaller $\\alpha$ to make the training data more local.\n\n1.3 For larger $k$, more training data will be mixed with points within the same class if the data have some cluster structure, as can be seen in Figure 2. Thus, the ratio of the same-class mixup will vary when $k$ changes. This may also influence the regularization effect of k-mixup and it could be possible that changing the ratio of same-class mixup can already improve the performance of mixup.\n\n2. The empirical benefit provided by $k$-mixup might not be significant enough, and this $k$-mixup method requires extra tuning for the hyperparameter $k$. Details are provided below:\n\n2.1 The performance gain by performing $k$-mixup is not consistent for different datasets and network structures. For instance, in the small $\\alpha$ regime ($\\alpha$=0.1), larger $k$ always does not improve the performance in most of the datasets while requiring more computation and parameter tuning. This could be because smaller $\\alpha$ better preserves the local structure of the data and larger $k$ is not needed.\n\n2.2 For the cases where $k$-mixup does improve the performance over the original mixup, the performance gain does not seem to be very large (usually less than 1%), and achieving this performance gain requires much work in tuning the hyperparameters $k$ and $\\alpha$. As mentioned in concern 1.2, the regularization effect provided by $k$-mixup is controlled by both $k$ and $\\alpha$, and based on the experimental results there seems not to be a consistent scaling law for the best $k$ and $\\alpha$. Specifically, from the best-performance model for original mixup($k$=1), achieving best performance sometimes require us to increase both $k$ and $\\alpha$, but sometimes will require increasing $k$ and decreasing (or keep) $\\alpha$ instead, depending on the task. This probably means tuning $k$-mixup requires a grid search over $k$ and $\\alpha$, which introduces extra computation cost.\n\n2.3 It would be better if the authors could compare $k$-mixup to other mixup variants. This paper only provides one experiment comparing $k$-mixup to manifold mixup on one task, so it might not be convincing enough that $k$-mixup could perform better than other variants of mixup.\n\n2.4 The authors claimed in their paper that the extra computation cost caused by $k$-mixup is small, and it could be better if they could provide numerical evidence for this, e.g., compare the wallclock time of training the same model using regular mixup to that of $k$-mixup where $k$=32.\n\n3. The assumptions and conclusions of the theoretical claims are somewhat unrealistic.\n\n3.1 The theoretical claims often require k to be \"large enough\", which actually needs $k$ to be larger than some exponential function of dimension $d$. This cannot be true in practice. For Proposition 1, we need $k$ to be larger than both $\\Omega(1/\\delta)^d$ and $(1/R_S)^d$. For Theorem 2, $k$ needs to ensure both $A_\\delta$ and $B_\\delta$ contain enough points, which could also require $k$ to be exponentially large. This is somewhat unrealistic because the inputs for the usual tasks are usually of high dimension. It would also be better if the authors could explicitly state the requirement of $k$ in their statements of theorems.\n\n3.2 The assumptions needed for the theoretical results might lack justifications. For section 3.2, the authors assumed that the input data to be $(m, \\Delta)$-clusterable and the distance between any pair of covering balls is at least $2\\Delta$. This assumption intuitively would result in a very large $m$ for real data and largely weaken the conclusions. Besides, it might be better if the authors could explicitly state this assumption outside the Lemma since Theorem 1 and 2 also need that assumption.\n\n3.3 Section 4 might seem a bit confusing. The expressions for the loss and regularizers are roughly the same as the previous paper (Zhang et al., 2020) except that the expectation in the regularization terms is taken over the \"locally-informed distribution\", but it seems unclear why this is better than the original distribution.\n\n-Minor Comments:\n\n1. Figure 1 seems a bit confusing and might need more interpretation. The authors claimed that it shows $k$-mixup can better keep the manifold support structure, but it seems that 4-mixup produces a more blurry function on Swiss Roll than 1-mixup, which seems confusing. Besides, it might be better if the authors could provide more detailed explanations about these datasets, e.g., how they are generated and labeled, to make Figure 1 more clear.\n\n2. Some of the intuitions from the paper might become weaker for higher-dimensional data. For example, in the regime when the number of data is not much larger than the dimension, the data points will become more separated in the sense that linear interpolation between any two points might not be close to any other points. This regime may be very different from the synthetic datasets visualized in Figures 1 and 2. Besides, since the theoretical results in this paper often require $k$ to be exponentially large in $d$, this could also be part of the reason why $k$-mixup doesn't work so well in high dimensions. The authors discussed this in section 6, and it might be better if the authors could comment more.\n\n3. For the Toy datasets, especially One Ring and Swiss Roll, normal mixup seems to work better for smaller $\\alpha$, so perhaps the authors could try to use even smaller $\\alpha$ and see whether that can give even better results.\n\n4. For the performance on Google Speech Commands, the authors claimed that the difference between the best $k$-mixup and the best normal mixup is 0.6508%. How is this number computed?\n\n-Typos: There is a duplicate sentence near the end of Section 2: \"The localized nature of the matchings makes it more likely that the averaged labels will smoothly interpolate over the decision boundaries.\" appears twice.\n\n---------------------Update--------------------------\n\nI have read all the other reviews, the authors' responses to all the reviewers, and the revisions the authors made in the updated draft, and I have decided to keep my score unchanged, i.e., I tend to recommend rejection. I would like to thank the authors for their very detailed response which addressed some of my concerns (e.g., ratio of same-class mixup, wallclock time comparison), but my major concerns (unclear justification, marginal performance gain) about this paper still remain. Detailed reasons why I keep my score are listed below:\n\n- The justification for $k$-mixup seems somewhat unclear, and this is a common concern for most of the reviewers (P7xo, iZL9, K2Mi, 8N9h). The authors claimed that this method can better preserve cluster and manifold structures and provide some smoothing effect between clusters. However, both claims might be too abstract. The authors provided theoretical explanations in Section 3, but the implications for these theorems seem unclear, e.g., as also mentioned by reviewer P7xo and K2Mi, they cannot explain why increasing k doesn't necessarily always improve the performance.\n\n- The performance improvements on real datasets seem marginal, and this is also a common concern for most reviewers (iZL9, EGaJ, 8N9h). Besides, getting this performance gain requires tuning an additional parameter $k$, and there is no simple indicator (e.g., one cannot use average squared distance to directly predict the performance gain) for this gain, so one really needs to train more models with different $k$'s and $\\alpha$'s and do cross-validation, which requires much more computation power.", "summary_of_the_paper": "This paper proposed $k$-mixup, which is a generalization of mixup, to better regularize neural networks during training. Specifically, instead of mixing totally random pairs of training data, the authors draw $k$ pairs of data each time and mix them in a way that minimizes the Wasserstein distance between them. The authors theoretically proved that their method can better preserve the local structure of the data. They also did experiments for various networks and datasets and showed that $k$-mixup can improve the generalization performance and robustness of the models compared to the original mixup.", "summary_of_the_review": "I tend to vote for rejecting this paper. Despite being clearly written, the justification for their proposed method is somewhat unclear, and the performance gain seems not significant and consistent enough. Therefore, I think more work needs to be done to provide enough justifications for $k$-mixup (perhaps from the theoretical side) and to further improve the empirical performances.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an extension of mixup (a data augmentation method) to k-mixup using optimal transport. The idea is to select randomly at each iteration  two subsets of  k samples and compute the optimal transport solution. Each pairs of samples assigned by the optimal transport plan will then be used to perform mixup and promote smoothness in the prediction function. The authors also provide some theoretical results about preservation of the clusters. Finally numeric experiment show the interest of k-mixup on toy and real life dataset classification and study the effect of k and the $\alpha$ parameter (of the $\beta$ distribution).

All reviewers found the paper interesting and acknowledge that it leads to some performance improvements in practice. But they had several concerns that lead to low scores. The justification of the method an more specifically the link with the theoretical findings was found lacking, indeed the result make sens fr a large $k$ which is not was is done in practice (but experiments also show a decrease sometimes for large $k$). One interesting discussion  between the proposed approach and minibatch OT is also missing. In addition the reviewers found the numerical experiments interesting but regret that some mixup approaches have not been compared and also noted a small gap in performance for the proposed approach (with no variance reported). Also the Adversarial robustness measure is now considered weak in the literature and those results could have been made stronger with more modern adversaries. Their final concern was the fact that the method now has two parameters that needs tuning and that can have a large impact on the performance for limited gain. The authors did a detailed reply a,d edition of the paper that was very appreciated by the reviewers but that did not change their opinion that this paper still deserves some more work before being accepted.

For these reasons the AC recommend to reject the paper but strongly suggests that the authors take into account the reveiwers' comments before resubmitting to a ML venue.
Decision: Reject