Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: This paper rigorously analyzed the convergence of data augmentation in linear regression under the convex setting. Its main result gives sufficient condition on the joint schedule of the learning rate and the augmentation strength under which asymptotic convergence rates are provided. Specializations The above result is then instantiated for additive Gaussian noise, random projections.
main_review: Originality: The convergence results of data augmentation algorithms are solid. The analysis techniques seem non-trivial

Quality: Some assumptions seems to strong. How to justify the assumptions (3.10) (3.11) and (3.12) are reasonable? Something for assumptions (3.7) (3.8) and (3.9).

Clarity: Overall, the writing is clear to me. 

Significance: First, I'm not convinced by the experimental results. It only runs on simulated data for additive Gaussian noise case. It would be better if the authors can provide the results for random projection case, and more importantly, if some real datasets can be used. I think additional experiments would have made the paper much stronger. Second, this paper only studies optimization of data augmentation. However, I think the most interesting and important thing is about the generalization of data augmentation, since the key goal of using data augmentation is to avoid over-fitting. Besides, it would also be better if the authors could provide some generalization results (such as testing error) in the experiments. 
limitations_and_societal_impact: No. See "Significance" in Main Review section.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper rigorously studies the sufficient conditions of the convergence of GD/SGD when data augmentation is applied to learn an overparameterized linear model. Some of the sufficient conditions are also necessary. In particular, the sufficient conditions are formulated in terms of the learning rate, 2nd and 4th moment of augmented data matrices.
main_review: -	This paper presents a solid theory that shed light on the understanding of the hyperparameters of data augmentation and GD/SGD, which affords many interesting insight, like Fig. 3.1. On the other hand, more numerical analysis with synthetic data is needed to further test the theory. In particular,
o	No numerical results are presented for the random projection augmentation in Sect. 5
o	It would be interesting to see if the sufficient conditions are sharp. If the selection of hyperparameters start to deviate from these conditions, would the error be slowly increasing, or would there be a phase transition from small error to large error?
-	Does the convergence result in Theorem 4.2 hold for any selection of minibatch size S_t that may be time dependent? Does the selection of the minibatch size and sigma_t need to jointly satisfy some constraints?
-	In Fig. 4.1, why does the MSE of Gauss exp schedule performs nearly the best for GD, but only outperforms the Gauss const for SGD? What is it in GD and SGD that leads to such difference?
limitations_and_societal_impact: Limitations and society impacts are adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the joint effect of data augmentation and learning rate scheduling on the optimization trajectory of overparameterized linear model. The authors study the conditions under which (S)GD will converge to the min-norm interpolator, even when the data augmentation distribution changes over time. With a more careful analysis, the authors also study the rate of convergence. Specific augmentations studied here are additive Gaussian noise and random projection.
main_review: The proofs are technical and the overall problem studied is interesting. It is important to study how data augmentation affects the optimization trajectory. As the authors have mentioned, my main concerns are that 1) the model discussed here is limited to linear case, how can this case provide us insight for more general classes like kernels? and 2) although the problem formulation is general enough to include many types of augmentations, the detailed results are derived only for additive noise and random projects, which may not be what people mostly use nowadays.

What appears more concerning is that it is unclear to me why studying the convergence to the min-norm solution is a good idea. On a high level, augmenting with noise should make the learned minimizer more robust (at least to noise). As the authors have mentioned (and proven before), training with random noise corresponds to training with l2 regularization (eq 3.2). Therefore I'm not sure why the authors consider min-norm solution as the limiting classifier. I'm also curious what if the condition eta_t->0 is relaxed (at least is allowed to decay much slower), the limiting behavior may be more interesting.
limitations_and_societal_impact: The limitations has been adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a theoretical framework on the convergence of (S)GD when considering learning rate and data augmentation. It presents the consistency and convergence rate results of a general optimization method, and gives some detailed examples of adaptive Gaussian noise and random projection. 

main_review: Originality: this paper is novel based on my knowledge. It provides a new theoretical framework to justify the convergence of optimization under changing learning rate and (either random or arbitrary) data augmentation. The results not only covers the situations where data augmentation is independent to iteration t, but also include more general results when data augmentation is related to t.

Quality and clarity: the paper is well written and the main text is easy to understand. The claims are well supported by the theoretical results. The detailed examples for the general theorems are clearly written. The authors are careful and mention both strengths and weaknesses (only for linear regression model) of this work. 

Some minor issue: 

(1) the current numerical experiments are weak to support the claims. However, since this paper is already well supported by theories, please consider moving the experiments to appendix and emphasize some other important things.

(2) the statements from line 120 to 128 are somewhat confusing. Please specify why they cannot be obtained from Theorem 3.1/3.2. If A_t is randomly generated and independent to iteration t, they can be viewed as some new data distribution, so they are supposed to converge in the optimization.

Significance: this paper provides detailed theories in the optimization of linear model, extending to other complicated algorithms is challenging, but it could potentially provide deeper understanding in data augmentation.




limitations_and_societal_impact: Some limitations are mentioned in the above.
There is no negative social impact.
review_title: null

Meta-review: As far as I am aware, this is the first work that presents theoretical results for optimization dynamics with data augmentation, and three of the four reviewers found the paper to be of sufficient significance and impact to warrant acceptance. I ultimately found the argument that the paper should be rejected on the grounds that it analyzes optimization dynamics instead of generalization error unconvincing. While I generally agree that the primary motivation for data augmentation is to prevent overfitting, it's not obvious to me that the effects of data augmentation on optimization are well understood or trivial, and it's not even a priori obvious to me that optimization should necessarily converge for all data augmentation schemes outside of basic ones like additive Gaussian noise.
Decision: Accept (Poster)