Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks
Authors: Wei Hu
Lechao Xiao
Jeffrey Pennington
Venue:  (2020)
Keywords: deep learning theory
non-convex optimization
orthogonal initialization

Abstract: The selection of initial parameter values for gradient-based optimization of deep neural networks is one of the most impactful hyperparameter choices in deep learning systems, affecting both convergence times and model performance. Yet despite significant empirical and theoretical analysis, relatively little has been proved about the concrete effects of different initialization schemes. In this work, we analyze the effect of initialization in deep linear networks, and provide for the first time a rigorous proof that drawing the initial weights from the orthogonal group speeds up convergence relative to the standard Gaussian initialization with iid weights. We show that for deep networks, the width needed for efficient convergence to a global minimum with orthogonal initializations is independent of the depth, whereas the width needed for efficient convergence with Gaussian initializations scales linearly in the depth. Our results demonstrate how the benefits of a good initialization can persist throughout learning, suggesting an explanation for the recent empirical successes found by initializing very deep non-linear networks according to the principle of dynamical isometry.

Published as a conference paper at ICLR 2020
PROVABLE BENEFIT OF ORTHOGONAL INITIALIZA- TION IN OPTIMIZING DEEP LINEAR NETWORKS
Wei Hu
Lechao Xiao Google Brain x c l com
Jeffrey Pennington Google Brain jpennin com
Princeton University huwe iess. piccs.pinneetoo. edu
ABSTRACT
The selection of initial parameter values for gradient-based optimization of deep neural networks one of the most impactful hyperparameter choices in deep learning systems, affecting both convergence times and model performance. Yet despite significant empirical and theoretical analysis, relatively little has been proved about the concrete effects of different initialization schemes. In this work, we analyze the effect of initialization in deep linear networks, and provide for the first time a rigorous proof that drawing the initial weights from the orthogonal group speeds up convergence relative to the standard Gaussian initialization with iid weights. We show that for deep networks, the width needed for efficient con- vergence to a global minimum with orthogonal initializations is independent of the depth, whereas the width needed for efficient convergence with Gaussian initial- izations scales linearly in the depth. Our results demonstrate how the benefits of a good initialization can persist throughout learning, suggesting explanation for the recent empirical successes found by initializing very deep non-linear networks according to the principle of dynamical isometry.
INTRODUCTION
Through their myriad successful applications across wide range of disciplines, it is now well es- tablished that deep neural networks possess an unprecedented ability to model complex real-world datasets, and in many cases they can do so with minimal overfitting. Indeed, the list of practi- cal achievements of deep learning has grown at an astonishing rate, and includes models capable of human-level performance in tasks such as image recognition (Krizhevsky et al., 2012), speech recognition (Hinton et al., 2012), and machine translation (Wu et al., 2016).
Yet to each of these deep learning triumphs corresponds a large engineering effort to produce such a nigh-performing model. Part of the practical difficulty in designing good models stems from a proliferation of hyperparameters and poor understanding of the general guidelines for their selec- tion. Given candidate network architecture, some of the most impactful hyperparameters are those governing the choice of the model's initial weights. Although considerable study has been devoted to the selection of initial weights, relatively little has been proved about how these choices affect important quantities such as rate of convergence of gradient descent.
In this work, we examine the effect of initialization on the rate of convergence of gradient descent in deep linear networks. We provide for the first time rigorous proof that drawing the initial weights from the orthogonal group speeds up convergence relative to the standard Gaussian initialization with iid weights. particular, we show that for deep networks, the width needed for efficient convergence for orthogonal initializations is independent of the depth, whereas the width needed for efficient convergence of Gaussian networks scales linearly the depth.
Orthogonal weight initializations have been the subject of significant amount of prior theoretical and empirical investigation. For example, in a line of work focusing on dynamical isometry, was found that orthogonal weights can speed up convergence for deep linear networks (Saxe et al., 2014: Advani & Saxe, 2017) and for deep non-lineat networks (Pennington et al., 2018; Xiao et al., 2018; Gilboa et al., 2019; Chen et al., 2018: Pennington et al., 2017; Tarnowski et al., 2019; Ling & Qiu, 2019) when they operate in the linear regime. In the context of recurrent neural networks, orthogonality can help improve the system's stability. A main limitation of prior work is that it

---

Published as a conference paper at ICLR 2020
has focused almost exclusively model's properties at initialization. In contrast, analysis focuses on the benefit of orthogonal initialization on the entire training process, thereby establishing provable benefit for optimization.
The paper is organized as follows. After reviewing related work in Section 2 and establishing some preliminaries in Section 3, we present main positive result efficient convergence from orthog- onal initialization in Section 4. Section 5, we show that Gaussian initialization leads to exponen- tially long convergence time if the width is small compared with the depth. In Section 6, we perform experiments to support our theoretical results.
RELATED WORK
Deep linear networks. Despite the simplicity of their input-output maps, deep linear networks de- fine high-dimensional non-convex optimization landscapes whose properties closely reflect those of their non-linear counterparts. For this reason, deep linear networks have been the subject of exten- sive theoretical analysis. A line of work (Kawaguchi, 2016; Hardt & Ma, 2016; Lu & Kawaguchi, 2017: Yun et al., 2017; Zhou & Liang. 2018; Laurent & von Brecht, 2018) studied the landscape properties of deep linear networks. Although it was established that all local minima are global under certain assumptions, these properties alone are still not sufficient to guarantee global conver- gence provide concrete rate of convergence for gradient- based optimization algorithms.
Another line of work directly analyzed the trajectory taken by gradient descent and established conditions that guarantee convergence to global minimum (Bartlett al., 2018; Arora et al., 2018; Du & Hu, 2019). Most relevant to our work is the result of Du & Hu (2019), which shows that the width of hidden layers is larger than the depth, gradient descent with Gaussian initialization can efficiently converge to a global minimum. Our result establishes that for Gaussian initialization, this linear dependence between width and depth is necessary, while for orthogonal initialization, the width can be independent of depth. Our negative result for Gaussian initialization also significantly generalizes the result of Shamir (2018), who proved similar negative result for 1-dimensional linear networks.
Orthogonal weight initializations. Orthogonal weight initializations have also found significant success non-linear networks. In the context of feedforward models, the spectral properties of network's input-output Jacobian have been empirically linked to convergence speed (Saxe al., 2014: Pennington et al., 2017; 2018; Xiao et al., 2018). It was found that when this spectrum initialization, property dubbed dynamical isometry, convergence times
concentrates around improved by orders of magnitude. The conditions for attaining dynamical isometry in the infinite- width limit were established by Pennington al. (2017; 2018) and basically require that input-output map to be approximately linear and for the weight matrices to be orthogonal. Therefore the training time benefits of dynamical isometry likely rooted in the benefits of orthogonality for deep linear networks, which we establish in this work.
Orthogonal matrices are also frequently used the context of recurrent neural networks, for which the stability of the state-to-state transition operator is determined by the spectrum of its Jaco- bian (Haber Ruthotto, 2017; Laurent & von Brecht, 2016). Orthogonal matrices can improve the conditioning, leading to an ability to learn over long time horizons (Le et al., 2015; Henaff et al., 2016; Chen et al., 2018; Gilboa et al., 2019). While the benefits of orthogonality can be quite large at initialization, little is known about whether in what contexts these benefits persist during training, a scenario that has lead to the development of efficient methods of constraining the optimization to the orthogonal group (Wisdom et al., 2016; Vorontsov et al., 2017; Mhammedi et al., 2017). Al- though we do not study the recurrent setting in this work, an extension our analysis might help determine when orthogonality is beneficial in that setting.
2

---

Published as a conference paper at ICLR 2020
3 PRELIMINARIES
3.1 NOTATION
Let [n] (1,2..... n). Denote by La the d d identity matrix, and by an identity matrix when its dimension is clear from context. Denote by (N, o²) the Gaussian distribution with mean j and variance ,², and by X the chi-squared distribution with degrees of freedom.
Denote by ||-|| the lg norm of a vector or the spectral norm of matrix. Denote by II-11 the Frobe- nius norm of a matrix. For symmetric matrix A, let Amax and Amin (A) be its maximum and minimum eigenvalues, and let (A) be its i-th largest eigenvalue. For a matrix B R n. let a; (B) be i-th largest singular value mmin (B) mi (B). Denote by vec (A)) be the vectorization of matrix A in column-first
..2...., min (m, n)), and let max () = a (B).
order. The Kronecker product between two matrices A E I Xni and B IR IR is defined as
01,1 B
01,ny B
A 2 B
E R RRmmmaXiing
0m,.1
aml n B
where dz is the element the (i,j)-th entry of A.
We use the standard O(-), 22(-) and @(.) notation to hide universal constant factors. We also use C to represent a sufficiently large universal constant whose specific value can differ from line line.
3.2 PROBLEM SETUP
Suppose that there are training examples (k)): Rd= R.a, Denote by X (Ii,-.., FF) IRd the input data matrix and by Y (y1,-..::h vn)) Rdd the target ma- trix. Consider an I--layr linear neural network with weight matrices Wi,... WL, which given an input R.d computes
f(z: W WL) = aW ... Wiz,
(1)
where W; (i ...... L), do dz, d,, = dy. and a is normalization constant which will be specified later according to the initialization scheme. We study the problem of training the deep linear network by minimizing the lz loss over training data:
<(W WL)
Σ W1 W1) ywll2
1 laWl ... W, YI
The algorithm we consider to minimize the objective (2) is gradient descent with random initializa- tion, which first randomly samples the initial weight matrices [0)) from certain distribu- tion, and then updates the weights using gradient descent: for time = 0, 1.
de (Wi(I)..... W2()),
Wi + 1) w.(() oo,
i [4],
(3)
where 77 > 0 is the learning rate. For convenience, The time index is used on any variable that depends on W Wi...., Wr to represent its value at time e.g. (t+(t) (t) Wttt), ((t) (t)....... Wz (t)), etc.
denote W WWW W, (1 < ラ < L) and W1-1 = [i e [4]).
EFFICIENT CONVERGENCE USING ORTHOGONAL INITIALIZATION
In this section present main positive result for orthogonal initialization. We show that orthog- onal initialization enables efficient convergence gradient descent to a global minimum provided that the hidden width is not small.
In order to properly define orthogonal weights, we let the widths all hidden layers be equal: d d2 d m, and let 2 max d,). Note that all intermediate matrices
3

---

Published as a conference paper at ICLR 2020
W..... WL-1 are square matrices, and W2 Rmxdx WL E Rd We sample each ini- tial weight matrix Wi( independently from a uniform distribution over scaled orthogonal matrices satisfying
(0) mld
W (O) W.(O),, (0) mlm
2 2
(4)
WO) (0) = -mla,
In accordance with such initialization, the scaling factor in (1) is set as Vml-id," which
||/| for any x E Rd=,! The same scaling factor was adopted in Du & Hu (2019), which preserves the expectation of the squared &g norm of any input.
ensures E (1; (o()).
(o)) (i(())
Let W E arg weRt ||WX Y and 2 || YI Then is the minimum value for the objective (2). Denote r = rank(X), K = Amaa(X (X X) A, x) and |
Our main
[
theorem in this section is the following:
Theorem 4.1. Suppose
m -
and m 2 dz.
(5)
for some 6 E (0,1) and a sufficiently large universal constant C > 0. Set the learning rate S du 2L|
Then with probability at least 1 - ê over the random initialization, we have
2(0) - E- =0 (1+ log(r/6)
+ ||W*()) |IXIPe
dy
E(1) r S (1 1 (1-0 (1- (((0) -8)-))) E*), 1= 1,0,,,2....
where E(I) is the objective value at iteration I.
Notably, in Theorem 4.1, the width m need not depend on the depth This in sharp contrast with the result of Du & Hu (2019) for Gaussian initialization, which requires m 2 (y(Trn&dy)) turns out that a near-linear dependence between and L is necessary for Gaussian initialization to have efficient convergence, as we will show in Section 5. Therefore the requirement in Du & Hu (2019) is nearly tight in terms of the dependence L. These results together rigorously establish the benefit of orthogonal initialization in optimizing very deep linear networks.
ZIズ)=> If we set the learning rate optimally according to Theorem 4.1 to 17 O dy ) we obtain that ((t) - L decreases by a ratio of 1 - -O(x-) after every iteration. This matches the convergence rate of gradient descent on the (1-layer) linear regression problem min WeRdyxd,
-|W YI
4.1 PROOF OF THEOREM 4.1
The proof uses the high-level framework from Du & Hu (2019), which tracks the evolution of the network's output during optimization. This evolution is closely related to a time-varying positive semidefinite (PSD) matrix (defined (7)), and the proof relies on carefully upper and lower bound- ing the eigenvalues of this matrix throughout training, which in turn implies the desired convergence result.
First, we can make the following simplifying assumption without loss of generality. See Appendix in Du & Hu (2019) for justification.
Assumption 4.1. (Without loss of generality) E Rd rank(X) = r, = W and
We have E [[l[(x: (2). (1(0)) a²E x WT (0) -.. -W. (0)Wz(0) (0)) ... Wi (0)x)). Note that
by our choice (4) we have E [W (0) dn and W. (0)W. = m/ (1 S S L 1), so we have E (ar; Wr. (O).... Wi (0) = a mm d,, ||=|| ||=||
24 is known the stable rank of X, which is always no more than the rank.
4

---

Notice that P(t) is always PSD since it the sum of PSD matrices. Therefore, in order to establish convergence, we only need to (i) show that the higher-order term Ett) is small and (ii) prove upper and lower bounds on P(t)'s eigenvalues. For the second task, it suffices to control the singular Published as a conference paper at ICLR 2020
Now briefly review Du & Hu (2019)'s framework. The key idea is to look the network's output, defined as
= L.La E Rdyxn
We also write Utt) L: the output at time t. Note that E(t) 1/2 =1(((t) I According to the gradient descent update rule, we write
(1 II W.(1) 11 de aw, ()) (z. -W) Σ n WL
de (1) (1) + E((),
aw.
where (t)) contains all the high-order terms (i.e., those with r/² higher). With this definition, the evolution of (t) can be written as the following equation:
vec (U(t + 1) U(t) -PP(t) vee (U(t) Y) a vee (E(t)x),
(6)
where
L Σ ((W-m))())) i=1
P(() = a
@ (Wo++10)W (W-n)(())))
values of W;11-1 (f) and (t) (i E [Z]). Under orthogonal initialization, these matrices perfectly isometric at initialization, and we will show that they stay close to isometry during training, thus enabling efficient convergence.
The following lemma summarizes some properties at initialization.
Lemma 4.2. At initialization, we have
mmax (O):(0)) = Guin (Wj:((0)
1-6+1
1 (ESSSSS((()) (1,)))111))))
(8)
Furthermore, with probability at least 1 the loss initialization satisfies
(1+ (
log(r/0) [|W*1²) || ||X
{(0) o
dy
Proof sketch. The spectral property (8) follows directly from (4).
To prove (9), we essentially need to upper bound the magnitude of the network's initial output. This turns out to be equivalent studying the magnitude of the projection of vector onto random low- dimensional subspace, which we can bound using standard concentration inequalities. The details given in Appendix A.I.
111+borr// lestr/0: + [|W*])) |X which dy is the upper bound on ε(0) from (9), Conditioned on (9) being satisfied, we will use induction on t to prove the following three properties A(t), B(t) and C(t) for all = 0, 1,...
Now proceed prove Theorem 4.1. We define B =000 +0(11
A(t): l(t) (1 Lo min (X)/d,) ((0) S (1 In min (X)/dy) B.
B(t): max (W (W):(t)) I 1.1m بtن m (W 0.9m iill (1,)) # L).
v1 S
8 &yBd,III 2
c(t): [[Wa(t)= W.(0)ll S
VI
A(0) and ((0) true according Lemma 4.2, and C(O) is trivially true. In order to prove A(t),
B(t) and C(t) for all t, we will prove the following claims for all t > 0:
Note that for symmetric matrices A and B, the set of eigenvalues of A & B is the set of products of an eigenvalue of A and eigenvalue of B.
5

---

Published as a conference paper at ICLR 2020
((t), Claim 4.3. A(0), A(0),....A(())BB00 ..... ((t) C(t 1).
Claim 4.4. C(I) - B(().
Claim 4.5. A(t), B(t) = 1).
The proofs of these claims are given in Appendix A. Notice that we finish the proof of Theorem 4.1 we prove A(I) for all > 0.
EXPONENTIAL CURSE OF GAUSSIAN INITIALIZATION
In this section, we show that gradient descent with Gaussian random initialization necessarily suf- fers from rumning time that scales exponentially with the depth of the network, unless the width becomes nearly linear in the depth. Since we mostly focus on the dependence of width and running time depth, will assume the depth L to be sufficiently large.
Recall that want minimize the objective ((W,.-... WL) lloWL.1 X - Y by gradient descent. We assume Y W for some W Rd, xd,, so that the optimal objective value is O. For convenience, we assume |X | (1) and || O(1).
Suppose that at layer E [ every entry of (0) is sampled from (0 of), and all weights in the network are independent, We the scaling factor a such that the initial output the network does not blow up exponentially (in expectation):
E [I[[=;; ()(()) (O). ... Wr(0)) < L00)) .|==1
Va E Rdd.
(10)
Note that E [I1:(:: Wi()), Wr.00))1 a² I1 (d:of) ||0|2² Thus (10) means
a² (d,o)) T,(1)
We also assume that the magnitude of initialization each layer cannot vanish with depth:
d 2 LOOI)'
Vi E [Z).
(11)
Note that the assumptions (10) and (11) just sanity checks rule out the obvious pathological cases - they are easily satisfied by all the commonly used initialization schemes in practice.
Now formally state main theorem in this section.
Theorem 5.1. Suppose max/do, di....,dy dz} S <OL' ( for some universal constant O < 1. Then there exists a universal constant e > 0 such that, if gradient descent is run with learning rate n eoL", then with probability at least 0.9 over the random initialization, for the first ((L)) iterations, the objective value stuck between 0.4 ||YI and 0.6 ||
Theorem 5.1 establishes that efficient convergence from Gaussian initialization is impossible for large depth unless the width becomes nearly linear in depth. This nearly linear dependence is the best hope for, since Du & Hu (2019) proved positive result when the width is larger than linear in depth. Therefore, phase transition from untrainable to trainable happens at the point when the width and depth has nearly linear relation. Furthermore, Theorem 5.1 generalizes the result of Shamir (2018), which only treats the special case of do = ... dp =
5.1 PROOF OF THEOREM 5.1
For convenience, we define a scaled version of Wi: let A, = Wi/(Vddd,)) and 3 =a[[[
Then we know 3 < (O1) and aW,, h. = 3AAaI where AJ.: = Aj ..... A..
We first give a simple upper bound on [0)]] for all 1 S iis
Lemma 5.2. With probability at least 1 - 8, we have [|A 50 00 a

---

Published as a conference paper at ICLR 2020
The proof of Lemma 5.2 is given in Appendix B.1. It simply uses Markov inequality and union bound.
Furthermore, a key property at initialization is that if j i is large enough, [|)]| will become exponentially small.
Lemma 5.3. With probability at least 1 - -0Q2)) for all 1 S i S j < L such that j - i 2 to- we have (O)ll S e-Q(12).
Proof. We first consider a fixed pair (i,j) such that j -- L In order to bound [Az=((0)]; we
10' first take an arbitrary unit vector o E Rd.- and bound (O)el[ We can write (0)ol))
IT Zz. where Zu-
(0) Note that for any nonzero v' E Bd independent of (o), | (1))el
As (0)o'll
the distribution of dx-
|0'1 is X.. Therefore, Zi...., Zj are independent, and dx ~ X², Recall the expression for the moments of chi-squared random variables:
(k= i, + 5)..
E [ = 2² (2T(da/2
(A) > 0). Taking X = 2 and using the bound
I(a+ [(a) S Va V.I !
(Qi & Luo, 2012), we get EE ZZ S
2(ds ((de/2-0.11 de
0.2 du
11-
0.1 da
Therefore we have
E
Zk
(1
0.1 dx
1
0.1
5-1+1
$ (1 (1- t =e -R(E))
O(LL-T)
Choose sufficiently
small
constant
d'
>
0.
By Markov inequality we have
Pr
VIlk Zx > d'
S
VIk Zx
S 22 (L))) = =2((2 Therefore we
have shown that for any fixed unit vector v E Rd-1,, with probability at least 1 - - we have (0)oul)) S e-L()))
Next, we use this bound (0)Il via an c-net argument. We partition the index set [d,-1] into [d,-1] = S₁ U S2 U... U S, such that |S I L (Vl E [4]) and g = O 4: ( For each I E [g]. let Ni be a j-neet for all the unit vectors in R4 1 with support in S,. Note that we can choose MV such that [W[] = cO((s))) = o(L7/33 Taking a union bound over Mi we know that [0)el] S e (09(17)) ||u|| simultaneously for all v E L/= with probability at least 1 - EE [il) e R(E7) 2 1 q. ((I77/)) -Q((7) 1
Now, for any и E Rdi-1, we write as u Ei= ard where a sealar and ur is unit vector supported on Sj. By the definition of 2 nntt for each I E [q] there exists 22 E M such that We know that (0)erl) I <--(())) ||0| wlll < 2- have
|| for all I E [4]. Let U = Ei= arg. We
[1)x1= = Ei_, lal (0)xnl - Ei 9 lail - 0(17) ||0||| Se -Q(E))
q >n, 1-1 of ||oi|
-Vge-au0 ||a|| e -Q((") |||||.
Note that ||u m|l -IE/_ a (w et)ll VIL af - 12l? z v V El_ af 1/2 |k]]/
which implies ||0|| < ||u|| Therefore we have
[l)u]())u|| < (0)e| + [0) -)ll S (--a(()) ||||| + (0)l ||u ml
S e 2((7)
||س||| + (0)ll))]| |ul|| = e -((77)
||^||| + ||) || 2/ ||
The above inequality is valid for any R4: 1. Thus we can take the unit vector u that maximizes (0)ull) This gives us [A))((0)) < e -0()) + 1 [0)]) which implies [} (0)) S e R227)
Finally, we take a union bound over all possible (i..). The failure probaility is at most - e0()))
7

---

Published as a conference paper at ICLR 2020
The following lemma shows that the properties in Lemmas 5.2 and 5.3 still to some extent preserved after applying small perturbations on all the weight matrices.
Lemma 5.4. Suppose that the initial weights satisfy ||A5:(0)]| & O(L2) for all 1 sisj S L, and [))( S e e- j 2 To where > 0 is universal constant. Then for another set of matrices ,.,..., Ar satisfying ||A (.))) S -0.6 for all i E [L]. we must have
|| - SO(9), VI visiiss,,
|| 5o 50 (0Taai))
L A MisssssLj- 4
(12)
Proof. It suffices to show that the difference A3a A,a(0) is tiny. Let A, A, A.()).
We have Aja = (A,(0) + A,) (As+1(0) + (A, + A,). Expanding this product. except for the one term corresponding to Aza(0), every other term has the form A1((,+1)(00) De, 1(c=-1)((..=+1)))()) A Ak, A(n ())))))(0),, where i I h1 < < k. S j.
By assumption, each D& has spectral norm -0.6,, and each Ay. (0) has spectral norm O so have || || Ak, A(,.-1)(4 Ak.., Dk, A 1)= s (e (0-066222) (O(L2) *+1 Therefore we have
5-i+1 Σ
( (
(e (-UBaL))) (O(L)))
|| - A,,(0)1 <
8
#=1
j-i+1
Σ L (e-0.60211) (O(L3)) s+1 00( Σ
(0(L")e-000))1))) <0(()) (1/2)==((L3)) <
s=1
s=1
which implies ||Ssl S (()3) for all 1 sisss
The proof the second part of the lemma postponed to Appendix B.2.
As a consequence of Lemma 5.4, we can control the objective value and the gradient at any point sufficiently close to the random initialization.
Lemma 5.5. For a set of weight matrices WI...., Wy with A, = W./(vdo,,) that satisfy (12), the objective and the gradient satisfy
0.4 I < E(W1..... WL) <0.6
I w. EWW,.... Wx)l S (VT.o)) 0.9
Vie [4]
The proof Lemma 5.5 is given in Appendix B.3.
Finally, we can finish the proof of Theorem 5.1 using the above lemmas.
Proof of Theorem 5.1. From Lemmas 5.2 and 5.3, we know that with probability at least 0.9, we have (i) ||Arss00]] O(L3) for all S i S j S L, and (ii) [|)]=(0)]| S e e- if (i, further satisfies j - 1 Here e₁ 0 is universal constant. From now properties being satisfied. We suppose that the learning rate 1) most 1.2e
are conditioned these
We say that a set of weight matrices WI...., WL are in the "initial neighborhood" if ||A, A, (0) S -0.6ce for all E [7.]. From Lemmas 5.4 and 5.5 we know that in the "ini- tial neighborhood" the objective value is always between 0.4 || and 0.6 || Therefore we have escape the "initial neighborhood" in order to get the objective value out of this interval.
Now we calculate how many iterations are necessary to escape the "initial neighborhood." move at most
According Lemma 5.5, inside the "initial neighborhood" each W. n ((daat)) -0000, in one iteration by definition of the gradient descent algorithm. In order to leave the "initial neighborhood," some W, must satisfy |[W; Wi(O)ll = v vd,a, || A > / -d, order to move this amount, the number of iterations has to be at least e.
0.3c, L
2..0, Ly 2 2177) (O1I
-(Vd 0.99
1
This finishes the proof.
8

---

Published as a conference paper at ICLR 2020
30
25
depth-width
25
depth-width
-30
2.0
2.-
logg0(
(ng(0(deptt))
2.-
-60
-11
-20
23
-22
20
-35
00
10gl0(width)
(a) Gaussian, steps= 1258
(b) Gaussian, stcps=
3.5
depth-width
depth-widtt
bnp2//depth)
45
3,5
-60
2.0
-30
10.
85
-12
10
1.5
23
3.0
5.0
1.5
3.0
log
(c) Orthogonal, steps= 1 1558
(d) Orthogonal, steps=10000
Figure 1: log 2(0) X(0)
at = 1258 and = 10000, for different dipth-width configurations and different initialization schemes. Darker color means smaller loss.
EXPERIMENTS
In this section, provide empirical evidence to support the results in Sections 4 and 5. To study how depth and width affect convergence speed gradient descent under orthogonal and Gaussian train family of linear networks with their widths ranging from 10 to
initialization schemes, 1000 and depths from to 700, on fixed synthetic dataset (X, Y).* Each network is trained using gradient descent staring from both Gaussian and orthogonal initializations. In Figure 1, We lay
logarithm of the relative training loss Z(Oj using heap-maps, at steps 1258 and = 10000. In each heat-map, each point represents the relative training loss one experiment: the darker the color, the smaller the loss. Figure clearly demonstrates sharp transition from untrainable to trainable (i.e., from red to black) when we increase the width of the network:
t(t)
for Gaussian initialization, this transition occurs across contour characterized by linear relation between width and depth;
for orthogonal initialization, the transition occurs at width that is approximately indepen- dent of the depth.
These observations excellently verify our theory developed in Sections 4 and 5.
To have a closer look into the training dynamics, we also plot "relative loss v.s. training time" for variety of depth-widhh configurations. See Figure 2. There again we can clearly see that orthogonal initialization enables fast training at small width (independent of depth), and that the required width for Gaussian initialization depends depth.
We choose X E R 1024X16 and W E 10x and set Y W X. Entries in X and W are drawn i...d from from.N(O (0 1).

---

Moritz Hardt and Tengyu Ma. Identity matters in deep learning. International Conference on Published as a conference paper at ICLR 2020
65-50
65-400
65-50
05-400
65:50
65:400
OT-50
-- 0T
0T:50
0T:400
07:30
0T
G5-800
65-100
65-100
0T:100
0T:100
200
1200
200
07-1200
0T-200
07-1200
14
07:200
0T-1200
(a) 55pth=50
(b) Depth=200
(c) Depth=400
Figure 2: Relative loss v.s. training time. For each plot, we vary width from 50 (yellow) 1200 (purple). Solid and dashed lines represent Gaussian (GS) and orthogonal (OT) initializations.
7 CONCLUSION
In this work, we studied the effect of the initialization parameter values of deep linear neural net- works on the convergence time of gradient descent. We found that when the initial weights are iid Gaussian, the convergence time grows exponentially in the depth unless the width is at least as large as the depth. the width needed to guarantee efficient convergence is in fact independent of the depth. These sults establish for the first time a concrete proof that orthogonal initialization is superior to Gaussian initialization in terms of convergence time.
contrast, when the initial weight matrices are drawn from the orthogonal group,
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in neural networks. arXiv preprint arXiv: 1eXxi:17100.0 171000367,7 2017.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis gradient descent for deep linear neural networks. arXiv preprint arXiv:1810.02281, 2018.
Peter Bartlett, Dave Helmbold, and Phil Long. Gradient descent with identity initialization effi ciently learns positive definite linear transformations. In International Conference on Machine Learming, pp. 520-529, 2018
Minmin Chen, Jeffrey Pennington, and Samuel S Schoenholz. Dynamical isometry and mean field theory of rnns: Gating enables signal propagation in recurrent neural networks. arXiv preprint arXiv: 05394, 2018
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference Machine Learning, pp. 1655-1664, 2019.
Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S Schoenholz, Ed H Chi, and Jeffrey Pennington. Dynamical isometry and a mean field theory of Istms and grus. arXiv preprint arXiv:1901.08987 2019,
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse Problems, 34(1):014004, 2017.
Learning Representations, 2016.
Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long- long-memory tasks. arXiv preprint 1xXiv:162..0666 2016.
Geoffrey Hinton, Deng. Dong Yu, George E. Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. 1EEE Signal Processing Magazine, 29(6):82-97, 2012.
10

---

Published as a conference paper at ICLR 2020
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pp. 586-594,22 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Thomas Laurent and James Brecht. A recurrent neural network without chaos. arXiv preprint arXiv:1612.06212, 2016.
Thomas Laurent and James von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning, pp. 2908-2913, 2018.
Quoe Le, Navdeep Jaitly, and Geoffrey Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv: wwXiv:1504.0091,, 2015.
Zenan Ling and Robert C Qiu. Spectrum concentration in deep residual learning: a free probability approach. IEEE Access, 7:105212-105223, 2019.
Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. arXiv preprint arXiv:1702.08580 085000800. 2017.
Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In Proceedings of the 34th International Conference on Machine Learning- Saarinng-Volume Volume 70, pp. 2401-2409. JMLR. org. 2017.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In Advances in neural information processing systems, pp. 4785-47955 2017.
Jeffrey Pennington, Samuel S Schoenholz, and Surya Ganguli. The emergence of spectral univer- sality in deep networks. arXiv preprint arXiv: 180i.0100200999 2018.
Feng Qi and Qiu-Ming Luo. Bounds for the ratio two gamma functions-from wendel's s and related inequalities to logarithmically completely monotonic functions. Banach Journal of Math- ematical Analysis, 6(2): 132-158,, 2012.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. International Conference on Learning Represen- tations, 2014.
Ohad Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. arXiv preprint arXiv:1809.08558 2018.
Wojeiech Tamowwki,, Piotr Warchot, Stanislaw Jastrzbski, Jacek Tabor, and Maciej Nowak. Dynam- ical isometry is achieved in residual networks in universal way for any activation function. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2221-2230, 2019.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learn- ing recurrent networks with long term dependencies. Proceedings of the 34th International Conference Machine Maaning-Volumee 70, pp. 3570-357 3578. JMLR. org, 2017.
Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. In Advances Neural Information Processing Systems, pp- 4880-4888, 2016.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao. Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1609:0600.08//0 0444, 2016.

---

Published as a conference paper at ICLR 2020
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dicksteii Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla con- volutional neural networks. In International Conference Machine Learning, pp. 5389-5398, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Global optimality conditions for deep neural networks. arXiv preprint 1rXiv:1707.0244 2017.
Yi Zhou and Yingbin Liang. Critical points of linear neural networks: Analytical forms and land- scape properties. 2018.
12

---

Published as a conference paper at ICLR 2020
A PROOFS FOR SECTION 4
A.1 PROOF OF LEMMA 4.2
Proof of Lemma 4.2. We only need to prove (9). We first upper bound the magnitude of the net- work's initial output any given input IR Let VmL (1) x E R Then
have ||2||| = ||=|| and f(;; (1) (2) = V d2 (0) 2 =
m
WL(O) 2. Note m
d
that
m of dimension dg. V/ (O) the (signed) projection of onto random subspace in o 4f odg
vm (O) =1" / || has the same distribution as 95.. where 91...., Im are i..d. samples from (0, 1). By the standard tail bounds for chi-squared distributions we have
Therefore
Pr g + ... + Lù, S d + 2 du + 2logg/////02l000000))) 2 1 - 8',
Pr 2 + +... Im 2 m 2/ m log(1/0")
2 1 - 8'.
Let 8' =
8. 2r
Note that m > C' looglo////// (8)). We know that with probability at least 1 - we have
2
dy + 2 dy (2r + log(2r/0) O(d, + log(r/6))
WL(0) =
m 2 m log(22/8)
2(m))
which implies
[x; Wi(0), (2)01) dy
1 (L(
m -o
10 + log(r/0)
||:1|
mm 00 |+ log(r/0) |=0|1
dg
m
(13)
dy
Finally, taking union bound, we know that with probability at least 8, the inequality (13) holds for every x E {aI....,22 ,ry,, which implies
((0)
lff(rs: (i))).... (2())) - 3wl12 < Σ (1(),................
(2)0))11 + [lvall)) 11 = o ( log(r/6)
1=1
k=1
log(r/8)
00
1+
| + Σ
|| | + ||
dy
dg
A=1
<0
log(r/0)
||
dy
A.2 PROOF OF CLAIM 4.3
Proof of Claim 4.3. Let = Lo (X)/dy. From A(O).... we have E(s) S (1-m7)* B for
all S < t. The gradient of the objective function (2) Dw. aWI, L. 1U (U- (U)Y) XW:
Thus we can bound the gradient norm as follows for all S s I t and all E [L]:
de aw,
(s)
La ([) - -Ylle 1: |X|||
(14)
1.1m + /2((s) 1.1m + |X|| < 2 (1 B)BB
|X||
VmL-Td.
Vd
where we have used B(s). Then for all E [T.] we have:
|[ + 1) W. < Σ
[ 1) - w.())) Σ
"1 now. (s)
13

---

Published as a conference paper at ICLR 2020
2 2/(1 (1
17)8BB
2gv B
1-1
20 B
11 ==0
| 1
|
(1-
||||
dd
Vd
vd,
7
==0
/vBd, |X||
Lo (X)
This proves C(I + 1).
A.3 PROOF OF CLAIM 4.4
8 8yBd, IIXII and A, Wi(() W.(0) (i E [L]). Then C(t) means Lo min (X)
Proof of Claim 4.4. Let
|| F I R (Vi E [Z]). For $ S j & L, we have
(ta(t) (W5(0) + AA) ... (W,(0) + A.)
Expanding this product, each term except W (0) has the form:
W j:(k, +1) As.
A.... Da. 11)
(15)
where i < kg < ... < lig S j are locations where terms like Dd, are taken out. Note that every factor in (15) the form Wj Wis (0) satisfies W (0)]l= = m ,'-r'41 according to (8). Thus, we can bound the sum of all terms of the form (15)
j-i+1
[W (t)) - W):(0)]l S
Σ
j --i+1
R m مييية = (Vm + RD- (Vm)
= -(Vm)i-it) ((1 + R/ vm)
i+1
1) S (Vmp-iit (1+ -1) s 001(vm)) it1
Here the last step uses m C(LR)² which implied by (5). Combined with (8), this proves (()).
A.4 PROOF OF CLAIM 4.5
Proof of Claim 4.5. Recall that we have the dynamics (6) for (t). In order to establish convergence from (6) we need to prove upper and lower bounds the eigenvalues of P(t), as well as show that the high-order term E(t) is small. We will prove these using Btt).
Using the definition (7) and property B(t). we have
Amax (P(t)) S a² Σ Amax ((W)- (Wi-L1(t)x)) Amax (t)
Σ
(1.1m² 1 m')x)x(X)) (1.1m +x)² 2Lo 2 (x)
m 1 dyy
t=1
Amia (P(tt) 2
Amia ((W-)1(t)X)) (W)=1((t)x)) Amia (WL. WT:tt (t))
m dg 00.9m* -ss )xs(()))
2 (0.9m =) 2 Lo (X)
2
3
5
In the lower bound above, we make use of the following relation on dimensions: m 2 dz 2 r, which enables the inequality Amin ((W)) T (Wi-na(txx)) = oz.n (W,-1a(t)X) 2
2 (W:1na(t) oiinn
Next, we will prove the following bound on the high-order term E(t):
EI
6 Amiin (P.) (U() - Y
14

---

Published as a conference paper at ICLR 2020
Recall that E(t is the sum of all high-order terms in the product
WLA(t + 1) 1)= = II Wi(() - " ow, (1)
de
Same as (14), we have
de J..
(1)
2
(Vi E [L]). Then we have Vd
1
1IE())xI1r
Vml-id
2 2 ((t) |XX||
m 1 |
n
m
dy
dd
2=2
L X
2 E(L) 2 ||X
L
1
m=3 3
Vdg
|XX
X
dy
/md
From 1 S
dy
we have
2nL ((C))IXII
Vd, (() /m [X]
Note that m > C
d,
2 C
d,2(0 [[
Thus
v Vmd,
||
we have
2 L-2
|E(+)x F S
m Vd, |
PnLL E(L)
0.5
/mli-Idg
/mdg
2
20LL
Vdy E(t) mm X
m 22
|
<
2
m
|
dly
Vmdy
dy
v /md,,
4 ||| E(t)
V mdy
suffices to show that the above bound is at most 1 (P:) [|U(()) YIIF = (Pt)
Since Amia (Pt) 2 3 Lo (X)/dy. it suffices to have
AnL ||| E(t) I
1 1)
3Lo²
min x)22((1)
md
5cly
which is true since > C 11
2 C.
XI
(X)
Piin (X)
Finally, from (6) and 17 Σ 2| S (P.)
dg
1 we have
[U( 1) Y| l|vec (U(t ((++))-Y))
1
(T - (/-n)((() vec (U) Y) + Vmn vec (F(()x)
$ (1 mmmin (P(t))) |ice (U(t) +)1l+ Vml-Idy dly |[(t)x(| 1F
1
<(1 Aimn (P(1)) - Y + 6
7 (UT() Y
5
1
Mmiin (P()) [T((t) - -YllF
6
1 m (x) (x)/dy) [|((t) YllF-
< 1
2
Therefore l(t+1) S (1
I (X)/d,)) e(t) s (1 Ln (X)/d,) E(t). Combined with
A(1), this proves A(l + 1).
15

---

Published as a conference paper at ICLR 2020
B PROOFS FOR SECTION 5
B.1 PROOF OF LEMMA 5.2
Proof of Lemma 5.2. Notice that for any 1 1 iiis S L we have E [| [1,)1 = d;-1. Then
by Markov inequality we have Pr (0)l 2 3/2*
- 66/12. Taking a union bound, we know that with probability at least 1- - 6, for all S i S S L simultancously we have ||]]|: s
di-1
( 8/ SOL216) (note that di-1 S -(L - O(L))
B.2 PROOF OF LEMMA 5.4
Proof of Lemma 5.4 (continued). For the second part of the lemma (j 0 4)) we need to bound
the terms of the form Ajik+1(0)- As- As)1=(0) more carefully. In fact, if - 2 4. then
max(j k 1 - i} 2 I0
L. which by assumption means either ()) or A 1 (0) has
spectral norm bounded by - This implies [A)*+1(0)) D Ak)1=(0)] S - L7
O(L3) = -1,0c L. O(L)). Therefore we have
j-H+1
|A - (0)l s (j - i - 1.6er -0(L))
Σ
(j-t+)
( (6-.6ort)) (O(L3))* ) at1
2=2
Se-9 Σ 1, c (0.600))) (O(T.))) -6-
8
Σ
x
e (e.5.c))))) = =0 - (c-oLL))
+
This implies |A I 00 (e
B.3 PROOF OF LEMMA 5.5
Proof of Lemma 5.5. We can bound the network's output as
(1) = |3 (0) - 0,00)_ e -Q(22) |X]| e -2((7)
Thus the objective value E(W,,... W1) = (. I| must be extremely close to || for large L. so 0.4 || E(W1. WL) 0.6 |Y||
As for the gradient, for any i E [4] we have
Ww, Wz)l = laW (aWL1X - Y) W
(1)
- -BB/(Vooo)) A (aWL1X X)X 1n 5
Vdi, A -(1) -|A--aal
Using (12), and noting that either i 1 or i 1 is greater than 1. we have
-1.0-01 Vw: ewW,,,, Wr)l S0 0 (e (c)) O(L3) S -1
16


Reviews:
[{"review_id": "Sygdb88AFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 convergence of deep linear networks under orthogonal initialization. Most of the problem setup, analysis techniques and proof roadmap are adapted from Du & Hu (2019). The difference is the orthogonal initialization compared with the Gaussian initialization in Du & Hu (2019). Since the product of orthogonal weight matrices is identity, the new initialization can remove the dependency of the number of nodes $m$ on the depth $L$ of the network. The authors also proved a lower bound of the loss function trained by Gaussian initialization within certain iterations. This justifies the disadvantage of Gaussian initialization.\n\nMy biggest concern is that this paper seems to be very similar to Du & Hu (2019) in many places. The whole Sections 3 & 4 are almost the same as Sections 3,4,5 & 7 in their paper. The contribution in this paper is too incremental given previous work. \n\nWhat is the advantage of using orthogonal matrices in (4) compared with just using identity matrices as initialization? Can we prove the same result with just identity initialization? In this case, what would we lose by restricting us to this special case?\n\nIn the proof of Lemma 4.2, it seems that only the randomness of the last layer $W_L(0)$ is used. Why do we need all the layers to be uniformly sampled?\n\nIt should be explained in more details that $W_L(0)$ is drawn from a uniform distribution over orthogonal matrices in $d_y\\times d_y$ space. Then $1/\\sqrt{m} W_L(0)\\cdot z /\\|z\\|^2$ is not distributed on the whole space of $d_y$-sphere. The argument in the proof of Lemma 4.2 thus needs more justification.\n\nIt would be interesting to see an empirical comparison of the proposed initialization and the Gaussian initialization. Due to the lower bound proved in this paper, the experiments are expected to show distinct difference between these two.\n", "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": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgU7E06FS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 rigorously proves that if a deep linear network is initialized with random orthogonal weights and trained with gradient descent, its width required for convergence  does not depend on its depth. To compare, when weights in deep linear networks are initialized with Gaussian initialization, the minimal width required for convergence will depend on the depth of the network. This proof explains why orthogonal weight initialization can help to train networks efficiently, especially for those very deep ones.\n\nThe theoretical contribution of this paper is very important. Orthogonal initialization is found to be useful in deep network training. Although the theory in this paper is developed for linear networks, it still has important guidance meaning in practices in more areas of deep learning. The derivations are correct to my best knowledge. And the paper is well-written and easy to read.\n\nMinor points:\n- typo in the last equation in (4)\n\n=======================\nUpdate: Despite the similarity with a previous paper, I still think the theoretical results and empirical observations important and thus I will keep my score.", "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": "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": "SJeRmfcAKH", "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 role of initialization for training deep linear neural networks. The authors specifically consider the orthogonal initialization, and prove that with the orthogonal initialization proposed in equation (4), the gradient descent can achieve zero training error in a linear convergence rate. The improvement of the orthogonal initialization lies at the dependence of the layer width $m$, which is independent of the network depth $L$.\n\nThe problem considered in this work is very interesting since there are lots of empirical studies show that good initialization can benefit the training of deep neural networks. However, my main concern about this work is its novelty, especially for the proof techniques used in the current paper. It seems that most of the proofs are similar to the previous work Du & Hu (2019), and the main reason that it can remove the dependence of $L$ seems to be Lemma 4.2, which can be derived using the orthogonal property of the initialization. In this sense, there is not too much contribution for the current paper given the previous work Du & Hu (2019). Are there any other significant changes need to be made in the proofs to get the main results? If the authors can provide the convergence guarantees of the stochastic gradient descent, the contributions would be strong. \n\nFor the proof of Theorem 5.1, is it a straightforward extension of the proofs in Shamir (2018)? What is the main challenge when prove the general $d$ case?\n\n\nMinor comments:\nFor the last equation in (4), why you need $W_L(0)W_L(0)^\\top=mI_{d_y}$ instead of $W_L(0)^\\top W_L(0)=d_yI$ as you used in the later proofs?\n\nThere is no experiment to verify the theory\n\nUpdate:\nI thank the authors for their response, I would like to keep my score.", "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": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that initializing the parameters of a deep linear network from the orthogonal group speeds up learning, whereas sampling the parameters from a Gaussian may be harmful.

The result of this paper can be interesting to the deep learning community. The main concern the reviewers raised is the huge overlap with the paper by Du & Hu (2019). It would have been nice to actually see whether the results for linear networks empirically also hold for nonlinear networks. 
Decision: Accept (Poster)