Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: An influential line of work has revealed that deep neural networks can exhibit non-monotonic behavior in their generalization error (double descent) as a function of model size, dataset size, and training time. Recent (and old) theoretical work has demonstrated that even simple models like linear regression exhibit the same non-monotonic behavior as a function of model and dataset size. The authors of this work build on this literature by demonstrating that linear teacher-student models trained with gradient descent can exhibit double descent as  a function of training time. Using replica theory, they derive a closed-form expression for the generalization error of this model as a function of training time. They show that double descent can arise when the student is trained on anisotropic data which includes a set of high SNR features and a set of low SNR features. Finally, the authors demonstrate a qualitative match between the generalization error behavior of linear teacher-student regression and a ResNet18 trained on CIFAR10 as a function of training time and regularization strength.
main_review: This insightful work demonstrates that another apparently exotic behavior of deep neural networks, non-monotonic generalization error over the course of training, is already present in simple, analytically tractable linear models. The paper is clearly written, the theory is well-motivated, and the results are neatly presented. I only wish that the authors dove more deeply into interpreting the behavior of their analytical theory: (1) what happens when features of more than two scales are present? is there triple descent in the generalization error? (2) how does epoch-wise double descent differ from model-size double descent? one difference seems to me that linear teacher-student models trained on isotropic data exhibit model-size double descent but apparently not epoch-wise double descent, which requires anisotropic data. What explains the difference? Moreover, the peak in the model-size double descent curve has a nice interpretation as the model size necessary to perfectly interpolate the training data. Is there a similar interpretation for the peak of the epoch-wise descent curve? More broadly, epoch-wise double descent is sometimes explained by training time controlling model complexity in analogy to model-size double descent - but this work appears to suggest a different mechanism. It would be interesting to discuss this further. (3) How do the results change as a function of the the overlap between the teacher and the anisotropy in the data? 

Note: I believe the color code in Fig. 2 is incorrect, and is misleading. I think the colors of the large and intermediate regularization strength curves should be flipped.
summary_of_the_review: I think this work is a valuable contribution which captures an interesting feature of the training dynamics of generalization error in deep neural networks in a simple, analytically tractable model. The close qualitative match between the behavior of the simple model and a ResNet on CIFAR10 suggests that the mechanisms identified here may be general, and the theory derived by the authors lays the groundwork for deeper investigations into the training dynamics of generalization error in neural networks.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work studied epoch-wise double descent using linear model as a proxy. Basically, authors proposed a linear teacher-student models to established analysis and used random matrix theory (rmt) to interpret the learning dynamics. Some simulation on the well-posed (n>p) linear regression problems backups the theory. Some real-world experiments based on ResNet-18 and noisy labels also demonstrate the relevance of proposed theorem.
main_review: My major concerns include:
1. The implicit regularization effects of SGD/GD on least square linear regression may perform as a Ridge regularization. (Ali and Ray Tibshrani's work at ICML 2020), where the number of learning epochs/steps are connected to the inverse of lambda (strength of Ridge effects). It is not superise that when you tune the lambda of Ridge, certain double descent would appear in testing accuracy.  Shall authors discuss the connections between this work and Rayn Tibshirani's works on ICML 2020 and AISTATS 2019 on Ridge-style implicit regularization of GD and SGD for OLS?

2. whether authors tried to connec their work to the linear regression problem under HDLSS settings (d>>p). In such setting, the analytical results of SGD convergence might be different (inclusion of pseudo inverse). In that sense, the result would lead to Ridgeless regression. There are quite a lot of works studying the double descent of Ridgeless. Shall authors discuss the connections between this work and those works?
summary_of_the_review: It is a solid work with theoretical analysis and empirical evaluation. Though it may connect to many pioneering works in the field, authors should discuss these connections.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically analyzes a student-teacher setting for which epoch-wise double descent occurs. (Epoch-wise double descent, previously discussed in the literature, refers to the non-monotonicity of the population error as a function of training time.) More specifically, the setup is: (a) a linear teacher with Gaussian noise; (b) a linear student whose inputs are a linear transformation F ("modulation matrix") applied to the teacher's inputs. The inputs are d-dimensional and there are n training samples. Exact analytic expressions for the test error can be derived by utilizing the replica method in the limit of n, d -> \infty. The case analyzed in most depth is a setting in which F has two scales for its singular values (with high degeneracy) -- c.f. Assumption 1. Both the theory and finite-size simulations indeed exhibit epoch-wise double descent depending on the choice of setting parameters (e.g. strength of regularization and condition number of F). The intuition behind this is that when the scales are well-separated and learnable (e.g. regularization not too strong), overfitting of the faster features occurs (leading to a rise in the test error) before learning of the slower features (which subsequently decreases the test error).
main_review: Strengths:

--The analysis of a simple model that exhibits epoch-wise double descent is illuminating and worthwhile, so the topic is of general interest.

--The concrete findings from the paper (exhibited in the numerics of Fig 2, Fig 3) help build intuition for the phenomenon; the agreement between finite-size experiments and analytic theory is good.




Weaknesses:

--Numerous typos in the main text and appendix that need to be addressed & divert the flow of the calculations for the reader. See more on this below. This also made it a bit challenging to check the calculations in full.

--I am not certain as to whether there are notable technical advancements in the paper. Relatedly, I am not positive if the intuition involved this paper (e.g. introducing multiple scales into the problem) has appeared before; for instance, can there be more discussion of how this paper relates to Heckel & Yilmiz (2020), as well as Stephenson & Lee (2021)?

--I think this paper could improve a bit on how the student-teacher model could be connected to the realistic setting (deep neural network with label noise on training data). Although I appreciate full analysis of a simple setting, I wonder if there is more that can be done (numerically or otherwise) to make a connection. Does the label noise effectively create two scales for the problem?

--I would like to better understand some of the prior results this work relies on for the analytic calculation; a self-contained discussion of the exact results drawn from older literature in the appendix would be helpful. For instance, regarding Eq. (17) and the probability distribution induced by SGD. Is this for a fixed choice of initialization, and considering the stochasticity / distributional nature arises from the Gaussian noise in SGD (Eq. 4)? In that case, how robust is this to other choices of noise? What justifies then the time-dependent distribution in Eq. 18, since there isn't a notion of equilibrium in the finite time case? Overall, I also think this paper could be clearer about how it treats the various sources of randomness (e.g. why it chooses to do averaging over SGD noise separately from the average over x and W).

--(Not a major source of weakness, but a suggestion.) Some of the writing and terminology seem too imprecise to be useful. For instance, I would suggest removing the first paragraph on Sec. 2.1 since it is somewhat tangential (discussion of microscopic & macroscopic quantities in the following paragraph are sufficient). The authors also write about the "interaction" of different feature learning speeds, which makes me think of a precise notion of interaction in the sense of physics, although I believe the authors simply mean the "presence" of different scales.

--The abstract mentions usage of tools from random matrix theory -- where does this appear?


Typos in manuscript & other comments:

--Eq.(5): Since there is an expectation over the teacher noise \epsilon, why isn't the loss in terms of (y-\hat{y}) instead of (y* - \hat{y})?

--It is common to average over the draw of finite-size training dataset. I am not sure how this appears in Eq. 5; could the authors comment on this? I understand E_{x} to be over the population distribution on x, and E_{W, \epsilon} average over the choice of teacher model. 

--Above Eq. 8, it is written X = F^T Z, but X = ZF is used in Eq. 8.

--Eq. (20) there is a reference to W* but I do not find it introduced earlier. (It seems these are the teacher weights, W -> W*?)

--Figure 2: a/b/c/d figures are mislabeled relative to the captions. In caption (b), k -> \kappa.

--Eq. (23): from the first to second line, how did z -> x without an appearance of F?

--In Eq. (24)/(25), the average over x gives rise to Kronecker delta orthogonality; since z ~ Normal, how does this hold for generic F? Is there an assumption of orthogonality on F?

--Eq. (28): Z^n should be labeled Z^r.

--Eq. (29): what is x^*? As with earlier equations, I assume this equation refers to the teacher network but don't see input z referenced.

--Eq. (30): capital N is introduced. \mu index also previously referenced training sample index (up to n).

--Eq. (31): usage of capital P, is this same as lowercase p?

--Eq. (35): two lines are copied identically.



summary_of_the_review: My slightly lower score is based on the following factors:
--Since the focus of this paper is not empirical (e.g. the observation in realistic networks has appeared before), the contributions come primarily from the theoretical side. In this respect, I am not sure if similar insights in linear models & control of multiple scales for epoch-wise double descent have appeared in earlier works and would appreciate if the authors could comment on this in detail. 
--The typos / errors made the calculations more ambiguous and harder to assess the correctness of the final result.

I would be happy to consider adjusting my score based on the author's response.
review_title: null

Meta-review: This paper examines the time-dependent generalization behavior of high-dimensional student-teacher linear regression models. It introduces a simple two-scale covariance model and examines the exact solutions for the dynamics, finding a tradeoff between the fast- and slow-learning features, leading to epoch-wise double descent. Qualitative comparisons are made with the SGD dynamics of ResNe18 on CIFAR-10.

The reviewers offer split opinions on this work, with most reviewers finding strength in exhibiting the complex behavior of epoch-wise double descent in a simple and analytically-tractable setting. Weaknesses highlighted in the discussion include clarity, discussion of prior work, and rigor of the analyses.

I believe a clear demonstration and analytical explanation for epoch-wise double-descent would certainly be of interest to the ICLR community, and I concur with the reviewers who emphasize these strengths of the paper. However, as one reviewer mentioned, this paper is primarily a theoretical work, and as such, the main theoretical advancements over prior work should be clear, and the novel results should be sufficiently rigorous. In this regard, the paper is lacking, as detailed below.

First of all, the discussion of SGD is imprecise, with no explicit definition of the optimization method that is actually being performed. What is the batch size? How is the sampling performed? What is the learning rate/schedule? The formulas in Secs. 2.1-2.2 suggest that full-batch gradient descent is being performed. In Sec. 2.3, stochasticity from SGD is induced via a Gibbs distribution. However, contrary to the discussion, I don't think that this is a "well-known" **result** (though of course it is a well-known **model**), and in high-dimensions I am not sure it is even correct (see e.g. [1]).

Second of all, even assuming the Gibbs distribution, the substitution on line (23) is only justified in words, whereas the cited results from Ali et al., 2020, only provide a bound. What is meant by "$\approx$"? Some discussion is given about this step of the derivation, but more precise statements would really help make the argument convincing.

Finally, the derivations seem to rely on the replica method from statistical physics, which is not rigorous. While I am generally supportive of such methods for technically challenging problems that do not readily admit alternative analyses, given the simplicity of the linear model setup here, I believe a more rigorous approach would not be prohibitively difficult. At the very least, some acknowledgement should be given about the lack of rigor in the derivation.

Overall, this paper presents a simple and analytically tractable model that sheds light on the importance phenomenon of epoch-wise double descent. Unfortunately, the presentation is not sufficiently clear and the derivations not sufficiently rigorous to merit publication at this time.

[1] Paquette, Courtney et al. “SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality.” COLT (2021).
Decision: Reject