Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.

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.


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


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

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

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

Questions and remarks:

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

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

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

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

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

6. What is the full batch size you used for your training ? Was it k ?

7. Could you please share a pseudo algorithm of your method ? It could be in appendix and help to understand some details of your training.

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

[1] DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation, Damadoran et al.

[2] Learning Generative Models with Sinkhorn Divergences, Genevay et al.

[3] Learning with minibatch Wasserstein: asymptotic and gradient properties, Fatras et al.

[4] Minibatch Optimal Transport distances; analysis and applications, Fatras et al.

[5] Unbalanced minibatch Optimal Transport; applications to Domain Adaptation, Fatras et al.


----------------------------------------------------------------------------------------------------------------------------------------------------------------
############################################ UPDATE ############################################
----------------------------------------------------------------------------------------------------------------------------------------------------------------
I 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an optimal transport-based mixup algorithm, theoretically analyzes the algorithm, and empirically evaluates its performance.
main_review: Major comments:

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

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

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

-- Performance comparisons with baseline algorithms are missing.  
--- Guo et al.'s AdaMixup
-- ["On Adversarial Mixup Resynthesis", Beckham et al.]

-- Some performance gains (compared to k = 1) on real datasets look too marginal; See Figure 10, Figure 11 

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

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

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

-- 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. 
(See Table 1 in this for instance -- https://arxiv.org/abs/2109.08203)

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


Minor comments:

-- "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_review: The theoretical claims look solid, but their implications are unclear.  The experimental settings and results could be improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.  

Detailed Notes from reading the paper: 

  -Modification of mixup where batches of k points are perturbed in the direction of k other points using interpolation under a Wasserstein metric.  

  -Proof with experiments and theory showing this k-mixup preserves cluster and manifold structure.  

  -K-mixup improves results (or keeps same) and improves adversarial robustness.  

  -Increasing K makes interpolated points more likely to be on data manifold.  

  -Use Hungarian algorithm to find L2 optimal permutation.  


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.  

Other comments: 
  -First paragraph of intro is really boilerplate that could be removed.  

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

  -Figure 2 is pretty convincing that more points are being interpolated onto the same manifold when using a larger K.  

  -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)?  

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

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

  -The improvement with large alpha is impressive.  

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


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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Pros: 
- This work is well-motivated and well-written.
- Theoretical study supports the claim of the paper (as k increases, the vicinal samples better reflect the local structure of the dataset).
- Experimental protocol seems sound and varied.

Cons:
- There are two hyper-parameters, k and alpha, whose choice is not completely clear to me (see below).

Questions and remarks: 
- It could be useful to the reader to elaborate on the advantage of the Hungarian algorithm over Sinkhorn w.r.t k.
- 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"? 
- 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.
- Could this technique be useful in the context of transfer learning (I am not asking for more experiments here)?
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: -Strengths:

1. This paper is generally well-written and well-organized, making it easy to understand.

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

3. The authors provided very detailed settings, e.g., network structures and hyperparameters, for their experiments. This makes their experiments quite reproducible.

-Concerns:

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

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

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

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

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

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

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

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

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

3. The assumptions and conclusions of the theoretical claims are somewhat unrealistic.

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

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

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

-Minor Comments:

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

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

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

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

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

---------------------Update--------------------------

I 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:

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

- 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_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.
review_title: null

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