Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Paper summary**
The paper gives theoretical proof showing that the recently proposed data augmentation technique Mixup can indeed improve generalization and help in robustness. The theorems cover GLMs and certain classes of neural networks. The paper also contains numerical experiments supporting some aspects of the theory.

**Strengths**
1. Currently, there is only a limited theoretical understanding of why Mixup works. This paper shows that Mixup is essentially equal to regularizing the first and second derivatives (with respect to the input $x$). Intuitively, this means that changing the training samples slightly shouldn't change the output of the model much. Further, the paper proves that the mixup loss is an upper bound on the $2^{nd}$ order Taylor approximation of the adversarial loss, and hence reducing mixup loss reduces adversarial loss. Finally, the paper proves that mixup helps in reducing the Rademacher complexity and hence improves generalization.
2. The results seem fairly general and apply to many models such as GLMs and neural networks.
3. The paper supports its approximations and claims by numerical experiments.

**Concerns**
1. The regularizing term $\mathcal{R}_3$ looks like it is minimizing $z^T\nabla f_\theta(x_i) z$ (for some $z$). This promotes the Hessian (wrt $x$) to have negative eigenvalues in the direction of $z$. Ideally, we would want the Hessian (and also the gradient) to be 0 around the training samples so that perturbing the input doesn't change the output much. Thus, I don't see how the $\mathcal{R}_3$ term helps regularize the Hessian properly.
2. The paper claims that Assumption 3.1 holds when the minimizers are not too dispersed. Does it still hold for practical neural networks where the minimizers can possible be fairly far apart?


**Comments**
Although the paper seems well written, I have a few suggestions:
1. The notation $cos(\theta, x)$ which refers to $\frac{\langle \theta, x \rangle}{\|\theta\|\|x\|}$ should be explained in the preliminary section.
2. On page 6, the statement $f_\theta(x)=\nabla f_\theta(x)^Tx$ should be proven. It will save the reader some time if the proof is provided.
3. In Remark 3.1, I think Theorem 3.2 should actually be Theorem 3.4

**Score justification**
There isn't much prior work on the theoretical understanding of Mixup. This paper provides theoretical guarantees for Mixup on two fronts - robustness and generalization; for both GLMs and ReLUs. 
review_title: Good paper that gives theoretical guarantees about Mixup

final_score: rating: 7: Good paper, accept
review_content: This paper shows that Mixup training is approximately certain kind of regularized loss minimization. Based on this, it provides some theoretical analysis on the advantages of Mixup training for the generalization and adversarial robustness over one-step attacks. 

This paper provides many insights on why Mixup works: e.g. connecting its 2nd order approximation with l2 adversarial loss; and shows that the Radmacher complexity of mixup adaptively characterize the intrinsic dimension of empirical data distribution. Though the techniques used in the paper were already developed by other works, the new results and insights on mixup in this work are worthy of being known by the community, particularly for that Mixup is such a popular data augmentation trick in deep learning. 

Some questions:
1.	Could you provide any comments on Mixup and adversarial training, e.g. one-step and multi-step ones?
2.	What about the generality of the analysis on L_infinity attacks? 

review_title: A nice theoretical analysis on Mixup 

final_score: rating: 7: Good paper, accept
review_content: The paper theoretically studies the beneficial effect of mixup on robustness and generalization of machine models. The mixup loss is  rewritten to be the sum of the original empirical loss and a regularization term (plus a high order term). For robustness, the regularization term is proven to be upper bound of first and second order terms of the adversarial loss's Taylor expansion. Hence, the mixup loss can upper bound the approximate adversarial loss. For generalization, the regularization term is used to control the hypothesis to have small Rademacher complexity. The paper is clearly written and well organized.

pros:
1. Rigorous theoretical analysis are conducted on non-linear models, specifically the neural network model. 
2. The theoretical results are clean and insightful. 

cons:
1. When studying robustness, an approximated adversarial loss is considered. The approximated loss is the truncation of the Taylor expansion of the original loss. The quality of the approximation is not explored in the paper. It is better to provide numerical evidence that whether the bounds in Thm 3.1 and 3.3 still hold for original adversarial loss, and how tight the bounds are. 
2. In the generalization part, only an indirect connection is built between mixup loss and the generalization gap. no result is provided concerning the generalization error of the solution found by minimizing the mixup loss. 
review_title: Good theoretical analysis

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary

This paper has extensive analysis on mixup augmentation, which focus on the effect of adversarial robustness and generalization. In adversarial robustness, They try to make a connection between mixup loss and adversarial loss, On the other hand of generalization,  they argue that mixup is a kind of data-apdaptive regularization.

Comment 
1. Good contribution about author's careful analysis on connecting between mixup loss and adversarial loss. It seems to be the first theoretical analysis on discussing their connection, since the past works just report the number to show how mixup and their variants to be robust to single-step adversarial attack.

2. Good to community about having a connection between Mixup and Rademacher complexity, I think it can make some impact to discuss the high-level connection between data augmentation and model generalization.
review_title: Careful analysis on theory, Good branch to help mixup community on adversarial robustness.

Meta-review: This paper provides theoretical justifications on why the data augmentation technique, Mixup (convex combinations of pairs of data examples) , can help in improving robustness and generalization of GLMs and ReLUs. The authors rewrote a Mixup loss function as the summation of a standard empirical loss and some regularization terms regularizing gradient, Hessian and some higher order terms. Using the quadratic approximation of the Mixup loss (ignoring the higher order terms), the authors proved that the quadratic approximation of the Mixup loss was equivalent to an upper bound of the second order Taylor expansion of an adversarial loss, providing justifications for why Mixup loss training could improve robustness against small attacks. Using the same quadratic approximation of the Mixup loss, the regularization term controlled the hypothesis class to have a smaller Rademacher complexity.

Overall, the paper provides insightful theoretical interpretations for a commonly used data augmentation technique in DL. The paper also supports its claims by numerical experiments. Although there is some minor concerns on using the quadratic approximation of the Mixup loss, as well as R3 term's regularization effect on a broader family of models, the paper provides unique and novel insights on Mixup.; all reviewers acknowledge the authors applying the existing proof techniques to analyze Mixup's effect on robustness and generalization.

Therefore, I recommend accepting this paper.
Decision: Accept (Spotlight)