A CONVERGENCE ANALYSIS OF GRADIENT DESCENT FOR DEEP LINEAR NEURAL NETWORKS
Year: 2018

Abstract:
We analyze speed of convergence to global optimum for gradient descent training a deep linear neural network (parameterized as x 7→ WNWN−1 · · ·W1x) by minimizing the `2 loss over whitened data. Convergence at a linear rate is guaranteed when the following hold: (i) dimensions of hidden layers are at least the minimum of the input and output dimensions; (ii) weight matrices at initialization are approximately balanced; and (iii) the initial loss is smaller than the loss of any rank-deficient solution. The assumptions on initialization (conditions (ii) and (iii)) are necessary, in the sense that violating any one of them may lead to convergence failure. Moreover, in the important case of output dimension 1, i.e. scalar regression, they are met, and thus convergence to global optimum holds, with constant probability under a random initialization scheme. Our results significantly extend previous analyses, e.g., of deep linear residual networks (Bartlett et al., 2018).

heading: 1 INTRODUCTION
text: Deep learning builds upon the mysterious ability of gradient-based optimization methods to solve related non-convex problems. Immense efforts are underway to mathematically analyze this phenomenon. The prominent landscape approach focuses on special properties of critical points (i.e. points where the gradient of the objective function vanishes) that will imply convergence to global optimum. Several papers (e.g. Ge et al. (2015); Lee et al. (2016)) have shown that (given certain smoothness properties) it suffices for critical points to meet the following two conditions: (i) no poor local minima — every local minimum is close in its objective value to a global minimum; and (ii) strict saddle property — every critical point that is not a local minimum has at least one negative eigenvalue to its Hessian. While condition (i) does not always hold (cf. Safran and Shamir (2018)), it has been established for various simple settings (e.g. Soudry and Carmon (2016); Kawaguchi (2016)). Condition (ii) on the other hand seems less plausible, and is in fact provably false for models with three or more layers (cf. Kawaguchi (2016)), i.e. for deep networks. It has only been established for problems involving shallow (two layer) models, e.g. matrix factorization (Ge et al. (2016); Du et al. (2018a)). The landscape approach as currently construed thus suffers from inherent limitations in proving convergence to global minimum for deep networks.
A potential path to circumvent this obstacle lies in realizing that landscape properties matter only in the vicinity of trajectories that can be taken by the optimizer, which may be a negligible portion of the overall parameter space. Several papers (e.g. Saxe et al. (2014); Arora et al. (2018)) have taken this trajectory-based approach, primarily in the context of linear neural networks — fully-connected neural networks with linear activation. Linear networks are trivial from a representational perspective, but not so in terms of optimization — they lead to non-convex training problems with multiple minima and saddle points. Through a mix of theory and experiments, Arora et al. (2018) argued that such non-convexities may in fact be beneficial for gradient descent, in the sense that sometimes, adding (redundant) linear layers to a classic linear prediction model can accelerate the optimization. This phenomenon challenges the holistic landscape view, by which convex problems are always preferable to non-convex ones.
Even in the linear network setting, a rigorous proof of efficient convergence to global minimum has proved elusive. One recent progress is the analysis of Bartlett et al. (2018) for linear residual networks — a particular subclass of linear neural networks in which the input, output and all hidden dimensions are equal, and all layers are initialized to be the identity matrix (cf. Hardt and Ma (2016)). Through a trajectory-based analysis of gradient descent minimizing `2 loss over a whitened dataset (see Section 2), Bartlett et al. (2018) show that convergence to global minimum at a linear rate — loss is less than > 0 after O(log 1 ) iterations — takes place if one of the following holds: (i) the objective value at initialization is sufficiently close to a global minimum; or (ii) a global minimum is attained when the product of all layers is positive definite.
The current paper carries out a trajectory-based analysis of gradient descent for general deep linear neural networks, covering the residual setting of Bartlett et al. (2018), as well as many more settings that better match practical deep learning. Our analysis draws upon the trajectory characterization of Arora et al. (2018) for gradient flow (infinitesimally small learning rate), together with significant new ideas necessitated due to discrete updates. Ultimately, we show that when minimizing `2 loss of a deep linear network over a whitened dataset, gradient descent converges to the global minimum, at a linear rate, provided that the following conditions hold: (i) the dimensions of hidden layers are greater than or equal to the minimum between those of the input and output; (ii) layers are initialized to be approximately balanced (see Definition 1) — this is met under commonplace near-zero, as well as residual (identity) initializations; and (iii) the initial loss is smaller than any loss obtainable with rank deficiencies — this condition will hold with probability close to 0.5 if the output dimension is 1 (scalar regression) and standard (random) near-zero initialization is employed. Our result applies to networks with arbitrary depth and input/output dimensions, as well as any configuration of hidden layer widths that does not force rank deficiency (i.e. that meets condition (i)). The assumptions on initialization (conditions (ii) and (iii)) are necessary, in the sense that violating any one of them may lead to convergence failure. Moreover, in the case of scalar regression, they are met with constant probability under a random initialization scheme. We are not aware of any similarly general analysis for efficient convergence of gradient descent to global minimum in deep learning.
The remainder of the paper is organized as follows. In Section 2 we present the problem of gradient descent training a deep linear neural network by minimizing the `2 loss over a whitened dataset. Section 3 formally states our assumptions, and presents our convergence analysis. Key ideas brought forth by our analysis are demonstrated empirically in Section 4. Section 5 gives a review of relevant literature, including a detailed comparison of our results against those of Bartlett et al. (2018). Finally, Section 6 concludes.

heading: 2 GRADIENT DESCENT FOR DEEP LINEAR NEURAL NETWORKS
text: We denote by ‖v‖ the Euclidean norm of a vector v, and by ‖A‖F the Frobenius norm of a matrixA.
We are given a training set {(x(i),y(i))}mi=1 ⊂ Rdx × Rdy , and would like to learn a hypothesis (predictor) from a parametric familyH := {hθ : Rdx → Rdy | θ ∈ Θ} by minimizing the `2 loss:1
min θ∈Θ
L(θ) := 1
2m ∑m i=1 ‖hθ(x(i))− y(i)‖2 .
When the parametric family in question is the class of linear predictors, i.e. H = {x 7→ Wx |W ∈ Rdy×dx}, the training loss may be written as L(W ) = 12m‖WX − Y ‖ 2 F , where X ∈ Rdx×m and Y ∈ Rdy×m are matrices whose columns hold instances and labels respectively. Suppose now that the dataset is whitened, i.e. has been transformed such that the empirical (uncentered) covariance matrix for instances — Λxx := 1mXX
> ∈ Rdx×dx — is equal to identity. Standard calculations (see Appendix A) show that in this case:
L(W ) = 1
2 ‖W − Λyx‖2F + c , (1)
1Much of the analysis in this paper can be extended to loss types other than `2. In particular, the notion of deficiency margin (Definition 2) can be generalized to account for any convex loss, and, so long as the loss is differentiable, a convergence result analogous to Theorem 1 will hold in the idealized setting of perfect initial balancedness and infinitesimally small learning rate (see proof of Lemma 1). We leave to future work treatment of approximate balancedness and discrete updates in this general setting.
where Λyx := 1mY X > ∈ Rdy×dx is the empirical (uncentered) cross-covariance matrix between instances and labels, and c is a constant (that does not depend onW ). Denoting Φ := Λyx for brevity, we have that for linear models, minimizing `2 loss over whitened data is equivalent to minimizing the squared Frobenius distance from a target matrix Φ:
minW∈Rdy×dx L 1(W ) :=
1 2 ‖W − Φ‖2F . (2)
Our interest in this work lies on linear neural networks — fully-connected neural networks with linear activation. A depth-N (N ∈ N) linear neural network with hidden widths d1, . . . , dN−1 ∈ N corresponds to the parametric family of hypotheses H := {x 7→ WNWN−1 · · ·W1x |Wj ∈ Rdj×dj−1 , j = 1, . . . , N}, where d0 := dx, dN := dy . Similarly to the case of a (directly parameterized) linear predictor (Equation (2)), with a linear neural network, minimizing `2 loss over whitened data can be cast as squared Frobenius approximation of a target matrix Φ:
minWj∈Rdj×dj−1 , j=1,...,N L N (W1, . . . ,WN ) :=
1 2 ‖WNWN−1 · · ·W1 − Φ‖2F . (3)
Note that the notation LN (·) is consistent with that of Equation (2), as a network with depth N = 1 precisely reduces to a (directly parameterized) linear model.
We focus on studying the process of training a deep linear neural network by gradient descent, i.e. of tackling the optimization problem in Equation (3) by iteratively applying the following updates:
Wj(t+ 1)←Wj(t)− η ∂LN
∂Wj
( W1(t), . . . ,WN (t) ) , j = 1, . . . , N , t = 0, 1, 2, . . . , (4)
where η > 0 is a configurable learning rate. In the case of depth N = 1, the training problem in Equation (3) is smooth and strongly convex, thus it is known (cf. Boyd and Vandenberghe (2004)) that with proper choice of η, gradient descent converges to global minimum at a linear rate. In contrast, for any depth greater than 1, Equation (3) comprises a fundamentally non-convex program, and the convergence properties of gradient descent are highly non-trivial. Apart from the caseN = 2 (shallow network), one cannot hope to prove convergence via landscape arguments, as the strict saddle property is provably violated (see Section 1). We will see in Section 3 that a direct analysis of the trajectories taken by gradient descent can succeed in this arena, providing a guarantee for linear rate convergence to global minimum.
We close this section by introducing additional notation that will be used in our analysis. For an arbitrary matrix A, we denote by σmax(A) and σmin(A) its largest and smallest (respectively) singular values.2 For d ∈ N, we use Id to signify the identity matrix in Rd×d. Given weights W1, . . . ,WN of a linear neural network, we let W1:N be the direct parameterization of the end-to-end linear mapping realized by the network, i.e. W1:N := WNWN−1 · · ·W1. Note that LN (W1, . . . ,WN ) = L
1(W1:N ), meaning the loss associated with a depth-N network is equal to the loss of the corresponding end-to-end linear model. In the context of gradient descent, we will oftentimes use `(t) as shorthand for the loss at iteration t:
`(t) := LN (W1(t), . . . ,WN (t)) = L 1(W1:N (t)) . (5)

heading: 3 CONVERGENCE ANALYSIS
text: In this section we establish convergence of gradient descent for deep linear neural networks (Equations (4) and (3)) by directly analyzing the trajectories taken by the algorithm. We begin in Subsection 3.1 with a presentation of two concepts central to our analysis: approximate balancedness and deficiency margin. These facilitate our main convergence theorem, delivered in Subsection 3.2. We conclude in Subsection 3.3 by deriving a convergence guarantee that holds with constant probability over a random initialization.

heading: 3.1 APPROXIMATE BALANCEDNESS AND DEFICIENCY MARGIN
text: In our context, the notion of approximate balancedness is formally defined as follows:
2If A ∈ Rd×d ′ , σmin(A) stands for the min{d, d′}-th largest singular value. Recall that singular values
are always non-negative.
Definition 1. For δ ≥ 0, we say that the matrices Wj ∈ Rdj×dj−1 , j=1, . . . , N , are δ-balanced if:∥∥W>j+1Wj+1 −WjW>j ∥∥F ≤ δ , ∀j ∈ {1, . . . , N − 1} . Note that in the case of 0-balancedness, i.e. W>j+1Wj+1 = WjW > j , ∀j ∈ {1, . . . , N − 1}, all matrices Wj share the same set of non-zero singular values. Moreover, as shown in the proof of Theorem 1 in Arora et al. (2018), this set is obtained by taking the N -th root of each non-zero singular value in the end-to-end matrix W1:N . We will establish approximate versions of these facts for δ-balancedness with δ > 0, and admit their usage by showing that if the weights of a linear neural network are initialized to be approximately balanced, they will remain that way throughout the iterations of gradient descent. The condition of approximate balancedness at initialization is trivially met in the special case of linear residual networks (d0 = · · · = dN = d and W1(0) = · · · = WN (0) = Id). Moreover, as Claim 2 in Appendix B shows, for a given δ > 0, the customary initialization via random Gaussian distribution with mean zero leads to approximate balancedness with high probability if the standard deviation is sufficiently small.
The second concept we introduce — deficiency margin — refers to how far a ball around the target is from containing rank-deficient (i.e. low rank) matrices.
Definition 2. Given a target matrix Φ ∈ RdN×d0 and a constant c > 0, we say that a matrix W ∈ RdN×d0 has deficiency margin c with respect to Φ if:3
‖W − Φ‖F ≤ σmin(Φ)− c . (6)
The term “deficiency margin” alludes to the fact that if Equation (6) holds, every matrix W ′ whose distance from Φ is no greater than that of W , has singular values c-bounded away from zero:
Claim 1. Suppose W has deficiency margin c with respect to Φ. Then, any matrix W ′ (of same size as Φ and W ) for which ‖W ′ − Φ‖F ≤ ‖W − Φ‖F satisfies σmin(W ′) ≥ c.
Proof. Our proof relies on the inequality σmin(A+B) ≥ σmin(A)−σmax(B) — see Appendix D.1.
We will show that if the weights W1, . . . ,WN are initialized such that (they are approximately balanced and) the end-to-end matrix W1:N has deficiency margin c > 0 with respect to the target Φ, convergence of gradient descent to global minimum is guaranteed.4 Moreover, the convergence will outpace a particular rate that gets faster when c grows larger. This suggests that from a theoretical perspective, it is advantageous to initialize a linear neural network such that the end-to-end matrix has a large deficiency margin with respect to the target. Claim 3 in Appendix B provides information on how likely deficiency margins are in the case of a single output model (scalar regression) subject to customary zero-centered Gaussian initialization. It shows in particular that if the standard deviation of the initialization is sufficiently small, the probability of a deficiency margin being met is close to 0.5; on the other hand, for this deficiency margin to have considerable magnitude, a non-negligible standard deviation is required.
Taking into account the need for both approximate balancedness and deficiency margin at initialization, we observe a delicate trade-off under the common setting of Gaussian perturbations around zero: if the standard deviation is small, it is likely that weights be highly balanced and a deficiency margin be met; however overly small standard deviation will render high magnitude for the deficiency margin improbable, and therefore fast convergence is less likely to happen; on the opposite end, large standard deviation jeopardizes both balancedness and deficiency margin, putting the entire convergence at risk. This trade-off is reminiscent of empirical phenomena in deep learning, by
3Note that deficiency margin c > 0 with respect to Φ implies σmin(Φ) > 0, i.e. Φ has full rank. Our analysis can be extended to account for rank-deficient Φ by replacing σmin(Φ) in Equation (6) with the smallest positive singular value of Φ, and by requiring that the end-to-end matrix W1:N be initialized such that its left and right null spaces coincide with those of Φ. Relaxation of this requirement is a direction for future work.
4In fact, a deficiency margin implies that all critical points in the respective sublevel set (set of points with smaller loss value) are global minima. This however is far from sufficient for proving convergence, as sublevel sets are unbounded, and the loss landscape over them is non-convex and non-smooth. Indeed, we show in Appendix C that deficiency margin alone is not enough to ensure convergence — without approximate balancedness, the lack of smoothness can cause divergence.
which small initialization can bring forth efficient convergence, while if exceedingly small, rate of convergence may plummet (“vanishing gradient problem”), and if made large, divergence becomes inevitable (“exploding gradient problem”). The common resolution of residual connections (He et al., 2016) is analogous in our context to linear residual networks, which ensure perfect balancedness, and allow large deficiency margin if the target is not too far from identity.

heading: 3.2 MAIN THEOREM
text: Using approximate balancedness (Definition 1) and deficiency margin (Definition 2), we present our main theorem — a guarantee for linear convergence to global minimum:
Theorem 1. Assume that gradient descent is initialized such that the end-to-end matrix W1:N (0) has deficiency margin c > 0 with respect to the target Φ, and the weights W1(0), . . . ,WN (0) are δ-balanced with δ = c2 /( 256 ·N3 · ‖Φ‖2(N−1)/NF ) . Suppose also that the learning rate η meets:
η ≤ c (4N−2)/N
6144 ·N3 · ‖Φ‖(6N−4)/NF . (7)

heading: Then, for any > 0 and:
text: T ≥ 1 η · c2(N−1)/N
· log ( `(0) ) , (8)
the loss at iteration T of gradient descent — `(T ) — is no greater than .

heading: 3.2.1 ON THE ASSUMPTIONS MADE
text: The assumptions made in Theorem 1 — approximate balancedness and deficiency margin at initialization — are both necessary, in the sense that violating any one of them may lead to convergence failure. We demonstrate this in Appendix C. In the special case of linear residual networks (uniform dimensions and identity initialization), a sufficient condition for the assumptions to be met is that the target matrix have (Frobenius) distance less than 0.5 from identity. This strengthens one of the central results in Bartlett et al. (2018) (see Section 5). For a setting of random near-zero initialization, we present in Subsection 3.3 a scheme that, when the output dimension is 1 (scalar regression), ensures assumptions are satisfied (and therefore gradient descent efficiently converges to global minimum) with constant probability. It is an open problem to fully analyze gradient descent under the common initialization scheme of zero-centered Gaussian perturbations applied to each layer independently. We treat this scenario in Appendix B, providing quantitative results concerning the likelihood of each assumption (approximate balancedness or deficiency margin) being met individually. However the question of how likely it is that both assumptions be met simultaneously, and how that depends on the standard deviation of the Gaussian, is left for future work.
An additional point to make is that Theorem 1 poses a structural limitation on the linear neural network. Namely, it requires the dimension of each hidden layer (di, i = 1, . . . , N−1) to be greater than or equal to the minimum between those of the input (d0) and output (dN ). Indeed, in order for the initial end-to-end matrixW1:N (0) to have deficiency margin c > 0, it must (by Claim 1) have full rank, and this is only possible if there is no intermediate dimension di smaller than min{d0, dN}. We make no other assumptions on network architecture (depth, input/output/hidden dimensions).

heading: 3.2.2 PROOF
text: The cornerstone upon which Theorem 1 rests is the following lemma, showing non-trivial descent whenever σmin(W1:N ) is bounded away from zero:
Lemma 1. Under the conditions of Theorem 1, we have that for every t = 0, 1, 2, . . . :5
`(t+ 1) ≤ `(t)− η 2 · σmin
( W1:N (t) ) 2(N−1) N · ∥∥∥∥dL1dW (W1:N (t)) ∥∥∥∥2 F . (9)
5Note that the term dL 1
dW (W1:N (t)) below stands for the gradient of L1(·) — a convex loss over (directly
parameterized) linear models (Equation (2)) — at the point W1:N (t) — the end-to-end matrix of the network at iteration t. It is therefore (see Equation (5)) non-zero anywhere but at a global minimum.
Proof of Lemma 1 (in idealized setting; for complete proof see Appendix D.2). We prove the lemma here for the idealized setting of perfect initial balancedness (δ = 0):
W>j+1(0)Wj+1(0) = Wj(0)W > j (0) , ∀j ∈ {1, . . . , N − 1} ,
and infinitesimally small learning rate (η → 0+) — gradient flow:
Ẇj(τ) = − ∂LN
∂Wj
( W1(τ), . . . ,WN (τ) ) , j = 1, . . . , N , τ ∈ [0,∞) ,
where τ is a continuous time index, and dot symbol (in Ẇj(τ)) signifies derivative with respect to time. The complete proof, for the realistic case of approximate balancedness and discrete updates (δ, η > 0), is similar but much more involved, and appears in Appendix D.2.
Recall that `(t) — the objective value at iteration t of gradient descent — is equal to L1(W1:N (t)) (see Equation (5)). Accordingly, for the idealized setting in consideration, we would like to show:
d
dτ L1 (W1:N (τ)) ≤ −
1 2 σmin
( W1:N (τ) ) 2(N−1) N · ∥∥∥∥dL1dW (W1:N (τ)) ∥∥∥∥2 F . (10)
We will see that a stronger version of Equation (10) holds, namely, one without the 1/2 factor (which only appears due to discretization).
By (Theorem 1 and Claim 1 in) Arora et al. (2018), the weightsW1(τ), . . . ,WN (τ) remain balanced throughout the entire optimization, and that implies the end-to-end matrixW1:N (τ) moves according to the following differential equation:
vec ( Ẇ1:N (τ) ) = −PW1:N (τ) · vec ( dL1
dW (W1:N (τ))
) , (11)
where vec(A), for an arbitrary matrix A, stands for vectorization in column-first order, and PW1:N (τ) is a positive semidefinite matrix whose eigenvalues are all greater than or equal to σmin(W1:N (τ))
2(N−1)/N . Taking the derivative of L1(W1:N (τ)) with respect to time, we obtain the sought-after Equation (10) (with no 1/2 factor):
d
dτ L1 (W1:N (τ)) =
〈 vec ( dL1
dW
( W1:N (τ) )) , vec ( Ẇ1:N (τ) )〉 = 〈 vec ( dL1
dW
( W1:N (τ) )) ,−PW1:N (τ) · vec ( dL1
dW (W1:N (τ)) )〉 ≤ −σmin ( W1:N (τ) ) 2(N−1) N · ∥∥∥∥vec(dL1dW (W1:N (τ)) )∥∥∥∥2 = −σmin ( W1:N (τ) ) 2(N−1) N · ∥∥∥∥dL1dW (W1:N (τ)) ∥∥∥∥2 F .
The first transition here (equality) is an application of the chain rule; the second (equality) plugs in Equation (11); the third (inequality) results from the fact that the eigenvalues of the symmetric matrix PW1:N (τ) are no smaller than σmin(W1:N (τ))
2(N−1)/N (recall that ‖·‖ stands for Euclidean norm); and the last (equality) is trivial — ‖A‖F = ‖vec(A)‖ for any matrix A.
With Lemma 1 established, the proof of Theorem 1 readily follows:
Proof of Theorem 1. By the definition of L1(·) (Equation (2)), for any W ∈ RdN×d0 :
dL1 dW (W ) = W − Φ =⇒
∥∥∥∥dL1dW (W ) ∥∥∥∥2 F = 2 · L1(W ) .
Plugging this into Equation (9) while recalling that `(t) = L1(W1:N (t)) (Equation (5)), we have (by Lemma 1) that for every t = 0, 1, 2, . . . :
L1 ( W1:N (t+ 1) ) ≤ L1 ( W1:N (t) ) · ( 1− η · σmin ( W1:N (t) ) 2(N−1) N ) .
Since the coefficients 1 − η · σmin(W1:N (t)) 2(N−1) N are necessarily non-negative (otherwise would contradict non-negativity of L1(·)), we may unroll the inequalities, obtaining:
L1 ( W1:N (t+ 1) ) ≤ L1 ( W1:N (0) ) · ∏t
t′=0
( 1− η · σmin ( W1:N (t ′) ) 2(N−1) N ) . (12)
Now, this in particular means that for every t′ = 0, 1, 2, . . . : L1 ( W1:N (t ′) ) ≤ L1 ( W1:N (0) ) =⇒ ‖W1:N (t′)− Φ‖F ≤ ‖W1:N (0)− Φ‖F .
Deficiency margin c of W1:N (0) along with Claim 1 thus imply σmin ( W1:N (t ′) ) ≥ c, which when inserted back into Equation (12) yields, for every t = 1, 2, 3, . . . :
L1 ( W1:N (t) ) ≤ L1 ( W1:N (0) ) · ( 1− η · c 2(N−1) N )t . (13)
η · c 2(N−1) N is obviously non-negative, and it is also no greater than 1 (otherwise would contradict non-negativity of L1(·)). We may therefore incorporate the inequality 1− η · c2(N−1)/N ≤ exp ( −
η · c2(N−1)/N ) into Equation (13):
L1 ( W1:N (t) ) ≤ L1 ( W1:N (0) ) · exp ( − η · c2(N−1)/N · t ) ,
from which it follows that L1(W1:N (t)) ≤ if:
t ≥ 1 η · c2(N−1)/N
· log ( L1(W1:N (0)) ) .
Recalling again that `(t) = L1(W1:N (t)) (Equation (5)), we conclude the proof.

heading: 3.3 BALANCED INITIALIZATION
text: We define the following procedure, balanced initialization, which assigns weights randomly while ensuring perfect balancedness:
Procedure 1 (Balanced initialization). Given d0, d1, . . . , dN ∈ N such that min{d1, . . . , dN−1} ≥ min{d0, dN} and a distribution D over dN × d0 matrices, a balanced initialization of Wj ∈ Rdj×dj−1 , j=1, . . . , N , assigns these weights as follows:
(i) Sample A ∈ RdN×d0 according to D. (ii) Take singular value decomposition A = UΣV >, where U ∈ RdN×min{d0,dN}, V ∈
Rd0×min{d0,dN} have orthonormal columns, and Σ ∈ Rmin{d0,dN}×min{d0,dN} is diagonal and holds the singular values of A.
(iii) Set WN ' UΣ1/N ,WN−1 ' Σ1/N , . . . ,W2 ' Σ1/N ,W1 ' Σ1/NV >, where the symbol “'” stands for equality up to zero-valued padding.6 7
The concept of balanced initialization, together with Theorem 1, leads to a guarantee for linear convergence (applicable to output dimension 1 — scalar regression) that holds with constant probability over the randomness in initialization:
Theorem 2. For any constant 0 < p < 1/2, there are constants d′0, a > 0 8 such that the following holds. Assume dN = 1, d0 ≥ d′0, and that the weights W1(0), . . . ,WN (0) are subject to balanced initialization (Procedure 1) such that the entries in W1:N (0) are independent zero-centered Gaussian perturbations with standard deviation s ≤ ‖Φ‖2/ √ ad20. Suppose also that we run gradient
6These assignments can be accomplished since min{d1, . . . , dN−1} ≥ min{d0, dN}. 7By design W1:N = A and W>j+1Wj+1 = WjW > j , ∀j ∈ {1, . . . , N−1}— these properties are actually all we need in Theorem 2, and step (iii) in Procedure 1 can be replaced by any assignment that meets them. 8As shown in the proof of the theorem (Appendix D.3), d′0, a > 0 can take on any pair of values for
which: (i) d′0 ≥ 20; and (ii) ( 1 − 2 exp(−d′0/16) )( 3 − 4F (2/ √ a/2) ) ≥ 2p, where F (·) stands for the cumulative distribution function of the standard normal distribution. For example, if p = 0.25, it suffices to take any d′0 ≥ 100, a ≥ 100. We note that condition (i) here (d′0 ≥ 20) serves solely for simplification of expressions in the theorem.
descent with learning rate η ≤ (s2d0)4−2/N /( 105N3‖Φ‖10−6/N2 ) . Then, with probability at least p over the random initialization, we have that for every > 0 and:
T ≥ 4 η
( ln(4) ( ‖Φ‖2 s2d0 )2−2/N + ‖Φ‖2/N−22 ln(‖Φ‖22/(8 )) ) ,
the loss at iteration T of gradient descent — `(T ) — is no greater than .
Proof. See Appendix D.3.

heading: 4 EXPERIMENTS
text: Balanced initialization (Procedure 1) possesses theoretical advantages compared with the customary layer-wise independent scheme — it allowed us to derive a convergence guarantee that holds with constant probability over the randomness of initialization (Theorem 2). In this section we present empirical evidence suggesting that initializing with balancedness may be beneficial in practice as well. For conciseness, some of the details behind our implementation are deferred to Appendix E.
We began by experimenting in the setting covered by our analysis — linear neural networks trained via gradient descent minimization of `2 loss over whitened data. The dataset chosen for the experiment was UCI Machine Learning Repository’s “Gas Sensor Array Drift at Different Concentrations” (Vergara et al., 2012; Rodriguez-Lujan et al., 2014). Specifically, we used the dataset’s “Ethanol” problem — a scalar regression task with 2565 examples, each comprising 128 features (one of the largest numeric regression tasks in the repository). Starting with the customary initialization of layer-wise independent random Gaussian perturbations centered at zero, we trained a three layer network (N = 3) with hidden widths (d1, d2) set to 32, and measured the time (number of iterations) it takes to converge (reach training loss within = 10−5 from optimum) under different choices of standard deviation for the initialization. To account for the possibility of different standard deviations requiring different learning rates (values for η), we applied, for each standard deviation independently, a grid search over learning rates, and recorded the one that led to fastest convergence. The result of this test is presented in Figure 1(a). As can be seen, there is a range of standard deviations that leads to fast convergence (a few hundred iterations or less), below and above which optimization decelerates by orders of magnitude. This accords with our discussion at the end of Subsection 3.3, by which overly small initialization ensures approximate balancedness (small δ; see Definition 1) but diminishes deficiency margin (small c; see Definition 2) — “vanishing gradient problem” — whereas large initialization hinders both approximate balancedness and deficiency margin — “exploding gradient problem”. In that regard, as a sanity test for the validity of our analysis, in a case where approximate balancedness is met at initialization (small standard deviation), we measured its persistence throughout optimization. As Figure 1(c) shows, our theoretical findings manifest themselves here — trajectories of gradient descent indeed preserve weight balancedness.
In addition to a three layer network, we also evaluated a deeper, eight layer model (with hidden widths identical to the former — N = 8, d1 = · · · = d7 = 32). In particular, using the same experimental protocol as above, we measured convergence time under different choices of standard deviation for the initialization. Figure 1(a) displays the result of this test alongside that of the three layer model. As the figure shows, transitioning from three layers to eight aggravated the instability with respect to initialization — there is now a narrow band of standard deviations that lead to convergence in reasonable time, and outside of this band convergence is extremely slow, to the point where it does not take place within the duration we allowed (106 iterations). From the perspective of our analysis, a possible explanation for the aggravation is as follows: under layer-wise independent initialization, the magnitude of the end-to-end matrix W1:N depends on the standard deviation in a manner that is exponential in depth, thus for large depths the range of standard deviations that lead to moderately sized W1:N (as required for a deficiency margin) is limited, and within this range, there may not be many standard deviations small enough to ensure approximate balancedness. The procedure of balanced initialization (Procedure 1) circumvents these difficulties — it assigns W1:N directly (no exponential dependence on depth), and distributes its content between the individual weights W1, . . . ,WN in a perfectly balanced fashion. Rerunning the experiment of Figure 1(a) with this initialization replacing the customary layer-wise scheme (using same experimental protocol), we obtained the results shown in Figure 1(b) — both the original three layer network, and the deeper eight layer model, converged quickly under virtually all standard deviations tried.
As a final experiment, we evaluated the effect of balanced initialization in a setting that involves non-linear activation, softmax-cross-entropy loss and stochastic optimization (factors not accounted for by our analysis). For this purpose, we turned to the MNIST tutorial built into TensorFlow (Abadi et al., 2016),9 which comprises a fully-connected neural network with two hidden layers (width 128 followed by 32) and ReLU activation (Nair and Hinton, 2010), trained through stochastic gradient descent (over softmax-cross-entropy loss) with batch size 100, initialized via customary layer-wise independent Gaussian perturbations centered at zero. While keeping the learning rate at its default value 0.01, we varied the standard deviation of initialization, and for each value measured the training loss after 10 epochs.10 We then replaced the original (layer-wise independent) initialization with a balanced initialization based on Gaussian perturbations centered at zero (latter was implemented per Procedure 1, disregarding non-linear activation), and repeated the process. The results of this experiment are shown in Figure 1(d). Although our theoretical analysis does not cover non-linear activation, softmax-cross-entropy loss or stochasticity in optimization, its conclusion of balanced initialization leading to improved (faster and more stable) convergence carried over to such setting.

heading: 5 RELATED WORK
text: Theoretical study of gradient-based optimization in deep learning is a highly active area of research. As discussed in Section 1, a popular approach is to show that the objective landscape admits the properties of no poor local minima and strict saddle, which, by Ge et al. (2015); Lee et al. (2016); Panageas and Piliouras (2017), ensure convergence to global minimum. Many works, both classic (e.g. Baldi and Hornik (1989)) and recent (e.g. Choromanska et al. (2015); Kawaguchi (2016); Hardt and Ma (2016); Soudry and Carmon (2016); Haeffele and Vidal (2017); Nguyen and Hein (2017); Safran and Shamir (2018); Nguyen and Hein (2018); Laurent and Brecht (2018)), have focused on the validity of these properties in different deep learning settings. Nonetheless, to our knowledge,
9https://github.com/tensorflow/tensorflow/tree/master/tensorflow/ examples/tutorials/mnist
10As opposed to the dataset used in our experiments with linear networks, measuring the training loss with MNIST is non-trivial computationally (involves passing through 60K examples). Therefore, rather than continuously polling training loss until it reaches a certain threshold, in this experiment we chose to evaluate speed of convergence by measuring the training loss once after a predetermined number of iterations.
the success of landscape-driven analyses in formally proving convergence to global minimum for a gradient-based algorithm, has thus far been limited to shallow (two layer) models only (e.g. Ge et al. (2016); Du and Lee (2018); Du et al. (2018a)).
An alternative to the landscape approach is a direct analysis of the trajectories taken by the optimizer. Various papers (e.g. Brutzkus and Globerson (2017); Li and Yuan (2017); Zhong et al. (2017); Tian (2017); Brutzkus et al. (2018); Li et al. (2018); Du et al. (2018c;b); Liao et al. (2018)) have recently adopted this strategy, but their analyses only apply to shallow models. In the context of linear neural networks, deep (three or more layer) models have also been treated — cf. Saxe et al. (2014) and Arora et al. (2018), from which we draw certain technical ideas for proving Lemma 1. However these treatments all apply to gradient flow (gradient descent with infinitesimally small learning rate), and thus do not formally address the question of computational efficiency.
To our knowledge, Bartlett et al. (2018) is the only existing work rigorously proving convergence to global minimum for a conventional gradient-based algorithm training a deep model. This work is similar to ours in the sense that it also treats linear neural networks trained via minimization of `2 loss over whitened data, and proves linear convergence (to global minimum) for gradient descent. It is more limited in that it only covers the subclass of linear residual networks, i.e. the specific setting of uniform width across all layers (d0 = · · · = dN ) along with identity initialization. We on the other hand allow the input, output and hidden dimensions to take on any configuration that avoids “bottlenecks” (i.e. admits min{d1, . . . , dN−1} ≥ min{d0, dN}), and from initialization require only approximate balancedness (Definition 1), supporting many options beyond identity. In terms of the target matrix Φ, Bartlett et al. (2018) treats two separate scenarios:11 (i) Φ is symmetric and positive definite; and (ii) Φ is within distance 1/10e from identity.12 Our analysis does not fully account for scenario (i), which seems to be somewhat of a singularity, where all layers are equal to each other throughout optimization (see proof of Theorem 2 in Bartlett et al. (2018)). We do however provide a strict generalization of scenario (ii) — our assumption of deficiency margin (Definition 2), in the setting of linear residual networks, is met if the distance between target and identity is less than 0.5.

heading: 6 CONCLUSION
text: For deep linear neural networks, we have rigorously proven convergence of gradient descent to global minima, at a linear rate, provided that the initial weight matrices are approximately balanced and the initial end-to-end matrix has positive deficiency margin. The result applies to networks with arbitrary depth, and any configuration of input/output/hidden dimensions that supports full rank, i.e. in which no hidden layer has dimension smaller than both the input and output.
Our assumptions on initialization — approximate balancedness and deficiency margin — are both necessary, in the sense that violating any one of them may lead to convergence failure, as we demonstrated explicitly. Moreover, for networks with output dimension 1 (scalar regression), we have shown that a balanced initialization, i.e. a random choice of the end-to-end matrix followed by a balanced partition across all layers, leads assumptions to be met, and thus convergence to take place, with constant probability. Rigorously proving efficient convergence with significant probability under customary layer-wise independent initialization remains an open problem. The recent work of Shamir (2018) suggests that this may not be possible, as at least in some settings, the number of iterations required for convergence is exponential in depth with overwhelming probability. This negative result, a theoretical manifestation of the “vanishing gradient problem”, is circumvented by balanced initialization. Through simple experiments we have shown that the latter can lead to favorable convergence in deep learning practice, as it does in theory. Further investigation of balanced initialization, including development of variants for convolutional layers, is regarded as a promising direction for future research.
The analysis in this paper uncovers special properties of the optimization landscape in the vicinity of gradient descent trajectories. We expect similar ideas to prove useful in further study of gradient descent on non-convex objectives, including training losses of deep non-linear neural networks.
11There is actually an additional third scenario being treated — Φ is asymmetric and positive definite — but since that requires a dedicated optimization algorithm, it is outside our scope.
121/10e is the optimal (largest) distance that may be obtained (via careful choice of constants) from the proof of Theorem 1 in Bartlett et al. (2018).

heading: ACKNOWLEDGMENTS
text: This work is supported by NSF, ONR, Simons Foundation, Schmidt Foundation, Mozilla Research, Amazon Research, DARPA and SRC. Nadav Cohen is a member of the Zuckerman Israeli Postdoctoral Scholars Program, and is supported by Schmidt Foundation.

heading: A `2 LOSS OVER WHITENED DATA
text: Recall the `2 loss of a linear predictor W ∈ Rdy×dx as defined in Section 2:
L(W ) = 1
2m ‖WX − Y ‖2F ,
where X ∈ Rdx×m and Y ∈ Rdy×m. Define Λxx := 1mXX > ∈ Rdx×dx , Λyy := 1mY Y > ∈ Rdy×dy and Λyx := 1mY X
> ∈ Rdy×dx . Using the relation ‖A‖2F = Tr(AA>), we have: L(W ) = 12m Tr ( (WX − Y )(WX − Y )> ) = 12m Tr(WXX >W>)− 1m Tr(WXY >) + 12m Tr(Y Y >)
= 12 Tr(WΛxxW >)− Tr(WΛ>yx) + 12 Tr(Λyy) .
By definition, when data is whitened, Λxx is equal to identity, yielding: L(W ) = 12 Tr(WW >)− Tr(WΛ>yx) + 12 Tr(Λyy)
= 12 Tr ( (W − Λyx)(W − Λyx)> ) − 12 Tr(ΛyxΛ > yx) + 1 2 Tr(Λyy)
= 12 ‖W − Λyx‖ 2 F + c ,
where c := − 12 Tr(ΛyxΛ > yx) + 1 2 Tr(Λyy) does not depend on W . Hence we arrive at Equation (1).

heading: B APPROXIMATE BALANCEDNESS AND DEFICIENCY MARGIN UNDER
text: CUSTOMARY INITIALIZATION
Two assumptions concerning initialization facilitate our main convergence result (Theorem 1): (i) the initial weights W1(0), . . . ,WN (0) are approximately balanced (see Definition 1); and (ii) the initial end-to-end matrix W1:N (0) has positive deficiency margin with respect to the target Φ (see Definition 2). The current appendix studies the likelihood of these assumptions being met under customary initialization of random (layer-wise independent) Gaussian perturbations centered at zero.
For approximate balancedness we have the following claim, which shows that it becomes more and more likely the smaller the standard deviation of initialization is:
Claim 2. Assume all entries in the matrices Wj ∈ Rdj×dj−1 , j = 1, . . . , N , are drawn independently at random from a Gaussian distribution with mean zero and standard deviation s > 0. Then, for any δ > 0, the probability of W1, . . . ,WN being δ-balanced is at least max{0, 1 − 10δ−2Ns4d3max}, where dmax := max{d0, . . . , dN}.
Proof. See Appendix D.4.
In terms of deficiency margin, the claim below treats the case of a single output model (scalar regression), and shows that if the standard deviation of initialization is sufficiently small, with probability close to 0.5, a deficiency margin will be met. However, for this deficiency margin to meet a chosen threshold c, the standard deviation need be sufficiently large.
Claim 3. There is a constant C1 > 0 such that the following holds. Consider the case where dN = 1, d0 ≥ 20,13 and suppose all entries in the matrices Wj ∈ Rdj×dj−1 , j = 1, . . . , N , are drawn independently at random from a Gaussian distribution with mean zero, whose standard deviation s > 0 is small with respect to the target, i.e. s ≤ ‖Φ‖1/NF / (105d30d1 · · · dN−1C1)1/(2N). Then,
for any c with 0 < c ≤ ‖Φ‖F /( 105d30C1(C1N) 2N ) , the probability of the end-to-end matrix W1:N having deficiency margin c with respect to Φ is at least 0.49 if: 14 15
s ≥ c1/(2N) · ( C1N ‖Φ‖1/(2N)F /(d1 · · · dN−1) 1/(2N) ) .
Proof. See Appendix D.5. 13The requirement d0 ≥ 20 is purely technical, designed to simplify expressions in the claim. 14The probability 0.49 can be increased to any p < 1/2 by increasing the constant 105 in the upper bounds for s and c. 15It is not difficult to see that the latter threshold is never greater than the upper bound for s, thus sought-after standard deviations always exist.

heading: C CONVERGENCE FAILURES
text: In this appendix we show that the assumptions on initialization facilitating our main convergence result (Theorem 1) — approximate balancedness and deficiency margin — are both necessary, by demonstrating cases where violating each of them leads to convergence failure. This accords with widely observed empirical phenomena, by which successful optimization in deep learning crucially depends on careful initialization (cf. Sutskever et al. (2013)).
Claim 4 below shows16 that if one omits from Theorem 1 the assumption of approximate balancedness at initialization, no choice of learning rate can guarantee convergence:
Claim 4. Assume gradient descent with some learning rate η > 0 is a applied to a network whose depth N is even, and whose input, output and hidden dimensions d0, . . . , dN are all equal to some d ∈ N. Then, there exist target matrices Φ such that the following holds. For any c with 0 < c < σmin(Φ), there are initializations for which the end-to-end matrix W1:N (0) has deficiency margin c with respect to Φ, and yet convergence will fail — objective will never go beneath a positive constant.
Proof. See Appendix D.6.
In terms of deficiency margin, we provide (by adapting Theorem 4 in Bartlett et al. (2018)) a different, somewhat stronger result — there exist settings where initialization violates the assumption of deficiency margin, and despite being perfectly balanced, leads to convergence failure, for any choice of learning rate:17
Claim 5. Consider a network whose depth N is even, and whose input, output and hidden dimensions d0, . . . , dN are all equal to some d ∈ N. Then, there exist target matrices Φ for which there are non-stationary initializations W1(0), . . . ,WN (0) that are 0-balanced, and yet lead gradient descent, under any learning rate, to fail — objective will never go beneath a positive constant.
Proof. See Appendix D.7.

heading: D DEFERRED PROOFS
text: We introduce some additional notation here in addition to the notation specified in Section 2. We use ‖A‖σ to denote the spectral norm (largest singular value) of a matrix A, and sometimes ‖v‖2 as an alternative to ‖v‖— the Euclidean norm of a vector v. Recall that for a matrix A, vec(A) is its vectorization in column-first order. We let F (·) denote the cumulative distribution function of the standard normal distribution, i.e. F (x) = ∫ x −∞ 1√ 2π e− 1 2u 2 du (x ∈ R).
To simplify the presentation we will oftentimes use W as an alternative (shortened) notation for W1:N — the end-to-end matrix of a linear neural network. We will also use L(·) as shorthand for L1(·) — the loss associated with a (directly parameterized) linear model, i.e. L(W ) := 1 2 ‖W − Φ‖ 2 F . Therefore, in the context of gradient descent training a linear neural network, the following expressions all represent the loss at iteration t:
`(t) = LN (W1(t), . . . ,WN (t)) = L 1(W1:N (t)) = L 1(W (t)) = L(W (t)) = 1
2 ‖W (t)− Φ‖2F .
Also, for weights Wj ∈ Rdj×dj−1 , j = 1, . . . , N of a linear neural network, we generalize the notation W1:N , and define Wj:j′ := Wj′Wj′−1 · · ·Wj for every 1 ≤ j ≤ j′ ≤ N . Note that W>j:j′ = W > j W > j+1 · · ·W>j′ . Then, by a simple gradient calculation, the gradient descent updates (4) can be written as
Wj(t+ 1) = Wj(t)− ηW>j+1:N (t) · dL
dW (W (t)) ·W>1:j−1(t) , 1 ≤ j ≤ N , (14)
where we define W1:0(t) := Id0 and WN+1:N (t) := IdN for completeness.
16For simplicity of presentation, the claim treats the case of even depth and uniform dimension across all layers. It can easily be extended to account for arbitrary depth and input/output/hidden dimensions.
17This statement becomes trivial if one allows initialization at a suboptimal stationary point, e.g. Wj(0) = 0, j = 1, . . . , N . Claim 5 rules out such trivialities by considering only non-stationary initializations.
Finally, recall the standard definition of the tensor product of two matrices (also known as the Kronecker product): for matrices A ∈ RmA×nA , B ∈ RmB×nB , their tensor product A ⊗ B ∈ RmAmB×nAnB is defined as
A⊗B =  a1,1B · · · a1,nAB... . . . ... amA,1B · · · amA,nAB  , where ai,j is the element in the i-th row and j-th column of A.

heading: D.1 PROOF OF CLAIM 1
text: Proof. Recall that for any matrices A and B of compatible sizes σmin(A + B) ≥ σmin(A) − σmax(B), and that the Frobenius norm of a matrix is always lower bounded by its largest singular value (Horn and Johnson (1990)). Using these facts, we have:
σmin(W ′) = σmin ( Φ + (W ′ − Φ) ) ≥ σmin(Φ)− σmax(W ′ − Φ)
≥ σmin(Φ)− ‖W ′ − Φ‖F ≥ σmin(Φ)− ‖W − Φ‖F ≥ σmin(Φ)− (σmin(Φ)− c) = c .

heading: D.2 PROOF OF LEMMA 1
text: To prove Lemma 1, we will in fact prove a stronger result, Lemma 2 below, which states that for each iteration t, in addition to (9) being satisfied, certain other properties are also satisfied, namely: (i) the weight matrices W1(t), . . . ,WN (t) are 2δ-balanced, and (ii) W1(t), . . . ,WN (t) have bounded spectral norms. Lemma 2. Suppose the conditions of Theorem 1 are satisfied. Then for all t ∈ N ∪ {0},
(A(t)) For 1 ≤ j ≤ N − 1, ‖W>j+1(t)Wj+1(t)−Wj(t)W>j (t)‖F ≤ 2δ.
(A′(t)) If t ≥ 1, then for 1 ≤ j ≤ N − 1,
‖W>j+1(t)Wj+1(t)−Wj(t)W>j (t)‖F ≤ ‖W>j+1(t− 1)Wj+1(t− 1)−Wj(t− 1)W>j (t− 1)‖F
+η2 ∥∥∥∥dL1dW W (t− 1) ∥∥∥∥ F · ∥∥∥∥dL1dW W (t− 1) ∥∥∥∥ σ · 4 · (2‖Φ‖F )2(N−1)/N .
(B(t)) If t = 0, then `(t) ≤ 12‖Φ‖ 2 F . If t ≥ 1, then
`(t) ≤ `(t− 1)− η 2 σmin(W (t− 1)) 2(N−1) N ∥∥∥∥dL1dW (W (t− 1)) ∥∥∥∥2 F .
(C(t)) For 1 ≤ j ≤ N , ‖Wj(t)‖σ ≤ (4‖Φ‖F )1/N .
First we observe that Lemma 1 is an immediate consequence of Lemma 2.
Proof of Lemma 1. Notice that condition B(t) of Lemma 2 for each t ≥ 1 immediately establishes the conclusion of Lemma 1 at time step t− 1.

heading: D.2.1 PRELIMINARY LEMMAS
text: We next prove some preliminary lemmas which will aid us in the proof of Lemma 2. The first is a matrix inequality that follows from Lidskii’s theorem. For a matrix A, let Sing(A) denote the rectangular diagonal matrix of the same size, whose diagonal elements are the singular values of A arranged in non-increasing order (starting from the (1, 1) position).
Lemma 3 (Bhatia (1997), Exercise IV.3.5). For any two matricesA,B of the same size, ‖ Sing(A)− Sing(B)‖σ ≤ ‖A−B‖σ and ‖ Sing(A)− Sing(B)‖F ≤ ‖A−B‖F .
Using Lemma 3, we get: Lemma 4. SupposeD1, D2 ∈ Rd×d are non-negative diagonal matrices with non-increasing values along the diagonal and O ∈ Rd×d is an orthogonal matrix. Suppose that ‖D1 − OD2O>‖F ≤ , for some > 0. Then:
1. ‖D1 −OD1O>‖F ≤ 2 .
2. ‖D1 −D2‖F ≤ .
Proof. Since D1 and OD2OT are both symmetric positive semi-definite matrices, their singular values are equal to their eigenvalues. Moreover, the singular values of D1 are simply its diagonal elements and the singular values of OD2OT are simply the diagonal elements of D2. Thus by Lemma 3 we get that ‖D1−D2‖F ≤ ‖D1−OD2OT ‖F ≤ . Since the Frobenius norm is unitarily invariant, ‖D1 −D2‖F = ‖OD1OT −OD2OT ‖F , and by the triangle inequality it follows that
‖D1 −OD1OT ‖F ≤ ‖OD1OT −OD2OT ‖F + ‖D1 −OD2OT ‖F ≤ 2 .
Lemma 5 below states that if W1, . . . ,WN are approximately balanced matrices, i.e. W>j+1Wj+1 − WjW > j has small Frobenius norm for 1 ≤ j ≤ N − 1, then we can bound the Frobenius distance between W>1:jW1:j and (W > 1 W1) j (as well as between Wj:NW>j:N and (WNW > N ) N−j+1).
Lemma 5. Suppose that dN ≤ dN−1, d0 ≤ d1, and that for some ν > 0,M > 0, the matrices Wj ∈ Rdj×dj−1 , 1 ≤ j ≤ N satisfy, for 1 ≤ j ≤ N − 1,
‖W>j+1Wj+1 −WjW>j ‖F ≤ ν, (15)
and for 1 ≤ j ≤ N , ‖Wj‖σ ≤M . Then, for 1 ≤ j ≤ N ,
‖W>1:jW1:j − (W>1 W1)j‖F ≤ 3
2 ν ·M2(j−1)j2, (16)
and ‖Wj:NW>j:N − (WNW>N )N−j+1‖F ≤ 3
2 ν ·M2(N−j)(N − j + 1)2. (17)
Moreover, if σmin denotes the minimum singular value of W1:N , σ1,min denotes the minimum singular value of W1 and σN,min denotes the minimum singular value of WN , then
σ2min − 3
2 νM2(N−1)N2 ≤ { σ2NN,min : dN ≥ d0. σ2N1,min : dN ≤ d0.
(18)
Proof. For 1 ≤ j ≤ N , let us write the singular value decomposition of Wj as Wj = UjΣjV >j , where Uj ∈ Rdj×dj and Vj ∈ Rdj−1×dj−1 are orthogonal matrices and Σj ∈ Rdj×dj−1 is diagonal. We may assume without loss of generality that the singular values of Wj are non-increasing along the diagonal of Σj . Then we can write (15) as
‖Vj+1Σ>j+1Σj+1V >j+1 − UjΣjΣ>j U>j ‖F ≤ ν.
Since the Frobenius norm is invariant to orthogonal transformations, we get that
‖Σ>j+1Σj+1 − V >j+1UjΣjΣ>j U>j Vj+1‖F ≤ ν.
By Lemma 4, we have that ‖Σ>j+1Σj+1−ΣjΣ>j ‖F ≤ ν and ‖ΣjΣ>j −V >j+1UjΣjΣ>j U>j Vj+1‖F ≤ 2ν. We may rewrite the latter of these two inequalities as
‖[ΣjΣ>j , V >j+1Uj ]‖F = ‖[ΣjΣ>j , V >j+1Uj ]U>j Vj+1‖F = ‖ΣjΣ>j −V >j+1UjΣjΣ>j U>j Vj+1‖F ≤ 2ν.
Note that Wj:NW > j:N = Wj+1:NUjΣjΣ > j U > j W > j+1:N .
For matrices A,B, we have that ‖AB‖F ≤ ‖A‖σ · ‖B‖F . Therefore, for j + 1 ≤ i ≤ N , we have that
‖Wi:NUi−1(Σi−1Σ>i−1)i−jU>i−1W>i:N −Wi+1:NUi(ΣiΣ>i )i−j+1U>i W>i+1:N‖F = ‖Wi+1:NUi ( ΣiV > i Ui−1(Σi−1Σ > i−1) i−jU>i−1ViΣ > i − (ΣiΣ>i )i−j+1 ) U>i W > i+1:N‖F ≤ ‖Wi+1:NUiΣi‖2σ · ‖(Σi−1Σ>i−1)i−j + [V >i Ui−1, (Σi−1Σ>i−1)i−j ]U>i−1Vi − (Σ>i Σi)i−j‖F ≤ ‖Wi:N‖2σ ( ‖[V >i Ui−1, (Σi−1Σ>i−1)i−j ]‖F + ‖(Σi−1Σ>i−1)i−j − (Σ>i Σi)i−j‖F ) .
Next, we have that ‖[V >i Ui−1, (Σi−1Σ>i−1)i−j ]‖F ≤ i−j−1∑ k=0 ‖(Σi−1Σ>i−1)k[V >i Ui−1,Σi−1Σ>i−1](Σi−1Σ>i−1)i−j−1−k‖F
≤ i−j−1∑ k=0 ‖(Σi−1Σ>i−1)i−j−1‖σ · ‖[V >i Ui−1,Σi−1Σ>i−1]‖F ≤ (i− j)‖Wi−1‖2(i−j−1)σ · 2ν.
We now argue that ‖(Σi−1Σ>i−1)k − (Σ>i Σi)k‖F ≤ ν · kM2(k−1). Note that ‖Σi−1Σ>i−1 − Σ>i Σi‖F ≤ ν, verifying the case k = 1. To see the general case, since square diagonal matrices commute, we have that
‖(Σi−1Σ>i−1)k − (Σ>i Σi)k‖F = ∥∥∥∥∥(Σi−1Σ>i−1 − Σ>i Σi) · ( k−1∑ `=0 (Σi−1Σ > i−1) `(Σ>i Σi) k−1−` )∥∥∥∥∥ F
≤ ν · k−1∑ `=0 ‖Wi−1‖2`σ · ‖Wi‖2(k−`−1)σ ≤ νkM2(k−1).
It then follows that
‖Wi:NUi−1(Σi−1Σ>i−1)i−jU>i−1W>i:N −Wi+1:NUi(ΣiΣ>i )i−j+1U>i W>i+1:N‖F ≤ ‖Wi:N‖2σ · ( (i− j)M2(i−j−1) · 2ν + ν(i− j)M2(i−j−1) )
= ‖Wi:N‖2σ · 3ν(i− j)M2(i−j−1).
By the triangle inequality, we then have that
‖Wj:NW>j:N − UN (ΣNΣ>N )N−j+1U>N ‖F
≤ ν N∑
i=j+1
‖Wi:N‖2σ · 3(i− j)M2(i−j−1)
≤ 3ν N∑
i=j+1
(i− j)M2(N−i+1)M2(i−j−1)
= 3νM2(N−j) N∑
i=j+1
(i− j) ≤ 3 2 ν ·M2(N−j) · (N − j + 1)2. (19)
By an identical argument (formally, by replacing Wj with W>N−j+1), we get that
||W>1:jW1:j − V1(Σ>1 Σ1)jV >1 ‖F ≤ 3
2 ν ·M2(j−1) · j2. (20)
(19) and (20) verify (17) and (16), respectively, so it only remains to verify (18).
Letting j = 1 in (19), we get
‖W1:NW>1:N − UN (ΣNΣ>N )NU>N ‖F ≤ 3
2 ν ·M2(N−1) ·N2. (21)
Let us write the eigendecomposition of W1:NW>1:N with an orthogonal eigenbasis as W1:NW > 1:N = UΣU>, where Σ is diagonal with its (non-negative) elements arranged in non-increasing order and U is orthogonal. We can write the left hand side of (21) as ‖UΣU> − UN (ΣNΣ>N )NU>N ‖F = ‖Σ− U>UN (ΣNΣ>N )NU>NU‖F . By Lemma 4, we have that
‖Σ− (ΣNΣ>N )N‖F ≤ 3
2 νM2(N−1)N2. (22)
Recall thatW ∈ RdN×d0 . Suppose first that dN ≤ d0. Let σmin denote the minimum singular value of W1:N (so that σ2min is the element in the (dN , dN ) position of Σ ∈ RdN×dN ), and σN,min denote the minimum singular value (i.e. diagonal element) of ΣN , which lies in the (dN , dN ) position of ΣN . (Note that the (dN , dN ) position of ΣN ∈ RdN×dN−1 exists since dN−1 ≥ dN by assumption.) Then
(σ2NN,min − σ2min)2 ≤ ( 3
2 νM2(N−1)N2
)2 ,
so
σ2NN,min ≥ σ2min − 3
2 νM2(N−1)N2.
By an identical argument using (20), we get that, in the case that d0 ≤ dN , if σ1,min denotes the minimum singular value of Σ1, then
σ2N1,min ≥ σ2min − 3
2 νM2(N−1)N2.
(Notice that we have used the fact that the nonzero eigenvalues of W1:NW>1:N are the same as the nonzero eigenvalues of W>1:NW1:N .) This completes the proof of (18).
Using Lemma 5, we next show in Lemma 6 that if W1, . . . ,WN are approximately balanced, then an upper bound on ‖WN · · ·W1‖σ implies an upper bound on ‖Wj‖σ for 1 ≤ j ≤ N .
Lemma 6. Suppose ν, C are real numbers satisfying C > 0 and 0 < ν ≤ C 2/N
30N2 . Moreover suppose that the matrices W1, . . . ,WN satisfy the following:
1. For 1 ≤ j ≤ N − 1, ‖W>j+1Wj+1 −WjW>j ‖F ≤ ν.
2. ‖WN · · ·W1‖σ ≤ C.
Then for 1 ≤ j ≤ N , ‖Wj‖σ ≤ C1/N · 21/(2N).
Proof. For 1 ≤ j ≤ N , let us write the singular value decomposition of Wj as Wj = UjΣjV >j , where the singular values of Wj are decreasing along the main diagonal of Σj . By Lemma 4, we have that for 1 ≤ j ≤ N − 1, ‖Σ>j+1Σj+1 − ΣjΣ>j ‖F ≤ ν, which implies that∣∣‖Σ>j+1Σj+1‖σ − ‖ΣjΣ>j ‖σ∣∣ ≤ ν. Write M = max1≤j≤N ‖Wj‖σ = max1≤j≤N ‖Σj‖σ . By the above we have that ‖ΣjΣ>j ‖σ ≥

heading: M2 −Nν for 1 ≤ j ≤ N .
text: Let the singular value decomposition of W1:N be denoted by W1:N = UΣV >, so that ‖Σ‖σ ≤ C. Then by (17) of Lemma 5 and Lemma 4 (see also (22), where the same argument was used), we have that
‖ΣΣ> − (ΣNΣ>N )N‖F ≤ 3
2 νM2(N−1)N2.
Then
‖(ΣNΣ>N )N‖σ ≤ ‖ΣΣ>‖σ + 3
2 νM (2(N−1))N2 ≤ ‖ΣΣ>‖σ +
3 2 ν ( ‖ΣNΣ>N‖σ + νN )N−1 N2.
(23)
Now recall that ν is chosen so that ν ≤ C 2/N
30·N2 . Suppose for the purpose of contradiction that there is some j such that ‖WjW>j ‖σ > 21/NC2/N . Then it must be the case that
‖ΣNΣ>N‖σ > 21/NC2/N − ν ·N ≥ (5/4)1/NC2/N > ν · 30N2, (24)
where we have used that 21/N − (5/4)1/N ≥ 1
30N for all N ≥ 2, which follows by considering the Laurent series exp(1/z) = ∑∞ i=1 1 i!zi , which converges in |z| > 0 for z ∈ C. We now rewrite inequality (24) as
ν ≤ ‖ΣNΣ > N‖σ
30N2 . (25)
Next, using (25) and (1 + 1/x)x ≤ e for all x > 0,
3 2 ν ( ‖ΣNΣ>N‖σ + νN )N−1 N2 ≤ e 1/30 20 · ‖ΣNΣ>N‖Nσ < e 20 · ‖ΣNΣ>N‖Nσ . (26)
Since ‖(ΣNΣ>N )N‖σ = ‖ΣNΣ>N‖Nσ , we get by combining (23) and (26) that
‖ΣNΣ>N‖σ < (1− e/20)−1/N · ‖ΣΣ>‖1/Nσ ≤ (1− e/20)−1/N · C2/N ,
and since 1−e/20 > 1/(5/4), it follows that ‖ΣNΣ>N‖σ < (5/4)1/NC2/N , which contradicts (24). It follows that for all 1 ≤ j ≤ N , ‖WjW>j ‖σ ≤ 21/NC2/N . The conclusion of the lemma then follows from the fact that ‖WjW>j ‖σ = ‖Wj‖2σ .

heading: D.2.2 SINGLE-STEP DESCENT
text: Lemma 7 below states that if certain conditions on W1(t), . . . ,WN (t) are met, the sought-after descent — Equation (9) — will take place at iteration t. We will later show (by induction) that the required conditions indeed hold for every t, thus the descent persists throughout optimization. The proof of Lemma 7 is essentially a discrete, single-step analogue of the continuous proof for Lemma 1 (covering the case of gradient flow) given in Section 3. Lemma 7. Assume the conditions of Theorem 1. Moreover, suppose that for some t, the matrices W1(t), . . . ,WN (t) and the end-to-end matrix W (t) := W1:N (t) satisfy the following properties:
1. ‖Wj(t)‖σ ≤ (4‖Φ‖F )1/N for 1 ≤ j ≤ N .
2. ‖W (t)− Φ‖σ ≤ ‖Φ‖F .
3. ‖W>j+1(t)Wj+1(t)−Wj(t)W>j (t)‖F ≤ 2δ for 1 ≤ j ≤ N − 1.
4. σmin := σmin(W (t)) ≥ c.
Then, after applying a gradient descent update (4) we have that
L(W (t+ 1))− L(W (t)) ≤ −η 2 σ 2(N−1)/N min ∥∥∥∥ dLdW (W (t)) ∥∥∥∥2 F .
Proof. For simplicity write M = (4‖Φ‖F )1/N and B = ‖Φ‖F . We first claim that
η ≤ min
{ 1
2MN−2BN ,
σ 2(N−1)/N min 24 · 2M3N−4N2B , σ 2(N−1)/N min 24N2M4(N−1) ,
σ 2(N−1)/(3N) min
(24 · 4M6N−8N4B2)1/3
} . (27)
Since c ≤ σmin, for (27) to hold it suffices to have
η ≤ min  18‖Φ‖(2N−2)/NF N , c2(N−1)/N 3 · 211‖Φ‖4(N−1)/NF N2 ,
c2(N−1)/(3N) 3 · 26 ( ‖Φ‖(8N−8)/NF )1/3 N4/3
 .
As the minimum singular value of Φ must be at least c, we must have c ≤ ‖Φ‖σ . Since then c ‖Φ‖F ≤ c ‖Φ‖σ ≤ 1, it holds that
c2(N−1)/N
‖Φ‖4(N−1)/NF ≤ min
{ 1
‖Φ‖2(N−1)/NF , c2(N−1)/(3N) ‖Φ‖(8N−8)/(3N)F
} ,
meaning that it suffices to have
η ≤ c 2(N−1)/N
3 · 211N2‖Φ‖4(N−1)/NF ,
which is guaranteed by (7).
Next, we claim that
2δ ≤ min
{ c2(N−1)/N
8 · 24N3‖Φ‖2(N−2)/NF ,
c2
6 · 24N2‖Φ‖2(N−1)/NF
} (28)
≤ min
{ σ
2(N−1)/N min
8N3M2(N−2) , σ2min 6N2M2(N−1)
} .
The second inequality above is trivial, and for the first to hold, since c ≤ ‖Φ‖F , it suffices to take
2δ ≤ c 2
128 ·N3 · ‖Φ‖2(N−1)/NF ,
which is guaranteed by the definition of δ in Theorem 1.
Next we continue with the rest of the proof. It follows from (14) that18
W (t+ 1)−W (t)
= j=N∏ 1 ( Wj(t)− ηW>j+1:N (t) dL dW (W (t))W>1:j−1(t) ) −W1:N (t)
= −η  N∑ j=1 Wj+1:NW > j+1:N (t) dL dW (W (t))W>1:j−1(t)W1:j−1(t) + (?), (29) where (?) denotes higher order terms in η. We now bound the Frobenius norm of (?). To do this, note that since L(W ) = 12‖W − Φ‖ 2 F , dL dW (W (t)) = W (t)− Φ. Then
‖(?)‖F ≤ N∑ k=2 ηk ·Mk(N−1)+N−k · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥k−1 σ · ( N k )
≤ ηM2N−2N ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F N∑ k=2 ( ηMN−2BN )k−1 ≤ η · (2ηM3N−4N2B) ·
∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F , (30)
18Here, for matrices A1, . . . , AK such that AKAK−1 · · ·A1 is defined, we write ∏j=K
1 Aj := AKAK−1 · · ·A1.
where the last inequality uses ηMN−2BN ≤ 1/2, which is a consequence of (27). Next, by Lemma 5 with ν = 2δ,∥∥∥∥∥ N∑ j=1 Wj+1:NW > j+1:N (t) dL dW (W (t))W>1:j−1(t)W1:j−1(t)
− N∑
j=1
(WNW > N )
N−j dL
dW (W (t))(W>1 W1) j−1 ∥∥∥∥∥ F
≤ ∥∥∥∥∥ N∑
j=1
(Wj+1:NW > j+1:N (t)− (WNW>N )N−j)
dL dW (W (t))W>1:j−1(t)W1:j−1(t) ∥∥∥∥∥ F
+ ∥∥∥∥∥ N∑
j=1
(WNW > N )
N−j dL
dW (W (t))(W>1:j−1W1:j−1 − (W>1 W1)j−1) ∥∥∥∥∥ F
≤ ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F · ( N−1∑ j=1 3 2 2δ ·M2(N−j)(N − j)2M2(j−1) + N∑ j=2 3 2 2δ ·M2(j−2)(j − 1)2M2(N−j) )
≤ ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F · 2δN3M2(N−2).
Next, by standard properties of tensor product, we have that
vec  N∑ j=1 (WNW > N ) N−j dL dW (W (t))(W>1 W1) j−1  =
N∑ j=1 ( (W>1 W1) j−1 ⊗ (WNW>N )N−j ) vec ( dL dW (W (t)) ) .
Let us write eigenvalue decompositions W>1 W1 = UDU >,WNW > N = V EV >. Then N∑ j=1 ( (W>1 W1) j−1 ⊗ (WNW>N )N−j )
= N∑ j=1 ( UDj−1U> ⊗ V EN−jV > )
= (U ⊗ V )  N∑ j=1 Dj−1 ⊗ EN−j  (U ⊗ V )>
= OΛO>, with O = U ⊗ V , and Λ = ∑N j=1D
j−1 ⊗ EN−j . As W1 ∈ Rd1×d0 , and WN ∈ RdN×dN−1 , then D ∈ Rd0×d0 , E ∈ RdN×dN , so Λ ∈ Rd0dN×d0dN . Moreover note that Λ D0⊗EN−1 +DN−1⊗ E0 = Id0 ⊗ EN−1 + DN−1 ⊗ IdN . If λD denotes the minimum diagonal element of D and λE denotes the minimum diagonal element of E, then the minimum diagonal element of Λ is therefore at least λN−1D + λ N−1 E . But, it follows from Lemma 5 (with ν = 2δ) that
max{λND , λNE } ≥ σ2min − 3
2 2δM2(N−1)N2 ≥ 3σ2min/4,
where the second inequality follows from (28). Hence the minimum diagonal element of Λ is at least (σ2min/(4/3))
(N−1)/N ≥ σ2(N−1)/Nmin /(4/3). It follows as a result of the above inequalities that if we writeE(t) = vec(W (t+1))−vec(W (t))+ η(OΛO>)vec ( dL dW (W (t)) ) , then
‖E(t)‖2 = ∥∥∥∥vec(W (t+ 1))− vec(W (t)) + η(OΛO>)vec( dLdW (W (t)) )∥∥∥∥ 2
≤ η ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F · (2ηM3N−4N2B + 2δN3M2(N−2)).
Then we have
L(W (t+ 1))− L(W (t)) ≤ vec ( d
dW L(W (t))
)> vec (W (t+ 1)−W (t)) + 1
2 ‖W (t+ 1)−W (t)‖2F
= η ( −vec ( d
dW L(W (t))
)> (OΛO>)vec ( d
dW L(W (t))
) + 1
η vec
( d
dW L(W (t))
)> E(t) )
+ 1
2 ‖W (t+ 1)−W (t)‖2F
≤ η ( − ∥∥∥∥ ddW L(W (t)) ∥∥∥∥2 F · σ 2(N−1)/N min 4/3 + ∥∥∥∥ ddW L(W (t)) ∥∥∥∥2 F · ( 2ηM3N−4N2B + 2δN3M2(N−2) ))
+ 1
2 ‖W (t+ 1)−W (t)‖2F ,
where the first inequality follows since L(W ) = 12‖W − Φ‖ 2 F is 1-smooth as a function of W .
Next, by (29) and (30),
‖W (t+ 1)−W (t)‖2F ≤ 2η2 · ( NM2(N−1) · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F )2 + 2η2 · (2ηM3N−4N2B)2 · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥2 F
= 2η2 ∥∥∥∥ dLdW (W (t)) ∥∥∥∥2 F · ( N2M4(N−1) + (4η2M6N−8N4B2) ) . (31)
Thus
L(W (t+ 1))− L(W (t)) ≤ η · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥2 F · ( −σ 2(N−1)/N min 4/3 + 2ηM3N−4N2B + 2δN3M2(N−2)
+η · (N2M4(N−1) + 4η2M6N−8N4B2) ) .
By (27, 28), which bound η, 2δ, respectively, we have that
L(W (t+ 1))− L(W (t)) ≤ η · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥2 F · ( −σ 2(N−1)/N min 4/3 + σ 2(N−1)/N min 24 + σ 2(N−1)/N min 8 + σ 2(N−1)/N min 24 + σ 2(N−1)/N min 24 )
= −1 2 σ 2(N−1)/N min η ∥∥∥∥ dLdW (W (t)) ∥∥∥∥2 F . (32)

heading: D.2.3 PROOF OF LEMMA 2
text: Proof of Lemma 2. We use induction on t, beginning with the base case t = 0. Since the weights W1(0), . . . ,WN (0) are δ-balanced, we get that A(0) holds automatically. To establish B(0), note that sinceW1:N (0) has deficiency margin c > 0 with respect to Φ, we must have ‖W1:N (0)−Φ‖F ≤ σmin(Φ) ≤ ‖Φ‖F , meaning that L1(W1:N (0)) ≤ 12‖Φ‖ 2 F .
Finally, by B(0), which gives ‖W (0)− Φ‖F ≤ ‖Φ‖F , we have that
‖W (0)‖σ ≤ ‖W (0)‖F ≤ ‖W (0)− Φ‖F + ‖Φ‖F ≤ 2‖Φ‖F . (33)
To show that the above implies C(0), we use condition A(0) and Lemma 6 with C = 2‖Φ‖F and ν = 2δ. By the definition of δ in Theorem 1 and since c ≤ ‖Φ‖F , we have that
2δ ≤ c 2 128 ·N3 · ‖Φ‖2(N−1)/NF = ‖Φ‖2/NF 128N3 · c 2 ‖Φ‖2F < ‖Φ‖2/NF 30N2 , (34)
as required by Lemma 6. As A(0) and (33) verify the preconditions 1. and 2., respectively, of Lemma 6, it follows that for 1 ≤ j ≤ N , ‖Wj(t)‖σ ≤ (2‖Φ‖F )1/N · 21/(2N) < (4‖Φ‖F )1/N , verifying C(0) and completing the proof of the base case. The proof of Lemma 2 follows directly from the following inductive claims.
1. A(t),B(t), C(t) ⇒ B(t + 1). To prove this, we use Lemma 7. We verify first that the preconditions hold. First, C(t) immediately gives condition 1. of Lemma 7. By B(t), we have that ‖W (t) − Φ‖σ ≤ ‖W (t) − Φ‖F ≤ ‖Φ‖F , giving condition 2. of Lemma 7. A(t) immediately gives condition 3. of Lemma 7. Finally, by B(t), we have that LN (W1(t), . . . ,WN (t)) ≤ LN (W1(0), . . . ,WN (0)), so σmin(W1:N (t)) ≥ c by Claim 1. This verifies condition 4. of Lemma 7. Then Lemma 7 gives that LN (W1(t + 1), . . . ,WN (t + 1)) ≤ LN (W1(t), . . . ,WN (t)) − 1 2σmin(W (t)) 2(N−1)/Nη ∥∥ dL dW (W (t)) ∥∥2 F , establishing B(t+ 1).
2. A(0),A′(1), . . . ,A′(t),A(t),B(0), . . . ,B(t), C(t) ⇒ A(t + 1),A′(t + 1). To prove this, note that for 1 ≤ j ≤ N − 1,
W>j+1(t+ 1)Wj+1(t+ 1)−Wj(t+ 1)W>j (t+ 1)
= ( W>j+1(t)− ηW1:j(t) dL
dW (W (t))>Wj+2:N (t) ) · ( Wj+1(t)− ηW>j+2:N (t) dL
dW (W (t))W>1:j(t) ) − ( Wj(t)− ηW>j+1:N (t) dL
dW (W (t))W>1:j−1(t) ) · ( W>j (t)− ηW1:j−1(t) dL
dW (W (t))>Wj+1:N (t)
) .
By B(0), . . . ,B(t), ‖W1:N (t) − Φ‖F ≤ ‖Φ‖F . By the triangle inequality it then follows that ‖W1:N (t)‖σ ≤ 2‖Φ‖F . Also A(t) gives that for 1 ≤ j ≤ N − 1, ‖Wj(t)W>j (t) − W>j+1(t)Wj+1(t)‖F ≤ 2δ. By Lemma 6 with C = 2‖Φ‖F , ν = 2δ (so that (34) is satisfied),∥∥W>j+1(t+ 1)Wj+1(t+ 1)−Wj(t+ 1)W>j (t+ 1)∥∥F ≤ ‖W>j+1(t)Wj+1(t)−Wj(t)W>j (t)‖F + η2 ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F · ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ σ
· ( ‖Wj+2:N (t)‖2σ‖W1:j(t)‖2σ + ‖W1:j−1‖2σ‖Wj+1:N‖2σ ) ≤ ‖W>j+1(t)Wj+1(t)−Wj(t)W>j (t)‖F
+4η2 ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ F ∥∥∥∥ dLdW (W (t)) ∥∥∥∥ σ (2‖Φ‖F )2(N−1)/N . (35)
In the first inequality above, we have also used the fact that for matricesA,B such thatAB is defined, ‖AB‖F ≤ ‖A‖σ‖B‖F . (35) gives us A′(t+ 1).
We next establish A(t + 1). By B(i) for 0 ≤ i ≤ t, we have that ∥∥ dL dW (W (i)) ∥∥ F = ‖W − Φ‖F ≤ ‖Φ‖F . Using A′(i) for 0 ≤ i ≤ t and summing over i gives
‖W>j+1(t+ 1)Wj+1(t+ 1)−Wj(t+ 1)W>j (t+ 1)‖F ≤ ‖W>j+1(0)Wj+1(0)−Wj(0)W>j (0)‖F
+4(2‖Φ‖F )2(N−1)/N · η2 t∑ i=0 ∥∥∥∥ dLdW (W (i)) ∥∥∥∥2 F . (36)
Next, by B(0), . . . ,B(t), we have that L(W (i)) ≤ L(W (0)) for i ≤ t. Since W (0) has deficiency margin of c and by Claim 1, it then follows that σmin(W (i)) ≥ c for all i ≤ t.
Therefore, by summing B(0), . . . ,B(t),
1 2 c2(N−1)/Nη t∑ i=0 ∥∥∥∥ dLdW W (i) ∥∥∥∥2 F
≤ 1 2 η t∑ i=0 σmin(W (i)) 2(N−1)/N ∥∥∥∥ dLdW (W (i)) ∥∥∥∥2 F
≤ L(W (0))− L(W (t))
≤ L(W (0)) ≤ 1 2 ‖Φ‖2F .
Therefore,
4 (2‖Φ‖F )2(N−1)/N η2 t∑ i=0 ∥∥∥∥ dLdW W (i) ∥∥∥∥2 F
≤ 16‖Φ‖2(N−1)/NF η ‖Φ‖2F
c2(N−1)/N
≤ 16‖Φ‖2(N−1)/NF · 1 3 · 211 ·N3 · c
(4N−2)/N
‖Φ‖(6N−4)/NF · ‖Φ‖ 2 F c2(N−1)/N (37)
≤ c 2
256N3‖Φ‖2(N−1)/NF = δ,
where (37) follows from the definition of η in (7), and the last equality follows from definition of δ in Theorem 1. By (36), it follows that
‖W>j+1(t+ 1)Wj+1(t+ 1)−Wj(t+ 1)W>j (t+ 1)‖F ≤ 2δ,
verifying A(t+ 1).
3. A(t),B(t) ⇒ C(t). We apply Lemma 6 with ν = 2δ and C = 2‖Φ‖F . First, the triangle inequality and B(t) give
‖W1:N (t)‖σ ≤ ‖Φ‖σ + ‖Φ−W1:N (t)‖σ ≤ ‖Φ‖F + √
2 · L(W1:N (t)) ≤ 2‖Φ‖F , verifying precondition 2. of Lemma 6. A(t) verifies condition 1. of Lemma 6, so for 1 ≤ j ≤ N , ‖Wj(t)‖σ ≤ (4‖Φ‖F )1/N , giving C(t).
The proof of Lemma 2 then follows by induction on t.

heading: D.3 PROOF OF THEOREM 2
text: Theorem 2 is proven by combining Lemma 8 below, which implies that the balanced initialization is likely to lead to an end-to-end matrix W1:N (0) with sufficiently large deficiency margin, with Theorem 1, which establishes convergence. Lemma 8. Let d ∈ N, d ≥ 20; b2 > b1 ≥ 1 be real numbers (possibly depending on d); and Φ ∈ Rd be a vector. Suppose that µ is a rotation-invariant distribution19 over Rd with a well-defined density, such that, for some 0 < < 1,
PV∼µ [ ‖Φ‖2√ b2d ≤ ‖V ‖2 ≤ ‖Φ‖2√ b1d ] ≥ 1− .
Then, with probability at least (1 − ) · 3−4F (2/ √ b1)
2 , V will have deficiency margin ‖Φ‖2/(b2d) with respect to Φ.
19Recall that a distribution on vectors V ∈ Rd is rotation-invariant if the distribution of V is the same as the distribution of OV , for any orthogonal d × d matrix O. If V has a well-defined density, this is equivalent to the statement that for any r > 0, the distribution of V conditioned on ‖V ‖2 = r is uniform over the sphere centered at the origin with radius r.
The proof of Lemma 8 is postponed to Appendix D.5, where Lemma 8 will be restated as Lemma 16.
One additional technique is used in the proof of Theorem 2, which leads to an improvement in the guaranteed convergence rate. Because the deficiency margin of W1:N (0) is very small, namely O(‖Φ‖2/d0) (which is necessary for the theorem to maintain constant probability), at the beginning of optimization, `(t) will decrease very slowly. However, after a certain amount of time, the deficiency margin of W1:N (t) will increase to a constant, at which point the decrease of `(t) will be much faster. To capture this acceleration, we apply Theorem 1 a second time, using the larger deficiency margin at the new “initialization.” From a geometric perspective, we note that the matrices W1(0), . . . ,WN (0) are very close to 0, and the point at which Wj(0) = 0 for all j is a saddle. Thus, the increase in `(t)− `(t+1) over time captures the fact that the iterates (W1(t), . . . ,WN (t)) escape a saddle point.
Proof of Theorem 2. Choose some a ≥ 2, to be specified later. By assumption, all entries of the end-to-end matrix at time 0, W1:N (0), are distributed as independent Gaussians of mean 0 and standard deviation s ≤ ‖Φ‖2/ √ ad20. We will apply Lemma 8 to the vector W1:N (0) ∈ Rd0 . Since its distribution is obviously rotation-invariant, in remains to show that the distribution of the norm ‖W1:N (0)‖2 is not too spread out. The following lemma — a direct consequence of the Chernoff bound applied to the χ2 distribution with d0 degrees of freedom — will give us the desired result:
Lemma 9 (Laurent and Massart (2000), Lemma 1). Suppose that d ∈ N and V ∈ Rd is a vector whose entries are i.i.d. Gaussians with mean 0 and standard deviation s. Then, for any k > 0,
P [ ‖V ‖22 ≥ s2 ( d+ 2k + 2 √ kd )] ≤ exp(−k)
P [ ‖V ‖22 ≤ s2 ( d− 2 √ kd )] ≤ exp(−k).
By Lemma 9 with k = d0/16, we have that P [ s2d0
2 ≤ ‖V ‖22 ≤ 2s2d0
] ≥ 1− 2 exp(−d0/16).
We next use Lemma 8, with b1 = ‖Φ‖22/(2s2d20), b2 = 2‖Φ‖22/(s2d20); note that since a ≥ 2, b1 ≥ 1, as required by the lemma. Lemma 8 then implies that with probability at least
(1− 2 exp(−d0/16)) 3− 4F
( 2/ √ a/2 )
2 , (38)
W1:N (0) will have deficiency margin s2d0/2‖Φ‖2 with respect to Φ. By the definition of balanced initialization (Procedure 1) W1(0), . . . ,WN (0) are 0-balanced. Since 24 · 6144 < 105, our assumption on η gives
η ≤ (s 2d0)
4−2/N
24 · 6144N3‖Φ‖10−6/N2 , (39)
so that Equation (7) holds with c = s 2d0
2‖Φ‖2 . The conditions of Theorem 1 thus hold with probability at least that given in Equation (38). In such a constant probability event, by Theorem 1 (and the fact that a positive deficiency margin implies L1(W1:N (0)) ≤ 12‖Φ‖ 2 2), if we choose
t0 ≥ η−1 (
2‖Φ‖2 s2d0
)2−2/N ln(4), (40)
then L1(W1:N (t0)) ≤ 18‖Φ‖ 2 2, meaning that ‖W1:N (t0) − Φ‖2 ≤ 12‖Φ‖2 = ‖Φ‖2 − 1 2σmin(Φ). Moreover, by condition A(t0) of Lemma 2 and the definition of δ in Theorem 1, we have, for 1 ≤ j ≤ N − 1,
‖WTj+1(t0)Wj+1(t0)−Wj(t0)WTj (t0)‖F ≤ 2s4d20
(2‖Φ‖2)2 · 256N3‖Φ‖2−2/N2 =
s4d20
512N3‖Φ‖4−2/N2 .
(41)
We now apply Theorem 1 again, verifying its conditions again, this time with the initialization (W1(t0), . . . ,WN (t0)). First note that the end-to-end matrix W1:N (t0) has deficiency margin c = ‖Φ‖2/2 as shown above. The learning rate η, by Equation (39), satisfies Equation (7) with c = ‖Φ‖2/2. Finally, since
s4d20 512N3‖Φ‖4−2/N2 ≤ ‖Φ‖ 2/N (a2d20) · 512N3 ≤ ‖Φ‖ 2/N (1/2)2 256N3
for d0 ≥ 2, by Equation (41), the matrices W1(t0), . . . ,WN (t0) are δ-balanced with δ = ‖Φ‖2/N (1/2)2
256N3 . Iteration t0 thus satisfies the conditions of Theorem 1 with deficiency margin ‖Φ‖2/2, meaning that for T − t0 ≥ η−1 · 22−2/N · ‖Φ‖2/N−2 ln ( ‖Φ‖22
8
) , (42)
we will have `(T ) ≤ . Therefore, by Equations (40) and (42), to ensure that `(T ) ≤ , we may take T ≥ 4η−1 ( ln(4) ( ‖Φ‖2 s2d0 )2−2/N + ‖Φ‖2/N−22 ln(‖Φ‖22/(8 )) ) .
Recall that this entire analysis holds only with the probability given in Equation (38). As limd→∞(1 − 2 exp(−d/16)) = 1 and lima→∞(3 − 4F (2 √ 2/a))/2 = 1/2, for any 0 < p < 1/2, there exist a, d′0 > 0 such that for d0 ≥ d′0, the probability given in Equation (38) is at least p. This completes the proof.
In the context of the above proof, we remark that the expressions 1 − 2 exp(−d0/16) and (3 − 4F (2 √ 2/a))/2 converge to their limits of 1 and 1/2, respectively, as d0, a→∞ quite quickly. For instance, to obtain a probability of greater than 0.25 of the initialization conditions being met, we may take d0 ≥ 100, a ≥ 100.

heading: D.4 PROOF OF CLAIM 2
text: We first consider the probability of δ-balancedness holding between any two layers: Lemma 10. Suppose a, b, d ∈ N and A ∈ Ra×d, B ∈ Rd×b are matrices whose entries are distributed as i.i.d. Gaussians with mean 0 and standard deviation s. Then for k ≥ 1,
P [∥∥ATA−BBT∥∥
F ≥ ks2
√ 2d(a+ b)2 + d2(a+ b) ] ≤ 1/k2. (43)
Proof. Note that for 1 ≤ i, j ≤ d, let Xij be the random variable (ATA−BBT )ij , so that
Xij = (A TA−BBT )ij = ∑ 1≤`≤a A`iA`j − ∑ 1≤r≤b BirBjr.
If i 6= j, then E[X2] = ∑ 1≤`≤a E[A2`iA2`j ] + ∑ 1≤r≤b E[B2irB2jr] = (a+ b)s4.
We next note that for a normal random variable Y of variance s2 and mean 0, E[Y 4] = 3s4. Then if i = j,
E[X2] = s4 · (3(a+ b) + a(a− 1) + b(b− 1)−ab) ≤ s4((a+ b)2 + 2(a+ b)). Thus
E[‖ATA−BBT ‖2F ] ≤ s4(d((a+ b)2 + 2(a+ b)) + d(d− 1)(a+ b)) ≤ s4(2d(a+ b)2 + d2(a+ b)).
Then (43) follows from Markov’s inequality.
Now the proof of Claim 2 follows from a simple union bound:
Proof of Claim 2. By (43) of Lemma 10, for each 1 ≤ j ≤ N − 1, k ≥ 1, P [ ‖WTj+1Wj+1 −WjWTj ‖F≥ks2 √ 10d3max ] ≤ 1/k2.
By the union bound, P [ ∀1 ≤ j ≤ N − 1, ‖WTj+1Wj+1 −WjWTj ‖F ≤ ks2 √ 10d3max ] ≥ 1−N/k2,
and the claim follows with δ = ks2 √
10d3max.

heading: D.5 PROOF OF CLAIM 3
text: We begin by introducing some notation. Given d ∈ N and r > 0, we let Bd(r) denote the open ball of radius r centered at the origin in Rd. For an open subset U ⊂ Rd, let ∂U := Ū\U be its boundary, where Ū denotes the closure of U . For the special case of U = Bd(r), we will denote by Sd(r) the boundary of such a ball, i.e. the sphere of radius r centered at the origin in Rd. Let Sd := Sd(1) and Bd := Bd(1). There is a well-defined uniform (Haar) measure on Sd(r) for all d, r, which we denote by σd,r; we assume σd,r is normalized so that σd,r(Sd(r)) = 1. Finally, since in the context of this claim we have dN = 1, we allow ourselves to regard the end-to-end matrix W1:N ∈ R1×d0 as both a matrix and a vector.
To establish Claim 3, we will use the following low-degree anti-concentration result of Carbery and Wright (2001) (see also Lovett (2010); Meka et al. (2016)): Lemma 11 (Carbery and Wright (2001)). There is an absolute constant C0 such that the following holds. Suppose that h is a multilinear polynomial of K variables X1, . . . , XK and of degree N . Suppose that X1, . . . , XK are i.i.d. Gaussian. Then, for any > 0:
P [ |h(X1, . . . , XK)| ≤ · √ Var[h(X1, . . . , XK)] ] ≤ C0N 1/N .
The below lemma characterizes the norm of the end-to-end matrix W1:N following zero-centered Gaussian initialization: Lemma 12. For any constant 0 < C2 < 1, there is an absolute constant C1 > 0 such that the following holds. Let N, d0, . . . , dN−1 ∈ N. Set dN = 1. Suppose that for 1 ≤ j ≤ N , Wj ∈ Rdj×dj−1 are matrices whose entries are i.i.d. Gaussians of standard deviation s and mean 0. Then
P [ s2Nd1 · · · dN−1 ( 1
C1N
)2N ≤ ‖W1:N‖22 ≤ C1d20d1 · · · dN−1s2N ] ≥ C2.
Proof. Let f(W1, . . . ,WN ) = ‖W1:N‖22, so that f is a polynomial of degree 2N in the entries of W1, . . . ,WN . Notice that
f(W1, . . . ,WN ) = d0∑ i0=1  d1∑ i1=1 · · · dN−1∑ iN−1=1 (WN )1,iN−1(WN−1)iN−1,iN−2 · · · (W1)i1,i0 2 . For 1 ≤ i0 ≤ d0, set
gi0(W1, . . . ,WN ) = d1∑ i1=1 · · · dN−1∑ iN−1=1 (WN )1,iN−1(WN−1)iN−1,iN−2 · · · (W1)i1,i0 ,
so that f = ∑d0 i0=1
g2i0 . Since each gi0 is a multilinear polynomial in W1, . . . ,WN , we have that E[gi0(W1, . . . ,WN )] = 0 for all 1 ≤ i0 ≤ d0. Also
Var[gi0(W1, . . . ,WN )] = E[gi0(W1, . . . ,WN )2]
= d1∑ i1=1 · · · dN−1∑ iN−1=1 E [ (WN ) 2 1,iN−1(WN−1) 2 iN−1,iN−2 · · · (W1) 2 i1,i0 ] = d1d2 · · · dN−1s2N .
It then follows by Markov’s inequality that for any k ≥ 1, P[g2i0 ≥ ks 2Nd1 · · · dN−1] ≤ 1/k. For any constant B1 (whose exact value will be specified below), it follows that
P[f(W1, . . . ,WN )≥B1d20d1d2 · · · dN−1s2N ]
= P [ d0∑ i0=1 gi0(W1, . . . ,WN ) 2≥B1d20d1d2 · · · dN−2s2N ] ≤ d0 · P[g1(W1, . . . ,WN )2≥B1d0d1 · · · dN−1s2N ] ≤ 1/B1. (44)
Next, by Lemma 11, there is an absolute constant C0 > 0 such that for any > 0, and any 1 ≤ i0 ≤ d0,
P [ |gi0(W1, . . . ,WN )| ≤ N √ s2Nd1 · · · dN−1 ] ≤ C0N .
Since f2 ≥ g2i0 for each i0, it follows that
P[f(W1, . . . ,WN ) ≥ 2Ns2Nd1 · · · dN−1] ≥ 1− C0N . (45)
Next, given 0 < C2 < 1, choose = (1− C2)/(2C0N), and B1 = 2/(1− C2). Then by (44) and (45) and a union bound, we have that
P [( 1− C2 2C0N )2N s2Nd1 · · · dN−1 ≤ f(W1, . . . ,WN ) ≤
2
1− C2 s2Nd20d1 · · · dN−1
] ≥ C2.
The result of the lemma then follows by taking C1 = max {
2 1−C2 , 2C0 1−C2
} .
Lemma 13. Let N, d0, . . . , dN−1 ∈ N, and set dN = 1. Suppose Wj ∈ Rdj×dj−1 for 1 ≤ j ≤ N , are matrices whose entries are i.i.d. Gaussians with mean 0 and standard deviation s. Then, the distribution of W1:N is rotation-invariant.
Proof. First we remark that for any orthogonal matrix O ∈ Rd0×d0 , the distribution of W1 is the same as that of W1O. To see this, let us denote the rows of W1 by (W1)1, . . . , (W1)d1 , and the columns of O by O1, . . . , Od0 . Then the (i1, i0) entry of W1O, for 1 ≤ i1 ≤ d1, 1 ≤ i0 ≤ d0 is 〈(W1)i1 , Oi0〉, which is a Gaussian with mean 0 and standard deviation s, since ‖Oi0‖2 = 1. Since 〈Oi0 , Oi′0〉 = 0 for i0 6= i′0, the covariance between any two distinct entries of W1O is 0. Therefore, the entries of W1O are independent Gaussians with mean 0 and standard deviation s, just as are the entries of W1.
But now for any matrix O ∈ Rd0×d0 , the distribution of W1:NO is the distribution of WNWN−1 · · ·W2(W1O), which is the same as the distribution of WNWN−1 · · ·W2W1 = W1:N , since W1,W2, . . . ,WN are all independent.
For a dimension d ∈ N, radius r > 0, and 0 < h < r, a (d, r)-hyperspherical cap of height h is a subset C ⊂ Bd(r) of the form {x ∈ Bd(r) : 〈x, u〉 ≥ r − h}, where u is any d-dimensional unit vector. We define the area of a (d, r)-hyperspherical cap of height h— C— to be σd,r(∂C∩Sd(r)). Lemma 14. For d ≥ 20, choose any 0 ≤ h ≤ 1. Then, the area of a (d, 1)-hyperspherical cap of height h is at least
3− 4F ((1− h) √ d− 3)
2 .
Proof. In Chudnov (1986), it is shown that the area of a (d, 1)-hyperspherical cap of height h is given by 1−Cd−2(h)/Cd−2(0)2 , where
Cd(h) := ∫ 1−h 0 (1− t2)(d−1)/2dt.
Next, by the inequality 1− t2 ≥ exp(−2t2) for 0 ≤ t ≤ 1/2,∫ 1 0 (1− t2)(d−3)/2dt ≥ ∫ 1/2 0 exp ( 2 · −t 2(d− 3) 2 ) dt
= √ π/(d− 3) ·
2F ( √
(d− 3)/2)− 1 2
≥ √ π/(d− 3) · 1− 2 exp(−(d− 3)/4)
2 , (46)
where the last inequality follows from the standard estimate F (x) ≥ 1 − exp(−x2/2) for x ≥ 1. Also, since 1− t2 ≤ exp(−t2) for all t,∫ 1−h
0
(1− t2)(d−3)/2dt ≤ ∫ 1−h
0
exp
( −t2(d− 3)
2
) dt
= √ 2π/(d− 3) · 2F ((1− h) √ d− 3)− 1
2 . (47)
Therefore, for d ≥ 20, by (46) and (47),
1− Cd−2(h)/Cd−2(0) 2 ≥ 1−
√ 2·(2F ((1−h) √ d−3)−1)
1−2 exp(−(d−3)/4)
2
≥ 1− √ 2 · (2F ((1− h) √ d− 3)− 1) · (1 + 4 exp(−(d− 3)/4))
2
≥ 3− 4F ((1− h) √ d− 3)
2 ,
where the second inequality has used 1/(1 − y) ≤ 1 + 2y for all 0 < y < 1/2 (and where y = 2 exp((−(d− 3)/4)) < 2 exp(−17/4) < 1/2), and the final inequality uses 1 + 4 exp(−(d− 3)/4) ≤ √ 2 for d ≥ 20. The above chain of inequalities gives us the desired result.
Lemma 15. Let d ∈ N, d ≥ 20; a ≥ 1 be a real number (possibly depending on d); and Φ ∈ Rd be some vector. Set r = ‖Φ‖2/ √ ad, and suppose that V ∈ Sd(r) is drawn according to the uniform measure. Then, with probability at least 3−4F (2/ √ a)
2 , V will have deficiency margin ‖Φ‖2/(ad) with respect to Φ.
Proof. By rescaling, we may assume without loss of generality that ‖Φ‖2 = 1, so that r = 1/ √ ad. Let D denote the intersection of Bd(r) with the open d-ball of radius 1− 1/(ad) centered at Φ. Let C ⊂ Bd(r) denote the (d, r)-hyperspherical cap of height r · ( 1 − 2/( √ ad) )
= r − 2/(ad) whose base is orthogonal to the line between 0 and Φ (see Figure 2). Note that σd,r(∂D∩Sd(r)), the Haar measure of the portion of ∂D intersecting Sd(r), gives the probability that V belongs to the boundary of D. By Lemma 14 above (along with rescaling arguments), since d ≥ 20, σd,r(∂C ∩ Sd(r)) ≥ 1 2 · (3− 4F (2/ √ a)), and therefore V ∈ ∂C with at least this probability.
We next claim that C ⊆ D. To see this, first let T ⊂ Rd denote the (d − 1)-sphere of radius 1 − 1/(ad) centered at Φ (see Figure 2). Let P be the intersection of T with the line from 0 to Φ, and Q denote the intersection of this line with the unique hyperplane of codimension 1 containing T ∩ ∂Bd(r) — we denote this hyperplane by H. If we can show that ‖P −Q‖2 ≤ 1/(ad), then it follows that C lies entirely on the other side ofH as 0, which will complete the proof that C ⊆ D. The calculation of ‖P −Q‖2 is simply an application of the law of cosines: letting θ be the angle determining the intersection of ∂Bd(r) and T (see Figure 2), note that
(1− 1/(ad))2 = r2 + 12 − 2r cos θ = 1/(ad) + 1− 2/ √ ad · cos(θ),
so d(P,Q) = r cos θ − 1/(ad) = 1
2 (1/(ad)− 1/(a2d2)) < 1/(ad),
as desired.
Using that C ⊆ D, we continue with the proof. Notice the fact that C ⊆ D is equivalent to ∂C ∩ Sd(r) ⊆ ∂D ∩ Sd(r), by the structure of C and D. Since the probability that V lands in ∂C is at least 3−4F (2/ √ a)
2 , this lower bound applies to V landing in ∂D as well. Since all V ∈ ∂D have distance at most 1 − 1/(ad) from Φ, and since σmin(Φ) = ‖Φ‖2 = 1, it follows that for any V ∈ ∂D, ‖V − Φ‖2 ≤ σmin(Φ) − 1/(ad). Therefore, with probability of at least 3−4F (2/ √ a)
2 , V has deficiency margin ‖Φ‖2/(ad) with respect to Φ.
Lemma 16 (Lemma 8 restated). Let d ∈ N, d ≥ 20; b2 > b1 ≥ 1 be real numbers (possibly depending on d); and Φ ∈ Rd be a vector. Suppose that µ is a rotation-invariant distribution over Rd with a well-defined density, such that, for some 0 < < 1,
PV∼µ [ ‖Φ‖2√ b2d ≤ ‖V ‖2 ≤ ‖Φ‖2√ b1d ] ≥ 1− .
Then, with probability at least (1 − ) · 3−4F (2/ √ b1)
2 , V will have deficiency margin ‖Φ‖2/(b2d) with respect to Φ.
Proof. By rescaling we may assume that ‖Φ‖2 = 1 without loss of generality. Then the deficiency margin of V is equal to 1 − ‖V − Φ‖2. µ has a well-defined density, so we can set µ̂ to be the
probability density function of ‖V ‖2. Since µ is rotation-invariant, we can integrate over spherical coordinates, giving
P[1− ‖V − Φ‖2 ≥ 1/(b2d)]
= ∫ ∞ 0 P [ 1− ‖V − Φ‖2 ≥ 1/(b2d) ∣∣ ‖V ‖2 = r]µ̂(r)dr ≥
∫ 1/(√b1d) 1/( √ b2d) 3− 4F (2r √ d) 2 µ̂(r)dr
≥ 3− 4F (2/ √ b1) 2 · ∫ 1/(√b1d)
1/( √ b2d)
µ̂(r)dr
≥ 3− 4F (2/ √ b1)
2 · (1− ),
where the first inequlaity used Lemma 15 and the fact that the distribution of V conditioned on ‖V ‖2 = r is uniform on Sd(r).
Now we are ready to prove Claim 3:
Proof of Claim 3. We let W ∈ R1×d0 ' Rd0 denote the random vector W1:N ; also let µ denote the distribution of W , so that by Lemma 13, µ is rotation-invariant. Let C1 be the constant from Lemma 12 for C2 = 999/1000. For some a ≥ 105, the standard deviation of the entries of each Wj is given by
s =
( ‖Φ‖22
ad30d1 · · · dN−1C1
)1/(2N) . (48)
Then by Lemma 12,
P [ ‖Φ‖22 ad30C1 · ( 1 C1N )2N ≤ ‖W‖22 ≤ ‖Φ‖22 ad0 ] ≥ 999 1000 .
Then Lemma 16, with d = d0, b1 = a and b2 = ad20C1 · (C1N)2N , implies that with probability at least 9991000 · 3−4F (2/ √ a) 2 , W has deficiency margin ‖Φ‖2/(ad 3 0C 2N+1 1 N
2N ) with respect to Φ. But a ≥ 105 implies that this probability is at least 0.49, and from (48),
‖Φ‖2 ad30C 2N+1 1 N 2N = s2Nd1 · · · dN−1 ‖Φ‖2(C1N)2N . (49)
Next recall the assumption in the hypothesis that s ≥ C1N(c · ‖Φ‖2 /(d1 · · · dN−1))1/2N . Then the deficiency margin in (49) is at least(
C1N(c ‖Φ‖2 /(d1 · · · dN−1))1/(2N) )2N
d1 · · · dN−1 ‖Φ‖2(C1N)2N = c,
completing the proof.

heading: D.6 PROOF OF CLAIM 4
text: Proof. The target matrices Φ that will be used to prove the claim satisfy σmin(Φ) = 1. We may assume without loss of generality that c ≥ 3/4, the reason being that if a matrix has deficiency margin c with respect to Φ and c′ < c, it certainly has deficiency margin c′ with respect to Φ.
We first consider the case d = 1, so that the target and all matrices are simply real numbers; we will make a slight abuse of notation in identifying 1 × 1 matrices with their unique entries. We set Φ = 1. For all choices of η, we will set the initializations W1(0), . . . ,WN (0) so that W1:N (0) = c. Then
‖W1:N (0)− Φ‖F = |W1:N (0)− Φ| = 1− c = σmin(Φ)− c,
so the initial end-to-end matrix W1:N (0) ∈ R1×1 has deficiency margin c. Now fix η. Choose A ∈ R with
A = max {√ ηN,
2
η(1− c)c(N−1)/N , 2000, 20/η,
( 20 · 102N−1
η2N
)1/(2N−2)} . (50)
We will set:
Wj(0) = { Ac1/N : 1 ≤ j ≤ N/2 c1/N/A : N/2 < j ≤ N, (51)
so that W1:N (0) = c. Then since LN (W1, . . . ,WN ) = 12 (1 −WN · · ·W1) 2, the gradient descent updates are given by
Wj(t+ 1) = Wj(t)− η(W1:N (t)− 1) ·W1:j−1(t)Wj+1:N (t), where we view W1(t), . . . ,WN (t) as real numbers. This gives
Wj(1) = { c1/NA− η(c− 1)c(N−1)/N/A : 1 ≤ j ≤ N/2 c1/N/A− η(c− 1)c(N−1)/NA : N/2 < j ≤ N.
Since 3/4 ≤ c < 1 and −η(c − 1)c(N−1)/NA ≥ 0, we have that A/2 ≤ 3A/4 ≤ Wj(1) for 1 ≤ j ≤ N/2. Next, since 1−c
1−c1/N ≤ N for 0 ≤ c < 1, we have that A 2 ≥ ηN ≥ η(1−c) 1−c1/N , which
implies thatA2 ≥ c1/NA2+η(1−c), or c1/NA+ η(1−c)A ≤ A. ThusWj(1) ≤ A forN/2 < j ≤ N . Similarly, using the same bound 3/4 ≤ c < 1 and the fact that η(1 − c)c(N−1)/NA ≥ 2 we get 3 16ηA ≤ Wj(1) ≤ ηA for N/2 < j ≤ N . In particular, for all 1 ≤ j ≤ N , we have that min{η,1}
10 A ≤Wj(1) ≤ max{η, 1}A. We prove the following lemma by induction:
Lemma 17. For each t ≥ 1, the real numbers W1(t), . . . ,WN (t) all have the same sign and this sign alternates for each integer t. Moreover, there are real numbers 2 ≤ B(t) < C(t) for t ≥ 1 such that for 1 ≤ j ≤ N , B(t) ≤ |Wj(t)| ≤ C(t) and ηB(t)2N−1 ≥ 20C(t).
Proof. First we claim that we may take B(1) = min{η,1}10 A and C(1) = max{η, 1}A. We have shown above that B(1) ≤ Wj(1) ≤ C(1) for all j. Next we establish that ηB(1)2N−1 ≥ 20C(1). If η ≤ 1, then
ηB(1)2N−1 = η2N · (A/10)2N−1 ≥ 20A = 20C(1), where the inequality follows from A ≥ (
20·102N−1 η2N
)1/(2N−2) by definition of A. If η ≥ 1, then
ηB(1)2N−1 = η(A/10)2N−1 ≥ 20ηA = 20C(1), where the inequality follows from A ≥ 2000 ≥ ( 20 · 102N−1 )1/(2N−2) by definition of A.
Now, suppose the statement of Lemma 17 holds for some t. Suppose first that Wj(t) are all positive for 1 ≤ j ≤ N . Then for all j, as B(t) ≥ 2, and ηB(t)2N−1 ≥ 20C(t),
Wj(t+ 1) ≤ C(t)− η · (B(t)N − 1) ·B(t)N−1
≤ C(t)− η 2 B(t)2N−1
≤ −9C(t), which establishes that Wj(t+ 1) is negative for all j. Moreover,
Wj(t+ 1) ≥ −η(C(t)N − 1) · C(t)N−1
≥ −ηC(t)2N−1. Now set B(t+ 1) = 9C(t) and C(t+ 1) = ηC(t)2N−1. Since N ≥ 2, we have that
ηB(t+ 1)2N−1 = η(9C(t))2N−1 ≥ η93C(t)2N−1 > 20ηC(t)2N−1 = 20C(t+ 1). The case that all Wj(t) are negative for 1 ≤ j ≤ N is nearly identical, with the same values for B(t + 1), C(t + 1) in terms of B(t), C(t), except all Wj(t + 1) will be positive. This establishes the inductive step and completes the proof of Lemma 17.
By Lemma 17, we have that for all t ≥ 1, LN (W1(t), . . . ,WN (t)) = 12 (W1:N (t)− 1) 2 ≥ 12 (2 N − 1)2 > 0, thus completing the proof of Claim 4 for the case where all dimensions are equal to 1.
For the general case where d0 = d1 = · · · = dN = d for some d ≥ 1, we set Φ = Id, and given c, η, we setWj(0) to be the d×d diagonal matrix where all diagonal entries except the first one are equal to 1, and where the first diagonal entry is given by Equation (51), whereA is given by Equation (50). It is easily verified that all entries of Wj(t), 1 ≤ j ≤ N , except for the first diagonal element of each matrix, will remain constant for all t ≥ 0, and that the first diagonal elements evolve exactly as in the 1-dimensional case presented above. Therefore the loss in the d-dimensional case is equal to the loss in the 1-dimensional case, which is always greater than some positive constant.
We remark that the proof of Claim 4 establishes that the loss `(t) := LN (W1(t), . . . ,WN (t)) grows at least exponentially in t for the chosen initialization. Such behavior, in which gradients and weights explode, indeed takes place in deep learning practice if initialization is not chosen with care.

heading: D.7 PROOF OF CLAIM 5
text: Proof. We will show that a target matrix Φ ∈ Rd×d which is symmetric with at least one negative eigenvalue, along with identity initialization (Wj(0) = Id, ∀j ∈ {1, . . . , N}), satisfy the conditions of the claim. First, note that non-stationarity of initialization is met, as for any 1 ≤ j ≤ N ,
∂LN (W1(0), . . . ,WN (0))
∂Wj(0) = Wj+1:N (0)
>(W1:N (0)− Φ)W1:j−1(0) = Id − Φ 6= 0,
where the last inequality follows since Φ has a negative eigenvalue. To analyze gradient descent we use the following result, which was established in Bartlett et al. (2018):
Lemma 18 (Bartlett et al. (2018), Lemma 6). If W1(0), . . . ,WN (0) are all initialized to identity, Φ is symmetric, Φ = UDU> is a diagonalization of Φ, and gradient descent is performed with any learning rate, then for each t ≥ 0 there is a diagonal matrix D̂(t) such that Wj(t) = UD̂(t)U> for each 1 ≤ j ≤ N .
By Lemma 18, for any choice of learning rate η, the end-to-end matrix at time t is given by W1:N (t) = UD̂(t)
NU>. As long as some diagonal element of D is negative, say equal to −λ < 0, then
`(t) = LN (W1(t), . . . ,WN (t)) = 1
2 ‖W1:N (t)− Φ‖2F =
1 2 ‖D̂(t)L −D‖2F ≥ 1 2 λ2 > 0.
E IMPLEMENTATION DETAILS
Below we provide implementation details omitted from our experimental report (Section 4).
The platform used for running the experiments is PyTorch (Paszke et al., 2017). For compliance with our analysis, we applied PCA whitening to the numeric regression dataset from UCI Machine Learning Repository. That is, all instances in the dataset were preprocessed by an affine operator that ensured zero mean and identity covariance matrix. Subsequently, we rescaled labels such that the uncentered cross-covariance matrix Λyx (see Section 2) has unit Frobenius norm (this has no effect on optimization other than calibrating learning rate and standard deviation of initialization to their conventional ranges). With the training objective taking the form of Equation (1), we then computed c — the global optimum — in accordance with the formula derived in Appendix A. In our experiments with linear neural networks, balanced initialization was implemented with the assignment written in step (iii) of Procedure 1. In the non-linear network experiment, we added, for each j ∈ {1, . . . , N − 1}, a random orthogonal matrix to the right of Wj , and its transpose to the left of Wj+1 — this assignment maintains the properties required from balanced initialization (see Footnote 7). During all experiments, whenever we applied grid search over learning rate, values between 10−4 and 1 (in regular logarithmic intervals) were tried.

Review summaries:
The paper provides the convergence analysis at linear rate of gradient descent to global minima for deep linear neural networks – the fully-connected neural networks with linear activation with l2 loss. The convergence only works under two necessary assumptions on initialization: “weight matrices at initialization are approximately balanced” and “the initial loss is smaller than the loss of any rank-deficient solution”. The result of this work is similar to that of Barlett et al. 2018, but the difference is that, in Barlett et al. 2018, they consider a subclass of linear neural networks (linear residual networks – a subclass of linear neural networks which the input, output and all hidden layers are the same dimensions). 

This paper continues the recent line of study on the convergence behaviour of gradient descent for deep linear neural networks. For more than 2 layers, the optimization problem is nonconvex and it is known strict saddle points exist. The main contribution is a relaxation of the balancedness condition in previous work by Arora et al and a new deficiency margin condition, which together allowed the authors to prove that gradient descent will converge to an epsilon solution in at most O(log 1/epsilon) iterations (under reasonable assumptions on step size and other parameters). Examples on how to satisfy the two conditions are discussed. Overall, the obtained results appear to be a solid contribution beyond our current understanding of deep linear neural networks, and potentially may be helpful towards our understanding of deep nonlinear neural networks.