THE IMPLICIT BIAS OF DEPTH: HOW INCREMENTAL LEARNING DRIVES GENERALIZATION
Year: 2019

Abstract:
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.

heading: 1 INTRODUCTION
text: Neural networks have led to a breakthrough in modern machine learning, allowing us to efficiently learn highly expressive models that still generalize to unseen data. The theoretical reasons for this success are still unclear, as the generalization capabilities of neural networks defy the classic statistical learning theory bounds. Since these bounds, which depend solely on the capacity of the learned model, are unable to account for the success of neural networks, we must examine additional properties of the learning process. One such property is the optimization algorithm - while neural networks can express a multitude of possible ERM solutions for a given training set, gradient-based methods with the right initialization may be implicitly biased towards certain solutions which generalize.
A possible way such an implicit bias may present itself, is if gradient-based methods were to search the hypothesis space for possible solutions of gradually increasing complexity. This would suggest that while the hypothesis space itself is extremely complex, our search strategy favors the simplest solutions and thus generalizes. One of the leading results along these lines has been by Saxe et al. (2013), deriving an analytical solution for the gradient flow dynamics of deep linear networks and showing that for such models, the singular values converge at different rates, with larger values converging first. At the limit of infinitesimal initialization of the deep linear network, Gidel et al. (2019) show these dynamics exhibit a behavior of “incremental learning” - the singular values of the model are learned separately, one at a time. Our work generalizes these results to small but finite initialization scales.
Incremental learning dynamics have also been explored in gradient descent applied to matrix completion and sensing with a factorized parameterization (Gunasekar et al. (2017), Arora et al. (2018), Woodworth et al. (2019)). When initialized with small Gaussian weights and trained with a small learning rate, such a model is able to successfully recover the low-rank matrix which labeled the data, even if the problem is highly over-determined and no additional regularization is applied. In their proof of low-rank recovery for such models, Li et al. (2017) show that the model remains lowrank throughout the optimization process, leading to the successful generalization. Additionally,
Arora et al. (2019) explore the dynamics of such models, showing the singular values are learned at different rates and that deeper models exhibit stronger incremental learning dynamics. Our work deals with a more simplified setting, allowing us to determine explicitly under which conditions depth leads to this dynamical phenomenon.
Finally, the learning dynamics of nonlinear models have been studied as well. Combes et al. (2018) and Williams et al. (2019) study the gradient flow dynamics of shallow ReLU networks under restrictive distributional assumptions, Ronen et al. (2019) show that shallow networks learn functions of gradually increasing frequencies and Nakkiran et al. (2019) show how deep ReLU networks correlate with linear classifiers in the early stages of training.
These findings, along with others, suggest that the generalization ability of deep networks is at least in part due to the incremental learning dynamics of gradient descent. Following this line of work, we begin by explicitly defining the notion of incremental learning for a toy model which exhibits this sort of behavior. Analyzing the dynamics of the model for gradient flow and gradient descent, we characterize the effect of the model’s depth and initialization scale on incremental learning, showing how deeper models allow for incremental learning in larger (realistic) initialization scales. Specifically, we show that a depth-2 model requires exponentially small initialization for incremental learning to occur, while deeper models only require the initialization to be polynomially small.
Once incremental learning has been defined and characterized for the toy model, we generalize our results theoretically and empirically for larger linear and quadratic models. Examples of incremental learning in these models can be seen in figure 1, which we discuss further in section 4.

heading: 2 DYNAMICAL ANALYSIS OF A TOY MODEL
text: We begin by analyzing incremental learning for a simple model. This will allow us to gain a clear understanding of the phenomenon and the conditions for it, which we will later be able to apply to a variety of other models in which incremental learning is present.

heading: 2.1 PRELIMINARIES
text: Our simple linear model will be similar to the toy model analyzed by Woodworth et al. (2019). Our input space will be X = Rd and the hypothesis space will be linear models with non-negative weights, such that:
fσ(x) = 〈σ, x〉 σ ∈ Rd≥0 (1)
We will introduce depth into our model, by parameterizing σ using w ∈ Rd≥0 in the following way:
∀i : σi = wNi
Where N represents the depth of the model. Since we restrict the model to having non-negative weights, this parameterization doesn’t change the expressiveness, but it does radically change it’s optimization dynamics.
Assuming the data is labeled by some σ∗ ∈ Rd≥0, we will study the dynamics of this model for general N under a depth-normalized1 squared loss over Gaussian inputs, which will allow us to derive our analytical solution:
`N (w) = 1
2N2 Ex[(〈σ∗, x〉 − 〈wN , x〉)2] =
1
2N2 ||wN − σ∗||2 (2)
We will assume that our model is initialized uniformly with a tunable scaling factor, such that:
∀i : wi(0) = N √ σ0 (3)

heading: 2.2 GRADIENT FLOW ANALYTICAL SOLUTIONS
text: Analyzing our toy model using gradient flow allows us to obtain an analytical solution for the dynamics of σ(t) along with the dynamics of the loss function for a general N . For brevity, the following theorem refers only to N = 1, 2 and N →∞, however the solutions for 3 ≤ N <∞ are similar in structure to N →∞, but more complicated. We also assume σ∗i > 0 for brevity, however we can derive the solutions for σ∗i = 0 as well. Note that this result is a special case adaptation of the one presented in Saxe et al. (2013) for deep linear networks: Theorem 1. Minimizing the toy linear model described in (1) with gradient flow over the depth normalized squared loss (2), with Gaussian inputs and weights initialized as in (3) and assuming σ∗i > 0 leads to the following analytical solutions for different values of N :
N = 1 : σi(t) = σ ∗ i + (σ0 − σ∗i )e−t
N = 2 : σi(t) = σ0σ
∗ i e σ∗i t σ0 ( eσ ∗ i t − 1 ) + σ∗i
N →∞ : t = 1 (σ∗i ) 2 log (σi(t)(σ0 − σ∗i ) σ0(σi(t)− σ∗i ) ) − 1 σ∗i ( 1 σi(t) − 1 σ0 )
Proof. The gradient flow equations for our model are the following:
ẇi = −∇wi` = 1 N wN−1i (σ ∗ i − wNi )
Given the dynamics of the w parameters, we may use the chain rule to derive the dynamics of the induced model, σ:
σ̇i = dσi dwi ẇi = w 2N−2(σ∗i − wNi ) = σ 2− 2N i (σ ∗ i − σi) (4)
This differential equation is solvable for all N , leading to the solutions in the theorem. Taking N →∞ in (4) leads to σ̇i = σ2i (σ∗i − σi), which is also solvable.
1This normalization is used for mathematical convenience to have solutions of different depths exhibit similar time scales in their dynamics. Equivalently, we can derive the solutions for the regular square loss and then use different time scalings in the dynamical analysis.
Analyzing these solutions, we see how even in such a simple model depth causes different factors of the model to be learned at different rates. Specifically, values corresponding to larger optimal values converge faster, suggesting a form of incremental learning. This is most clear for N = 2 where the solution isn’t implicit, but is also the case for N ≥ 3, as we will see in the next subsection. These dynamics are depicted in figure 2, where we see the dynamics of the different values of σ(t) as learning progresses. When N = 1, all values are learned at the same rate regardless of the initialization, while the deeper models are clearly biased towards learning the larger singular values first, especially at small initialization scales.
Our model has only one optimal solution due to the population loss, but it is clear how this sort of dynamic can induce sparse solutions - if the model is able to fit the data after a small amount of learning phases, then it’s obtained result will be sparse. Alternatively, if N = 1, we know that the dynamics will lead to the minimal `2 norm solution which is dense. We explore the sparsity inducing bias of our toy model by comparing it empirically2 to a greedy sparse approximation algorithm in appendix D, and give our theoretical results in the next section.

heading: 3 INCREMENTAL LEARNING
text: Equipped with analytical solutions for the dynamics of our model for every depth, we turn to study how the depth and initialization effect incremental learning. While Gidel et al. (2019) focuses on incremental learning in depth-2 models at the limit of σ0 → 0, we will study the phenomenon for a general depth and for σ0 > 0.
First, we will define the notion of incremental learning. Since all values of σ are learned in parallel, we can’t expect one value to converge before the other moves at all (which happens for infinitesimal initialization as shown by Gidel et al. (2019)). We will need a more relaxed definition for incremental learning in finite initialization scales.
2The code for reproducing all of our experiments can be found in https://github.com/dsgissin/ Incremental-Learning
Definition 1. Given two values σi, σj such that σ∗i > σ∗j > 0 and both are initialized as σi(0) = σj(0) = σ0 < σ ∗ j , and given two scalars s ∈ (0, 14 ) and f ∈ ( 3 4 , 1), we call the learning of the values (s, f)-incremental if there exists a t for which:
σj(t) ≤ sσ∗j < fσ∗i ≤ σi(t)
In words, two values have distinct learning phases if the first almost converges (f ≈ 1) before the second changes by much (s 1). Note that for any N , σ(t) is monotonically increasing and so once σj(t) = sσ∗j , it will not decrease to allow further incremental learning. Given this definition of incremental learning, we turn to study the conditions that facilitate incremental learning in our toy model.
Our main result is a dynamical depth separation result, showing that incremental learning is dependent on σ ∗ i
σ∗j in different ways for different values ofN . The largest difference in dependence happens
between N = 2 and N = 3, where the dependence changes from exponential to polynomial:
Theorem 2. Given two values σi, σj of a toy linear model as in (1), where σ∗i σ∗j = r > 1 and the model is initialized as in (3), and given two scalars s ∈ (0, 14 ) and f ∈ ( 3 4 , 1), then the largest initialization value for which the learning phases of the values are (s, f)-incremental, denoted σth0 , is bounded in the following way:
sσ∗j ( s rf ) 1 (1−f)(r−1) ≤σth0 ≤ sσ∗j ( s rf ) 1−s r−1
N = 2
sσ∗j ( (1− f)(r − 1) 1 + (1− f)(r − 1) ) N N−2 ≤σth0 ≤ sσ∗j (r − 1 r − s ) N N−2
N ≥ 3
Proof sketch (the full proof is given in appendix A). Rewriting the separable differential equation in (4) to calculate the time until σ(t) = ασ∗, we get the following:
tα(σ) = ∫ ασ∗ σ0
dσ
σ2− 2 N (σ∗ − σ)
The condition for incremental learning is then the requirement that tf (σi) ≤ ts(σj), resulting in:
∫ fσ∗i σ0
dσ
σ2− 2 N (σ∗i − σ) ≤ ∫ sσ∗j σ0
dσ
σ2− 2 N (σ∗j − σ)
We then relax/restrict the above condition to get a necessary/sufficient condition on σ0, leading to a lower and upper bound on σth0 .
Note that the value determining the condition for incremental learning is σ ∗ i
σ∗j - if two values are in the
same order of magnitude, then their ratio will be close to 1 and we will need a small initialization to obtain incremental learning. The dependence on the ratio changes with depth, and is exponential for N = 2. This means that incremental learning, while possible for shallow models, is difficult to see in practice. This result explains why changing the initialization scale in figure 2 changes the dynamics of the N ≥ 3 models, while not changing the dynamics for N = 2 noticeably. The next theorem extends part of our analysis to gradient descent, a more realistic setting than the infinitesimal learning rate of gradient flow:
Theorem 3. Given two values σi, σj of a depth-2 toy linear model as in (1), such that σ∗i σ∗j = r > 1 and the model is initialized as in (3), and given two scalars s ∈ (0, 14 ) and f ∈ ( 3 4 , 1), and assuming σ∗j ≥ 2σ0, and assuming we optimize with gradient descent with a learning rate η ≤ cσ∗1 for
c < 2( √
2 − 1) and σ∗1 the largest value of σ∗, then the largest initialization value for which the learning phases of the values are (s, f)-incremental, denoted σth0 , is lower and upper bounded in the following way:
1
2
s
1− s σ∗j (1− f 2rf s 1− s ) 1 A−1 ≤ σth0 ≤ s 1− s σ∗j (1− f f s 1− s ) 1 B−1

heading: Where A and B are defined as:
text: A = log ( 1− cσ ∗ i σ∗1 + c2 (σ∗i σ∗1 )2) log ( 1− cσ ∗ j
σ∗1 − c24 (σ∗j σ∗1
)2) B = log ( 1− cσ ∗ i σ∗1 − c 2 4 (σ∗i σ∗1 )2) log ( 1− cσ ∗ j
σ∗1 + c2 (σ∗j σ∗1 )2) We defer the proof to appendix B.
Note that this result, while less elegant than the bounds of the gradient flow analysis, is similar in nature. Both A and B simplify to r when we take their first order approximation around c = 0, giving us similar bounds and showing that the condition on σ0 for N = 2 is exponential in gradient descent as well.
While similar gradient descent results are harder to obtain for deeper models, we discuss the general effect of depth on the gradient decent dynamics in appendix C.

heading: 4 INCREMENTAL LEARNING IN LARGER MODELS
text: So far, we have only shown interesting properties of incremental learning caused by depth for a toy model. In this section, we will relate several deep models to our toy model and show how incremental learning presents itself in larger models as well.

heading: 4.1 MATRIX SENSING
text: The task of matrix sensing is a generalization of matrix completion, where our input space is X = Rd×d and our model is a matrix W ∈ Rd×d, such that:
fW (A) = 〈W,A〉 = tr ( WTA ) Following Arora et al. (2019), we introduce depth by parameterizing the model using a product of matrices and the following initialization scheme (Wi ∈ Rd×d):
W = WNWN−1 · · ·W1 (5) ∀i ∈ [N ], Wi(0) = N √ σ0I
Note that when d = 1, the deep matrix sensing model reduces to our toy model without weight sharing. We study the dynamics of the model under gradient flow over a depth-normalized squared loss, assuming the data is labeled by a matrix sensing model parameterized by a PSD W ∗ ∈ Rd×d:
`N (WNWN−1 · · ·W1) = 1
2N EA[(〈
( WNWN−1 · · ·W1 ) −W ∗, A〉2]
= 1 2N || ( WNWN−1 · · ·W1 ) −W ∗||2F
(6)
The following theorem relates the deep matrix sensing model to our toy model, showing the two have the same dynamical equations:
Theorem 4. Optimizing the deep matrix sensing model described in (5) with gradient flow over the depth normalized squared loss ((6)), with weights initialized as in (5) leads to the following dynamical equations for different values of N :
σ̇i(t) = σi(t) 2− 2N (σ∗i − σi(t))
Where σi and σ∗i are the ith singular values of W and W ∗, respectively, corresponding to the same singular vector.
The proof follows that of Saxe et al. (2013) and Gidel et al. (2019) and is deferred to appendix E.
Theorem 4 shows us that the bias towards sparse solutions introduced by depth in the toy model is equivalent to the bias for low-rank solutions in the matrix sensing task. This bias was studied in a more general setting in Arora et al. (2019), with empirical results supporting the effect of depth on the obtainment of low-rank solutions under a more natural loss and initialization scheme. We recreate and discuss these experiments and their connection to our analysis in appendix E, and an example of these dynamics in deep matrix sensing can also be seen in panel (a) of figure 1.

heading: 4.2 QUADRATIC NEURAL NETWORKS
text: By drawing connections between quadratic networks and matrix sensing (as in Soltanolkotabi et al. (2018)), we can extend our results to these nonlinear models. We will study a simplified quadratic network, where our input space is X = Rd and the first layer is parameterized by a weight matrix W ∈ Rd×d and followed by a quadratic activation function. The final layer will be a summation layer. We assume, like before, that the labeling function is a quadratic network parameterized by W ∗ ∈ Rd×d. Our model can be written in the following way, using the following orthogonal initialization scheme:
fW (x) = d∑ i=1 (wTi x) 2 = xTWTWx = 〈WTW,xxT 〉 (7)
WT0 W0 = σ0I
Immediately, we see the similarity of the quadratic network to the deep matrix sensing model with N = 2, where the input space is made up of rank-1 matrices. However, the change in input space forces us to optimize over a different loss function to reproduce the same dynamics: Definition 2. Given an input distribution over an input space X with a labeling function y : X → R and a hypothesis h, the variance loss is defined in the following way:
`var(h) = 1
16 Ex[(y(x)− h(x))2]−
1
16 Ex[y(x)− h(x)]2
Note that minimizing this loss function amounts to minimizing the variance of the error, while the squared loss minimizes the second moment of the error. We note that both loss functions have the same minimum for our problem, and the dynamics of the squared loss can be approximated in certain cases by the dynamics of the variance loss. For a complete discussion of the two losses, including the cases where the two losses have similar dynamics, we refer the reader to appendix F. Theorem 5. Minimizing the quadratic network described and initialized as in (7) with gradient flow over the variance loss defined in (2) leads to the following dynamical equations:
σ̇i(t) = σi(t)(σ ∗ i − σi(t))
Where σi and σ∗i are the ith singular values of W and W ∗, respectively, corresponding to the same singular vector.
We defer the proof to appendix F and note that these dynamics are the same as our depth-2 toy model, showing that shallow quadratic networks can exhibit incremental learning (albeit requiring a small initialization).

heading: 4.3 DIAGONAL/CONVOLUTIONAL LINEAR NETWORKS
text: While incremental learning has been described for deep linear networks in the past, it has been restricted to regression tasks. Here, we illustrate how incremental learning presents itself in binary classification, where implicit bias results have so far focused on convergence at t→∞ (Soudry et al. (2018), Nacson et al. (2018), Ji & Telgarsky (2019)). Deep linear networks with diagonal weight matrices have been shown to be biased towards sparse solutions when N > 1 in Gunasekar et al. (2018), and biased towards the max-margin solution for N = 1. Instead of analyzing convergence at t → ∞, we intend to show that the model favors sparse solutions for the entire duration of optimization, and that this is due to the dynamics of incremental learning.
Our theoretical illustration will use our toy model as in (1) (initialized as in (3)) as a special weightshared case of deep networks with diagonal weight matrices, and we will then show empirical results for the more general setting. We analyze the optimization dynamics of this model over a separable dataset {xi, yi}mi=1 where yi ∈ {±1}. We use the exponential loss (`(f(x), y) = e−yf(x)) for the theoretical illustration and experiment on the exponential and logistic losses.
Computing the gradient for the model over w, the gradient flow dynamics for σ become:
σ̇i = N2 m σ 2− 2N i m∑ j=1 e−yj〈β,xj〉xj
We see the same dynamical attenuation of small values of σ that is seen in the regression model, caused by the multiplication by σ2− 2 N
i . From this, we can expect the same type of incremental learning to occur - weights of σ will be learned incrementally until the dataset can be separated by the current support of σ. Then, the dynamics strengthen the growth of the current support while relatively attenuating that of the other values. Since the data is separated, increasing the values of the current support reduces the loss and the magnitude of subsequent gradients, and so we should expect the support to remain the same and the model to converge to a sparse solution.
Granted, the above description is just intuition, but panel (c) of figure 1 shows how it is born out in practice (similar results are obtained for the logistic loss). In appendix G we further explore this model, showing deeper networks have a stronger bias for sparsity. We also observe that the initialization scale plays a similar role as before - deep models are less biased towards sparsity when σ0 is large.
In their work, Gunasekar et al. (2018) show an equivalence between the diagonal network and the circular-convolutional network in the frequency domain. According to their results, we should expect to see the same sparsity-bias of diagonal networks in convolutional networks, when looking at the Fourier coefficients of σ. An example of this can be seen in panel (d) of figure 1, and we refer the reader to appendix G for a full discussion of their convolutional model and it’s incremental learning dynamics.

heading: 5 CONCLUSION
text: Gradient-based optimization for deep linear models has an implicit bias towards simple (sparse) solutions, caused by an incremental search strategy over the hypothesis space. Deeper models have a stronger tendency for incremental learning, exhibiting it in more realistic initialization scales.
This dynamical phenomenon exists for the entire optimization process for regression as well as classification tasks, and for many types of models - diagonal networks, convolutional networks, matrix completion and even the nonlinear quadratic network. We believe this kind of dynamical analysis may be able to shed light on the generalization of deeper nonlinear neural networks as well, with shallow quadratic networks being only a first step towards that goal.

heading: ACKNOWLEDGMENTS
text: This research is supported by the European Research Council (TheoryDL project).

heading: A PROOF OF THEOREM 2
text: Theorem. Given two values σi, σj of a toy linear model as in (1), such that σ∗i σ∗j = r > 1 and the model is initialized as in (3), and given two scalars s ∈ (0, 14 ) and f ∈ ( 3 4 , 1), then the largest initialization value for which the learning phases of the values are (s, f)-incremental, denoted σth0 , is lower and upper bounded in the following way:
sσ∗j ( s rf ) 1 (1−f)(r−1) ≤σth0 ≤ sσ∗j ( s rf ) 1−s r−1
N = 2
sσ∗j ( (1− f)(r − 1) 1 + (1− f)(r − 1) ) N N−2 ≤σth0 ≤ sσ∗j (r − 1 r − s ) N N−2
N ≥ 3
Proof. Our strategy will be to define the time tα for which a value reaches a fraction α of it’s optimal value, and then require that tf (σi) ≤ ts(σj). We begin with recalling the differential equation which determines the dynamics of the model:
σ̇ = σ2− 2 N (σ∗ − σ)
Since the solution for N ≥ 3 is implicit and difficult to manage in a general form, we will define tα using the integral of the differential equation. The equation is separable, and under initialization of σ0 we can describe tα(σ) in the following way:
tα(σ) = ∫ ασ∗ σ0
dσ
σ2− 2 N (σ∗ − σ)
Incremental learning takes place when σi(tf ) = fσ∗i happens before σj(ts) = sσ ∗ j . We can write this condition in the following way:
∫ fσ∗i σ0
dσ
σ2− 2 N (σ∗i − σ) ≤ ∫ sσ∗j σ0
dσ
σ2− 2 N (σ∗j − σ)
Plugging in σi = rσj and rearranging, we get the following necessary and sufficient condition for incremental learning:
∫ frσ∗j σ0
dσ
σ2− 2 N (1− σrσ∗j )
≤ r ∫ sσ∗j σ0
dσ
σ2− 2 N (1− σσ∗j )
Our last step before relaxing and restricting our condition will be to split the integral on the left-hand side into two integrals:
∫ sσ∗j σ0
dσ
σ2− 2 N (1− σrσ∗j )
+ ∫ frσ∗j sσ∗j
dσ
σ2− 2 N (1− σrσ∗j )
≤ r ∫ sσ∗j σ0
dσ
σ2− 2 N (1− σσ∗j )
(8)
At this point, we cannot solve this equation and isolate σ0 to obtain a clear threshold condition on it for incremental learning. Instead, we will relax/restrict the above condition to get a necessary/sufficient condition on σ0, leading to a lower and upper bound on the threshold value of σ0.

heading: SUFFICIENT CONDITION
text: To obtain a sufficient (but not necessary) condition on σ0, we may make the condition stricter either by increasing the left-hand side or decreasing the right-hand side. We can increase the left-hand side by removing r from the left-most integral’s denominator (r > 1) and then combine the left-most and right-most integrals:
∫ frσ∗j sσ∗j
dσ
σ2− 2 N (1− σrσ∗j )
≤ (r − 1) ∫ sσ∗j σ0
dσ
σ2− 2 N (1− σσ∗j )
Next, we note that the integration bounds give us a bound on σ for either integral. This means we can replace 1 − σσ∗j with 1 on the right-hand side, and replace 1 − σ rσ∗j
with 1 − f on the left-hand side:
1
1− f ∫ frσ∗j sσ∗j dσ σ2− 2 N ≤ (r − 1) ∫ sσ∗j σ0 dσ σ2− 2 N
We may now solve these integrals for everyN and isolate σ0, obtaining the lower bound on σth0 . We start with the case where N = 2:
1 1− f ( log(frσ∗j )− log(sσ∗j ) ) ≤ (r − 1) ( log(sσ∗j )− log(σ0) ) Rearranging to isolate σ0, we obtain our result:
σ0 ≤ sσ∗j ( s rf ) 1 (1−f)(r−1)
For the N ≥ 3 case, we have the following after solving the integrals:
1
1− f (( 1 sσ∗j )1− 2N − ( 1 rfσ∗j )1− 2N ) ≤ (r − 1)(( 1 σ0 )1− 2N − ( 1 sσ∗j )1− 2N ) For simplicity we may further restrict the condition by removing the term ( 1
rfσ∗j )1− 2N . Solving for σ0 gives us the following:
σ0 ≤ sσ∗j ( (1− f)(r − 1)
1 + (1− f)(r − 1)
) N N−2

heading: NECESSARY CONDITION
text: To obtain a necessary (but not sufficient) condition on σ0, we may relax the condition in (8) either by decreasing the left-hand side or increasing the right-hand side. We begin by rearranging the equation:
∫ frσ∗j sσ∗j
dσ
σ2− 2 N (1− σrσ∗j )
≤ r ∫ sσ∗j σ0
dσ
σ2− 2 N (1− σσ∗j )
− ∫ sσ∗j σ0
dσ
σ2− 2 N (1− σrσ∗j )
Like before, we may use the integration bounds to bound σ. Plugging in σ = sσ∗j for all integrals decreases the left-hand side and increases the right-hand side, leading us to the following:
r
r − s ∫ frσ∗j sσ∗j dσ σ2− 2 N ≤ ( r 1− s − r r − s ) ∫ sσ∗j σ0 dσ σ2− 2 N
Rearranging, we get the following inequality:
∫ frσ∗j sσ∗j dσ σ2− 2 N ≤ r − 1 1− s ∫ sσ∗j σ0 dσ σ2− 2 N
We now solve the integrals for the different cases. For N = 2, we have:
log(frσ∗j )− log(sσ∗j ) ≤ r − 1 1− s
( log(sσ∗j )− log(σ0) ) Rearranging to isolate σ0, we get our condition:
σ0 ≤ sσ∗j ( s rf ) 1−s r−1
Finally, for N ≥ 3, we solve the integrals to give us:
(( 1 sσ∗j )1− 2N − ( 1 rfσ∗j )1− 2N ) ≤ r − 1 1− s (( 1 σ0 )1− 2N − ( 1 sσ∗j )1− 2N ) Rearranging to isolate σ0, we get our condition:
σ0 ≤ sσ∗j (r − 1 r − s ) N N−2

heading: SUMMARY
text: For a given N , we derived a sufficient condition and a necessary condition on σ0 for (s, f )- incremental learning. The necessary and sufficient condition on σ0, which is the largest initialization value for which we see incremental learning (denoted σth0 ), is between the two derived bounds.
The precise bounds can possibly be improved a bit, but the asymptotic dependence on r is the crux of the matter, showing the dependence on r changes with depth with a substantial difference when we move from shallow models (N = 2) to deeper ones (N ≥ 3)

heading: B PROOF OF THEOREM 3
text: Theorem. Given two values σi, σj of a depth-2 toy linear model as in (1), such that σ∗i σ∗j = r > 1 and the model is initialized as in (3), and given two scalars s ∈ (0, 14 ) and f ∈ ( 3 4 , 1), and assuming σ∗j ≥ 2σ0, and assuming we optimize with gradient descent with a learning rate η ≤ cσ∗1 for c < 2( √ 2 − 1) and σ∗1 the largest value of σ∗, then the largest initialization value for which the learning phases of the values are (s, f)-incremental, denoted σth0 , is lower and upper bounded in the following way:
1
2
s
1− s σ∗j (1− f 2rf s 1− s ) 1 A−1 ≤ σth0 ≤ s 1− s σ∗j (1− f f s 1− s ) 1 B−1

heading: Where A and B are defined as:
text: A = log ( 1− cσ ∗ i σ∗1 + c2 (σ∗i σ∗1 )2) log ( 1− cσ ∗ j
σ∗1 − c24 (σ∗j σ∗1
)2) B = log ( 1− cσ ∗ i σ∗1 − c 2 4 (σ∗i σ∗1 )2) log ( 1− cσ ∗ j
σ∗1 + c2 (σ∗j σ∗1 )2)
Proof. To show our result for gradient descent and N = 2, we build on the proof techniques of theorem 3 of Gidel et al. (2019). We start by deriving the recurrence relation for the values σ(t) for general depth, when t now stands for the iteration. Remembering that wni = σi, we write down the gradient update for wi(t):
wi(t+ 1) = wi(t) + η 1
N wi(t)
N−1(σ∗i − σi(t)) = N √ σi(t) + η 1
N σi(t)
1− 1N (σ∗i − σi(t))
Raising wi(t) to the N th power, we get the gradient update for the σ values:
σi(t+ 1) = ( N √ σi(t) + η 1
N (σ∗i − σi(t))σi(t)1− 1 N
)N = σi(t) ( 1 + η 1
N σi(t) 1− 2N (σ∗i − σi(t)) )N (9)
Next, we will prove a simple lemma which gives us the maximal learning rate we will consider for the analysis, for which there is no overshooting (the values don’t grow larger than the optimal values).
Lemma 1. For the gradient update in (9), assuming σi(0) < σ∗i , if η ≤ (
1 σ∗1
)2− 2N and N ≥ 2,
then:
∀t : σi(t) ≤ σ∗i
Proof. Plugging in η = c (
1 σ∗i
)2− 2N for c ≤ 1, we have:
σi(t+ 1) = σi(t) ( 1 + c
N (σi(t) σ∗i )1− 2N ( 1− (σi(t) σ∗i )))N ≤ σi(t)e
( σi(t)
σ∗ i
)1− 2 N ( 1− ( σi(t)
σ∗ i
))
Defining ri = σiσ∗i and dividing both sides by σ ∗ i , we have:
ri(t+ 1) ≤ ri(t)eri(t) 1− 2 N (1−ri(t))
It is enough to show that for any 0 ≤ r ≤ 1, we have that rer 1− 2
N (1−r) ≤ 1, as over-shooting occurs when ri(t) > 1. Indeed, this function is monotonic increasing in 0 ≤ r ≤ 1 (since the exponent is non negative), and equals 1 when r = 1. Since r = 1 is a fixed point and no iteration that starts at r < 1 can cross 1, then ri(t) ≤ 1 for any t. This concludes our proof.
Under this choice of learning rate, we can now obtain our incremental learning results for gradient descent when N = 2. Our strategy will be bounding σi(t) from below and above, which will give us a lower and upper bound for tα(σi). Once we have these bounds, we will be able to describe either a necessary or a sufficient condition on σ0 for incremental learning, similar to theorem 2.
The update rule for N = 2 is:
σi(t+ 1) = σi(t) ( 1 + 1
2 η(σ∗i − σi(t)) )2 Next, we plug in η = cσ∗1 for c < 2( √ 2− 1) < 1 and denote Ri = σ ∗ i σ∗1 ≤ 1 and ri(t) = σi(t)σ∗i ≤ 1 to get:
σi(t+ 1) = σi(t) ( 1 + c
2 Ri(1− ri(t))
)2
Following theorem 3 of Gidel et al. (2019), we bound 1σi(t) :
1
σi(t+ 1) =
1
σi(t) 1( 1 + c2Ri(1− ri(t)) )2 = 1
σi(t)
1 1 + (1− ri(t)) ( cRi + c2 4 R 2 i (1− ri(t)) ) ≥ 1 σi(t) 1 1 + (1− ri(t)) ( cRi + c2 4 R 2 i ) )
≥ 1 σi(t)
( 1− (1− ri(t))(cRi + c2
4 R2i ) ) = 1
σi(t) − ( 1 σi(t) − 1 σ∗i )(cRi + c2 4 R2i )
Where in the fourth line we use the inequality 11+x ≥ 1 − x, ∀x ≥ 0. We may now subtract 1 σ∗i from both sides to obtain:
1 σi(t) − 1 σ∗i ≥ ( 1 σi(t− 1) − 1 σ∗i )( 1− cRi − c2 4 R2i ) ≥ ( 1 σ0 − 1 σ∗i )( 1− cRi − c2 4 R2i )t
We may now obtain a bound on tα(σi) by plugging in σi(t) = ασ∗i and taking the log:
log ( 1− α α(
σ∗i σ0 − 1)
) ≥ tα · log ( 1− cRi − c2 4 R2i )
Rearranging (note that log ( 1 − cRi − c 2 4 R 2 i ) < 0 and that our choice of c keeps the argument of the log positive), we get:
tα(σi) ≥ log ( 1−α α( σ∗ i σ0 −1) ) log ( 1− cRi − c 2 4 R 2 i
) Next, we follow the same procedure for an upper bound. Starting with our update step:
1
σi(t+ 1) =
1
σi(t)
1 1 + (1− ri(t)) ( cRi + c2 4 R 2 i (1− ri(t)) ) ≤ 1 σi(t) 1 1 + (1− ri(t))cRi
≤ 1 σi(t)
( 1− (1− ri(t))cRi + (1− ri(t))2c2R2i ) Where in the last line we use the inequality 11+x ≤ 1− x+ x
2, ∀x ≥ 0. Subtracting 1σ∗i from both sides, we get:
1 σi(t) − 1 σ∗i ≤ ( 1 σi(t− 1) − 1 σ∗i )( 1− cRi + c2R2i ) ≤ ( 1 σ0 − 1 σ∗i )( 1− cRi + c2R2i )t Rearranging like before, we get the bound on the α-time:
tα(σi) ≤ log ( 1−α α( σ∗ i σ0 −1) ) log ( 1− cRi + c2R2i )
Given these bounds, we would like to find the conditions on σ0 that allows for (s, f)-incremental learning. We will find a sufficient condition and a necessary condition, like in the proof of theorem 2.

heading: SUFFICIENT CONDITION
text: A sufficient condition for incremental learning will be one which is possibly stricter than the exact condition. We can find such a condition by requiring the upper bound of tf (σi) to be smaller than the lower bound on ts(σj). This becomes the following condition:
log ( 1−f f σ0 σ∗i−σ0 ) log ( 1− cRi + c2R2i ) ≤ log ( 1−s s σ0 σ∗j−σ0 ) log ( 1− cRj − c 2 4 R 2 j
) Defining A = log ( 1−cRi+c2R2i ) log ( 1−cRj− c 2 4 R 2 j
) and rearranging, we get the following: log (1− f
f σ0 σ∗i − σ0
) ≥ A log (1− s s σ0 σ∗j − σ0 ) We may now take the exponent of both sides and rearrange again, remembering σ ∗ i
σ∗j = r > 1, to get
the following condition:
(σ∗j − σ0)A
σA−10 (rσ ∗ j − σ0)
≥ f 1− f (1− s s )A Now, we will add the very reasonable assumption that σ∗j ≥ 2σ0, which allows us to replace σ∗j−σ0 rσ∗j−σ0 with 12r and replace (σ ∗ j−σ0)A−1 with ( 12σj)
A−1, only making the condition stricter. This simplifies the expression to the following:
(σ∗j σ0 )A−1 ≥ rf 1− f (2− 2s s )A Now we can rearrange and isolate σ0 to get a sufficient condition for incremental learning:
σ0 ≤ 1
2
s
1− s σ∗j (1− f 2rf s 1− s ) 1 A−1

heading: NECESSARY CONDITION
text: A necessary condition for incremental learning will be one which is possibly more relaxed than the exact condition. We can find such a condition by requiring the lower bound of tf (σi) to be smaller than the upper bound on ts(σj). This becomes the following condition:
log ( 1−f f σ0 σ∗i−σ0 ) log ( 1− cRi − c 2 4 R 2 i ) ≤ log ( 1−s s σ0 σ∗j−σ0 ) log ( 1− cRj + c2R2j
) Defining B = log ( 1−cRi− c 2 4 R 2 i
) log ( 1−cRj+c2R2j
) and rearranging, we get the following: log (1− f
f σ0 σ∗i − σ0
) ≥ B log (1− s s σ0 σ∗j − σ0 )
We may now take the exponent of both sides and rearrange again, remembering σ ∗ i
σ∗j = r > 1, to get
the following condition:
(σ∗j − σ0)B
σB−10 (rσ ∗ j − σ0)
≥ f 1− f (1− s s )B We may now relax the condition further, by removing the r from the denominator of the left-hand side and the σ0 from the numerator. This gives us the following:
(σ∗j σ0 )B−1 ≥ f 1− f (1− s s )B Finally, rearranging gives us the necessary condition:
σ0 ≤ s
1− s σ∗j (1− f f s 1− s ) 1 B−1

heading: C DISCUSSION OF GRADIENT DESCENT FOR GENERAL N
text: While we were able to generalize our result to gradient descent for N = 2, our proof technique relies on the ability to get a non-implicit solution for σ(t) which we discretized and bounded. This is harder to generalize to larger values of N , where the solution is implicit. Still, we can informally illustrate the effect of depth on the dynamics of gradient descent by approximating the update rule of the values.
We start by reminding ourselves of the gradient descent update rule for σ, for a learning rate η = c (
1 σ∗1 )2− 2N : σi(t+ 1) = σi(t) ( 1 + c
N ( 1 σ∗1 )2− 2N σi(t)1− 2N (σ∗i − σi(t)))N To compare two values in the same scales, we will divide both sides by the optimal value σ∗i and look at the update step of the ratio ri =
σi(t) σ∗i , also denoting Ri = σ∗i σ∗1 :
ri(t+ 1) = ri(t) ( 1 + c
N R
2− 2N i ri(t) 1− 2N (1− ri(t)) )N
We will focus on the early stages of the optimization process, where r 1. This means we can neglect the 1 − ri(t) term in the update step, giving us the approximate update step we will use to compare the general i, j values:
ri(t+ 1) ≈ ri(t) ( 1 + c
N R
2− 2N i ri(t)
1− 2N )N
We would like to compare the dynamics of ri and rj , which is difficult to do when the recurrence relation isn’t solvable. However, we can observe the first iteration of gradient descent and see how depth affects this iteration. Since we are dealing with variables which are ratios of different optimal values, the initial values of r are different. Denoting r = σ ∗ i
σ∗j , we can describe the initialization of rj
using that of ri:
rj(0) = rri(0)
Plugging in the initial conditions and noting that Ri = rRj , we get:
ri(1) ≈ ri(0) ( 1 + cR 2− 2N i
N ri(0)
1− 2N )N
rj(1) ≈ ri(0) ( N √ r + (1 r )N−1 N cR 2− 2N i N ri(0) 1− 2N )N
We see that the two ratios have a similar update, with the ratio of optimal values playing a role in how large the initial value is versus how large the added value is. When we use a small learning rate, we have a very small c which means we can make a final approximation and neglect the higher order terms of c:
ri(1) ≈ri(0) + cR 2− 2N i ri(0) 2− 2N
rj(1) ≈rri(0) + (1 r )N−1 N cR 2− 2N i ri(0) 2− 2N
We can see that while the initial conditions favor rj , the size of the update for ri is larger by a factor of r N−1 N when the initialization and learning rates are small. This accumulates throughout the optimization, making ri eventually converge faster than rj .
The effect of depth here is clear - the deeper the model, the larger the relative step size of ri and the faster it converges relative to rj .

heading: D COMPARISON OF THE TOY MODEL AND OMP
text: Learning our toy model, when it’s incremental learning is taken to the limit, can be described as an iterative procedure where at every step an additional feature is introduced such that it’s weight is non-zero and then the model is optimized over the current set of features. This description is also relevant for the sparse approximation algorithm orthogonal matching pursuit (Pati et al., 1993), where the next feature is greedily chosen to be the one which most improves the current model.
While the toy model and OMP are very different algorithms for learning sparse linear models, we will show empirically that they behave similarly. This allows us to view incremental learning as a continuous-time extension of a greedy iterative algorithm.
To allow for negative weights in our experiments, we augment our toy model as in the toy model of Woodworth et al. (2019). Our model will have the same induced form as before:
fσ(x) = 〈σ, x〉
However, we parameterize σ using w+, w− ∈ Rd in the following way:
σi = w N +,i − wN−,i
∀i, w+,i(0) = w−,i(0) = N √ σ0
We can now treat this algorithm as a sparse approximation pursuit algorithm - given a dictionary D ∈ Rd×n and an example x ∈ Rd, we wish to find the sparsest α for whichDα ≈ x by minimizing the `0 norm of α subject to ||Dα − x||22 = 03. Under this setting, we can compare OMP to our toy model by comparing the sets of features that the two algorithms choose for a given example and dictionary.
In figure 3 we run such a comparison. Using a dictionary of 1000 atoms and an example of dimensionality 80 sampled from a random hidden vector of a given sparsity s, we run both algorithms and record the first s features chosen4.
3Note that this problem is equivalent to learning the toy model over the squared loss, where the examples in the original learning problem play the role of the dictionary.
4For the toy model, we define a feature to be “chosen” once it’s σi value passes some small threshold in absolute value.
For every sparsity s, we plot the mean fraction of agreement between the sets of features chosen by OMP and the toy model over 100 experiments. We see that the two algorithms choose very similar features at the beginning, suggesting that the deep model approximates the discrete behavior of OMP. Only when the number of features increases do we see that the behavior of the two models begins to differ, caused by the fact that the toy model has a finite initialization scale and learning rate.
These experiments demonstrate the similarity between the incremental learning of deep models and the discrete behavior of greedy approximation algorithms such as OMP. Adopting this view also allows us to put our finger on another strength of the dynamics of deep models - while greedy algorithms such as OMP require the analytical solution or approximation of every iterate, the dynamics of deep models are able to incrementally learn any differentiable function. For example, looking back at the matrix sensing task and the classification models in section 4, we see that while there isn’t an immediate and efficient extension of OMP for these settings, the dynamics of learning deep models extends naturally and exhibits the same incremental learning as OMP.
E INCREMENTAL LEARNING IN MATRIX SENSING

heading: E.1 PROOF OF THEOREM 4
text: Theorem. Minimizing the deep matrix sensing model described in (5) with gradient flow over the depth normalized squared loss (6), with Gaussian inputs and weights initialized as in (5) leads to the following dynamical equations for different values of N :
σ̇i(t) = σi(t) 2− 2N (σ∗i − σi(t))
Where σi and σ∗i are the ith singular values of W and W ∗, respectively, corresponding to the same singular vectors.
Proof. We will adapt the proof from Saxe et al. (2013) for multilayer linear networks. The gradient flow equations for Wn, n ∈ [N ] are:
Ẇn = 1
N WT1:n−1(W ∗ −W )WTn+1:N
Where we denote Wj:k = ∏k i=jWi.
Since we assumed W ∗ is (symmetric) PSD, there exists an orthogonal matrix U for which D∗ = UW ∗UT where D∗ is diagonal. Under the initialization in (3), U diagonalizes all Wn matrices at initialization such that Dn = UWnUT = N √ σ0I . Making this change of variables for all Wn, we get:
Ẇn = 1
N UTD1:n−1U(W ∗ −W )UTDn+1:NU
Rearranging, we get a set of decoupled differential equations for the singular values of Wn:
Ḋn = 1
N D1:n−1(D
∗ −D)Dn+1:N
Note that since these matrices are all diagonal at initialization, the above dynamics ensure that they remain diagonal throughout the optimization. Denoting σn,i as the i’th singular value of Wn and σi as the i’th singular value of W , we get the following differential equation:
σ̇n,i = 1
N (σ∗i − σi) ∏ j 6=n σj,i
Since we assume at initialization that ∀n,m, i : σn,i(0) = σm,i(0) = N √ σ0, the above dynamics are the same for all singular values and we get ∀n,m, i : σn,i(t) = σm,i(t) = N √ σi(t). We may now use this to calculate the dynamics of the singular value of W , since they are the product the the singular values of all Wn matrices. Denoting σ−n,i = ∏ k 6=n σk,i and using the chain rule:
σ̇i = N∑ n=1 σ−n,iσ̇n,i = σ 2− 2N i (σ ∗ i − σi)

heading: E.2 EMPIRICAL EXAMINATION
text: Our analytical results are only applicable for the population loss over Gaussian inputs. These conditions are far from the ones used in practice and studied in Arora et al. (2019), where the problem is over-determined and the weights are drawn from a Gaussian distribution with a small variance. To show our conclusions regarding incremental learning extend qualitatively to more natural settings, we empirically examine the deep matrix sensing model in this natural setting for different depths and initialization scales as seen in figure 4.
Notice how incremental learning is exhibited even when the number of examples is much smaller than the number of parameters in the model. While we can’t rely on our theory for describing the exact dynamics of the optimization for these kinds of over-determined problems, the qualitative conclusions we get from it are still applicable.
Another interesting phenomena we should note is that once the dataset becomes very small (the second row of the figure), we see all “currently active” singular values change at the beginning of every new phase (this is best seen in the bottom-right panel). This suggests that since there is more than one optimal solution, once we increase the current rank of our model it may find a solution that has a different set of singular values and vectors and thus all singular values change at the beginning of a new learning phase. This demonstrates the importance of incremental learning for obtaining
sparse solutions - once the initialization conditions and depth are such that the learning phases are distinct, gradient descent finds the optimal rank-i solution in every phase i. For these dynamics to successfully recover the optimal solution at every phase, the phases need to be far enough apart from each other to allow for the singular values and vectors to change before the next phase begins.
F INCREMENTAL LEARNING IN QUADRATIC NETWORKS

heading: F.1 PROOF OF THEOREM 5
text: Theorem. Minimizing the quadratic network described and initialized as in (7) with gradient flow over the variance loss defined in (2) with Gaussian inputs leads to the following dynamical equations:
σ̇i(t) = σi(t)(σ ∗ i − σi(t))
Where σi and σ∗i are the ith singular values of W and W ∗, respectively, corresponding to the same singular vectors.
Proof. Our proof will follow similar lines as the analysis of the deep matrix sensing model. Taking the expectation of the variance loss over Gaussian inputs for our model gives us:
`var(W ) = 1
16 Ex[(〈WT∗ W∗ −WTW,xxT 〉)2]−
1
16 Ex[〈WT∗ W∗ −WTW,xxT 〉]2
= 1
8 ||WT∗ W∗ −WTW ||2F +
1
16 Tr(WT∗ W∗ −WTW )2 −
1
16 Tr(WT∗ W∗ −WTW )2
= 1
8 ||WT∗ W∗ −WTW ||2F
Following the gradient flow dynamics over W leads to the following differential equation:
Ẇ = 1
2 W (WT∗ W∗ −WTW )
We can now calculate the gradient flow dynamics of WTW using the chain rule:
˙WTW = WT Ẇ + ẆTW = 1
2
( WTW (WT∗ W∗ −WTW ) + (WT∗ W∗ −WTW )WTW ) (10)
Now, under our initialization WT0 W0 = σ0I , we get that W TW and WT∗ W∗ are simultaneously diagonalizable at initialization by some matrix U , such that the following is true for diagonal D and D∗:
D(0) = UTW (0)TW (0)U
D∗ = UTWT∗ W∗U
Multiplying equation (10) by U and UT gives us the following dynamics for the singular values of WTW :
Ḋ = 1
2
( D(D∗ −D) + (D∗ −D)D ) = D(D∗ −D)
These matrices are diagonal at initialization, and remain diagonal throughout the dynamics (the offdiagonal elements are static according to these equations). We may now look at the dynamics of a single diagonal element, noticing it is equivalent to the depth-2 toy model:
σ̇i = σi(σ ∗ i − σi)

heading: F.2 DISCUSSION OF THE VARIANCE LOSS
text: It may seem that the variance loss is an unnatural loss function to analyze, since it isn’t used in practice. While this is true, we will show how the dynamics of this loss function are an approximation of the square loss dynamics.
We begin by describing the dynamics of both losses, showing how incremental learning can’t take place for quadratic networks as defined over the squared loss. Then, we show how adding a global bias to the quadratic network leads to similar dynamics for small initialization scales.

heading: F.2.1 DYNAMICAL DERIVATION
text: in the previous section, we derive the differential equations for the singular values of WTW under the variance loss:
σ̇i = σi(σ ∗ i − σi)
We will now derive similar equations for the squared loss. The scaled squared loss in expectation over the Gaussian inputs is:
`(W ) = 1
16 Ex[(〈WT∗ W∗ −WTW,xxT 〉)2]
= 1
8 ||WT∗ W∗ −WTW ||2F +
1
16 Tr(WT∗ W∗ −WTW )2
Defining ∆ = WT∗ W∗ −WTW for brevity, the differential equations for W become:
Ẇ = 1
2 W∆ +
1 4 Tr(∆)W
Calculating the dynamics ofWTW after noting that it is simultaneously diagonalizable withWT∗ W∗ (as in the derivation for the variance loss) leads to the following differential equations for the singular values of WTW :
σ̇i = σi ( σ∗i − σi + 1
2 ∑ j (σ∗j − σj) )
We see that the equations are now coupled and so we cannot solve them analytically. Another issue is that for our initialization, all singular values have very similar dynamics at initialization due to the coupling. For example, values corresponding to small optimal singular values grow much faster than in the variance loss dynamics, due to the effect the large optimal singular values have on them.
We see from these equations that we shouldn’t expect quadratic networks optimized over the squared loss to exhibit incremental learning behavior. We next show how adding a global bias to our model can help.
F.2.2 VARIANCE LOSS APPROXIMATES THE SQUARED LOSS
To see how the variance loss can have dynamics resembling those of the squared loss, we will add a global (trainable) bias to our model. This means our model is now parameterized by W ∈ Rd×d and a scalar b ∈ R:
fW,b(x) = 〈WTW,xxT 〉+ b
We may now analyze gradient flow of the squared loss. Following the same methods as before, this leads us to the following differential equations:
σ̇i =σi ( σ∗i − σi + 1
2 ∑ j (σ∗j − σj) + 1 2 (b∗ − b) ) ḃ =
∑ j (σ∗j − σj) + b∗ − b
Notice how, if b is at it’s optimum at a given time (b = ∑ j(σ ∗ j −σj) + b∗), the dynamics of σi align with those of the variance loss. Alternatively, when b = b∗, we recover the dynamics of the squared loss without the global bias term.
To convince ourselves that the dynamics of this model resemble those of the variance loss, we would need to explain why the global bias is at it’s optimum “most of the time”, such that the singular values don’t change much during the times when it is not at it’s optimum.
Observing the differential equations for b and for σi, we see they are similar (if we ignore the σ∗i −σi value which doesn’t change the order of magnitude of the entire expression when there haven’t been many learning phases yet). The only difference being a multiplication by σi. This means that we may informally write:
σ̇i(t)
ḃ(t) ≈ σi(t)
Since at initialization and until the learning phase of σi takes place, we have σi(t) 1, we see that the global bias optimizes much faster than the singular values for which the learning phase hasn’t begun yet. This means these singular values will remain small during the times in which
the bias isn’t optimal, and so incremental learning can still take place (assuming a small enough initialization).
Under these considerations, we say that the dynamics of the squared loss for a quadratic network with an added global bias resemble the idealized dynamics of the variance loss for a depth-2 linear model which we analyze formally in the paper. In figure 5 we experimentally show how adding a bias to a quadratic network does lead to incremental learning similar to the depth-2 toy model.
G INCREMENTAL LEARNING IN CLASSIFICATION

heading: G.1 DIAGONAL NETWORKS
text: In section 4.3 we viewed our toy model as a special case of the deep diagonal networks described in Gunasekar et al. (2018), expected to be biased towards sparse solutions. Figure 6 shows the dynamics of the largest values of σ for different depths of the model. We see that the same type of incremental learning we saw in earlier models exists here as well - the features are learned one by one in deeper models, resulting in a sparse solution. The leftmost panel shows how the initialization scale plays a role here as well, with the solution being more sparse when the initialization is small. We should note that these results do not defy the results of Gunasekar et al. (2018) (from which we would expect the initialization not to matter), since their results deal with the solution at t→∞.

heading: G.2 CONVOLUTIONAL NETWORKS - PRELIMINARIES
text: The linear circular-convolutional network of Gunasekar et al. (2018) deals with one-dimensional convolutions with the same number of outputs as inputs, such that the mapping from one hidden layer to the next is parameterized by wn and defined to be:
hn[i] = d−1∑ k=0 wn[k]hn−1[(i+ k) mod d] = (hn−1 ? wn)[i]
The final layer is a fully connected layer parameterized by wN ∈ Rd, such that the final model can be written in the following way:
fσ(x) = ((((x ? w1) ? w2) · · · ) ? wN−1)TwN (11)
Lemma 3 from Gunasekar et al. (2018) shows how we can relate the Fourier coefficients of the weight vectors to the Fourier coefficients of the linear model induced by the model: Lemma. For the circular-convolutional model as in (11):
σ̂ = diag(ŵ1) · · · diag(ŵN−1)ŵN ,
where for n = 1, 2, ..., N, ŵn ∈ Cd are the Fourier coefficients of the parameters wn ∈ Rd.
This lemma connects the convolutional network to the diagonal network, and thus we should expect to see the same incremental learning of the values of the diagonal network exhibited by the Fourier coefficients of the convolutional network.

heading: G.3 CONVOLUTIONAL NETWORKS - EMPIRICAL EXAMINATION
text: In figure 7 we see the same plots as in figure 6 but for the Fourier coefficients of the convolutional model. We see that even when the model is far from the toy parameterization (there is no weight sharing and the initialization is with random Gaussian weights), incremental learning is still clearly seen in the dynamics of the model. We see how the inherent reason for the sparsity towards sparse solution found in Gunasekar et al. (2018) is the result of the dynamics of the model - small amplitudes are attenuated while large ones are amplified.

Review summaries:
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 paper studies the phenomenon of incremental learning in several deep models. It starts with analyzing the optimization dynamics of a toy model, and showing that it follows incremental learning, a notion defined clearly in the paper. In particular, it shows that depth affects the strength of incremental learning in the sense that when the depth of the model is increased (especially when going from N=2 to N=3), the maximal initialization value with which incremental learning can occur is increased. In this sense, deeper models experience incremental learning more easily. The paper then moves on to other “deep linear“ models, including matrix sensing, one-hidden-layer quadratic neural networks and diagonal/convolutional linear neural networks, derives ODEs for the evolution of the singular values in the learned models, which is argued to also lead to incremental learning.