Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: UPDATE: The authors have addressed my concerns. Taking also into account the responses to the other reviews, my positive view of the paper has been confirmed and I have therefore increased my score.



Summary:

The paper deals with the phenomenon of double descent as a function of training time and offers an alternative explanation as a superposition of bias-variance tradeoffs with minima at different epochs. The analysis is first done theoretically for an early stopped linear least squares problem with different scalings of the features as well as a two-layer network. For both cases it is shown theoretically that the risk function is approximated by a function consisting of overlapping bias-variance tradeoffs. By controlling the stepsizes and initializations it is then possible to mitigate double descent. Motivated by this theory, the authors then consider two recent architectures empirically, a 5-layer CNN and a ResNet model, and show experimentally how double descent can be avoided by adapting the stepsizes corresponding to the last layers. 


Strengths:

- The paper provides a novel theoretical explanation of the epoch-wise double descent phenomenon, which recently has gained some interest in the community. Understanding the epoch-wise descent better is important to better understand early stopping in neural networks.
- The theory also suggests a simple and effective mitigation strategy by adaptation of the different stepsizes corresponding to the different U-shaped curves appearing in the approximate risk formulation. This strategy is shown to work not only for the theoretically analyzed models, but also empirically on two common standard architectures, namely 5-layer CNN and ResNet. Thus it may have significant impact for the practical performance of neural networks and may be adopted by the community.
- The paper is well-written, well-motivated, and relatively easy to follow, taking into account the technical nature of the problem.


Questions:

- By choosing the stepsizes according to Prop. 1, we achieve the lowest value of the approximate risk expression (1). However, since the quality of the approximation in (2) also depends on the choices of the stepsizes, how can we make the conclusion that this also corresponds to the lowest risk?
- In the discussion after Theorem 2, I do not quite understand what is meant by the statement "the theorem pertains to the kernel regime where the network behaves similar to an associated linear model". Maybe you could elaborate a bit on this statement. 


Conclusion:

Overall, the paper constitutes a solid contribution to the understanding of epoch-wise double descent as well as a practical way to mitigate and improve the early stopping performance. Moreover, the paper is well-written and technically sound. I vote for acceptance.


Minor comments:

- Page 2, before Section 1.1: "overparamterized" -> "overparameterized"
- Page 4, before Theorem 1: "as formalized be the theorem" -> "as formalized in/by the theorem"
- page 4, after (2): "provided the model is sufficiently underparameterized, (i.e. $\frac{d}{n}$ is large)" -> should be "$\frac{d}{n}$ is small"
- Page 5, in "Network model": double "and"
review_title: Solid contribution to the understanding of epoch-wise double descent and practical way to improve early stopping performance

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the phenomenon of double descent. The claim is that double descent is caused by the superposition of multiple bias-variance trade-offs arising from the fact that different parts of the network are trained at different speeds. To corroborate this claim, the following main results are presented:

(1) Analytical results for linear regression in the under-parameterized regime (input dimension $d$ much smaller than the number of training samples $n$). In particular, it is shown that the risk of gradient descent is close to the sum of $d$ U-shaped curves (this is dubbed as the "risk of early stopped least squares"). The bound depends on the covariance structure of the model and, in case such a structure is known, one can optimize the learning rates associated to the various components so as to minimize the risk. 

(2) Analytical results for two-layer networks in the "lazy regime". The author(s) provide an upper bound on the risk which has again the form of the sum of U-shaped curves. The bound depends on the singular values/vectors of the Gram matrix associated to the network. By estimating (or knowing in advance) the spectrum of such a Gram matrix, one can eliminate the double descent phenomenon and optimize the risk.

(3) Empirical results showing how to mitigate the phenomenon of double descent by choosing different step sizes for different layers (or different components). The author(s) provide results both for the toy models analyzed theoretically (see Figure 1 and 3) and for neural networks used in practice (5 layer CNN and ResNet-18 trained on CIFAR, see Figure 4 in the main paper and Figure 6 in the Appendix).

The analysis for linear regression is quite simple. The analysis for the two-layer network is more involved and it heavily relies on previous literature, in particular recent work by Heckel & Soltanolkotabi.

Overall, the paper is well written, the results appear correct (although I did not do a thorough check on the appendix), and the perspective proposed by the paper is fresh and interesting. However, I am not fully persuaded of the impact that the results of the submission will have on the community. In fact, the paper presents the following major weaknesses:

(a) Theorem 2 provides an upper bound on the risk of two-layer networks. However, there is no indication of how good this upper bound actually is. Is it tight in any way? Does it even go to 0 as n and t grow? It seems that the bound on the risk comes from a bound on the training error, and the training error is known to vanish (as $n$ and $t$ grow) in the over-parameterized regime considered here. However, after staring at the formula for a while, it is not obvious to me that the RHS of (5) can be made arbitrarily small (by taking sufficiently large $t, n$). 

(b) The risk of early stopped least squares seems to vanish by taking sufficiently large $n, t$. However, the dependence on t of the RHS of (2) is not clear. There is no explicit t in the formula. Is the dependence hidden in the numerical constant c?

(c) The numerical results in Section 4 are not convincing. The double descent phenomenon appears mitigated, but the test error improves only slightly for the 5-layer CNN (Figure 4) and it is even worse for ResNet-18 (Figure 6 in the appendix). I agree with the author(s) that choosing different learning rates can mitigate double descent. However, it is not clear at all whether this would actually improve performance at the scale of a practical network.  

Minor points:

(d) Is it possible to provide bounds on linear regression in the over-parameterized regime? Do you expect to obtain results somewhat similar to (Hastie et al., 2019)? 

(e) Can you make the probability of Theorem 1 arbitrarily close to 1? Now, it is at best 1-2e^{-32}.  

(f) Could you add some technical details explaining how your approach differs from the vast literature on the analysis of two-layer networks in the lazy regime? This would help assess the technical novelty of the paper. 


--------------------------------------------

UPDATE AFTER AUTHORS RESPONSE: The authors partially addressed my concerns and I (slightly) increased my score. 
review_title: Interesting take on double descent, but there are several issues

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper provides an interesting analysis and direction to improve generalization capability by eliminating double decent during training by setting learning rates differently for each feature and using early stopping. In terms of technical contributions, the authors prove double decent phenomenon during training due to bias-variance tradeoff in toy problems, and provide experimental results with synthetic data using CIFAR-10 dataset with random label noise.

In theorem 1, a type of quantifier over t is ambiguous. As I did not see, for example, a (union) bound over t in the main text, I would suspect that the authors mean that t is fixed for this probabilistic statement. But then the relationship only holds for a single t with high probability, which does not support the claim of the paper, which is about a phenomenon for all t up to an early stopping time. So, I think it should be taking some probabilistic bound over time. In either case, the authors can specify it to be clearer. 

I like the idea and potential of this direction. Indeed, reading this paper was like attending one of the best talks in my experience. My major concern is that supporting evidence is very week for a technical paper (although it is great for a talk). The main theorems are proven only in very simple unrealistic settings. Theorem for neural network training is really theorem for shallow linear models with the fixed kernel, NTK. This is not for neural network training. The assumption that k >= n^10 in terms of the order is unrealistic, and known to make the neural network to be basically a shallow linear model. As a sufficiently wide neural network is a shallow linear model with a fixed NTK, theory is trivial and simpler in a sense than that of deep linear networks: for example, deep linear network change NTK during training unlike the wide network and its effect was recently studied in https://arxiv.org/abs/2003.02218 (deep linear network with one hidden layer) to understand neural network beyond NTK regime. 

Given the weakness in theory, it will be nice to have more comprehensive experimental results. I think if there are more extensive experimental results, this paper is already strong without improving theory. It is understandable that proving theory under practical setting is challenging for neural networks. However, in the current form of the paper, experimental results are not conclusive. It only uses a single synthetic data (CIFAR-10 with random label noise, instead of original CIFAR-10), does not report error bars and statistical information of the experiments, and does not report sensitivity of hyper-parameters or the way the authors picked hyper-parameters in details. In such an experiment, one can easily construct an artificial case to support the claims. 

It is also highly desirable to conduct experiments with a real dataset without adding random label noise. It can be an artifact of Gaussian (or simple) random label noise. In real worlds, the label noise tends to be much more complicated and the purpose of the experiments should confirm the theory in the simple setting to be valid in some extend in such a more realistic case, instead of keeping the noise to be an artificial one. 

In Figure 4, test errors (and training errors) are much better for the case of ii at the beginning of training, epoch = 1. Can you report the values at epoch = 0 to make sure that both are the same initially? In either case, most improvements seem to be coming from the first epoch. At the first epoch, training error is also better for the case ii, instead of only testing error. Therefore, this observation would change as we change step size and other hyper-parameters (for example, batch size and momentum). 


- Typo: “as formalized be the theorem bellow” -> “as formalized in the theorem bellow” in page 4.

review_title: Very interesting idea and direction but not with strong supporting evidence

final_score: rating: 7: Good paper, accept
review_content: UPDATE: The authors have addressed my concerns and I have therefore increased my score.

This work proposes an explanation for the double-descent phenomenon observed by Nakkiran et al. as a function of training time, in models with significant label corruption. Classical theory suggests that the test loss should follow a U-shaped curve, where the model initially learns but then overfits. The proposed explanation is that the observed double-descent curve is a superposition of two such U-shaped curves, each originating from a different underlying "scale". This is demonstrated in the context of linear models trained with MSE loss and noisy labels: Each eigenmode of the kernel independently leads to a U-shaped curve in the test loss, and the time scale for each curve is a function of the corresponding eigenvalue. A similar effect is shown for wide 2-layer networks, using wide network theory to relate this network to a linear model. In this case the two scales in the kernel originate from an imbalance between the two layers. The double descent effect can be eliminated by adjusting the initialization scales (or learning rates) of the two layers.

As a test of this proposal, it is shown empirically that double descent can similarly be eliminated in ResNet-18 and another model by adjusting the learning rates of different layers. The paper presents this as a way to mitigate double descent, although it is not clear that this is beneficial. First, the double descent effect happens relatively quickly (it is over in a fraction of the time it takes to train the network). Second, in the example of ResNet-18, the network that exhibits double-descent ends up performing better than the network where double-descent is mitigated. I do think that the explanation suggested for the origin of double descent is plausible and valuable. In particular, it neatly explains why label noise enhances the effect.

Following the proposed explanation, it is not clear to me why models exhibit double-descent and not multi-descent behavior. Given the linear model results, it is possible to engineer linear setups with any number of separate U-shaped curves. Why are there only two typical scales rather than multiple such scales in typical deep learning setups? The paper suggests that the main imbalance is between the last layer and all the previous layers (why?), but based on the ResNet-18 results it seems the imbalance can happen in other parts of the network as well.

Things that would lead me to increase my rating:

1. A clear explanation of why we observe double descent rather than "multi descent" in typical deep learning setups.

2. Clarifying the connection (even if only empirically) between mitigating double descent and final model performance. The two convolution networks shown in the paper point to different conclusion. One way to strengthen the conclusion would be to scan over the per-layer learning rates, and determine whether the optimal learning rates in terms of performance do or do not exhibit double descent.

Typos and nits:

- "such as a neural networks"
- "explains why neural network often"
- Below Theorem 2 it says "for a very related Gram matrix". What does "very related" mean in this context?
review_title: A plausible explanation for temporal double-descent

Meta-review: This paper provides a novel theoretical analysis of epoch-wise double descent for a linear model and a two-layer non-linear model in the constant-NTK regime. Some reviewers noted that these models may be too simple to offer a full explanation for the phenomenon in state-of-the-art practical models, for which the NTK is known to change significantly. While this may be true, I believe that the detailed understanding derived in these simple settings provides an important first step and will surely be of interest to the community. I therefore recommend acceptance.
Decision: Accept (Poster)