A leading hypothesis for the surprising generalization of neural networks is that the dynamics of gradient descent bias the model towards simple solutions, by searching through the solution space in an incremental order of complexity. We formally define the notion of incremental learning dynamics and derive the conditions on depth and initialization for which this phenomenon arises in deep linear models. Our main theoretical contribution is a dynamical depth separation result, proving that while shallow models can exhibit incremental learning dynamics, they require the initialization to be exponentially small for these dynamics to present themselves. However, once the model becomes deeper, the dependence becomes polynomial and incremental learning can arise in more natural settings. We complement our theoretical findings by experimenting with deep matrix sensing, quadratic neural networks and with binary classification using diagonal and convolutional linear networks, showing all of these models exhibit incremental learning.
*Contributions*
This paper deals with the theoretical study of the gradient dynamics in deep neural networks. More precisely, this paper define a notion of incremental learning for a particular learning dynamics and study how the depth of the network influence it. Then, the authors show two cases where it applies: matrix sensing, quadratic neural networks and provide intuitions on how it could also apply to linear convolutional networks. 
This work leverage the framework and the proofs of Gidel et al. 2019 and Saxe et al. 2014 [1] to study the impact of depth in that sequential learning (that is the novelty of this work).
I really like the idea of studying the impact of the depth in the training dynamics. And the results (Thm2 and 3) are really interesting (but a bit hard to interpret in my opinion, see my questions)
Also, this work should make clearer that the results stated in Thm1 were already substantially presented in Saxe et al. 2013 ( eq. 17 and eq. 12 in [1])
Note that this paper is borderline regarding anonymity since it contains an acknowledgement section revealing the fundings of the authors (that could give enough information to identify the authors of this paper). 
 
*Decision*
Weak accept: The key results in this work is Theorem 2 and it’s extension to discrete case Theorem 3. they seems really interesting: when $N > 2$ in order to observe sequential learning, the dependence in the eigengap for the initialization goes from polynomial ($N=2$) to polynomial. 
Showing that result is interesting (even in this limited setting) because it theoretically shows (at least for these simple classes of problem) that deeper network perform a notion of incremental learning of components with non-prohibitively small initialization. 
However, these results are very hard to read. They could be interpreted and simplified in that purpose. I think it would greatly improve the quality of this work. 
I develop these points in the *questions* section of my review.
 
*Questions*
- The definition 1 is hard to interpret. For instance why do you need $t_i$ and $t_j$ since the functions $\sigma_i$ are increasing ? (note: the fact that these function are increasing is never mentioned in the paper but is key to talk about “incremental learning” and for your Definition 1 to make sense, since otherwise $\sigma_i$ could be “forgotten” without violating Definition 1) thus for any $t \in [t_i,t_j] $ we have $\sigma_i(t) \geq f \sigma_i^*$. Using only one time would make the definition easier to understand. 
- The result presented in theorem 2, (and 3) are hard to interpret because of the many parameters that distract the reader to the main point. The dependence in s and f would be interesting if we would like to compute these bound in practice but I think that the interest of this work is in the distinction exponential versus polynomial (in $r$). Thus even though I think that a version with s and f is worth being in the appendix, a version with $s = f = ½$ would make the result statement and the discussion way clearer. (other question why restrict yourself to $s \in (0,½)$ and $f \in (¾,1)$?)
- In the theorem 3 who is $c$ ? who is $\sigma_1$ (the largest eigenvalue?) ?
- In theorem 3, I am very surprised that there is no notion of eigengap that restrict the size of $\eta$. for instance let us consider the three eigenvalues $\{2,2-\epsilon,1\}$ with epsilon very small. I think that this condition is implicitly appearing in A and B. Actually for a fixed $c$, if we do $\sigma_j^* \to \sigma_1^* = \sigma_i^*$ then we got $A = 1/B $ thus one of them is smaller than 1. 
- You restrict yourself to a uniform initialization. Could you extend your results (and definitions) to non-uniform initialization (particularly initialization where  
- Very small initialization is a big issue in practice because it induces very small gradient at the beginning of the training 
 
- Figure 2, why is the time to learn those components increasing ? (i guess it is because of the $w^(2-2/N)$ that get smaller as $N$ increases. Isn’t it an issue in practice ? What is the sensitivity to the step size? in the discrete size (i.e. can we increase the step size to compensate the slower learning)? 
 
*Minor remark*
- Saxe et al. 2013 as been accepted to ICLR in 2014 (would be better to cite the ICLR proceedings) see [1]
 
[1] Saxe et al. 2014 in ICLR url: https://openreview.net/forum?id=_wzZwKpTDF_9C
=== After rebuttal === 
I have read the authors' response.
I think the authors could have discussed more the interpretation of Theorem 3. in the revision. 
But, I really like the main takeaway which is that there is a huge discrepancy between 2 and 3 layers in terms of dynamics.  
I maintain my weak accept