Year: 2019

Abstract:
We show that for any convex differentiable loss, a deep linear network has no spurious local minima as long as it is true for the two layer case. This reduction greatly simplifies the study on the existence of spurious local minima in deep linear networks. When applied to the quadratic loss, our result immediately implies the powerful result by Kawaguchi (2016). Further, with the recent work by Zhou & Liang (2018), we can remove all the assumptions in (Kawaguchi, 2016). This property holds for more general “multi-tower” linear networks too. Our proof builds on the work in (Laurent & von Brecht, 2018) and develops a new perturbation argument to show that any spurious local minimum must have full rank, a structural property which can be useful more generally.

heading: 1 INTRODUCTION
text: One major mystery in deep learning is that deep neural networks do not seem to suffer from spurious local minima. Understanding this mystery has become one of the most important topics in the machine learning theory. This problem turns to be quite challenging. Even for the subcase of the deep linear network, much still remains unknown despite a long line of studies on this subject.
In this paper, we prove a useful structural property about the deep linear networks. We show that for any convex differentiable loss function, any spurious local minima in a deep linear network should already be present in a two layer linear network. Hence, depth does not create more spurious local minima in linear networks. This reduction greatly simplifies the study about the existence of spurious local minima in deep linear networks. When applied to the quadratic loss, it leads to the first unconditional proof that there is no local minima in deep linear networks.
Baldi & Hornik (1989) started the investigation on the existence of spurious local minima in linear networks. They showed that, under mild assumptions, for quadratic loss, two layer linear networks do not have spurious local minima. They also conjectured it is true for deep linear networks. This conjecture is only proved recently by Kawaguchi (2016). For the special case of linear residual networks, Hardt & Ma (2017) showed that there are no spurious local minima through a simpler argument.
While most existing work have been on quadratic loss functions, Laurent & von Brecht (2018) showed a surprisingly general result for any convex differentiable loss. In (Laurent & von Brecht, 2018), the authors consider the special linear networks which have no bottlenecks, i.e. when the narrowest layer is on the either end. They showed that for any convex differential loss function, there is no spurious local minima in such networks. In addition to its generality, the proof in (Laurent & von Brecht, 2018) is quite intuitive through a novel perturbation argument. However, their special cases excludes networks with bottleneck layers, commonly used in the practice and studied in the literature (Baldi & Hornik, 1989; Kawaguchi, 2016).
We build on the work in (Laurent & von Brecht, 2018) and further develop the technique to show that for general deep linear networks, whether there are spurious local minima is reduced to the two layer case. Theorem 1. Given any convex differentiable function f : Rm×n → R. For any k ≥ 2, let Lk(M1, . . . ,Mk) = f(Mk · · ·M1) where Mi ∈ Rdi×di−1 for 1 ≤ i ≤ k with dk = m and d0 = n. Let d = min0≤i≤k di. Define L2(A,B) = f(AB) for A ∈ Rm×d, B ∈ Rd×n. Then Lk has no spurious local minima iff L2 has no spurious local minima.
We emphasize that in the above theorem, f depends on both the data and the loss function. Hence the reduction is instance specific and does not depend on the global property of a family of loss functions.
To prove Theorem 1, we show a non-degeneracy property of local minima, namely, any spurious local minimum must have rank same as the width of the bottleneck. This property can be useful for the two layer case too – it implies that each layer in a spurious local minimum cannot be rankdeficient, hence covering subcases which may otherwise require onerous analysis (Baldi & Hornik, 1989; Zhou & Liang, 2018). Theorem 2. With the same notation as in Theorem 1, if A,B is a spurious local minimum of L2, then both A,B must have full rank.
As an application of Theorem 1, for quadratic loss, Theorem 1, together with (Baldi & Hornik, 1989), immediately implies the main result in (Kawaguchi, 2016). We can further remove all the assumptions needed in (Baldi & Hornik, 1989; Kawaguchi, 2016), using the recent result by Zhou & Liang (2018) (Theorem 2(1)), hence providing the first unconditional proof of the non-existence of spurious local minima in deep linear networks for quadratic loss functions. Below ‖ · ‖ denotes the Frobenius norm. Corollary 1. For anyX ∈ Rd0×n, Y ∈ Rdk×n, let L(M1, . . . ,Mk) = ‖Mk · · ·M1X−Y ‖2 . Then L has no spurious local minima.
Theorem 1 can be further generalized to “multi-tower” linear networks. Define a multi-tower linear network as the sum of multiple deep linear networks (towers), i.e. M1k1 · · ·M11 + . . . + Msks · · ·Ms1), where Mij ∈ Rdi,j×di,j−1 with di,ki = m and di,0 = n. For 1 ≤ i ≤ s, let bi = minj di,j denote the bottleneck size of each tower i. Write b = ∑ i bi. Corollary 2. For any differentiable convex loss f , a multi-tower linear network has no spurious local minima iff the linear network AB, where A ∈ Rm×b, B ∈ Rb×n, has no spurious local minima. Moreover, if b ≥ m,n, there is no spurious local minima in this network.
There are two main technical ideas in our proof. First, we show a reduction of any local minimum of the multi-layer network to a critical point of a two-layer network. Secondly, we generalize the local perturbation argument in (Laurent & von Brecht, 2018) to weaker critical conditions. Besides the conceptual importance of our results, these technical contributions might be useful for understanding deep networks too.

heading: 1.1 RELATED WORK
text: In Baldi & Hornik (1989), it is shown that, under mild assumptions on data, two layer linear network with quadratic loss has no spurious local minima. This is probably the first positive result on this long line of investigation. Kawaguchi (2016) showed that it holds for deep linear network too. The tour de force proof in (Kawaguchi, 2016) works by examining the Hessian using powerful tools from the matrix theory. There have been much subsequent work to simplify and generalize the result. For example, Lu & Kawaguchi (2017) came up with a different argument. Yun et al. (2018; 2019) showed simpler arguments for special cases and considered more general non-linear networks. Hardt & Ma (2017) showed that under certain assumptions, there might not even be stationary point in the deep linear residual network. Venturi et al. (2018) defined a notion of spurious valleys and showed that for quadratic losses, there is no spurious valley in deep linear networks. Venturi et al. (2018) was able to remove all the assumption in (Baldi & Hornik, 1989) under this weaker notion. The mild assumption in Baldi & Hornik (1989), which was also needed in Kawaguchi’s proof, was removed by Zhou & Liang (2018), which leads to our Corollary 1.
Laurent & von Brecht (2018) considers the special case of linear networks with the narrowest layer on the either end. It uses a novel perturbation argument to show that for any convex differentiable loss, there is no spurious local minimum in such network. However, the special case considered in (Laurent & von Brecht, 2018) excludes networks through low rank approximation such as autoencoders. But it is really the intuitive yet powerful result in (Laurent & von Brecht, 2018) that motivated this work.
There have been recent studies on the gradient descent convergence on the deep linear networks (Arora et al., 2018; Bartlett et al., 2018; Arora et al., 2019). It has been shown by Arora
et al. (2018) that, under certain conditions, increasing the depth of linear networks can speed up the convergence, which is another positive property of deep linear networks.
There have been much work (Soltanolkotabi et al., 2018; Li & Liang, 2018; Allen-Zhu et al., 2018a;b; Du et al., 2018a; Zou et al., 2018; Du et al., 2018b) recently on studying the optimization landscape and convergence of non-linear networks. They focus mostly on shallow networks with over-parameterized wide layers.

heading: 2 PRELIMINARIES
text: We define notations used through the paper. We state some simple facts and the main theorem from Laurent & von Brecht (2018) which we need in our proof.
Deep linear networks. Denote by Rm×n all the matrices with m rows and n columns. For 1 ≤ i ≤ k, letMi ∈ Rdi×di−1 . For i ≥ j, denote byMi · · ·Mj the matrix product ofMi ·Mi−1 . . . ·Mj . A (deep) linear network with parameters M1, · · · ,Mk is defined as Φ(x) = Mk · · ·M1x. We call k the depth of the network and d0, dk the input and the output dimensions, respectively. Define d = min0≤i≤k di be the narrowest width. We say a network has a bottleneck if both d0 > d and dk > d. A multi-tower linear network is defined as the sum of multiple linear networks (towers) with the same input and output dimensions.
Empirical loss. Given training data D which consist of examples of pairs of x, y where the input feature vector x ∈ Rd0 , and the label y in some arbitrary set, we wish to minimize the total loss:
L(M1, · · · ,Mk;D) = ∑
(x,y)∈D
fy(Φ(x)) = ∑
(x,y)∈D
fy(Mk · · ·M1x) .
Define f(A) = ∑
(x,y)∈D fy(Ax). Then L(M1, · · · ,Mk;D) = f(Mk · · ·M1). If fy’s are all convex differentiable functions1, then clearly f is convex differentiable too. Below we omit D and consider the loss function L : Rd1×d0 × . . . × Rdk×dk−1 → R where L(M1, · · · ,Mk) = f(Mk · · ·M1) for some f : Rdk×d0 → R.
Derivative. Denote by ∂L∂M the matrix form of the partial derivative of L with respect to M . If L has only one variable M , we write L′ = ∂L∂M . For simplicity, we sometimes abuse the notation by using the same symbol for the variable and the value and omit the value. If L(X,Y ) = f(XY ), by the chain rule, ∂L∂X = f ′(XY )Y T and ∂L∂Y = X T f ′(XY ).
Local minimum. For any loss function L, M1, . . . ,Mk is a local minimum of L if there exists an open ball B, in Frobenius norm, centered at M1, . . . ,Mk such that L(M1, . . . ,Mk) ≤ L(M ′1, · · · ,M ′k) for any (M ′1, · · · ,M ′k) ∈ B. A local minimum is called spurious if it is not a global minimum. If L is differentiable, then any local minimum is a critical point of L. In particular, if L(M1, · · · ,Mk) = f(Mk · · ·M1), then M1, · · · ,Mk satisfy that ∂L∂Mi = (Mk · · ·Mi+1)T f ′(Mk · · ·M1)(Mi−1 · · ·M1)T = 0
We need the following theorem from Laurent & von Brecht (2018): Theorem 3. Let Lk(M1, . . . ,Mk) = f(Mk · · ·M1) where f : Rdk×d0 → R is a convex differentiable function. If there is no bottleneck, i.e. d0 or dk = min0≤i≤k di, then any local minimum of Lk is a global minimum of f .

heading: 3 PROOFS
text: With the above preparation, we will now prove Theorem 1. If the network we consider has no bottleneck, i.e. d = dk or d = d0, then Theorem 3 immediately implies that all the local minima
1In practice, fy’s are typically convex. They are usually differentiable, and if not, can be smoothly approximated. For example the hinge loss can be approximated by the modified Huber loss (Zhang, 2004).
for Lk are global minima of f so the statement is vacuously true. Below we consider the case when d = dj for some 0 < j < k. Let A = Mk · · ·Mj+1 and B = Mj · · ·M1. The following is the main technical claim of the paper.
Lemma 1. If M1, . . . ,Mk is a local minimum, then either f ′(AB) = 0 or A,B both have rank d.
We first show that the above lemma implies Theorem 1.
Proof. (Theorem 1) If L2 has spurious local minima, then Lk has too. Since dj = min0≤i≤k di, for any A ∈ Rdk×dj and B ∈ Rdj×d0 , we can easily construct matrices Mi ∈ Rdi×di−1 for 1 ≤ i ≤ k such that Mk · · ·Mj+1 = A, and Mj · · ·M1 = B. If A,B is a spurious local minimum of L2, then clearly M1, · · · ,Mk is a spurious local minimum of Lk. The other direction is implied by Lemma 1. This implication has been used before multiple times by Kawaguchi (2016); Lu & Kawaguchi (2017); Yun et al. (2018). Here we include the easy proof for completeness. Suppose that M1, · · · ,Mk is a local minimum of Lk. Then by Lemma 1, either f ′(AB) = 0 orA,B both have rank d. If f ′(AB) = 0, thenAB = Mk · · ·M1 is a global minimum of f because f is convex. Hence M1, . . . ,Mk is a global minimum of Lk too.
In the other case, A and B both have full rank d. We show that any local perturbation to A (resp. B) can be performed by local perturbation to Mk (resp. M1). If A = Mk · · ·Mj+1 has rank d, then A1 = Mk−1 · · ·Mj+1 ∈ Rdk−1×d has rank d too because d ≤ dk−1. Then for any D ∈ Rdk×d, there exists D1 ∈ Rdk×dk−1 such that D1A1 = D. Hence (Mk + D1)A1 = MkA1 + D1A1 = A+D. This implies any local perturbation toA can be done through local perturbation toM1. More precisely, there exists a constant c > 0, such that for any D ∈ Rdk×d, there exists D1 ∈ Rdk×dk−1 with ‖D1‖ ≤ c‖D‖ and D1A1 = D. Same is true for B. This implies that if Lk(M1, . . . ,Mk) is minimum in an open ball of radius δ centered at M1, . . . ,Mk, then L2(A,B) is minimum in an open ball of radius δ/c centered atA,B. Hence ifM1, . . . ,Mk is a local minimum of Lk, thenA,B is a local minimum of L2. If L2 has no spurious local minima, A,B, hence M1, . . . ,Mk, is a global minimum.
In the above proof, we actually showed that if M1, . . . ,Mk is a spurious local minimum of Lk, then A = Mk · · ·Mj+1, B = Mj · · ·M1 is a spurious local minimum of L2. That is, every spurious local minima of Lk can be directly mapped to a spurious local minimum of L2, hence the title of the paper.
Lemma 1 directly implies Theorem 2.
Proof. (Theorem 2) Consider the case of k = 2 and j = 1. Then we have A = M2 ∈ Rd2×d1 and B = M1 ∈ Rd1×d0 with d1 < min(d0, d2). If A,B is a spurious local minimum of L2, then f ′(AB) 6= 0 because otherwise they would have been a global minimum of f . By Lemma 1, we have that both A,B are of rank d1, i.e. they both have full rank because d1 < d0, d2.
To prove Lemma 1, we first observe that
Lemma 2. If M1, . . . ,Mk is a local minimum of Lk, then ∂L2∂A (A,B) = 0, ∂L2 ∂B (A,B) = 0.
Proof. Define gB(X) = L2(X,B) = f(XB). Clearly gB is convex and differentiable too. Let L̃B(Mj+1, . . . ,Mk) = gB(Mk · · ·Mj+1). If M1, . . . ,Mk is a local minimum of Lk, then Mj+1, . . . ,Mk must be a local minimum of L̃B . In addition, dj = min0≤i≤k di = minj≤i≤k di, so there is no bottleneck in Mj+1, . . . ,Mk. We apply Theorem 3 to get that A = Mk · · ·Mj+1 is a global minimum of gB , hence ∂L2∂A (A,B) = 0. Similarly ∂L2 ∂B (A,B) = 0.
Now we prove the key technical claim of Lemma 1.
Proof. (Lemma 1)
We just need to show that if f ′(AB) 6= 0, thenA,B must be of rank d. Below we assume f ′(AB) 6= 0. We will show that A has rank d. For B, we can apply the same argument to g(X) = f(XT ).
Let r denote the rank of A. We will derive contradiction by assuming r < d. We first use an argument by Laurent & von Brecht (2018) to construct a family of local minima. Since A = Mk · · ·Mj+1 is of rank r < d, for any 2 ≤ i ≤ j + 1, Mk · · ·Mi has rank at most r. Since r < d ≤ di−1, there exists nonzero wi−1 ∈ Rdi−1 such that Mk · · ·Miwi−1 = 0. Then for any vi−1 ∈ Rdi−2 , we have
Mk · · ·Mi(Mi−1 + wi−1vTi−1) = Mk · · ·Mi−1 .
Now for any v1, v2, · · · , vj where vi ∈ Rdi−1 , we claim that
Mk · · ·Mj+1(Mj + wjvTj ) · · · (M1 + w1vT1 ) = Mk · · ·M1 . (1)
This can be shown inductively for i = j, · · · , 1.
Mk · · ·Mj+1(Mj + wjvTj ) · · · (Mi + wivTi ) = Mk · · ·Mi
Since M = (M1, . . . ,Mk) is a local minimum, it is the minimum in an open neighborhood of M . If we set ‖vi‖’s small enough so that M̃ = (M1 + w1vT1 , · · · ,Mj + wjvTJ ,Mj+1, · · · ,Mk) is in a smaller neighborhood, then M̃ is a local minimum too since Lk(M̃) = Lk(M). See Claim 1 in (Laurent & von Brecht, 2018) for a rigorous proof.
Let B̃ = M̃j · · · M̃1. Then by Lemma 2, ∂L2∂A (A, B̃) = 0, i.e ∂f(AB) ∂A (A, B̃) = f ′(AB̃)B̃T = 0. Since AB̃ = AB, we have that for any M̃1, . . . , M̃j constructed above,
f ′(AB)B̃T = 0 . (2)
For any matrix M ∈ Rm1×m2 , denote by M ` ∈ Rm2 the `-th row vector of M , and by R(M) all the row vectors of M . Consider the linear subspace
V = {v ∈ Rd0 | f ′(AB)v = 0 } .
Then (2) implies that R(B̃) ⊆ V . We now show that we can choose vi’s for 1 ≤ i ≤ j, such that B̃ = M̃j · · · M̃1 contains a row vector which is not in V to reach a contradiction. Let i∗ = min{i |R(Mi · · ·M1) ⊆ V }. If i∗ = 1, we choose a sufficiently small non-zero vector v1 /∈ V . This can be done by our assumption that f ′(AB) 6= 0. Set M̃1 = M1 + w1vT1 . Since w1 6= 0, there exists ` such that w1` 6= 0. Then M̃ `1 = M `1 + w1`v1. By M `1 ∈ V, v1 /∈ V,w1` 6= 0, we have M̃ `1 /∈ V since V is a linear subspace. Now assuming i∗ > 1. Suppose that we have constructed M̃i, . . . , M̃1, for some i ≥ i∗ − 1 ≥ 1, such that R(M̃i · · · M̃1) * V . We show the construction for i+ 1. If R(Mi+1M̃i · · · M̃1) * V , then we can simply set M̃i+1 = Mi+1. Assume below that R(Mi+1M̃i · · · M̃1) ⊆ V . By inductive hypothesis R(M̃i · · · M̃1) * V , thus there exists say the `-th row vector v of M̃i · · · M̃1 not in V . Set vi+1 as the `-th basis vector in Rdi so that vTi+1M̃i · · · M̃1 = vT . Now let M̃i+1 = Mi+1 + wi+1vTi+1. Then
M̃i+1M̃i · · · M̃1 = Mi+1M̃i · · · M̃1 + wi+1vTi+1M̃i · · · M̃1 = Mi+1M̃i · · · M̃1 + wi+1vT .
Since R(Mi+1M̃i · · · M̃1) ⊆ V but v /∈ V and wi+1 6= 0, by the same argument as for i∗ = 1, there must exist a row vector in M̃i+1 · · · M̃1 which is not in V . We have inductively constructed B̃ = M̃j · · · M̃1 such that R(B̃) * V , contradicting to (2). Hence A must have rank d. This concludes the proof.
Corollary 1 immediately follows from Theorem 1 and Theorem 2(1) in (Zhou & Liang, 2018). In the following, we prove Corollary 2.
Proof. (Corollary 2) If some tower has no bottleneck, we can fix all the parameters but this tower, we can then apply Theorem 1 to show that any local minimum is a global minimum. Hence the statement holds. Below we assume that each tower has a bottleneck with width bi.
Suppose that we have a spurious local minimum M = (M11, · · · ,M1k1 , · · · ,Ms1, · · · ,Msks). Similar to the proof of Theorem 1, we can break each tower i as Ai ∈ Rm×bi , Bi ∈ Rbi×n at the bottleneck layer. Write M = ∑ AiBi. Similarly we can show that either f ′(M) = 0 or all the Ai, Bi’s have full rank. SinceM is a spurious local minimum, it must be the second case, i.e. all the
Ai, Bi have full rank. Now let A = (A1, · · · , As) and B = B1... Bs . Then A ∈ Rm×b, B ∈ Rb×n where b = b1 + · · · + bs. By the same argument in the proof of Theorem 1, any perturbation of A,B can be done through perturbation ofM, henceA,B is a spurious local minimum for the single tower two layer network AB. If b ≥ m,n, then Theorem 3 implies that any local minimum is a global minimum of f .

heading: 4 CONCLUSION
text: We have shown a non-degeneracy property of local minima in deep linear networks for general convex differentiable loss. This property allows us to reduce the existence of spurious local minima in a deep (with depth ≥ 3) linear network to the two layer linear network, and, for two layer networks, to simplify analysis by removing the rank-deficient case. We show the application to quadratic loss functions and the generalization to multi-tower deep linear networks. Our proof uses a novel perturbation argument and does not require any heavy mathematical machinery.
It would be interesting to study when there is no spurious local minima beyond the quadratic loss. By our result, we only need to consider the two layer case. Another interesting question is whether similar phenomenon exists for non-linear networks.

Review summaries:
The motivation of this paper is training deep neural network seems to not suffer from local minima, and it tries to explain this phenomenon by showing that all local minima of deep neural network is global minima. The paper shows that for any convex differentiable loss function, a deep linear neural network has no so called spurious local minima, which to be specific, are local minima that are not global minima, as long as it is true for two-layer Neural Network. The motivation is that combining with existing result that no spurious local minima exists for quadratic loss in two-layer Neural Network, this relation connecting between two-layer and deeper linear neural network immediately implies an existing result that all local minima are global minima, removing all assumptions. The result also holds for general “multi-tower” linear networks.