The Implicit Bias of Depth: How Incremental Learning Drives Generalization
Authors: Daniel Gissin
Shai Shalev-Shwartz
Amit Daniely
Venue:  (2020)
Keywords: gradient flow
gradient descent
implicit regularization
implicit bias
generalization
optimization
quadratic network
matrix sensing

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.

Published as a conference paper at ICLR 2020
THE IMPLICIT BIAS OF DEPTH: How INCREMENTAL LEARNING DRIVES GENERALIZATION
Daniel Gissin, Shai Shalev-Shwartz, Amit Daniely School Computer Science The Hebrew University Jerusalem, Israel (daniel.gine gissin, shais, amit wet...dnnelyyyll @mai huj1 ac. i1
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 condi- tions on depth and initialization for which this phenomenon arises in deep linear models. Our main theoretical contribution is dynamical depth separation re- sult, proving that while shallow models can exhibit incremental learning dynam- ies, they require the initialization to be exponentially small for these dynamics present themselves. However, once the model becomes deeper, the dependence becomes polynomial and incremental learning can arise more natural settings. We complement our theoretical findings by experimenting with deep matrix sens- ing, quadratic neural networks and with binary classification using diagonal and convolutional linear networks, showing all of these models exhibit incremental learning.
INTRODUCTION
Neural networks have led 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 neural networks defy the classic statis- tical learning theory bounds. Since these bounds, which depend solely on the capacity of the learned model, are unable to account for the success neural networks, we must examine additional proper- ties 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.
possible way such an implicit bias may present itself, is if gradient-basee 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 [axx et al. (013). 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 the model are learned separately, one at 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 com- pletion and sensing with a factorized parameterization (Gunasekar et al. (2077), Arora et al. (2018), Woodworth et al. (201)). When initialized with small Gaussian weights and trained with small learning rate, such model able to successfully recover the low-rank matrix which labeled the data, even if the problem is highly over-determined and additional regularization is applied. In their proof of low-rank recovery for such models, Li et al. (2017) show that the model remains low- rank throughout the optimization process, leading the successful generalization. Additionally,

---

networks, denotes Published as a conference paper at ICLR 2020
120
2.8
80
okt)
0.4-
10-
40-
0.0
0-
20000
40000
5000
10300
5000
10000
5000
10000
Iteration
Iteration
Iteration
Iteration
(a) Matrix Sensing
(b) Quadratic Nets
(c) Diagonal Nets
(d) Convolutional Nets
Incremental learning dynamics in deep models. Each panel shows the evolution of the five largest values a, the parameters of the induced model. All models were trained using gradient descent with small initialization and learning rate, small training such that there mul- tiple possible solutions. In all cases, the deep parameterization of the models lead to "incremental learning", where the values are learned different rates (larger values are learned first), leading to sparse solutions. (a) Depth 4 matrix sensing, a denotes singular values (see section 4.1). (b) Quadratic networks, denotes singular values (see section (4.)). (c) Depth 3 diagonal networks, denotes feature weights (see section 4.3). (d) Depth 3
Figure I:
amplitudes the frequency domain of the feature weights (see appendix G
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 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 strictive distributional assumptions, |Ronen et al. (2019) show that shallow networks learn functions of gradually increasing frequencies and Nakkiran et (2019) show how deep ReLU networks cor- relate with linear classifiers in the early stages of training.
These findings, along with others, suggest that the generalization ability of deep networks 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 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 seen in figure [
which we discuss further in section 4
2 DYNAMICAL ANALYSIS OF TOY MODEL
We begin by analyzing incremental learning for simple model. This will allow gain clear understanding of the phenomenon and the conditions for it, which we will later be able to apply to variety of other models which incremental learning present.
2.1
PRELIMINARIES
Our simple linear model will be similar to the toy model analyzed by Woodworth et al. (0019) Our input space will be X' = dd and the hypothesis space will be lincar models with non-negative weights, such that:
[a(x) (0,
Rd
2

---

Published as a conference paper at ICLR 2020
We will introduce depth into model, by parameterizing using B in the following way:
Ví: o, w
Where N represents the depth of the model. Since 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 o* E 22 we will study the dynamics of this model for general N under depth-normalized" squared loss over Gaussian inputs, which will allow us to derive our analytical solution:
1 2N
(w)
E . -w 2))
2N 1w N o=11
(2)
We will assume that our model is initialized uniformly with tunable scaling factor, such that:
Vi w0( Voo
(3)
2.2 GRADIENT FLOW ANALYTICAL SOLUTIONS
Analyzing our toy model using gradient flow allows us to obtain an analytical solution for the dy- namics of (t) along with the dynamics of the loss function for a general N. For brevity, the following theorem refers only to = 1,2 and N - oo, however the solutions for 3 < N < oo are similar in structure to N - oc, but more complicated. We also assume of > 0 for brevity, however we can derive the solutions for of = O as well. Note that this result is special case adaptation of the presented in [axe al. (013)) for deep linear networks:
Theorem 1. Minimizing the toy linear model described in ( with gradient flow over the depth normalized squared loss (2), with Gaussian inputs and weights initialized in (3) and assuming o > O leads to the following analytical solutions for different values of N:
= 1: (t = o + (ov - -²)e
o00 e72
= 2: (t 5o ce 1) + +
log (:(()(00 o7)
1
N 00: t= (ot)² (olaai()) a;)
(f(
Proof. The gradient flow equations for our model are the following:
i =
N w [o; -w
N-1
Given the dynamics of the w parameters, we may use the chain rule to derive the dynamics of the induced model, o:
6.
do:
i = w 2N 2N 2N; - 10
2- (oī -.,)
(4)
dw:
This differential equation is solvable for all N, leading to the solutions in the theorem. Taking N 0o in leads to = oo(a a,), which is also solvable.
'This normalization is used for mathematical convenience to have solutions of different depths exhibit similar time scales in their dynamics. Fquivalently, can derive the solutions for the regular square loss and then use different time scalings in the dynamical analysis.
3

---

Published as a conference paper at ICLR 2020
N- 1, 0g.00.00.. -0.1
N 2, 0o-000000... 0.1
N 3, dg-00000. 0.1
N 4, 0.1
1.00
1.00
1.00
1.00
0.73
0.15
0.75
0.75
oi(c)
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
2000
4000
0
1000
2000
1000
2000
1000
2000
N = 1, 00=0.001
N = 2, 0o=0.001
N = 3, 0o=0.001
N = 4, 0g=0.001
1.00
1.00
0.75
0.75
0.75
0.75
oiti)
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
2000
4000
Time 4000
5000
10000
10000
20000
Time
Time
Time
Figure 2: Incremental learning dynamics in the toy model. Each panel shows the evolution of (x(0) for of {12, 6, 4,33 according to analytical solutions theorem under different depths and initializations. The first column has all values converging at the same rate. Notice how the deep parameterization with small initialization leads to distinct phases of learning, where values are learned incrementally (bottom-right) The shallow model's 's much weaker incremental learning, even at small initialization scales (second column), is explained theorem
of
Analyzing these solutions, we see how even 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 2 3, as we will see in the next subsection.
These dynamics are depicted in figure 2 where we see the dynamics the different values (() as learning progresses. When N T, 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 induce sparse solutions if the model is able to fit the data after small amount of learning phases, then it's obtained result will be sparse. Alternatively, if dynamics will lead the minimal & norm solution which is dense. We explore the sparsity inducing bias of our toy model by comparing empirically to a greedy sparse approximation algorithm in appendix D and give our theoretical results the next section.
1, we know that the
INCREMENTAL LEARNING
Equipped with analytical solutions for the dynamics of model for every depth, 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 on + 0, we will study the phenomenon for general depth and for do > 0.
study
First, will define the notion of incremental learning. Since all values of learned in parallel, we can't I expect one value to converge before the other moves at all (which happens for infinitesimal initialization as shown by Gidel (2019). We will need more relaxed definition for incremental learning in finite initialization scales.
Thhe code for reproducing all of our experiments can be found in https: Incrementa Barning
//gi :/mpps://// thub. com dsgissin/ ssin/
4

---

Published as a conference paper at ICLR 2020
Definition 1. Given two values o, such that of 00 0 and both are initialized oz
(,(0) do < dj and given two scalars (0, 1) and f (2. 1), we call the learning of the values (s. - if there exists for which:
0 S s0j < foj S (a((1)
In words, two values have distinct learning phases if the first almost converges ( < 1) before the second changes by much (s < 1). Note that for any N, at) is monotonically increasing and so once 5, (t) = soj, 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 a dynamical depth separation result, showing that incremental learning is depen- si of in different ways for different values of N. The largest difference in dependence happens
dent on between Ñ = 2 and = 3, where the dependence changes from exponential to polynomial:
Theorem 2. Given two values oi oj of toy linear model as in ① where zi
of - and the model initialized as in (3) and given two sealars s E (0, 4) and f E (2.1). then the largest initialization value for which the learning phases of the values are (s, -incremment denoted ob"
bounded in the following way:
30 rf)
8 11-16-11
Soa < Ssoj
8
N =
rf
(1 (1- []r (r-)) 1)
N-
Soo th S soj
x
2
11 f)
Proof sketch (the full proof is given in appendix Rewriting the separable differential equation in 4 to calculate the time until at) ao", get the following:
do
(o)
σ²
l0
The condition for incremental learning is then the requirement that ty(0,) S to(a,), resulting in:
50z do
do
02
(a
t -0)
60
We then relax/restrict the above condition to get necessary/suffiiient condition do. leading to lower and upper bound on oh
Note that the value determining the condition for incremental learning is di if two values are in the of same order of magnitude, then their ratio will close to and we will need small initialization to obtain incremental learning. The dependence the ratio changes with depth, and is exponential for N = This means that incremental learning, while possible for shallow models, is difficult to in practice. This result explains why changing the initialization scale in figure 2 changes the dynamics of the 2 3 models, while not changing the dynamics for N noticeably.
The next theorem extends part of our analysis gradient descent, more realistic setting than the infinitesimal learning rate of gradient flow:
Theorem 3. Given two values di, Tj of depth-2 toy linear model as in 1 such that
and the model initialized as (3) and given two scalurs & E (0, 1/ and f E (2, 1), and assuming o3 2 200, and assuming optimize with grudient descent with learning rate y S oo
for
5

---

Published as a conference paper at ICLR 2020
2((22 - and of the largest value of o², then the largest initialization value for which the learning phases of the values are (s, -iicrreeenttt denoted o is lower and upper bounded in the following way:
1
x I 0
1-f
21 8 jj
0j 1
fr 1 s
8
Where A and B are defined as:
log (1
2. + c² (2) 01
log (1
1 1 log 0 + c² of ?
(
B
log (1 C 0j
We defer the proof to appendix
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 when we take their first order approximation around O, giving us similar bounds and showing that the condition on dg for 2 is exponential in gradient descent as well.
While similar gradient descent results are harder obtain for deeper models, we discuss the general effect of depth on the gradient decent dynamics in appendix
INCREMENTAL LEARNING IN LARGER MODELS
So far, we have only shown interesting properties of incremental learning caused by depth for a toy model. In this section, will relate several deep models toy model and show how incremental learning presents itself in larger models as well.
4.1 MATRIX SENSING
The task of matrix sensing is generalization of matrix completion, where input space is X Rdxd and our model is matrix W E Rdddd such that:
fw(()) (W, A) to (w("A)
Following Arora et al. (2019), we introduce depth by parameterizing the model using a product of matrices and the following initialization scheme (W; RRdxd):
W = WW W1
(5)
Wi E [N], W.(0)= = 1o0
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 depth-normalized squared loss. assuming the data is labeled by matrix sensing model parameterized by PSD W e dd
WWWWWN-I' WT) EAI(((W>WN-1 ... W1) W*, W*
2N
(6)
1
[I(WNNNN=1 WNII W1) 1
2N
The following theorem relates the deep matrix sensing model to our toy model, showing the two have the same dynamical equations:

---

Published as a conference paper at ICLR 2020
Theorem 4. Optimizing the deep matrix sensing model described in (5) with gradient flow
the depth normalized squared loss (6)), with weights initialized as in leads to the following dynamical equations for different values of N:
(t) (t)2 (t)2)(2)))) (o; at((t)
Where o, and of are the ith singular values of W and W* respectively, corresponding to the same singular vector.
The proof follows that of Saxe al. (2013) and Gidel al. (2019) and deferred to appendix
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 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 deep matrix sensing can also be seen in panel (a) figure
4.2 QUADRATIC NEURAL NETWORKS
By drawing connections between quadratic networks and matrix sensing (as in Soltanolkotabi et al. (2018), we can extend our results to these nonlinear models. will study a simplified quadratic network, where input space is X' R& and the first layer parameterized by weight matrix W e Rdxd and followed by a quadratic activation function. The final layer will be a summation layer. We assume, like before, that the labeling function is quadratic network parameterized by W' E RRdxd Our model can be written in the following way, using the following orthogonal initialization scheme:
d (w(x) Σ = (WTW,xx")
w Wo = ao1
Immediately, we see the similarity of the quadratic network to the deep matrix sensing model with N = 2. where the input space is made of rank- I matrices. However, the change in input space forces us to optimize over different loss function to reproduce the same dynamics: Definition 2. Given an input distribution over an input space X with a labeling function X - R and a hypothesis h, the variance loss is defined the following way:
1 [<(((( (x)))² 16
Cear
[y(((()) h(x))²
16
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 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 in 7 with gradientfloow over the variance loss defined in (2) leads to the following dynamical equations:
-a((t)
Where as and of 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 the same depth-2 toy model. showing that shallow quadratic networks can exhibit incremental learning (albeit requiring a small initialization).

---

Published as a conference paper at ICLR 2020
4.3 DIAGONAL/CONVOLLTIINN LINEAR NETWORKS
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 convergence at t + oo (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 xc, we intend 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 (initialized as (3) as special weight- shared case of deep networks with diagonal weight matrices, and we will then show empirical results for the more general setting. We analyze the optimization dynamies of this model over separable
dataset {æ;, 31 /m where y; {+1]. We use the exponential loss (L(f(x),)) v) wf(()) 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:
N
m
2
Us (9 zj
0
m
We see the same dynamical attenuation of small values of a that is seen in the regression model, caused by the multiplication by a, 2- From this, we can expect the same type of incremental learning occur weights of will be learned incrementally until the dataset can be separated by the current support of a. Then, the dynamics strengthen the growth of the current support while relatively attenuating that of the other values. Since the data 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 converge to a sparse solution.
Granted, the above description is just intuition, but panel (c) of figure I 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 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 do is large.
In their work, Gunasekar et al. (2018) show an equivalence between the diagonal network and the circular-convolutione network in the frequency domain. According to their results, we should ex- pect to see the same sparsity-bias of diagonal networks in convolutional networks, when looking at the Fourier coefficients of a. An example of this can be seen in panel (d) of figure and we refer the reader to appendix G for a full discussion of their convolutional model and it's incremental learning dynamics.
5 CONCLUSION
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 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 first step towards that goal.
ACKNOWLEDGMENTTS
This research is supported by the European Research Council (TheoryDL project).
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization.. arXiv preprint arXiv: 06009, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems 32, pp. 7411-7422. Curran Associates, Inc., 2019. URL http:://papers.nips..ccoo pdf 8960-1mp Bee- wtt.://aa.......oeeaaaaaaaaaaaaa
Remi Tachet des Combes, Mohammad Pezeshki, Samira Shabanian, Aaron Courville, and Yoshua Bengio. On the learning dynamics of deep neural networks. arXiv preprint arXiv:/809 888406884, 2018.
Gauthier Gidel, Francis Bach, and Simon Lacoste-lulien. Implicit regularization of discrete gradient dynamics in linear neural networks. Advances in Neural Information Processing Systems, pp- 3196-3206, 2019.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp- 9461-9471, 2018
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference Learning Theory, pp. 1772-1798, 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterizee matrix sensing and neural networks with quadratic activations. arXiv preprint arXiv: 1711v22712.092033 2017.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro HP Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. arXiv preprint 1rXiv:1803.01905. 2018.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang. Benjamin L Edelman, Fred Zhang, and Boaz Barak. Sgd on neural networks learns functions of increasing complexity. arXiv preprint arXiv: 1rX5v:I905. 19w..11955...,,... 2019.
Yagyensh Chandra Pati, Ramin Rezaïifar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pp. 40 44. IEEE, 1993.
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. gence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems 32, pp. 4763-4772. Cur- ran Associates, Inc., 2019.
The conver-
URL. http: http:///ppprrr..ssssccopmom
-723-the-comee www.ee--onveeeeceee....eo rate- ofnteall-eurall- nww.oneewwweoeeeoe for Stt.reeeeeeeeteeeeeaaaaeeeeettaa -er.rrroo------eaaeeee---eeooooo of-fffferee-e fr
pdf
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2))742-769, 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-287) 2018.

---

Published as a conference paper at ICLR 2020
Francis Williams, Matthew Trager, Claudio Silva, Daniele Panozzo, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. arXiv preprint 1rXiv:1906.0766 07842, 2019.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. arXiv preprint arXiv:1906.05827, 2019, 2019.
A PROOF OF THEOREM
Theorem. Given values ds, Jjj of toy linear model as in Q such that of o; = 1 and the model initialized as in ( and given two sealars s E (0, 3) and f E (2, then the largest initialization value for which the learning phases of the values are f inncremmenll denoted ob is lower and upper bounded in the following way:
s0ī 3 1
(1/)
5 7
0000 S $0
N = 2
rf
rf
80
[r- - 1+ (1-1 f)
N
Soa th
S soj
T
2 3
Proof. Our strategy will be to define the time ta for which a value reaches a fraction a it's optimal value, and then require that ty (a;) I (a,). We begin with recalling the differential equation which determines the dynamics of the model:
3 (a 0)
Since the solution for N 2 3 is implicit and difficult to manage in general form, we will define fo using the integral of the differential equation. The equation is separable, and under initialization of ao can describe to (o) in the following way:
o00"
do
(a)
02 3 l0" -
Incremental learning takes place when or(t)) = fot happens before (T((,) = -07.. We write this condition in the following way:
10
do
500
do
(a 0)
o²
(a)
σ)
Plugging in d; roy and rearranging, we get the following necessary and sufficient condition for incremental learning:
fTØ
do
do
x
2
ra
Our last step before relaxing and restricting condition will be to split the integral the left-hand side into two integrals:
do
fro + ro
da
do
<
(8)
3
20;
At this point, cannot solve this equation and isolate do obtain clear threshold condition on it for incremental learning. Instead, we will relax/restrict the above condition to get a neces- sary/sufficient condition do, leading to lower and upper bound on the threshold value of do-
10

---

Published as a conference paper at ICLR 2020
SUFFICIENT CONDITION
To obtain a sufficient (but not necessary) condition on on, we may make the condition stricter either by increasing the left-hand side 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:
{
do
do
S (r
(r-
*
a $
Next, we note that the integration bounds give us a bound on a for either integral. This means we can replace 1 with on the right-hand side, and replace 1 side:
_ with f on the left-hand raj
STo S
do 22
(an) do /
(r (r- -
saz
We may now solve these integrals for every N and isolate on. obtaining the lower bound o We start with the case where
1 1- (log(fro3) log(sa3)) $ (r ())g(())))) - log(on))
Rearranging to isolate do, obtain our result:
an S s0j o (
For the N 2 3 case, we have the following after solving the integrals:
1 (
1 - (r (r-1)(( ( 1 1
(
))
1- 80
rfaj
80;
1-
For simplicity we may further restrict the condition by removing the term do gives us the following:
Soolvin for
r/03
(1- f) x²= 1 (r
To S 80z
NECESSARY CONDITION
To obtain a necessary (but not sufficient) condition on on. we may relax the condition in (8) either by decreasing the left-hand side increasing the right-hand side. We begin by rearranging the equation:
fro Jtrme 203
do
800
da
80
da
<
0²
3
(1
3
rd
Like before, we may the integration bounds bound a. Plugging in so for all integrals decreases the left-hand side and increases the right-hand side, leading us to the following:
r
fra
do
r
r
da
<
0² N

---

Published as a conference paper at ICLR 2020
Rearranging, get the following inequality:
f do
[0] do
8 og d² x2-
We now solve the integrals for the different cases, For = 2, we have:
log(Sro)) log(so)) S (1o((503) - log(
Rearranging to isolate oo, we get our condition:
σ S so
Finally, for N 2 3, we solve the integrals to give us:
(1
1 (00 -
{ -
)
1-
=000)
rfoj
s0g
Rearranging to isolate co, we get our condition:
(--1) x
σ0 S 80
SUMMARY
For a given N, we derived a sufficient condition and a necessary condition dn for (s incremental learning. The necessary and sufficient condition on dg, which the largest initialization value for which we see incremental learning (denoted of"). 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 changes with depth with substantial difference when we move from shallow models (N 2) to deeper ones (N 2 3)
B PROOF OF THEOREM 3
Theorem. Given two values os, oj of a depth-2 toy linear model as ① such that zi and the model is initialized as in (3, and given two scalars s E (0, 1) and f E (2,1) 1), and assuming optimize with gradient descent with learning rate n &f for c 2(v2 - 1) and of the largest value o", then the largest initialization value for which the learning phases of the values are (s, (s,f)) f)-incrrmmnttal, denoted th is lower and upper bounded in the following way:
0f 2 20 and assuming
1
d-11 < o <
1 1-f
21
2r
1- 8
Where A and B are defined as:
log (1 - c - o
+ 0
log (1
2
A =
B
o
log (1 Co
22
log (1
+ 2
(-)
0j
0
12

---

Published as a conference paper at ICLR 2020
Proof. To show result for gradient descent and N build on the proof techniques of theorem Gidel et al. (2019). We start by deriving the recurrence relation for the values (tt) for general depth, when & now stands for the iteration. Remembering that w di write down the gradient update for (t):::
1 (0) (oi(t)+ 1 va00+ o.)
wi(t+ w:(() +
Raising (() to the Nth power, get the gradient update for the values:
1 - -())))))))))))))) =1 (o;--))) oo:())
o,(t+1)==
Next, we will prove simple lemma which gives the maximal learning rate will consider for the analysis, for which there no overshooting (the values don't grow larger than the optimal values).
Lemma 1. For the gradient update in 99, assuming a,(0) < of if S (3, 2- then:
(=)²-²
and N 2 2,
Vt: o, - oī
Proof. Plugging in = c
2-
for c v 1, we have:
(cal1)) 1
(1)(2(()))
Gi(()
1-
(1-(-s(t)
0, -1)+))=;;([[ N
Soi
o;
Defining and dividing both sides by of we have:
of
(t + S (it)eer(0) & (1-r,(1)
It is enough show that for any 0 < < 1, have that re" (1-r) < 1, over-shooting occurs when rt(t) > 1. Indeed, this function is monotomic increasing in 0 S S (since the exponent is non negative), and equals 1 when < 1 can cross 1, then (t) < 1 for any t. This concludes our proof.
1. Since
is a fixed point and no iteration that starts at
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 (t) from below and above, which will give us a lower and upper bound for ta (az). Once we have these bounds, we will be able to describe either necessary or sufficient condition on dg incremental learning, similar theorem
The update rule for N = is:
1 n (M0;-oo((1) =x(t)))² o, =(t++)=o((tt((
Next, we plug e for 2(V2 1) 1 and denote R, oj and r.(t) e:(t) get:
o; < to
of
( 1 c (((1):(1)))
13

---

Published as a conference paper at ICLR 2020
Following theorem 3 of Gidel et al. (2019), we bound (1)
07(1 1) 0:(() (1+ gR (t)))
1
0,(1) 1+ (1 (e(t) + ((()
0,(1) 1+ (1 (1-r (1) + 1 R3))
o,(() (1 11111 (1 + c²
R₂))
1
2²
(cR,
4 R
(t
o,(t) 0,
Where in the fourth line we use the inequality from both sides obtain:
I
2 1 -
vx 2
0.
We may now subtract of
14
- cR: -
)1
R
1
)1 1
cR.
R
(t) of
o,(t
4
80
oi
4
We may now obtain a bound on la (a;) by plugging in o1( ao} and taking the log:
log 1
c²
) 2 ta log (1 cRt
R
a1 c.
4
Rearranging (note that log (1 - cRa - & n?) the log positive), we get:
< 0 and that our choice of e keeps the argument of
1-a log
al
1)
ta (o,) 2 log (1 cR: 22 R2)
Next, we follow the same procedure for an upper bound. Starting with our update step:
1 0, ( 11) 0,(t) 1+ (1 (1)r)(()) - (((11
1
1
0,(() 1 + (1 (1)))e))
ot) (1 - (1-r)(t))eR + (1 (11rr((t) (1)
Where in the last line we use the inequality + < x x2 Yx N 0. Subtracting J from both sides, we get:
(t) or I -
(1-
cR. + +
< -
cR, + RR?) oi )1 -
11 oi
To
Rearranging like before, we get the bound on the a-time:
log
1 1-a
al -1)
ta (0,)) < log (1 - cR, + c2R(
14

---

Published as a conference paper at ICLR 2020
Given these bounds, would like to find the conditions do that allows for f) -incremental learning. We will find a sufficient condition and a necessary condition, like in the proof of theorem 2
SUFFICIENT CONDITION
sufficient condition for incremental learning will be one which is possibly stricter than the exact condition. We can find such condition by requiring the upper bound of (y(a)) to be smaller than the lower bound on &g (Oz). This becomes the following condition:
log
1-f d0
log
1-s 10
1 ai -0-00 cR. o R.)
0j -00
log
log (1 cRj R2)
log 1 eR, +o² +2²)2) and rearranging, we get the following:
Defining A
1- ot n2))
1 do log
Ou
Alog
f a; 00
0
We may now take the exponent of both sides and rearrange again, remembering = 1, get the following condition:
(0j -00)
2 0)
o - σ0)
Now, we will add the very reasonable assumption that 03 200. which allows us replace -i-00 with + and replace (o;-o)) 1-1 with (50,) only making the condition stricter. This simplifies the expression to the following:
-00
rf 2 - 28 s
Now rearrange and isolate de get sufficient condition for incremental learning:
0j 1 1- - σo - 21-8 5 2r
NECESSARY CONDITION
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 tt (ar;) to be smaller than the upper bound on ta,). This becomes the following condition:
log 1-1 ag 7
1-x log
oj 0j-00
o3
log cR, - R?)
log (1 -CR, + RRR
log 11 eR, 2² R log [1 t tc2
Defining B
and rearranging, we get the following:
log
1 1- du
2 B log
d
f 03 00
0 d0
15

---

Published as a conference paper at ICLR 2020
We may take the exponent of both sides and rearrange again, remembering 0 the following condition:
1, get
(0) σa) (roj σ
1 - 8)
0
We may now relax the condition further, by removing the from the denominator of the left-hand side and the do from the numerator. This gives us the following:
8
Finally, rearranging gives us the necessary condition:
1
Oo S 1
oj f
C DISCUSSION OF GRADIENT DESCENT FOR GENERAL N
While we were able to generalize our result to gradient descent for N = 2, our proof technique relies the ability get non-implicit solution for (t) which discretized and bounded. This harder to generalize to larger values of N, where the solution is implicit. Still, we can informally illustrate the effect of depth 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 a,, for a learning rate 7) c( [ 3.
oit) =((++)=a((t(( c - o,t)) (0)-))))))))
oi
To compare two values in the same scales, we will divide both sides by the optimal value of and look at the update step of the ratio r; of
az(t) also denoting RG of
oi.
(t(t 11)+))= N xr,)² (1-rr(())))
We will focus on the early stages of the optimization process, where & This means we can neglect the 1 - r:(t) term in the update step, giving us the approximate update step we will use to compare the general j.j values:
r: ((++1)=r(0)) e ((()=+()))
We would like to compare the dynamics r; and rj, which difficult to when the recurrence relation isn't solvable. However, 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 c. we can describe the initialization of ry using that of ry:
observe the first iteration of gradient descent and see how
(y = (0;
Plugging in the initial conditions and noting that R. rRj, we get:
16

---

Published as a conference paper at ICLR 2020
r1(1) r:(0) (1 1 cRa
N ~r:(0)=-3 -r((0)=-3)
N
ry(1) = r.()) Vrr 1 - CR 2
N x)(0)²*))
N
We that the two ratios have similar update, with the ratio of optimal values playing role in how large the initial value is versus how large the added value is. When we use a small learning rate, have very small which means can make final approximation and neglect the higher order terms of c:
(1) (0) + cR,-R rr((0)= (1) (0) + ( x cR² & (0)
We can see that while the initial conditions favor ry. the size of the update for r, is larger by factor of r " when the initialization and learning rates are small. This accumulates throughout the optimization, making 7 eventually converge faster than ry.
The effect of depth here is clear- the deeper the model, the larger the relative step size of r, and the faster it converges relative to ry.
D COMPARISON OF THE TOY MODEL AND OMP
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 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 timinuuus-time extension
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:
fx(
(a, x)
However, we parameterize using w4, w_ Rdd in the following way:
0, w N w
Vi, W4, (+) w w_.
Vo
We can now treat this algorithm as a sparse approximation pursuit algorithm given a dictionary D E Rdxn and an example Rdd wish find the sparsest for which Da z x by minimizing Under this setting, we can compare OMP to our toy
the to norm of a subject to Da - x 2 ( model by comparing the sets of features that the two algorithms choose for a given example and dictionary.
In figure 3 we such a comparison. Using dictionary of 1000 atoms and example of dimen- sionality 80 sampled from random hidden vector of a given sparsity we run both algorithms and record the first s features c
Note that this problem is equivalent learning the toy model the squared loss, where the examples in the original learning problem play role the dictionary.
'oor the toy model, we define feature to be "chosen" once it's value passes some small threshold in absolute value.
17

---

Published as a conference paper at ICLR 2020
Fraction of Same Feature Sets
0.9
0.8
0.6
0.5
0.3
10
20
25
Sparsity of Solution
Figure 3: Empirical comparison of the dynamics the toy model to OMP. The toy model has depth of 5 and was initialized with scale of le-4 and learning rate of 3e-3. We compare the fraction of agreement between the sets of first s features selected the two algorithms for every given sparsity level s, averaged over 100 experiments (the shaded regions are empirical standard deviations). For example, for sparsity level 3, we look at the sets of first features selected by each algorithm and calculate the fraction of them that appear in both sets.
For every sparsity s, 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 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 put our finger on another strength of the dynamics deep models while greedy algo- rithms such OMP require the analytical solution 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 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 OMP.
E INCREMENTAL LEARNING IN MATRIX SENSING
E. PROOF OF THEOREM
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 in (5) leads to the following dynamical equations for different values of N:
6,(1) 00) & (t())
Where o; and of are the ith singular values of W and W respectively, corresponding to the same singular vectors.
18

---

Published as a conference paper at ICLR 2020
Proof. We will adapt the proof from Saxe al. (2013) for multilayer linear networks. The gradient flow equations for Wn, n E [M] are:
Wa = N WT (W* W)W #+1:N
Where we denote Wi:k
I W..
Since assumed W* (symmetrie) PSD, there exists an orthogonal matrix U for which D UW where D* diagonal. Under the initialization in (3). U diagonalizes all Wa matrices at initialization such that D, = UW,U"= Voul. Making this change of variables for all W we get:
1 T D - W Du+E:NU N
Wr
Rearranging, we get a set of decoupled differential equations for the singular values of W
D. 1 Din -D)Dn+1NN N
Note that since these matrices are all diagonal initialization, the above dynamics ensure that they remain diagonal throughout the optimization. Denoting nn,i as the i'th singular value of W,, and d; as the i'th singular value of W, we get the following differential equation:
Tnii N [ - oi) II
jØn
Since we assume at initialization that Vn, m, i: (0,) 0 (0) = Vou, the above dynamics the same for all singular values and we get Vn, m, (t, = T (t) a/o,(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 W,, matrices. Denoting o --n, -Il Tk, and using the chain rule:
N
On.i n.i =o; 2- 2 (o; o4))
E.2 EMPIRICAL EXAMINATION
Our analytical results only applicable for the population loss over Gaussian inputs. These condi- tions 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 Gaussian distribution with small variance. To show our conclusions regarding incremental learning extend qualitatively to more natural settings, we empirically examine the deep matrix sensing model 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 our theory for describing the exact dynamics of the optimization for these kinds of over-determined problems, the qualitative conclusions 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 increase the current rank of our model may find a solution that has a different set of singular values and vectors and thus all singular values change at the beginning of new learning phase. This demonstrates the importance of incremental learning for obtaining
19

---

Published as a conference paper at ICLR 2020
Depth 1, 1000 ecanples
Depth ecamptes
Depth 1000 noumples
Depth moupple
2200
4000
6200
8000
20003
2539 500
7590
20000 32306 25003
2002 4002 66c3 6890 103002200040000
5000 136ce 15300 20000 2000
35
Soxlect
Figure 4: Evolution of the top-5 singular values of the deep matrix sensing model, with Gaussian initialization with variance such that the initial singular values are in expectation le-4. The model's size and data in 50x50 The columns correspond different parameterization depths, while the rows correspond to different dataset sizes. In both cases the problem is over-determined, since the number of examples is smaller than the number of parameters. Since the original matrix is rank-4, we can recognize an unsuccessful recovery when all five singular values are nonzero, as seen clearly for both depth-1 plots.
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 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 QUADRATIC NETWORKS
F.1 PROOF OF THEOREM 5
Theorem. Minimizing the quadratic network described and initialized as in 7 with gradient flow the variance loss defined in 2 with Gaussian inputs leads the following dynamical equa- tions:
a,(t)= - -
Where o, and of are the ith singular values of W and W respectively, corresponding to the same singular vectors.
Proof. Our proof will follow similar lines the analysis of the deep matrix sensing model. Taking the expectation of the variance loss over Gaussian inputs for our model gives us:
(W)
E. Ex(((W? V W, W, E. (WT - W W, xx= 1)=
16
16
1
I! W. -W'll 16
Tr(W. w
Tr(W? - W
| W. WTW
Following the gradient flow dynamics over W leads the following differential equation:
20

---

Published as a conference paper at ICLR 2020
W W(W WWTW)
We can now calculate the gradient flow dynamics of W using the chain rule:
wTw WTW WTW WWT
WTW) (WTW. -W WTW)WTW) (10) ( WWW
Now, under our initialization W Wo = Tn we get that WTW and WTW: W. are simultaneously
diagonalizable at initialization by some matrix U, such that the following is true for diagonal D and D":
D(0) = U"W)")
D" = W'=
Multiplying equation 100 by U and U gives us the following dynamics for the singular values of WTW:
D
These matrices diagonal initialization, and remain diagonal throughout the dynamics (the off- diagonal elements are static according to these equations). We may now look at the dynamics of single diagonal element, noticing it equivalent to the depth-2 toy model:
à; = o. - -;:)
F.2 DISCUSSION OF THE VARIANCE LOSS
may seem that the variance loss is an unnatural loss function to analyze, since it isn't used in prac- tice. While this 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 defined over the squared loss. Then, we show how adding global bias the quadratic network leads similar dynamics for small initialization scales.
F.2.1 DYNAMICAL DERIVATION
in the previous section, derive the differential equations for the singular values of WTW under the variance loss:
à; = a; - -;)
We will now derive similar equations for the squared loss. The scaled squared loss expectation over the Gaussian inputs is:
1 F. ((W..WWW -WT WT
((W)
16
1
W W. - w" + -
1
Tr(W? W. wy
16
21

---

Published as a conference paper at ICLR 2020
Defining A WTW. W for brevity, the differential equations for W become:
1 W " WA + 1 TT(A))
Calculating the dynamics of W W after noting that it is simultaneously diagonalizable with W W. (as in the derivation for the variance loss) leads to the following differential equations for the singular values of W:W::
ē, = 0. (: oi + D0j -o))
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's expect quadratic networks optimized over the squared loss to exhibit incremental learning behavior: We next show how adding 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 E Rdxd and scalar E I::
fw.o(æ) = (W W, (xx +
We may now analyze gradient flow of the squared loss. Following the same methods as before, this leads us to the following differential equations:
6 -0,000 (0; os -(0 l0j o,) - - b))
b = E63 - o,) 6 3
Notice how, if b is at it's optimum given time (b 00= (o b*), the dynamics of align with those of the variance loss. Alternatively, when b = 6", 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 it's optimum "most of the time", such that the singular values don't 't change much during the times when it is not at it's optimum.
Observing the differential equations for and for as, we see they are similar (if we ignore the of -a; value which doesn't change the order of magnitude of the entire expression when there haven't 't been many learning phases yet). The only difference being a multiplication by o,, This means that we may informally write:
6,(1) b(1)
~ o1
Since at initialization and until the learning phase of o; takes place, have (t) < 1, 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
22

---

Published as a conference paper at ICLR 2020
044
US0 1008
183 183 263
1200
3200
2010
100
33
652
2003
200
2013
230. 205
2007 120
2005
6.0 10%
1/5
245 1022 000 1977
1002
Figure 5: Quadratic model's evolution of top-5 singular values for rank-4 labeling function. The rows correspond to whether or not a global bias is introduced to the model. The first two columns for large dataset (one optimal solution) and the last two columns determined problem). When a bias introduced, is initialized to it's optimal value at initialization. Note how without the bias, the singular values are learned together and there over-shooting of the optimal singular value caused by the coupling of the dynamics of the singular values. For the small datasets, we see that the model with no bias reaches a solution with larger rank. Once a global bias is introduced, the dynamics become more incremental as in the analysis of the variance loss. Note that in this case the solution obtained for the small dataset is the optimal low-rank solution.
for small dataset (over-
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 added global bias resemble the idcalized dynamics of the variance loss for depth-2 linear model which we analyze formally in the paper. In figure 5 we experimentally show how adding bias quadratic network does lead incremental learning similar the depth-2 toy model.
G INCREMENTAL LEARNING IN CLASSIFICATION
G.1 DIAGONAL NETWORKS
we viewed our toy model as special case of the deep diagonal networks described in Gunasekar et al. (2018), expected dynamics of the largest values of a for different depths of the model. We see that the same type of incremental learning we saw in earlier models exists here 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 role here well, with the solution being more sparse when the initialization is small. We should note that these results do not defy the results Gunasekar et al, (2018) (from which we would expect the initialization not matter), since their results deal with the solution t -
In section 4.3
be biased towards sparse solutions. Figure 6 shows the
G.2 CONVOLUTIONAL NETWORKS PRELIMINARIES
The linear circular- convolutoan 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 w,, and defined to be:
h [
Σ wn 1:)An-11( + k) mod d = (hn-1 w.)ld
23

---

Published as a conference paper at ICLR 2020
Correlation vs Depth
Depth 1
Depth
Depth 3
1.00
T0p Weights
Top-5 Weightts
Top-5 Welghts
22.3
5823
1200 8000
<300 66co scao Iteration
Depti
Iteration
Iteration
Figure 6: Incremental learning in binary classification. model in section 4.3 is trained over 200 ii.d. random Gaussian examples, where = 100. The data is labeled by weight vector with nonzero values, making the problem realizable with a sparse solution while the max-margin solution isn't sparse. The left panel describes the obtained solution's 's correlation with the sparse labeling vector for different depths and initializations. The results are averaged over 100 experiments, with shaded regions denoting empirical standard deviations. We see that depth-1 models reach results similar to the max-margin SVM solution predicted by Gunasekar et al. (2018), while deeper models are highly correlated with the sparse solution, with this correlation increasing when the initialization scale is small. The other panels show the evolution of the absolute values of the top-5 weights of for the smallest initialization scale. Note that increase the depth, incremental learning is clearly presented.
The final layer is fully connected layer parameterized by wN Rd, such that the final model be written in the following way:
fo (I) ((((x * w1) ..2)...) wI)
(11)
Lemma 3 from Gunasekar et al. 2018)) shows how we can relate the Fourier coefficients of the weight vectors the Fourier coefficients of the linear model induced by the model:
Lemma. For the circular-comvolttiond model as in 11
diag((r)
where for = 1,2, N, tn E Cdd are the Fourier coefficients of the parameters w.. E 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 the convolutional network.
G.3 CONVOLUTIONAL NETWORKS EMPIRICAL EXAMINATION
In figure 7 we the same plots in figure 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 al. (2018) is the result of the dynamics of the model small ampli- tudes are attenuated while large ones are amplified.
24

---

Published as a conference paper at ICLR 2020
Carrelation Depth
Death
Death
100
100
334
3009
20000
2000
3300
1000
8000
4000 0000 100 1000 5003
0800
Figure 7: Incremental learning in convolutional networks. A model as in appendix G is trained over 200 i.i.d. random Gaussian examples, where d 100. The weights initialized randomly and the data is labeled by weight vector with 4 nonzero frequencies, making the problem realizable with sparse solution the frequency domain. The left panel describes the obtained solution's 's correlation in the frequency domain with the sparse labeling vector for different depths and initializations. The results are averaged over experiments, with shaded regions denoting empirical standard deviations. We see that depth-1 models reach results similar to the max-margin SVM solution, while deeper models are highly correlated with the optimal sparse solution. The other panels show the evolution of the amplitudes of the top-5 frequencies of a for the smallest initialization scale. Note that increase the depth, incremental learning is clearly presented.
25


Reviews:
[{"review_id": "rkg7aURHjB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI would recommend a “weak accept” for this paper. The nice contributions include a clear definition of incremental learning, results showing the depth’s effect on incremental learning as well as extensions to several other models. My main question is regarding the relevance of the toy model to more realistic models, as I will discuss below, and I’d love to hear more about the authors’ thoughts on this.\n\nBesides being linear, another important simplification of the toy model is that there is no interaction among the hidden units, which is rather crucial for ordinary neural networks. I am curious to what extent the authors think this simplification matters for incremental learning. It’s nice that similar analysis can be extended to other settings including matrix sensing, quadratic NNs and linear diagonal/convolutional NNs. But it seems that there is no theorem analogous to theorems 2 and 3 for those models, and I am curious why.\n\nThe qualitative transition from N=2 to N=3 in the toy model is interesting. Is there a more intuitive explanation for it? Also, from Figure 2, it seems hard to say whether there really is a qualitative change between N=2 and N=3.\n\nSome other suggestions for improvement:\n1. It may be helpful to somehow visualize the bounds obtained in theorems 2 and 3.\n2. Some typos: \n1) “it’s” should be “its” in the last paragraph of section 2.\n2) ”effect” should be “affect” in the first paragraph of section 3.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BylBwTjpFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the role of depth on incremental learning in several toy models for neural networks. In particular, they show that in these models, deep models require polynomially small initializations to exhibit incremental learning than shallow models. The paper is well written, and I think there are several interesting contributions.\n\nThe authors contribute analysis for non-asymptotically small initializations, and study an interesting role of depth in how small this initialization must be. Furthermore, they extend their results to several other models including matrix sensing, linear convnets, and classification.\n\nI think nonetheless the paper suffers from a few issues. Some very important ones.\n\n1) The authors study the role of depth on incremental learning, and exhibit how several models theoretically have this property. However, they do not study how incremental learning drives generalization. In the entire paper, the gradient flow is with respect to the *expected* loss, rather than the empirical loss. The research program of incremental learning for deep neural networks would show something like \"Incremental learning exists when minimizing empirical loss\", \"Incremental learning and early stopping imply certain properties (like low capacity) on the resulting neural network\" and \"These properties imply low generalization error\". However, the fact that the authors' models minimize the expected loss altogether a priori rules out the direct applicability of this result to explaining generalization. That is OK, in the sense that one could aim for these results to be modified and applied with empirical losses, and then a separate line of research could study how incremental learning bounds generalization error.\nIn this sense, I think the authors should take out the \"how incremental learning drives generalization\" since there is no study on generalization whatsoever, just how depth plays a role in incremental learning. An alternative title could be \"How depth drives incremental learning.\" or something like that.\n\n2) Another point is that all these models are very toy and mostly linear. That is OK again, but the introduction overclaims in this respect. The sentences \"we characterize the effect of the model's depth [...] showing how deeper models allow for incremental learning in larger (realistic) initialization scales.\" and \"Once incremental learning has been defined and characterized for the toy model, we generalize our results theoretically and empirically for larger models\". This makes it seem that results apply to realistic settings, which is really far from true. I'm not expecting realistic results, this is a nascent theory, but I am expected the claims made to be validated and not misleading.\n\n3) In section 2.2, sigma(t) for N-> \\infty is undefined, and the proof for this result is missing (only for finite N appears). In particular, it is not clear if sigma(t) for N -> \\infty is obtained by a) taking limit N -> \\infty in the ODE of equation (8), and then finding the solution of this limiting ODE, or b) finding \\sigma(t) for equation (8) on finite N and then taking limit N -> \\infty of the solution. I.e. there are two potentially different ways to define \\sigma(t) for N -> \\infty which are solving the ODE and then taking limit or taking limit and then solving the limiting ODE. The definition of \\sigma(t) for N -> \\infty is completely missing so I have no way to assess the validity of this result.\n\nA small pet peeve: when writing math, try to avoid using symbols like \\forall and \\exists unless you're writing a logic paper. Instead, try to write equation 2 like $$\\sigma_i = w_i^N \\quad \\text{for all i = 1, \\dots, d} $$, which reads a lot nicer. Also, avoid assigning equation numbers to equations you never reference.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bye65cRntB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Contributions*\nThis 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. \nThis 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).\n\nI 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)\nAlso, 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])\n\nNote 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). \n \n*Decision*\nWeak 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. \nShowing 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. \nHowever, 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. \nI develop these points in the *questions* section of my review.\n \n*Questions*\n- 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. \n- 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)$?)\n- In the theorem 3 who is $c$ ? who is $\\sigma_1$ (the largest eigenvalue?) ?\n- 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. \n- You restrict yourself to a uniform initialization. Could you extend your results (and definitions) to non-uniform initialization (particularly initialization where  \n- Very small initialization is a big issue in practice because it induces very small gradient at the beginning of the training \n \n- 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)? \n \n*Minor remark*\n- Saxe et al. 2013 as been accepted to ICLR in 2014 (would be better to cite the ICLR proceedings) see [1]\n \n[1] Saxe et al. 2014 in ICLR url: https://openreview.net/forum?id=_wzZwKpTDF_9C\n\n\n=== After rebuttal === \nI have read the authors' response.\nI think the authors could have discussed more the interpretation of Theorem 3. in the revision. \nBut, I really like the main takeaway which is that there is a huge discrepancy between 2 and 3 layers in terms of dynamics.  \n\nI maintain my weak accept\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the role of depth on incremental learning, defined as a favorable learning regime in which one searches through the hypothesis space in increasing order of complexity. Specifically, it establishes a dynamical depth separation result, whereby shallow models require exponetially smaller initializations than deep ones in order to operate in the incremental learning regime. 

Despite some concerns shared amongst reviewers about the significance of these results to explain realistic deep models (that exhibit nonlinear behavior as well as interactions between neurons) and some remarks about the precision of some claims, the overall consensus -- also shared by the AC -- is that this paper puts forward an interesting phenomenon that will likely spark future research in this important direction. The AC thus recommends acceptance. 
Decision: Accept (Poster)