Title: DEPTH CREATES NO MORE SPURIOUS LOCAL MINIMA IN LINEAR NETWORKS

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.

1. INTRODUCTION:

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 : R m×n → R.

For any k ≥ 2, let L k (M 1 , . . . , M k ) = f (M k • • • M 1 ) where M i ∈ R di×di-1 for 1 ≤ i ≤ k with d k = m and d 0 = n. Let d = min 0≤i≤k d i . Define L 2 (A, B) = f (AB) for A ∈ R m×d , B ∈ R d×n .

Then L k has no spurious local minima iff L 2 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 L 2 , 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 any

X ∈ R d0×n , Y ∈ R d k ×n , let L(M 1 , . . . , M k ) = M k • • • M 1 X -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.

M 1k1 • • • M 11 + . . . + M sks • • • M s1 ), where M ij ∈ R di,j ×di,j-1 with d i,ki = m and d i,0 = n. For 1 ≤ i ≤ s, let b i = min j d i,j denote the bottleneck size of each tower i. Write b = i b i .

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 ∈ R m×b , B ∈ R b×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.

1.1. RELATED WORK:

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.

2. PRELIMINARIES:

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 R m×n all the matrices with m rows and n columns. For

1 ≤ i ≤ k, let M i ∈ R di×di-1 . For i ≥ j, denote by M i • • • M j the matrix product of M i •M i-1 . . .•M j . A (deep) linear network with parameters M 1 , • • • , M k is defined as Φ(x) = M k • • • M 1 x.

We call k the depth of the network and d 0 , d k the input and the output dimensions, respectively. Define d = min 0≤i≤k d i be the narrowest width. We say a network has a bottleneck if both d 0 > d and d k > 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 ∈ R d0 , and the label y in some arbitrary set, we wish to minimize the total loss:

L(M 1 , • • • , M k ; D) = (x,y)∈D f y (Φ(x)) = (x,y)∈D f y (M k • • • M 1 x) . Define f (A) = (x,y)∈D f y (Ax). Then L(M 1 , • • • , M k ; D) = f (M k • • • M 1 ).

If f y 's are all convex differentiable functions1 , then clearly f is convex differentiable too. Below we omit D and consider the loss function L : R d1×d0 × . .

. × R d k ×d k-1 → R where L(M 1 , • • • , M k ) = f (M k • • • M 1 ) for some f : R d k ×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, M 1 , . . . , M k is a local minimum of L if there ex- ists an open ball B, in Frobenius norm, centered at M 1 , . . . , M k such that L(M 1 , . . . , M k ) ≤ 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(M 1 , • • • , M k ) = f (M k • • • M 1 ), then M 1 , • • • , M k satisfy that ∂L ∂Mi = (M k • • • M i+1 ) T f (M k • • • M 1 )(M i-1 • • • M 1 ) T = 0

We need the following theorem from Laurent & von Brecht (2018) :

Theorem 3. Let L k (M 1 , . . . , M k ) = f (M k • • • M 1 ) where f : R d k ×d0 → R is a convex differen- tiable function. If there is no bottleneck, i.e. d 0 or d k = min 0≤i≤k d i , then any local minimum of L k is a global minimum of f .

3. PROOFS:

With the above preparation, we will now prove Theorem 1. If the network we consider has no bottleneck, i.e. d = d k or d = d 0 , then Theorem 3 immediately implies that all the local minima for L k are global minima of f so the statement is vacuously true. Below we consider the case when d = d j for some 0 < j < k.

Let A = M k • • • M j+1 and B = M j • • • M 1 .

The following is the main technical claim of the paper. Lemma 1. If M 1 , . . . , M k 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 L 2 has spurious local minima, then L k has too. Since d j = min 0≤i≤k d i , for any A ∈ R d k ×dj and B ∈ R dj ×d0 , we can easily construct matrices

M i ∈ R di×di-1 for 1 ≤ i ≤ k such that M k • • • M j+1 = A, and M j • • • M 1 = B. If A, B is a spurious local minimum of L 2 , then clearly M 1 , • • • , M k is a spurious local minimum of L k .

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

M 1 , • • • , M k is a local minimum of L k . Then by Lemma 1, either f (AB) = 0 or A, B both have rank d. If f (AB) = 0, then AB = M k • • • M 1 is a global minimum of f because f is convex. Hence M 1 , . . . , M k is a global minimum of L k 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 M k (resp. M 1 ).

If A = M k • • • M j+1 has rank d, then A 1 = M k-1 • • • M j+1 ∈ R d k-1 ×d has rank d too because d ≤ d k-1 . Then for any D ∈ R d k ×d , there exists D 1 ∈ R d k ×d k-1 such that D 1 A 1 = D. Hence (M k + D 1 )A 1 = M k A 1 + D 1 A 1 = A+D.

This implies any local perturbation to A can be done through local perturbation to M 1 . More precisely, there exists a constant c > 0, such that for any D ∈ R d k ×d , there exists

D 1 ∈ R d k ×d k-1 with D 1 ≤ c D and D 1 A 1 = D. Same is true for B. This implies that if L k (M 1 , . . . , M k ) is minimum in an open ball of radius δ centered at M 1 , . . . , M k , then L 2 (A, B) is minimum in an open ball of radius δ/c centered at A, B. Hence if M 1 , . . . , M k is a local minimum of L k , then A, B is a local minimum of L 2 . If L 2 has no spurious local minima, A, B, hence M 1 , . . . , M k , is a global minimum.

In the above proof, we actually showed that if M 1 , . . . , M k is a spurious local minimum of L k , then

A = M k • • • M j+1 , B = M j • • • M 1 is a spurious local minimum of L 2 .

That is, every spurious local minima of L k can be directly mapped to a spurious local minimum of L 2 , 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 = M 2 ∈ R d2×d1 and B = M 1 ∈ R d1×d0 with d 1 < min(d 0 , d 2 ). If A, B is a spurious local minimum of L 2 , then f (AB) = 0 because otherwise they would have been a global minimum of f . By Lemma 1, we have that both A, B are of rank d 1 , i.e. they both have full rank because d 1 < d 0 , d 2 .

To prove Lemma 1, we first observe that

Lemma 2. If M 1 , . . . , M k is a local minimum of L k , then ∂L2 ∂A (A, B) = 0, ∂L2 ∂B (A, B) = 0. Proof. Define g B (X) = L 2 (X, B) = f (XB). Clearly g B is convex and differentiable too. Let L B (M j+1 , . . . , M k ) = g B (M k • • • M j+1 ). If M 1 , . . . , M k is a local minimum of L k , then M j+1 , .

. . , M k must be a local minimum of L B . In addition, d j = min 0≤i≤k d i = min j≤i≤k d i , so there is no bottleneck in M j+1 , . . . , M k . We apply Theorem 3 to get that

A = M k • • • M j+1 is a global minimum of g B , 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) = 0, then A, B must be of rank d. Below we assume f (AB) = 0. We will show that A has rank d. For B, we can apply the same argument to g(X) = f (X T ).

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 b i .

Suppose that we have a spurious local minimum M

= (M 11 , • • • , M 1k1 , • • • , M s1 , • • • , M sks ).

Similar to the proof of Theorem 1, we can break each tower i as A i ∈ R m×bi , B i ∈ R bi×n at the bottleneck layer. Write M = A i B i . Similarly we can show that either f (M ) = 0 or all the A i , B i 's have full rank. Since M is a spurious local minimum, it must be the second case, i.e. all the 

4. CONCLUSION:

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.

:

In 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).

Figures and Tables:

i , B i have full rank. Now let A = (A 1 , • • • , A s ) and B = Then A ∈ R m×b , B ∈ R b×n where b = b 1 + • • • + b s . By the same argument in the proof of Theorem 1, any perturbation of A, B can be done through perturbation of M, hence A, 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 .

Peer review (iclr2020):
The paper shows an interesting result: deep linear NN has introduced no more spurious local minima than two layer NN and provides an intuitive and short proof for the results, which improve and generalize the previous results under milder assumptions. Overall, the paper is well written and clear in comparison and explanation. The weakness is that the main theoretical contribution seems to be merely Lemma 1, and all other theorems are a direct corollary. Also, it would be of great interest to see concrete results on non-linear neural networks, since that is exactly what is used in common practice.