Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper aims to offer a theoretical analysis of the training with data augmentation and associated consistency loss. While it is intuitive that training with data augmentation and consistency loss will help, this paper offers a theoretical justification of the intuitions. The simple framework (to view DAC as a hypothesis space complexity reduction technique) is neat and intuitive. 
main_review: **Strengths**

This work presents several clear strengths. 

  - This paper is one of the several works pioneering the discussions of data augmentation when used together with consistency loss, although several preceding works have been ignored [1, 2]. 

  - After the general form is introduced, several applications can be directly extended, which shows the potential of this work. 

  - An interesting definition of the strength of the augmentation

**Weakness**

However, I also have several major concerns about this work, for example

 - If I understand correctly, Theorem 1 is essentially a re-use of the standard generalization error bound with a replacement of the original hypothesis space to the regularized hypothesis space, and then, the main argument is that since regularized hypothesis space is believed to be smaller, then the new bound is tighter. Overall, I don't think this result is significant enough, especially considering it takes a major position in this paper. 
   
      - I think is too trivial to be considered as an important theorem of a publication at this level. It might be more appropriate to call it a lemma or a proposition of the theorem of the error bound with standard hypothesis space. 
      - A smaller upper bound does not really say much of the performances, both of the bounds could be not tight, and even they are tight, some discussions of how smaller the regularized one is will be helpful. 

  - While it is very interesting to see the definition of the strength of the augmentation, it does not say much in practice. Without a deeper or broader discussion, the definition seems to be a math brick for the theorem, discussions on how it is linked to the practice could be helpful, especially since the definition plays a central role as the major assumption in following theoretical results. 
    - The intuitive explanation offered by the authors are not intuitive enough, in particular, for the examples of using rotation as augmentation (the authors state they use rotation in this paper), what are the intuitions of the definition, how different degrees of rotation corresponds to different strengths, and any numerical evidence can be reported? 
    - Also, what's the intuitive explanation of Assumption 1? 

  - With Theorem 1 being trivial, as discussed above, Theorem 2 is probably one of the most important result in this paper, yet there seems  also some issues. 
      -. The proof of Theorem 2 critically depends on Assumption 1, this is not made clear in the main text. 
      -. It might be better to put the full statement, at least the full definition of d' back to the main manuscript. 


 - The empirical results do not offer any validation to the new theoretical discussion, but used to show that training with DAC can benefit in comparison to ERM, a fact that the community has known for a while. 


[1] Invariance-inducing regularization using worst-case transformations suffices to boost accuracy and spatial robustness

[2] Squared ℓ2 Norm as Consistency Loss for Leveraging Augmented Data to Learn Robust and Invariant Representations
summary_of_the_review: Overall, I feel like the theoretical discussion is not significant enough, and the associated experiments are also weak (in the context of theoretical papers)
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: ### Summary

The paper introduces a statistical framework to analyze data augmentation to interpret consistency regularization as a way to reduce function class complexity. Building upon this framework: the paper

- shows that for linear regression, consistency regularization is more efficient than empirical risk minimization
- provides generalization bounds under consistency regularization for logistic regression, two-layer neural networks,
- provides a generalization bound for expansion-based data augmentations for multiclass classification


main_review: 

### Strengths

1. The paper introduces a formal framework to study data augmentations and consistency regularization. The ideas are simple but novel, with several meaningful results and implications.
2. The paper is quite well-written, with the main ideas outlined clearly. The approach is well-motivated and seems to be built upon established literature. The review of related works is informative.

### Weakness

1. My main concern with the paper is about the results of Theorem 3 and Theorem 5, which appear (very much) weaker than they should be.
     - Theorem 5: "*For some* δ ∈ (0, 1)*, with probability at least* 1 − δ..." From a mathematical point of view, this is an extremely weak result (delta could be 0.999999). A regular generalization bound would have stated "For all delta>0, when n is large enough...".
     - Theorem 3: "*With constant probability, learning.."* The face value of the statement would be that the probability of the event stated in the theorem remains constant as n changes, which is obviously not true. I suppose that the author means "with probability bounded from below by a constant". Even in that case, this is a very weak result: wouldn't we want the probability to be at least close to one, or say, greater than 1/2?
     - The appendix, which is supposed to contain formal statements and proofs, also runs into that problem. Statements about "constant probability" appear in several places. The main assumption of the analysis, Assumptions 3: 

          n ≫ ρ^4 (d − d_{*aug}* + log(1/δ)  
         is also stated for **some** delta>0.
     - Theorem 4, in technicality, doesn't share the same problem. However, its result is only meaningful under Assumption 3, which is subject to the same constraint.

   If I understand correctly, the proofs of the paper might be adapted to support typical generalization bounds, but the manuscript in its current state didn't do that, and the results of the theorems do not make much sense.
2. The technical contributions of the other main results of the paper, Theorem 1 and Theorem 2, are limited. The proof (and result) of Theorem 1 is straightforward. The result of Theorem 2 for linear regression is interesting, but the proof involves standard computations.

### Other comments

- Throughout the manuscript and also in the appendix (which is supposed to contain rigorous proof), the author used several asymptotic notations such as <<, <~, and big-O notation, which may not be appropriate since (1) the analyses of the paper is non-asymptotic and involves many parameters (2) in rigorous non-asymptotic analyses, statements such as n ≥ N(\delta) is important but will be obscured using big-O notations
- A significant part of the proof in the appendix (10 pages) was to prove several results that correspond to a three-sentence remark in the main texts with no result statements. If the authors believe that this is a central point, a subsection in the main text should be created to provide the details. Otherwise, I suggest removing those parts out of the text (just the remarks) and the appendix, since those materials are not central to the content, totally not peer-reviewed, and shouldn't be associated with the paper if it is accepted.
- Example 1: "It can be verified that...". It would be helpful if a short verification is included in the appendix.
- Proof of Theorem 2: "The rest of proof is identical to standard regression analysis". This part is central to the result, so more details should be spelled out, or a reference should be given.
- Notations: rho is used both as a metric and as the sub-Gaussian constant. This is further confusing since they appear close to each other at times.
- Proof of Lemma 5:
    - The last statement on page 28 is incorrect. O(d) do not dominate d.
    - There is a typo in the equation "ρ2 ≥ ε2/16"

### Questions

- How are the regularizing constant (lambda =10) chosen in the last 4 experiments, while it is not the optimal value in the first one?

summary_of_the_review: Overall, my vote for the paper is a (weak) reject. I think the framework of the paper is original and the ideas are intuitive with several interesting results and implications. On the other hand, the statements of some of the results are very weak (to an extent that they are not meaningful). The writing of the main text, as well as the proofs, are non-rigorous (which was partially an intention of the authors, at least for the main text, but might have affected the paper's mathematical quality).

==== Update after response and revisions

The revision addresses my main concern about the weakness of the results of Theorem 3 and 5. On the other hand, I'm still of the opinions that the heavy uses of asymptotic representations and the choices of present thee results of the main text in non-rigorous manner have affected the paper's mathematical quality. A few other concerns are left unaddressed. I thus raise my score from 5 to 6
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Data augmentation is a common technique to improve generalization, especially when data is scarce. This paper introduces a theoretical framework for analyzing the effectiveness of consistency regularization when data augmentation is employed. In the limit, consistency regularization is akin to solving a constrained optimization problem with consistency constraints. The paper theoretically studies this limit for linear regression, logistic regression, and a two-layer perceptron with ReLU activation, and tries to characterize the benefits of consistency regularization beyond that of vanilla data augmentation. The paper then continues to experiments where it is shown that consistency regularization outperforms data augmentation on three benchmarks, and the benefits are significant especially when labeled data is scarce. 
main_review: Data augmentation (DA) is a common technique to improve generalization, especially when data is scarce. This paper introduces a theoretical framework for analyzing the effectiveness of consistency regularization when data augmentation is employed. In the limit, consistency regularization is akin to solving a constrained optimization problem with consistency constraints.
- While data augmentation is used for better generalization with less data, it is also used to suppress spurious features and generalize to unseen distributions. A discussion around that is warranted. Also, the theory unfortunately is not applicable to this other major usecase of DA.
- While this paper introduces a regularizer $\rho$ in Eq. (1), the exact functional form of the regularizer is of no use as long as it is a proper divergence between the original samples and the augmented samples. However, this is practically not true as the functional form of the regularizer can be make or break in obtaining results. This is a shortcoming of the analysis in this paper, which needs to be clearly reflected.
- Eq. (2) can be obtained as a limit of Eq. (1) when $\lambda \to \infty$ only if $\rho$ satisfies certain regularity conditions (e.g., being a divergence). No such conditions are stated in the paper, so the deduction is wrong as stated.
- The mathematical model for DA that is described in Definition 1 is limited in scope. For example, it cannot capture some of the motivating works that the paper cites, such as mixup. This needs to be clearly stated.
- The operational meaning of the DA strength in Definition 2 is unclear beyond the linear examples that are provided, as this does not capture any nonlinear relationship between features.
- As far as I followed, from a theoretical perspective, the data augmentation in this paper $\widetilde{\mathcal{A}}(X)$ is always linear for deriving the main Theorems (2-4). 
- It is not clear how Definition 2 does or can capture randomness in training examples or the augmentation function as $d_\text{aug}$ itself becomes a random variable.
- Another important relationship that is missing is the relationship between $d_\text{aug}$ and $\alpha$ (which is the number of times data is augmented). Can you at least say what happens when $\alpha \to \infty$?
- One major issue that has been ignored is that $\widehat{h}^{\text{dac}}$ as defined in Eq. (2) is not directly solvable through the empirical risk minimization framework. Even worse, it is unclear whether there is any way to devise a stochastic solver for it. Hence, the theoretical study of the paper is only applicable to a solver that is not practically existing.
- In Theorem 1, it is unclear how one would be able to relate the Rademacher complexity of $T^{\text{dac}}_{\widetilde{\mathcal{A}}, X}$ to $\alpha$ and $d_{\text{aug}}$. Henceforth, it is not clear how to interpret the improvement beyond **there is some improvement associated with dac compared to vanilla DA,** which we already knew.
- In Theorem 1, what is $C_l$?
- In Theorem 1 and its proof, the data augmentation seem to have been assumed to be a fixed linear transformation. That should be clearly communicated. In particular, in the second line of the proof on Page 13 in Appendix A.1, there is no expectation with respect to the randomness associated with DA. Even if the DA function is deterministic, the set $T^{\text{dac}}_{\widetilde{\mathcal{A}}, X}$ is random so I don’t know how to interpret the inequality.


The paper theoretically studies this limit for linear regression, logistic regression, and a two-layer perceptron with ReLU activation, and tries to characterize the benefits of consistency regularization beyond that of vanilla data augmentation. 
- Please change the notation of $\widehat{h}^{erm}$ in Eq. (3). I suggest calling this DA-ERM rather than ERM not to confuse with ERM w/o/ augmentation.
- The benefit of the consistency regularizer in LR is characterized in Theorem 2 through a quantity called d’. It is not clear to me how to interpret that even after reading Remark 2 and Example 1. Can you please provide a more intuitive explanation?

- Can you please better explain Figure 2? Is the x-axis d’? How is it calculated?

- Why is the bound in Theorem 3 presented in this obscure form rather than the more commonly used high probability bound?
- Wouldn’t data augmentation without consistency regularization also admit the same form as Theorem 3? If so, then how does Theorem 3 characterize benefits of consistency regularization? In particular, I am not sure if I can follow the argument about the generalization properties of $\widehat{h}^{erm}$ stated without proof after Theorem 3, and I suspect it to be incorrect.
- The proof of Theorem 4 is inscrutable. I could not make my way through it although I consider myself to be on the more theoretical side of the spectrum. So, I would say the mathematical exposition of the paper is not accessible to the ICLR general audience.
- I could not follow what the goal of Section 4.3 is.
- Theorem 5 is stated for realizable model classes. It is known that in this case, the generalization bounds admit “fast” $O(1/n)$ rates rather than the usual $O(1/\sqrt{n})$ rates; see Tsybakov (2004); Steinke and Zakynthinou (2020). Hence, the upper bound in Theorem 5 is order-wise loose, and I am not sure how to interpret it.


The paper then continues to experiments where it is shown that consistency regularization outperforms data augmentation on three benchmarks, and the benefits are significant especially when labeled data is scarce. While I like the results, there are several major concerns here.
- First, it is unclear what form of regularizer function $\rho$ has been used to produce the results in the experiments section. Can you please clearly explain the regularizer for all experiments.
- As is well known and can also be seen in the experiments, when dealing with overparameterized non-convex neural models, choosing $\lambda \to \infty$ practically results in convergence to poor local minima that do not generalize. For example, this can be seen in Table 1 for $\lambda = 20$ and if $\lambda$ is even further increased, the resulting model would achieve the performance of a random classifier. This is a big discrepancy between the theoretical setup of this paper and the empirical setup, and a discussion around this shortcoming is warranted.
- In Table 1, can you please explain the drop of the performance seen for $\lambda =1$? One would intuitively expect that increasing $\lambda$ from 0, the performance would increase, and then it will plateau and then start to deteriorate. Hence, $lambda =1$ performance is counter-intuitive.
- It is claimed that “the DAC regularization gives a worse performance as it falsely enforces DAC regularization where the label of the augmented sample may have changed.” However, this is not substantiated through sufficient evidence. Either change the language to “might be explained” or provide more evidence.


Typos:
- pg 4, after (1): as an regularizer -> as a regularizer
- pg 17, Statement of Thm 8: satisfies -> satisfy

References
- Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004. 
- Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Proceedings of Thirty Third Conference on Learning Theory, volume 125, pages 3437–3452, 09–12 Jul 2020. 

summary_of_the_review: This paper develops a mathematical framework for consistency regularization. Several theoretical results and empirical results are provided. Overall, I like the general idea of the paper, however, there are several major concerns with the way it is executed. In particular, the major issue is that the theory and experiments are disjoint and do not support each other. (1) The theory is too tied to linear models and it is unclear how it could be extended beyond linear models. (2) The theory is only applicable to linear models with $\lambda \to \infty$. This regime is not even viable in the empirical world when we deal with neural models (as also evidenced in the experiments of the paper). (3) While the experiments are interesting, they are not conclusive on their own and lack important details. For example the regularizer function $\rho$ is not specified. Also, baselines for these benchmarks are not compared against. While there are many things that I like about the paper, it does not tell a coherent story, and especially one that would benefit the ICLR audience, and hence I recommend the paper to be rejected in its current form. I hope the authors can clarify some of the explicit comments/questions that I have raised in my review during the rebuttal.


====== update after author response ======

I would like to thank the authors for their extensive responses to my original comments as well as the follow-up comments, and also for their revisions to the paper which has improved the paper significantly. Thus, I am raising my score from 3 to 5. While some of my previous concerns are addressed, there are many remaining concerns that would require another careful/extensive revision and would require another round of review, which is why I still don't think the paper is ready to be accepted. I would like to emphasize that I like the general formulation of the problem, and the general positioning of the paper and I think the paper would be a nice contribution to the literature once the problems (especially with mathematical exposition) are fixed. Here are some explicit pointers for the authors:

- **Imprecise and inscrutable mathematical exposition:** There are lots of imprecise statements (which also **Reviewer s3Ue** complained about) still in the revised paper. For example, what does $\gg$ mean in Assumption 2 (page 15)? At the same time, the math is not followable. I still could not follow some of the proofs.


- **Hard to gain intuition/takeaways from theoretical results:** While the authors present several results, it is hard to understand takeaways from the developed theory. While they have addressed many concerns, several still remain. For example, RHS of (the revised) Thm 5 does not depend on any of the data augmentation parameters, such as $d_{\text{aug}}$ and $\alpha$. What is the takeaway from this theorem given that the same bound also applies to ERM and DA-ERM?

- **gap between theory and practice not discussed:** Although I explicitly gave feedback to address the gap between the theory and practice, it is not well discussed yet. For example, the theory is developed for $\lambda \to \infty,$ while there is a practical sweet spot for $\lambda$ in the experiments based on the optimization challenges. While I think that this gap should not be the reason to not accept the paper, it warrants a discussion around the results and their practical applicability, which is currently missing from the paper.

I hope the authors would find these comments useful in revising their paper for a future submission.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a regularization approach based on data augmentation and develops learning bounds for that setting. The main motivation is to provide means to characterize reduction in sample complexity as a result of employing data augmentation techniques during training.
main_review: - What would be the difference between data augmentation and consistency regularization? This is unclear from the introduction and it serves as a motivation for this work. Previous work has demonstrated that regularized risk minimization problems with augmented training samples (the setting known as vicinal risk minimization) can have identical effect as "consistency regularization", i.e., low variance between predictions over original and augmented samples. Please check out the work on vicinal risk minimization and references further developing that line of work.
[1] O Chapelle, J Weston, L Bottou, V Vapnik (NIPS). Vicinal risk minimization.

- Definition 1: This definition is overly restrictive. For some instances it is natural to have the conditional distribution with larger entropy and yet the instance is a proper augmentation. There are definitely transformations of images that are more confusing relative to labels of interest, when compared to the notion of original instance. This assumption is, thus, not motivated by practical considerations and might be an artefact required for theoretical analysis.
Here, it is also important to properly introduce "original", because in different worlds pairs (x, y) sampled from a data generating distribution are different. This would then imply that the notion of original is not unique.

- Definition 2: It is common actually that the data lies on a low-dimensional manifold and augmentation is in a number of cases just a walk over that manifold. Thus, I see no reason why this metric would be of any use in assessing the informativeness of data augmentation. Also, the difference is the perturbation over the input space which might have nothing to do with the manifold that we would like to learn and over which the data generating distribution actually operates.

- Consistency regularization: What is so special about Eq. (1) in the context of prior work (not discussed nor covered in details)? Is this not equivalent to learning with empirical risk minimization and augmented samples (known as vicinal risk minimization for 20+ years)? For the latter, it can be demonstrated theoretically that it minimizes the variance over the neighborhood in the instance space defined by augmented samples. I can see that Eq. (1) might provide more flexibility when it comes to the enforcement of label alignment over such neighborhoods but that needs to be demonstrated. The vicinal setting is also quite flexible.

- The theoretical results are under restrictive assumptions and in my understanding apply only to linear models. Theorem 4 is an attempt to obtain a theoretical result on the effectiveness for two layer neural network, but the assumption $(x_i^{\top}B)_{+} = (x_{i,j}^{\top}B)_{+}$ actually restricts this to linear models as well.

- Experiments: The performance improvements are rather modest, 1% relative on CIFAR-100. In the training setting, were the batches ordered in the same way? The problem is non-convex and that might impact the generalization performance.
- Table 2: The experiment with different number of samples 1,000 - 20,000: Why only 3 augmented samples per training instance? In such cases, augmentation typically adds many more samples and it would be nice to see the results with 10+ additional samples per training instance, as in the case for the experiment in Table 1.
- Table 3: How can the performance be consistently the same with 3, 7, and 15 augmented samples? This might be an indication that the augmentation scheme does not do enough to describe the local neighborhoods around training samples. This, in turn, might then not be an objective assessment of the effectiveness.
Table 4: The same argument as for Table 3, one would expect much more differentiation between numbers for "strength" 2, 5, and 10. In fact, this experiment increases my scepticism in the utility of the $d_{aug}$ as a measure of augmentation informativeness.
summary_of_the_review: The assumptions under which the paper operates are quite restrictive and do not see that they hold in practice, and thus apply to widely used data augmentation schemes along with deep learning models. The crux of the theoretical contributions is restricted to linear models, which further limits their scope. The paper does not also cover well the prior work on empirical risk minimization problems, especially the line of work on vicinal risk minimization. Experiments show rather incremental improvement (1% relative) and it is quite strange that there is no substantially larger effect of augmentation when the replication factor goes from 3 to 15.
review_title: null

Meta-review: This paper shows how constraining the representation to be invariant to augmentation shrinks the hypothesis space to improve generalization more than just introducing additional samples through augmentation. I agree with the reviewers that this is a novel, intuitive, and interesting finding. However, there were many technical and clarity issues with the original submission. These were partially addressed by the authors in the rebuttal. The reviewers appreciated the authors' efforts and commitment in the rebuttal, but my conclusion from our discussion that this paper requires another round of revisions. I hope the authors would follow the reviewer's comments, improve the paper, and re-submit.
Decision: Reject