Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper is stuffed with mathematical theorems which makes it almost impossible for me to evaluate the contribution of the work without going through the proofs in the appendix, making this paper more suited for a journal than a conference with 8 pages limit in my opinion. They consider additive Gaussian noise as a data augmentation technique for mini-batch SGD over a simple linear regression with Frobenius loss. The main contribution of the work, as far as I understood, is to derive a range of possible annealing learning rate and additive noise power in Theorem 6.2 that can guarantee convergence of SGD to the global minima of the Frobenius linear regression loss which is convex. But I'm not sure about the derivation; for instance, take x=y=0.4 and e=0.3, then $W_t$ does not necessarily converge to $W_{min}$ in Theorem 6.2, right? Or have I missed something? 

Anyway, my biggest problem with the paper is the generality of the proposed framework, which only takes into consideration additive noise and depends strictly on the calculation of gradients as the Frobenius loss illustrates. The author tried to explain a rough idea about how to handle a nonlinear case on Page 4, but this approach can be dramatically cumbersome for the deep neural networks as it needs the calculation of Hessian and gradient with respect to the input x even! Besides, the derivations strictly depend on the additive noise power model $\sigma_t$, but the author claims that their framework is applicable to advanced data augmentation techniques such as Mixup. This is not possible in my opinion. For instance, take a data augmentation technique like Mixup which is not totally data-agnostic such as additive noise. As you know, Mixup is applied to each mini-batch after shuffling in each step of SGD, resulting in a convex combination of the samples of different classes.  In other words, there is no parameter like the noise power $\sigma_t$ that you can control during each step of SGD. There is only $\alpha$ which is not quite flexible either in Mixup as it usually takes a value around 0.2. 

Therefore, I strongly doubt the universality of the proposed framework to deal with various networks and data augmentation techniques that are mostly used by practitioners nowadays and do not see the paper as a good fit for a conference like ICLR.

After rebuttal: I thank the author for their response and have raised my rating by one after reading the author's response, but my concern still holds unfortunately regarding the whole approach that the author has taken to analyze the effect of data augmentation. Therefore, I'm still not confident about my rating.
review_title: An analytical study of additive noise data augmentation in SGD for linear regression loss

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper considers stochastic gradient descent with noisy gradients. In contrast to the standard setting (e.g., gradient Langevin dynamics) where additive Gaussian noise is added to the model gradient, this work focuses on additive perturbations of data instances. As a result of this, the optimization objective changes throughout the training process because the data is no longer static/fixed but assumed to be sampled from some distribution governing the perturbation process (see Eq. 3.3).

Section 4 restricts its consideration to multi-output linear models. A review of prior works shows that stochastic gradient descent with Gaussian perturbations of the inputs is in that setting equivalent (under suitable conditions on the loss) to optimizing regularized objective with the squared Frobenius norm of the weight matrix acting as a regularizer. The problem is then how to characterize the relation between the standard deviation of the Gaussian perturbation measure and learning rate. The main contribution is Theorem 5.1 which provides conditions under which the stochastic gradient descent converges to the min-norm solution. Theorem 4.1 is a special case designed to illustrate the relationship between perturbations and learning rate. The main result is further extended in Theorem 6.1 to mini-batch stochastic gradient descent.

# clarity
I find that the paper is to a certain extent well-written. Still there are parts which are difficult to follow and a revision would be required. For example, I have had problems below Eq. 5.3 when referring to $Q_{||}$. It is not clear what is being projected to $V_{||}$. I have lost track at that point and this then complicates understanding of Theorem 5.1 and pretty much everything that follows. Moreover, checking the proofs was equally confusing.

# originality
The title of this work is miss-leading and not really sure why this is the case. I was expecting to see characterizations of more complex data augmentation schemes that span group theory (e.g., Lie group perturbations). Focusing on additive Gaussian noise might be better suited to stochastic gradient descent with noisy gradients. The noise is different from, for example, Langevin dynamics but there are similarities certainly. Given that I am not an expert on numerous settings and versions of stochastic gradient descent it is difficult to assess the originality. Still, I think that the setting with input perturbations is interesting and worth studying. In addition to this, it might be worthwhile to mention in the abstract (if not in the title) that the focus is on linear models.

# quality
I find the theoretical contribution non-trivial and technical. Still I am not completely convinced in the significance. The first reason for this is in the quite robust nature of Theorem 5.1. I find it difficult to assess how realistic the assumptions are in that theorem (see 5.7 and 5.8). The work attempts to give a more readable result in, for example, Theorem 4.1. The confusing part is what happens to assumptions 5.7 and 5.8. Are they assumed to hold?

I am also not convinced about the related work on data augmentation and stochastic gradient descent with noisy gradients. I am unaware of other works on stochastic gradient descent studying this particular case with input space perturbations. Still some previous works that might be related are:
[1] Vicinal Risk Minimization (NIPS). Chapelle et al.
[2] Variance-based Regularization with Convex Objectives (NIPS). Namkoong & Duchi.

I would also expect a detailed analysis of the contributions relative to:
[3] A Kernel Theory of Modern Data Augmentation (ICML). Dao et al.

review_title: ICLR 2021 Conference Paper753 AnonReviewer2

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a framework that re-interprets data augmentation as stochastic optimization for a time-varying sequence of objectives. The paper also provides a theoretical analysis of the simple case of over-parameterized linear regression. 

Comments:

1. In section 4, the paper claims that the gradient descent will not converge to W_min because gradient descent “cannot see” the directions in the e in the orthogonal complement of the column span of XX^T. However, it’s easy to choose an initial point W_0 which is in the column span of XX^T. Then the gradient descent may converge to W_min.

2. For over-parameterized linear regression, we can directly compute W_min from the data matrix X and Y. The authors should point out the situation where data augmentation is necessary.

3. Thm 5.1 and Thm 5.2 requires some conditions on W_t, which depends on the algorithm rather than the data.

4. I think the authors should add some experiments to verify the effectiveness of their methods. For example, the experiments can compare the performance of gradient descent and data augmentation with Gaussian noise.
review_title: Some necessary discussions about other possible solutions are missing

final_score: rating: 7: Good paper, accept
review_content: **Summary.** Authors present a novel theoretical framework for assessing the effect of data augmentation (e.g. mini batch SGD), noise addition and the learning rate setup in gradient-based optimization with overparametrized models. Despite the analysis is only performed for linear regression, results extend the well-known Monro-Robbins theorem on rates of convergence. The manuscript is a first step for future analysis of the aforementioned techniques with other type of models and/or loss functions.

**Strengths.** The paper is extremely well-written and even being theoretical, authors did an effort for making it fully understandable to non-familiar readers. I particularly recognize that the line of argumentation is thorough and step-by-step decisions and equations are carefully described with intuitive sentences. i.e. first paragraphs in section 4.

The organization of the paper is good as well, first presenting the type of regression model to be analyzed, the fact of augmenting data, second with the noise-additive models and their implications and finally, connecting all the previous insights with the Moneo-Robbins theorem for a general result that authors fit with mini-batch SGD.

Authors recognize the limitations of their analysis since it is focused in linear models, but to me, this is not an issue for this type of paper. The results, focused on three trending methods as data augmentation, learning rate selection and additive noise are elegant, and as authors mention it only relies on first order moments. 

I took a look on the appendix demonstrations and extra information, results seems to be reproducible. References are pretty contemporaneous (last two years).

**Weaknesses, Questions & Recommendations.** 
The main weaknesses (to me) in the paper are:
[W1]. Data augmentation is described in a very general way during the first 5-6 papers without much description, and, in the last page, authors focus on the particular case of mini-batch SGD. I understand the reasons for doing this, but preferably, a comment on the application to the mini-batch SGD case would help at the beginning. 
[W2]. In a similar way as in [W1], I missed some information about the conditions of $D_t$ wrt $D$ in the beginning of section 3.
[W3]. References are “clustered” in the introduction and related work, but later on, not many of them are connected to the main text. So, connections are difficult to establish with the results and the argumentation. One example is in Section 4, where I missed some cases or references about the synthetic additive noise.

Questions:
[Q1]. Could authors enumerate or describe cases/examples of data augmentation different from mini-batch SGD? References would help. (To make an idea)
[Q2]. In pp.4 authors mention a sufficiently smooth function g. How smooth this function must be? How can we measure this sort of smoothness.
[Q3]. Similarly as before, additive noise is referred with a small \sigma_t. Which is the scale of sigma values considered?
[Q4]. I liked when authors expand the previous results to the case of having the expectation term E[X_t X_t^{\top}]. Just a silly question, in this case, could the expectation operator work as a lower bound? Similarly as in free energy methods or similar? If so, maybe working with the lower bound could help for obtaining similar results for non-linear models.
[Q5]. I do not see why V_{||} in Eq. 5.3 is independent of t as mentioned below Eq. (5.4). The expected value remains stable?

Recommendations:
[Rec1]. A bit more of intuitive descriptions in section 4. for Eq. 4.1. and Eq. 4.2 would help to follow posterior explanations.
[Rec2]. Similarly as Rec1, a bit more of description about Eq. 5.12 and the intrinsic time would help. I lost myself a bit on that part.
[Rec3]. There a few “negative” sentences in the last two pages: “Though SGD is not often considered as a form of …” and “the restriction of the present work to linear models is…”. I think rewriting them in a more positive way would be better. This is an opinion.

**Reasons for score.** I vote for accepting the paper at the conference. Despite the fact that the work is limited to linear models, I think the results are interesting and authors demonstrated a deep comprehension of the main strategies for optimization/fitting of models that are nowadays used everywhere. I would appreciate if authors elaborate a bit more during the rebuttal on the questions pointed out and particularly in the examples of data augmentation.

**Post-Rebuttal Comments.** Thanks for the author's response and their dedication during the rebuttal period, I re-read the updated version of the manuscript and authors did an effort for adding extra content and editing based on the questions and recommendations. In my particular review, they answered and solved the questions that I did. I understand the points addressed by the other reviewers and the theoretical limitations of the method. However, I still have a positive opinion about the paper, and I believe that the aforementioned limitations are well indicated in the paper, something that is valuable. For these reasons, I keep my score.
review_title: Stochastic optimization, theoretical results, update of Monro-Robbins theorem to data augmentation, additive noise and learning rate.

Decision: Reject