Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
Authors: Andrew Saxe, James L. McClelland, Surya Ganguli
ICLR 2014

Abstract: Despite the widespread practical success of deep learning methods, our theoretical understanding of the dynamics of learning in deep neural networks remains quite sparse. We attempt to bridge the gap between the theory and practice of deep learning by systematically analyzing learning dynamics for the restricted case of deep linear neural networks. Despite the linearity of their input-output map, such networks have nonlinear gradient descent dynamics on weights that change with the addition of each new hidden layer. We show that deep linear networks exhibit nonlinear learning phenomena similar to those seen in simulations of nonlinear networks, including long plateaus followed by rapid transitions to lower error solutions, and faster convergence from greedy unsupervised pretraining initial conditions than from random initial conditions. We provide an analytical description of these phenomena by finding new exact solutions to the nonlinear dynamics of deep learning. Our theoretical analysis also reveals the surprising finding that as the depth of a network approaches infinity, learning speed remains finite: for a special class of initial conditions on the weights, very deep networks incur only a finite delay in learning speed relative to shallow networks. We further show that, under certain conditions on the training data, unsupervised pretraining can find this special class of initial conditions, thereby providing analytical insight into the success of unsupervised pretraining in deep supervised learning tasks.


Peer review:
[Review]:
Thank you for the careful reviews! We've incorporated the suggestions made into a new revised draft, which will appear on arxiv soon (by Thu Feb 20th ).  We've split up our responses below by reviewer.

All reviewers:

Formatting issues: Thank you for pointing these out, we have corrected these issues in the revised draft.

Length/lack of space:  We realize this paper is a little long.  We tried to make our presentation as clear as possible in lieu of adhering strictly to the page limit, since the ICLR call for papers said it would not be too strict about space.  However, if it is necessary to get it down to size it will be straightforward to do so by judiciously moving a bunch of information to the supplementary material.  The fact that the paper will have large amounts of supplementary material should not on the other hand be interpreted as a weakness - but rather as a strength.   Moreover, if the paper is chosen as one of the ones to be published in JMLR, the supplementary material can be brought back in to make a substantive longer paper we feel.   


Reviewer a044:
-'It should be noted that the authors' learning rule is not the batch version of the standard backpropagation algorithm'

We note, as mentioned in our earlier response, that we do in fact treat standard backpropagation. Our equations may look unfamiliar but they are simply a rearrangement of the terms in standard backpropagation (and the rearrangement uses the linearity of the network).


Reviewer 733d:

-Special initial conditions: “The central issue I have with this paper is that the special initial conditions in which in analysis is done are essentially a partial solution to an SVD problem, which if it were solved fully, would give the optimal weights of the linear network in one step. In particular, the assumptions used require that the weight matrices share singular vectors in a way that basically turns the optimization across all layers into a decoupled set of scalar optimizations. In non-linear networks, where the optimal solution isn't given by an SVD, it is harder to believe that this kind of partial SVD would help as much as it does in the linear case (or perhaps at all).

Our main goal is to understand the dynamics of learning in deep linear networks. In linear networks, the SVD is crucial to the solution--and hence it should not be surprising that it plays a critical role in understanding the dynamics as well. Finding a change of variables in which the dynamics decouple is a central contribution of this paper. We also note that the dynamics starting from small random weights are very well described by our solutions (see our Fig. 3)--hence our special initial conditions are not too special, in the sense that they behave similarly to starting from small random weights. We certainly agree that the change of variables we use will not necessarily help decouple the dynamics in nonlinear networks when they are operating in their nonlinear regime, but we believe our results shed light on certain behaviors of nonlinear networks for two reasons. First, even nonlinear networks, when they contain nonlinearities such as tanh and are initialized with small random values, may start off in a roughly linear regime that is well described by our results (see our Fig. 3 for an empirical example). Thus early in training, nonlinear networks may behave similarly, though the quality of the linear approximation is likely to break down as training proceeds and the network enters its nonlinear regime. Second, our deep linear networks exhibit a number of features seen in nonlinear nets, such as long plateaus during training with relatively little performance improvement followed by rapid learning; a slowing of training speeds with depth; and faster convergence from pretrained initial conditions than from small random initial conditions. Fully understanding these phenomena in the linear case is an important goal in its own right, and may lead to further avenues of analysis for certain nonlinearities (such as piecewise linear activation functions like rectified linear units).

Furthermore, in the newer version of the manuscript, we note that we have analyzed not only pre-trained initial conditions on weights, but also a new class of random orthogonal initial conditions on weights, and shown that they both yield depth independent learning times, in contrast to random Gaussian (Glorot-style) initialization.   Thus our newer version yields an initialization method (random orthogonal) that does not involve solving any part of the optimization problem (not that pre-training either involves solving the supervised learning problem). 

-Learning speed analysis in continuous and discrete time
We've been thinking about your suggestion to bound the error one gets by taking a continuous time approximation and choosing lambda based on when this error can be argued to be negligible. At the moment, we see no clear criterion to use to argue that error will be negligible. Our curvature condition, by contrast, has been widely used in theoretical analyses in the field, and our empirical experiments back up the results we obtain using this method. For this reason we have confidence that our analysis gives an accurate picture of learning speeds in deep linear networks.  In particular, the main qualitative result of the analytic theory that pre-trained and random orthogonal initialization, but not random Gaussian, achieve depth independent training times was confirmed by numerical simulations of gradient descent in discrete time.  This gives us confidence that our analytic methods describe well what happens in discrete time.

-'edge of chaos': Thank you, we have edited the paper to introduce this term before using it, since it may be unfamiliar.  We give an intuitive description of it in the introduction.

-'the input-output correlation matrix contains all of the information about the dataset used in learning' is indeed only true for linear networks. We do not feel it is necessary to reiterate our use of linear networks here, given that this restriction is clearly stated in our title, abstract, introduction, first sentence of the section, and all equations and derivations leading up to this point in the text.

-Page 3: 'column of W^{21}' This should have a bar over it, thank you. We have corrected this in our new draft.

-Page 4: 'What kinds of networks did ref [19] analyze?' Thank you for the comment, we have edited the draft to indicate that the analysis was for linear neural networks. ([19] presents an analysis of three layer networks).

-Page 6: 'caveat' We've changed the wording in the draft.

-Page 7: Clarification of classification task. We've changed the wording to make it clear that details of the task, not just the learning rate, can be found in appendix C.

-Page 8: 'Optimization performance is only improved in the short term and maybe medium terms by pre-training vs standard carefully scaled inits. In the longer term (which is what really matters in the end, as it dominates most of the run-time) the difference is less significant, if it is present at all.' 

While this may indeed be a feature of nonlinear neural network learning, our goal in this paper is to understand the linear case. We feel this is an important prerequisite for understanding more complex nonlinear networks (we agree that it is hard to imagine saying much about arbitrary nonlinearities, but rectified linear units and other recent piecewise linear activation functions might be amenable to future analysis building on our own). Your comment raises an important point that we have included in our revised draft: Our analysis is likely, to the extent that it does also illuminate the behavior of nonlinear networks, to be most accurate in the early epochs of learning when the nonlinear network is operating in a roughly linear regime (assuming it starts from small weights, with a nonlinearity that is roughly linear around the origin such as tanh). We make no claims that this initial period represents the bottleneck in training deep nonlinear networks. Our goal is to study the linear case, and show which pieces of nonlinear behavior can be explained in this way. We have edited the draft to make it clear that our results, depending on details of initializations and nonlinearities, might describe the early portion of training a nonlinear network; but cannot be expected to apply to later portions of training, when the nonlinear network is in a more nonlinear regime. We also note that linear networks serve as a sort of lower bound on training times. Thus the fact that very deep linear networks, such as the 100 layer networks we train, can require 150 epochs to reach the error obtained in just a few epochs by a pretrained net, means that a nonlinear network of this depth would almost certainly suffer at least as severely, and hence pretraining will provide a speed boost early in training.

-'it seems reasonable to suspect that in later stages of optimization that the network may behave in a much less linear fashion as the units move out of their linear regimes, and so the optimization advantages of pre-training will diminish or even disappear' 
We definitely agree that as neurons move out of their linear regime our analysis should not be expected to apply. We have edited our draft to emphasize this. We note that, unless random initial conditions somehow speed up late in training relative to pretrained initial conditions (i.e., pretraining actually hurts you once you’re in the nonlinear regime), the benefits accrued early in training are likely to persist (though they may be small relative to the overall training time). It therefore seems unlikely that the optimization advantage will “disappear” entirely.

-'In Appendix D you cite some evidence from other papers. But the results with Hessian-free optimization and other methods are consistent with what is written above (believe me, I know this work very well). Look for example at the results for SGD in Figure 3 of the Chapelle & Erhan paper that you cite. SGD reaches nearly identical KLs on MNIST after 700 dataset passes when you compare random initializations vs RBM pre-trained initializations. The Curves results seem to favor pre-training a small bit with SGD, but the difference is small (maybe 1.5x faster), and would likely become insignificant in the longer term as random-init SGD appears to be catching up before the graph cuts off. My experience, along with that of many other people who have studies these methods is that if you run these kinds of experiments longer, the approximate 1.5-2x speed increase with pre-training wanes significantly over time, eventually reaching near parity with well chosen random initialization methods, so that overall not much time is saved, if any.' 
Based on the published evidence, we believe we are justified in concluding that pretraining confers an optimization advantage. To take your example of Chapelle & Erhan, Fig. 3, the KL divergence of RBM-pretrained nets on MNIST using SGD reaches about 4.8 by epoch 700. The random initialization takes until approximately epoch 1000 to reach this level (in making these comparisons, note that both the x and y axes differ between subplots). Hence pretraining does confer an optimization advantage in this instance of about 300 epochs. Furthermore, the plot you identified (Fig. 3 MNIST) is the one in which this advantage is least evident; their Fig. 1 shows Hessian free methods converging more quickly on both MNIST and Curves datasets (Curves: pretrained initializations reach a KL divergence of 10 on iteration 10 or so, compared to iteration 120 for random initializations. MNIST: pretrained drops below 10 by iteration 30, while for random none have dropped below 10 by iteration 70). The other dataset used in Fig. 3 (Curves) shows a robust optimization advantage due to pretraining (pretrained KL drops below 2 around iteration 400; random drops below 2 around iteration 1400). Although the current evidence available in the literature does not appear to document it, we certainly agree it is possible that this speed advantage would wane if these experiments were run for a longer time. Our analysis is only for linear networks, and hence cannot be expected to accurately apply to networks in their nonlinear regime. Thus we would expect our analysis to be most relevant early in training. Nevertheless, the empirical results we have cited show a very consistent optimization advantage due to pretraining, even in nonlinear nets, that persists and remains significant to a reasonable length of training time (hundred to a thousand iterations). We also emphasize that the magnitude of the speed increase may not always be large enough in practice to warrant the extra trouble (and time) of pretraining a network. Our goal is not to say that pretraining should always be used by practitioners, but rather, to understand why it confers an optimization advantage.
   Also, we now give a random (orthogonal) initialization scheme that does as well as pre-training.  We are fundamentally not interested in advocating one initialization scheme over another; we just want to gain an understanding of *why* an initialization scheme confers an advantage when it does. 

-Page 8: 'The discussion about what pre-training should do didn't make sense to me in multiple places.'
We're sorry this section was not clear enough--we've rewritten it completely in the new draft. 

-'For example, previously you said that you were assuming Sigma^11 = I, but I guess this is no longer the case.'
That is correct. In fact our analytic results for the learning dynamics can be generalized to allow Sigma^11 = VDV^T where V are the right singular values of the input-output correlation matrix. Then each mode still completely decouples. We excluded this result from our main exposition in the interest of brevity and simplicity, but we've now seen that it's necessary to explain the advantage of pretraining. The details of this will be added to the supplementary appendix.


-'You then say that the product of the weights converges to Sigma^31(Sigma^31)^-1. But how can this be true unless N2 >= N1,N3? When N2 < N1,N3, the product of the weight matrices has rank at most N2, while Sigma^31(Sigma^31)^-1 will be full-rank in general.'

Yes this is true, we were taking the full rank case to simplify the presentation and focus on intuitions. Details of the extension to the rank constrained case are very straightforward (take the best rank N2 approximation).


-'You defined a^alpha to be a vector before, but now it is a 'strength'?'
Thank you for catching the typo, we meant 'a', not 'a^alpha'. 'a' is the scalar strength of the mode.


-When you consider taking W21 = R2Q^T where R2 is 'an arbitrary orthogonal matrix', what does this actually mean? Orthogonal matrices are square, and so is Q, so does that make W21 square (i.e. N1 = N2)? And if R2 is truly arbitrary, then it is meaningless, as any orthogonal matrix M can be written as R2 Q^T for some R2 (take R2 = MQ). 

Thank you for the comment, we have abused notation a bit here: R2 will not always be orthogonal (since it may not be square) depending on the size of N2 and N1. What we require for a decoupled initialization is that R2^TR2=I. For square R2, this means it must be orthogonal and, as you rightly point out, arbitrary--W21 might converge to any orthogonal matrix. Interestingly, in this case pretraining reduces simply to establishing the orthogonal initial conditions that we discuss in the subsequent section. For N2 < N1, R2 is size N2 x N1 and R2^TR2 cannot equal the identity. We require that it equal a diagonal matrix D of size N1 that is only nonzero for N2 elements on the diagonal, where it must be equal to 1. I.e., it must ignore some input directions, and learn the rest with unity scaling. With pretraining, the directions with the most input variance will be learned, and the directions with smaller variance will be the ones ignored. Hence, compared to random orthogonal initializations, pretraining biases the initial solution to input directions with high variance. Thus in this case we obtain a slightly modified consistency condition: input-analyzing singular vectors must match input principal components for the first N2 highest input variance directions, and the set of the N2 largest input variance components must be the same set as the N2 largest singular values of the task. Clearly for this setting, R2 is not arbitrary. Finally for N2 > N1, we do require R2^TR2=I, but this does not mean R2R2^T=I. We can write R2 as AB where A is size N2 x N2 orthogonal, and B is a matrix of size N2 x N1 with C = [R; 0] where R is N1 x N1 orthogonal. We have edited the draft to clarify this.

-'When you say 'Now consider fine-tuning on...' are you now taking the input and output not to be equal. This is confusing especially since this sentence appears in a paragraph which starts by saying that we are now talking about auto-encoding with input = output.'

Yes. In the standard pretraining/finetuning paradigm, one first pretrains a network using an unsupervised method, in our case an autoencoder, and subsequently finetunes on a task of interest, in our case by minimizing squared error on a set of input-output pairs. This is the setting we analyze. We are only talking about autoencoding for the pretraining period.


-Page 9: 'What is the error being plotted in the figure?'

All throughout the paper, our linear networks are trained to minimize squared error as defined in the first section. Details of the input and output data are in the supplementary material.


-Page 9: 'That initializing a linear network with part of the optimal SVD solution (which if you take the full solution, will instantly give the optimal error) isn't too surprising. It would be much more interesting to see if these initialization schemes work well in the nonlinear case.'

We believe there's a misunderstanding here--the network is not initialized with the full solution. It is initialized with the results of unsupervised pretraining using an autoencoder. This is an unsupervised initialization that clearly cannot know the full solution to the final supervised task. Indeed, the pretrained initial condition can in theory be very different from what is required to learn the task. It will be relevant to the solution to the degree that our consistency condition is satisfied. We hope that our revision of this section, which was not originally clear enough, will have made this evident.

-Page 9: “The Glorot initialization scheme uses uniform random numbers, and I think there is a factor of 6 somewhere in there. Gaussians with 1/sqrt(N) is definitely not what they end up recommending. Also, they did their calculations for tanh units, although it should probably work for linear ones. In my experience, getting the scale constants and other details right matters a lot in practice!”

The recommendation of Glorot et al. is an initialization that allows the variance of the gradient to remain constant with depth. To do this, the variance of the distribution each weight is drawn from, var(W), must equal 1/N. Using uniform random numbers, this requires initializing to U[-sqrt(6)/sqrt(2N), sqrt(6)/sqrt(2N)]. For Gaussian random variables, this requires a variance of 1/sqrt(N) as we have used. Glorot et al. makes no claim that uniform is better than Gaussian. In fact, our empirical results in Fig. 6 are for the uniform initialization (the exact initialization used in Glorot et al.), not a Gaussian initialization--we have edited the text to note this fact. We certainly agree that getting scale constants right matters greatly in practice--this is the effect we're analyzing. Using a uniform distribution without the factor of sqrt(6), or using a Gaussian with an extra factor of sqrt(6) will change the results a great deal.

-Page 9: How can you have the weight matrices be random orthogonal matrices? Orthogonal matrices are square and the weight matrices don't have to be. 

The generalization of orthogonal matrix to the rectangular case is any matrix whose singular values are all 1.  Moreover one can maintain perfect dynamical isometry in products of such matrices in a subspace of dimension as large as the number of neurons in the smallest layer. To do so, one need only have the column space of one layer feed into the row space of the next layer, so that no further dimensions of activity get killed.  We have added a note to the document. 


-Page 11: Merely scaling g very large won't be any good. The 'activity' will propagate, yes, but the units will completely saturate. 

Yes we agree, a very large g might accomplish the goal of allowing activity to propagate through a deep network, but might hinder other important goals such as keeping units desaturated. Nowhere do we claim that scaling g very large is optimal, or that activity propagation is the only relevant concern in deep networks.  In fact we show that g near 1 guarantees the nice property of dynamical isometry for random scaled orthogonal initializations with the tanh nonlinearity. 

-Page 12: 'Variance' isn't really what eqn 21 is measuring. That implies deviation from the mean, which doesn't have to be 0 here. The units could all be completely saturating (this is bad), but eqn 21 would still have a non-zero finite value. 

We neglected to mention an implicit assumption:  if the nonlinearity is odd, and the weights are random orthogonal, then the distribution of activations x_i across neurons i in a layer will be symmetric about the origin, and therefore this distribution will have zero mean.  Therefore Eqn 21 is measuring variance.  We have added this note to the text.

-Page 12: The analysis done in section seems interesting. It does sound similar to work done on Echo State Networks (ESNs) and initializations. Have you compared to that? 

We're glad you found the analysis interesting, yes, this is similar to echo state networks among others, which is why we used the term 'edge of chaos, in analogy with terminology for recurrent networks' (p12). In ESNs, however, the results are for a fixed recurrent matrix that is often not altered during learning.   More generally, this analysis is essentially the method of mean field theory from statistical physics, which predates the advent of echo-state networks.

 -What is missing for me from this section is an application of these ideas to real networks. Do these ideas improve on optimization performance? 

As you can imagine, we are very interested in this question! However we think that to do a proper, careful comparison is too much for this already long submission.


Reviewer 9c88:

Thank you for the kind comments, we are very encouraged that you found the analysis insightful!

-Ambiguity of 'learning time': We agree, this is an important point. We have changed the text to indicate that we are considering only iterations and not computation time.

- p 9:  'mode strength was chosen to be small (u=0.001)' because ... ? 

A small initial mode strength is an accurate approximation for learning that starts from small random initial conditions on the weights. If a large initial mode strength is used, this corresponds to embedding knowledge about the task before learning starts--in the extreme, if the initial mode strengths are chosen to be the corresponding singular values, then the input-output map is initialized at its optimum and no learning is necessary. Greedy layer wise pretraining on MNIST, because MNIST satisfies the consistency condition, provides an unsupervised way to initialize mode strengths to greater values than can be achieved using small random weights. This correspondingly improves learning speeds. We included this note as an attempt to explain the difference between the two plots--although both start on the decoupled manifold, pretrained solutions start with a larger mode strength and hence learn much more quickly.

We've corrected the typos below in the new draft, thanks for catching them.
-'We show (Fig 6A, left, red curve)' -> 'We empirically show (…'
- Figure 6: 'A Histograms of the singular values' should be 'B Histograms of the singular values':
- p 11:  'netoworks' -> 'networks'  
- Discussion: 'propery' -> 'property'  

- Section 4: 'and phi(x) is any nonlinearity that saturates as ...' Any nonlinearity, really? This doesn't sound right, since any nonlinearity could incorporate some scaling that could override the role of gain factor g. You should more specifically characterize the properties of the nonlinearity, and state here which one(s) you will actually consider.  

At the level of generality that we first introduce phi, it can indeed be any nonlinearity. We say in general that there exists a g_c such that if the gain g < g_c activity decays, and if g > g_c activity does not decay (and does not blow up due to saturation).  g_c of course depends on the nature of the nonlinearity (and could be 0 or infinity).  We have not specified how in general it depends on the nonlinearity (one has to solve the fixed point equation in the appendix).   When the nonlinearity is tanh (or any monotonically increasing nonlinearity with slope 1 at the origin), g_c = 1.  

-Appendix D.2: 'An analysis of this effect in deep linear networks' I believe you meant to write 'in deep nonlinear networks' since linear networks would all converge to equivalent solutions (at different paces) and thus could not exhibit any difference in generalization.

We did actually mean deep linear networks--by 'this effect' we meant the generalization advantage due to pretraining, which we believe can exist in deep linear networks, though it may require reformulating the learning problem. The ref [20] we cite provides an example of how generalization performance can be analyzed in deep linear networks (there a three layer network), and our suggestion is that it may be possible to build on this work to analyze the case of using unlabeled data to do unsupervised pretraining, followed by supervised fine tuning. Their analysis uses overrealizeable input-output maps and adds measurement noise to the training data. Whether analysis based on these assumptions would shed light on what happens in typical deep nonlinear networks is unclear to us, but it seems worth pursuing. We agree that, if training is run to completion, all linear nets would converge to the same solution, and thus some early stopping criterion might be necessary. Working through these issues is an interesting goal for future work.   Interestingly - our work reveals analytically the effects of early stopping - it kills the components of the small singular values/vectors of the input-output correlation matrix in the product of weights across layers.