Depth Creates No Bad Local Minima
Haihao Lu Kenji Kawaguchi



[NO \title GIVEN]
    [NO \author GIVEN]
    December 30, 2023
======================




  In deep learning, depth, as well as nonlinearity, create non-convex loss surfaces. Then, does depth alone create bad local minima? In this paper, we prove that without nonlinearity, depth alone does not create bad local minima, although it induces non-convex loss surface. Using this  insight, we greatly simplify a recently proposed proof to show that all of the local minima of feedforward deep linear neural networks are global minima. Our theoretical results generalize previous results with fewer assumptions, and this analysis provides a method to show similar results beyond square loss in deep linear models.




§ INTRODUCTION

Deep learning has recently had a profound impact on
the machine learning, computer vision, and artificial intelligence
communities. In addition to its practical successes, previous studies have revealed several reasons why deep learning has been successful from the viewpoint of its model classes. An (over-)simplified explanation is the harmony of its great expressivity and big data: because of its great expressivity, deep learning can have less bias, while a large training dataset leads to less variance. The great expressivity can be seen from an aspect of representation learning as well:
whereas traditional machine learning makes use of features designed by human users or experts as a type of prior, deep learning tries to learn features from the data as well. More accurately, a key aspect of the model classes in deep learning is the generalization property; despite its great expressivity, deep learning model classes can maintain great generalization properties <cit.>. This would distinguish deep learning from other possibly too flexible methods, such as shallow neural networks with too many hidden units, and traditional kernel methods with a too powerful kernel. Therefore, the practical success of deep learning seems to be supported by the great quality of its model classes.   

However, having a great model class is not so useful if we cannot find a good model in the model class via training. Training a deep model is typically framed as non-convex optimization. Because of its non-convexity and high dimensionality, it has been unclear whether we can efficiently train a deep model. 
Note that the difficulty comes from the combination of non-convexity and high dimensionality in weight parameters. If we can reformulate the training problem into several decoupled training problems, with each having a small number of weight parameters, we can effectively train a model via non-convex optimization as theoretically shown in Bayesian optimization and global optimization literatures <cit.>. As a result of non-convexity and high-dimensionality, it was shown that training a general neural network model is NP-hard <cit.>. However, such a hardness-result in a worst case analysis  would not tightly capture what is going on in practice, as we seem to be able to efficiently train deep models in practice. 

To understand its practical success beyond worst case analysis, theoretical and practical investigations on the training of deep models have recently become an active research area <cit.>. 

 
An important property of a deep model is that the non-convexity comes from depth, as well as nonlinearity: indeed, depth by itself creates highly non-convex optimization problems. One way to see a property of the non-convexity induced by depth is the non-uniqueness owing to weight–space symmetries <cit.>: the  model represents the same function mapping from the input to the output with different distinct settings in the weight space.  Accordingly, there are many distinct globally optimal points and many distinct points with the same loss values due to weight–space symmetries, which would  result in a non-convex epigraph (i.e., non-convex function) as well as non-convex sublevel sets (i.e., non-quasiconvex function). Thus, it has been unclear whether depth by itself can create a difficult non-convex loss surface. The recent  work <cit.> indirectly showed, as a consequence of its main theoretical results, that depth does not create bad local minima of deep linear model with Frobenius norm although it creates potentially bad saddle points. 

In this paper, we directly prove that all local minima of deep linear model corresponds to local minima of shallow model. Building upon this new theoretical insight, we propose a simpler proof for one of the main results in the recent work <cit.>; all of the local minima of feedforward deep linear neural networks with Frobenius norm are global minima. The power of this proof can go beyond Frobenius norm: as long as the loss function satisfies Theorem <ref>, all local minima of deep linear model corresponds to local minimum of shallow model.      
















     


§ MAIN RESULT


To examine the effect of depth alone, we consider the following optimization problem of feedforward deep linear neural networks with the square error loss: 

    _W   L(W)=1/2W_H W_H-1⋯ W_1X-Y_F^2,


where W_i∈^d_i× d_i-1 is the weight matrix,  X∈^d_0× m is the input training data, and Y∈^d_H× m is the target training data. Let p=min_0≤ i≤ Hd_i be the index corresponding to the smallest width. Note that for any W, we have (W_H W_H-1⋯ W_1) ≤ d_p. To analyze optimization problem (<ref>), we also consider the following optimization problem with a “shallow” linear model, which is equivalent to problem (<ref>) in terms of the global minimum value: 

    _R   F(R)= RX-Y_F^2     s.t.     (R)≤ d_p,

where R∈^d_H× d_0. Note that problem (<ref>) is non-convex, unless d_p = min(d_H,d_0), whereas problem (<ref>) is non-convex, even when d_p ≥min(d_H,d_0) with H>1. In other words, deep parameterization creates a non-convex loss surface even without nonlinearity. 

Though we only consider the Frobenius loss here, the proof holds for general cases. As long as the loss function satisfies Theorem <ref>, all local minima of deep linear model corresponds to local minimum of shallow model.

Our first main result states that even though deep parameterization creates a non-convex loss surface, it does not create new bad local minima. In other words, every local minimum in problem (<ref>) corresponds to a local minimum in problem (<ref>).



 
(Depth creates no new bad local minima)
Assume that X and Y have full row rank. If W̅={W̅_1,…,W̅_H} is a local minimum of problem (<ref>), then R̅ = W̅_HW̅_H-1⋯W̅_1 achieves the value of a local minimum of problem (<ref>).
 



Therefore, we can deduce the property of the local minima in problem (<ref>) from those in problem (<ref>). Accordingly, we first analyze the local minima in problem (<ref>), and obtain the following statement.  

  
  
(No bad local minima for rank restricted shallow model)
If X has full row rank, all local minima of optimization problem (<ref>) are global minima.


  

By combining Theorems <ref> and <ref>, we conclude that every local minimum is a global minimum for feedforward deep linear networks with a square error loss.   


  
 
(No bad local minima for deep linear neural networks)
If X and Y have full row rank, then all local minima of problem (<ref>) are global minima.
 

  

Theorem <ref> generalizes one of the main results in  <cit.> with fewer assumptions. Following the theoretical work with a random matrix theory <cit.>, the recent work <cit.>  showed that under some strong assumptions, all of the local minima are global minima for a class of nonlinear deep networks.
Furthermore, the recent work <cit.> proved the following properties for a class of general deep linear networks with arbitrary depth and width: 1) the objective function is non-convex and non-concave; 
2) all of the local minima are global minima;
3) every other critical point is a saddle point; and
4) there is no saddle point with the Hessian having no negative eigenvalue for shallow networks with one hidden layer, whereas such saddle points exist for deeper networks. Theorem <ref> generalizes the second statement  with fewer assumptions; the  previous papers <cit.> assume that the data matrix YX^T(XX^T)^-1XY^T has distinct eigenvalues, whereas we do not assume that.  



§ PROOF

In this section, we provide the proofs of Theorems <ref>, <ref>, and <ref>.  




 §.§ Proof of Theorem <ref>

In order to deduce the proof of Theorem <ref>, we need some fundamental facts in linear algebra. The next two lemmas recall some basic facts of perturbation theory for singular value decomposition (SVD).


Let M and M̅ be two m× n (m≥ n) matrices with
SVDs

    B=UΣ V^T=(U_1,U_2)([ Σ_1;     Σ_2;    ;     ])([ V_1^T; V_2^T ])



    B̅=U̅Σ̅V̅^T=(U̅_1,U̅_̅2̅)([ Σ̅_1;      Σ̅_2;     ;      ])([ V̅_1^T; V̅_2^T ]),

where Σ_1=(σ_1,⋯,σ_k), Σ_2=(σ_k+1,⋯,σ_n),
Σ_1=(σ̅_1,⋯,σ̅_k), Σ_2=(σ̅_k+1,⋯,σ̅_n), U, V, U̅ and V̅ are orthogonal matrices.


  
 Continuity of Singular Value
The singular value σ_i of a matrix is a continuous map of entries of the matrix.


  

 <cit.> Continuity of Singular Space

If 
    ρ:=min{min_1≤ i≤ k,1≤ j≤ n-k|σ_i-σ̅_k+j|,min_1≤ i≤ kσ_i}>0 ,

then:

    √(sin(U_1,U̅_1)_F^2+sin(V_1,V̅_1)_F^2)≤√((M̅-M)V_1_F^2+(M̅^*-M^*)U_1_F^2)/ρ.



For a fixed matrix B, we say “matrix A is a perturbation of matrix B” if A - B_∞ is o(1), which means that the difference between A and B is much smaller than any non-zero number in matrix B.

Lemma <ref> implies that any SVD for a perturbed matrix is a perturbation of some SVD for the original matrix under full rank condition. More formally:

Let M̅ be a full-rank matrix with singular value decomposition M̅=U̅Σ̅V̅^T. M is a perturbation of M̅. Then, there exists one SVD of M, M=UΣ V^T, such that U is a perturbation of U̅, Σ is a perturbation of Σ̅ and V is a perturbation of V̅.(Notice that SVD  of a matrix may not be unique due to rotation of the eigen-space corresponding to the same eigenvalue)

Proof: With the small perturbation of matrix M̅, Lemma <ref> shows that the singular values does not change much. Thus, if M̅-M_∞ is small enough, |σ_i-σ̅_i| is also small for all i. Remember that all singular values of M̅ are positive. By letting Σ_1 contain only the singular value σ_i (which may be multiple, and hence U_1 and V_1 are the singular spaces corresponding to the singular value σ_i), we have ρ > 0 in Lemma <ref>, thus Lemma <ref> implies that the singular space of the perturbed matrix corresponding to singular value σ_i in the initial matrix does not change much. The statement of the lemma follows by combining this result for the different singular values together (i.e., consider each index i for different σ_i in the above argument).  

We say that W satisfies the rank condition, if (W_H⋯    W_1) = d_p. Any perturbation of the products of matrices is the product of the perturbed matrices, when the original matrix satisfies the rank constraint. More formally:


  
  Let R̅=W̅_HW̅_H-1⋯W̅_1 with (R̅)=d_p. Then, for any R, such that R is a perturbation of R̅ and (R)≤ d_p, there exists {W_1,W_2,…,W_H}, such that W_i is perturbation of W̅_i for all i ∈{1,…,H} and R=W_H W_H-1⋯ W_1.


  

We will prove the theorem by induction. When H=2, we can easily show that the perturbation of the  product of two matrices is the product of one matrix and the perturbation of the other matrix. When H=k>=3, we let M be the product of two specific matrices, and by induction the perturbation of the product (R) is the product of a perturbation of M and perturbations of the other H-2 matrix. And a perturbation of M is also the product of perturbations of those two specific matrices, which proves the statement when H=k.


Proof: The case with H=1 holds by setting W_1=R. We prove the lemma with H≥ 2 by induction. 

We first consider the base case where H=2 with  R̅=W̅_2W̅_1. 

Let  R̅=U̅Σ̅V̅^T be the SVD of R̅. It follows Lemma <ref> that there exists an SVD of R, R = U Σ V^T, such that U is a perturbation of U̅, Σ is a perturbation of S̅i̅g̅m̅a̅ and V is a perturbation of V̅. Because (R̅)=d_p, with a small perturbation, the positive singular values remain strictly positive, whereby, (R)≥ d_p. Together with the assumption (R)≤ d_p, we have (R)=d_p. Let S̅_2 = U̅^T W̅_2 and S̅_1 = W̅_1V̅. Note that U̅Σ̅V̅^T= R̅= W̅_2W̅_1. Hence, S̅_2 S̅_1 = Σ̅ is a diagonal matrix. Remember Σ is a perturbation of Σ̅, thus there is an S_2, which is a perturbation of S̅_2 (each row of S_2 is a scale of the corresponding row of S̅_2), such that S_2S̅_1 = Σ. Let W_2=US_2 and W_1=S̅_1 V. Then, W_1 is a perturbation of W̅_1, W_2 is a perturbation of W̅_2, and W_1W_2=R, which proves the case when H=2.
 

For the inductive step, given that the lemma holds for the case with H= k≥ 2, let us consider the case when H=k+1≥ 3 with R̅=W̅_k+1W̅_k⋯W̅_1. Let ℐ be an index set defined as ℐ = {p,p-1} if p≥ 2, ℐ = {p+2,p+1} if p=0 or p=1. We denote the i-th element of a set ℐ by ℐ_i. Then, M̅ =W̅_ℐ_2W̅_ℐ_1 exists as k+1≥ 3. Note that R̅ can be written as a product of k matrices with M̅ (for example,  R̅=W̅_H⋯W̅_I_1+1M̅W̅_I_2-1⋯W̅_1). Thus, from the inductive hypothesis, for any R, such that R is a perturbation of R̅ and (R)≤ d_p, there exists a set of desired  k matrices M and W_i for i∈{1,…,k+1}∖ℐ, such that W_i is perturbation of W̅_i for all i∈{1,…,k+1}∖ℐ,  M is perturbation of M̅,  and the product is equal to R. Meanwhile, because M̅ is either a d_p by d_p-2 matrix or a d_p + 2 by d_p matrix, we have (M̅)≤ d_p and (M) ≤ d_p, and it follows (R̅)=d_p that (M̅)=d_p. Thus, by setting R̅←M̅ and R ← M (note that d_p in R̅ = W̅_k+1W̅_k⋯W̅_1 is equal to d_p in M̅ =W̅_ℐ_2W̅_ℐ_1), we can apply the proof for the case of H=2 to conclude: there exists { W_ℐ_2, W_ℐ_1}, such that W_i is perturbation of W̅_i for all i ∈ℐ, and M= W_ℐ_2 W_ℐ_1. Combined with the above statement from the inductive hypothesis, this implies the lemma with H=k+1, whereby we finish the proof by induction. 


The next two theorems show that, for any local minimum of L(·), there is another local minimum of L(·), whose function value is the same as the original and it satisfies the rank constraint.


  
 Let W={W_1,⋯,W_H} be a local minimum of
problem (<ref>) and R≜ W_H W_H-1⋯ W_1. If W_i is not of full rank, then there
exists a W̅_̅i̅, such that W̅_i is of full rank, W̅_i is a perturbation of W_i,  W̅={W_1,⋯,W_i-1,W̅_i,W_i+1,⋯,W_H}
is a local minimum of problem (<ref>), and L(W)=L(W̅). 


  

The idea of the proof is that if we just change one weight W_i and keep all other weights, it becomes a convex least square problem. Then we are able to perturb W_i to maintain the objective value as well as the perturbation is full rank.

Proof of Theorem <ref> For notational convenience, let A=W_i-1⋯ W_1X
and B=W_i+1⋯ W_H, and let L_i(W_i)=1/2B^TW_iA-Y_F^2. Because
W is a local minimum of L, W_i is a local minimum
of L_i. Let A=U^T_1D_1V_1 and B=U^T_2D_2V_2 are
the SVDs of A and B, respectively, where D_i is a diagonal
matrix with the first s_i terms being strictly positive, i=1,2.
Minimizing L_i over W_i is a least square problem, and the
normal equation is


    BB^TW_iAA^T=BYA^T,


hence

    W_i   ∈(BB^T)^+BYA^T(AA^T)^++{ M|BB^TMAA^T=0}
        =U_2D_2^+V_2^TYV_1D_1^+U_1^T+{ U_2KU_1^T|K_1:s_2,1:s_1=0},

 
where (·)^+ is a Moore–Penrose pseudo-inverse
and K is a matrix with suitable dimension with the entries in the
top left s_2× s_1 rectangular being 0. 

Since V_2^TYV_1 is of full rank, 

    (D_2^+V_2^TYV_1D_1^+)
    ≥max{ 0,s_2+s_1-max{d_i,d_i-1}}

Thus, we can choose a proper K (which contains d_i+d_i-1-s_2-s_1
1s at proper positions with all other terms being 0s)  such that D_2^+V_2^TYV_1D_1^++K
is of full rank, whereby U_2(D_2^+V_2^TYV_1D_1^++K)U_1^T
is of full rank. Therefore, there is a full rank Ŵ_̂î that
satisfies the normal equation (<ref>).

Let W̅_i(μ)=W_i+ μ(Ŵ_i-W_i).
Then, W̅_i(μ) also satisfies the normal equation, and  L(W̅(μ))=L_i(W̅_i(μ))=L_i(W_i)=L(W),
for any μ>0.

Note that W is a local minimum of L(W). Thus, there exists a δ>0,
such that for any W^0 satisfying W^0-W_∞≤δ, we have
L(W^0)≥ L(W). It follows from Ŵ_̂î being full rank that
there exists a small enough μ, such that W̅_i(μ)
is full rank and W̅_i(μ)-W_i_∞ is arbitrarily small (in particular, W̅_i(μ)-W_i_∞≤δ/2), because the non-full-rank matrices are discrete on the line of W̅_i(μ)
with parameter μ>0 by considering the determine of W_i^T(μ)W_i(μ) or  W_i(μ)W_i^T(μ) as a polynomial of λ. Therefore, for any W^0, such that W^0-W̅(μ)_∞≤δ/2,
we have 
    W^0-W_∞≤W^0-W̅(μ)_∞+W̅_i(μ)-W_i_∞≤δ ,

whereby 
    L(W^0) ≥ L(W) = L(W̅(μ))  .
 This shows that W̅(μ)={W_1,⋯,W_i-1,W̅_i(μ),W_i+1,⋯,W_H} is also a local minimum of problem (<ref>) for some small enough μ. 











  

Let R=AB for two given matrices A∈ R^d_1× d_2 and B∈ R^d_2× d_3. If d_1≤ d_2, d_1≤ d_3 and rank(A)=d_1, then any perturbation of R is the product of A and perturbation of B.


Proof: Let A=UDV^T be the SVD of A, then, R=UDV^TB. Let
R̅ be a perturbation of R and let B̅=B+VD^+U^T(R̅-R).
Then, B̅ is a perturbation of B and AB̅=R̅ by noticing DD^+=I, as A has full row rank. 


  
 
If W̅={W̅_1,⋯,W̅_H} is a local
minimum with W̅_i being full rank, then, there exists Ŵ={Ŵ_1,⋯,Ŵ_H},
such that Ŵ_i is a perturbation of W̅_̅i̅  for all
i∈{ 1,…,H}, Ŵ is a local minimum,
L(Ŵ)=L(W̅), and (Ŵ_HŴ_H-1⋯Ŵ_1)=d_p.


  

In the proof of Theorem <ref>, we will use Theorem <ref> and Lemma <ref> to show that we can perturb W̅_p-1,  W̅_p-2…, W̅_1 in sequence to make sure the perturbed weight is still the optimal solution and (Ŵ_pŴ_p-1)=d_p. Similar strategy can make sure (Ŵ_HŴ_H-1⋯Ŵ_p+1)=d_p, which then proves the whole theorem.

Proof of Theorem <ref> :  If p≠1, consider 
    L_1(T):=W̅_H⋯W̅_p+1T W̅_p-2⋯W̅_1X-Y_F^2.

Then, it follows from Lemma <ref> and W̅ is a local minimum of L(W) that T̅ is a local minimum of L_1, where T̅=W̅_pW̅_p-1.
It follows from Theorem <ref> that there exists T̂, such
that T̂ is close enough to T̅, T̂ is a local
minimum of L_1(T), L_1(T̂)=L_1(T̅), and (T̂)=d_p.
Note T̂ is a perturbation of T̅, whereby, from Lemma <ref>,
there exists Ŵ_p, Ŵ_p-1, which are perturbations
of W̅_p and W̅_p-1, respectively, such that Ŵ_pŴ_p-1 = T̂. Thus, Ŵ^0=(W̅_H,⋯,W̅_p+1,Ŵ_p,Ŵ_p-1,W̅_p-2⋯,W̅_1)
is a local minimum of L(W), L(Ŵ)=L(W̅) and (Ŵ_pŴ_p-1)=d_p. 

By that analogy, we can find Ŵ_p⋯Ŵ_1, such
that Ŵ^1=(W̅_H,⋯,W̅_p+1,Ŵ_p,Ŵ_p-1,⋯,Ŵ_1)
is a local minimum of L(W), Ŵ_i is a perturbation of
W̅_i for i=1,⋯,p, L(Ŵ^1)=L(W̅) and
(Ŵ_pŴ_p-1⋯Ŵ_1)=d_p. 

Similarly, we can find Ŵ_H⋯Ŵ_p+1, such that Ŵ^2=(Ŵ_H,⋯,Ŵ_p+1,Ŵ_p,Ŵ_p-1,⋯,Ŵ_1)
is a local minimum of L(W), Ŵ_i is a perturbation of
W̅_i for i=p+1,⋯,H, L(Ŵ^2)=L(Ŵ^1)=L(W̅)
and (Ŵ_HŴ_H-1⋯Ŵ_p+1)=d_p. 

Noticing that 

    (Ŵ_H⋯Ŵ_1) 
     ≥(Ŵ_HŴ_H-1⋯Ŵ_p+1)
    +(Ŵ_pŴ_p-1⋯Ŵ_1)-d_p = d_p

and (Ŵ_H⋯Ŵ_1)≤min_i=0,…,Hd_i=d_p,
we have (Ŵ_H⋯Ŵ_1)=d_p, which completes
the proof. 


  
Proof of Theorem <ref>:
It follows from Theorem <ref> and Theorem <ref> that there exists another local minimum Ŵ= Ŵ={Ŵ_1,⋯,Ŵ_H}, such that L(Ŵ) = L(W̅) and (Ŵ_HŴ_H-1⋯Ŵ_1)=d_p. Remember that R̂=Ŵ_HŴ_H-1⋯Ŵ_1. It then follows from Theorem <ref> that for any R, such that R is a perturbation of R̂ and (R)≤ d_p, we have R = W_HW_H-1⋯ W_1, where W_i is a perturbation of Ŵ_i. Therefore, by noticing Ŵ is a local minimum of (<ref>), we have

    F(R)= L(W)≥ L(Ŵ) = F(R̂) ,

which shows that R̂ is a local minimum of (<ref>). 


In the proof of Theorem <ref>, we at first show that we just need to consider the case where X is an identity matrix and Y is a diagonal matrix by noticing rotation is invariant under Frobenius norm. Then we show that the local minimum must be a block diagonal and symmetric matrix, and each block term is a projection matrix on the space corresponding to the same eigenvalue of the diagonal matrix Y. Finally, we show that those projection matrices must be onto the eigenspace of Y corresponding to the as large as possible eigenvalues, which then shows that the local minimum shares the same function value.



 §.§ Proof of Theorem <ref>

Let X=U_1Σ_1 V_1^T be the SVD decomposition of X, where Σ_1 is a diagonal matrix with full row rank. Then, 

    F(R)    = RU_1 Σ_1 V_1^T -Y_F^2 
    = RU_1Σ_1 - YV_1_F^2 
    
       = (RU_1)(Σ_1)_1:d_1, 1:d_1 - (YV_1)_1:d_2,1:d_1_F^2 + Const,

where Const is a constant in R and (·)_t_1:t_2,t_3:t_4 is a submatrix of (· ), which contains the t_1 to t_2 row and t_3 to t_4 column of (·). If R is a local minimum of (<ref>), then S=RU_1 is a local minimum of

    [                min_S G(S) = SΣ̂_1 - Ŷ_F^2;                 s.t.            (S)≤ k  , ]

 where Σ̂_1 := (Σ_1)_1:d_1, 1:d_1, Ŷ := (YV_1)_1:d_2,1:d_1 and the difference of objective function values of (<ref>) and (<ref>) is a constant. Let Ŷ := U_2Σ_2 V_2^T be the SVD of Ŷ, then 
    G(S)= SΣ̂_1 - U_2Σ_2 V_2^T_F^2 = U_2^TSΣ̂_1V_2 - Σ̂_2_F^2 ,

and if S is a local minimum of G(S), we have T:=U_2^TSΣ̂_1V_2 is a local minimum of 

    [              min_T H(T) = T - Σ_2_F^2;               s.t.          (T)≤ k  , ]

and the objective function values of (<ref>) and (<ref>) are the same at corresponding points. Let Σ_2 have r distinct positive diagonal terms λ_1>⋯>λ_r≥0
with multiplicities m_1,⋯,m_r. Let T^* be a local
minimum of (<ref>), and 

    T^*=U^*Σ^*V^*T=[U_S^*U_N^*][[ Σ_S^*     0;     0     0 ]][[ V_S^*T; V_N^*T ]]

 be the SVD of T, where Σ^*_S are positive singular values.
Let P_L:=U_S^*(U_S^*TU_S^*)^-1U_S^*T
and P_R:=V_S^*(V_S^*TV_S^*)^-1V_S^*T be the
projection matrix to the space spanned by U_S^* and V_S^*,
respectively. Note that { T|P_LT=T}⊆{ T|rank(T)≤ k},
thus, T^* is also a local minimum of

    min   T-Σ_2_F^2
     s.t.     P_LT=T,

which is a convex problem, and it can be shown by the first order optimality condition that the only local minimum of (<ref>) is T^*=P_LΣ_2. Similarly, we have T^*=Σ_2P_R.
Then, D:=Σ_2Σ_2^T is a diagonal matrix, with r
distinct non-zero diagonal terms λ_1^2>⋯>λ_r^2>0
with multiplicities m_1,⋯,m_r. Therefore,

    P_LDP_L   =P_LΣ_2Σ_2^TP_L^T=T^*T^*T=Σ_2P_RP_R^TΣ_2^T
       =Σ_2P_RΣ_2^T=Σ_2T^*T=Σ_2Σ_2^TP_L^T=DP_L.

Note that the left hand is a symmetric matrix, thus, DP_L is
also a symmetric matrix. Meanwhile, P_L is a symmetric matrix,
whereby P_L is a r-block diagonal matrix with each block corresponding
to the same diagonal terms of D. Therefore, T^*=P_LΣ_2
is also a r-block diagonal matrix. 

Let 

    T^*=[[ T_1^*;           ⋱;             T_r^*;                       0 ]],

where T_i^* is a m_i× m_i matrix, then T^*T^*T=Σ_2T^*T
implies T_i^*T_i^*T=λ_iT_i^*T. Thus, T_i^*
is a symmetric matrix and T_i^*/λ_i is a projection
matrix. Let rank(T_i^*)=d_p_i,
then, ∑_i=1^rd_p_i≤ p and tr(T_i^*)=λ_id_p_i, whereby, 

    H(T^*)   =∑_i=1^rT_i^*-λ_iI_m_i_F^2
       =∑_i=1^rtr(T_i^2)-2λ_itr(T_i)+m_iλ_i^2
       =∑_i=1^r(m_i-d_p_i)λ_i^2.

Let j be the largest number that ∑_i=1^jm_i < d_p. Then,
it is easy to find that the global minima of (<ref>) satisfy d_p_i=m_i
for i≤ j, d_p_j+1=d_p-∑_i=1^jm_i and d_p_i = 0 for i>j+1 which gives all
of the global minima.

Now, let us show that all local minima must be global minima. As local
minima T^* is a block diagonal matrix, thus, we
can assume without loss of generality that both Σ_2 and T^* are square matrices, because
the all 0 rows and columns in Σ_2 and T do not change
anything. Thus, it follows T_i^* is symmetric that T^*
is a symmetric matrix. Remember that T_i^*/λ_i
is a projection matrix, thus the eigenvalues of T_i^* are either
0 or λ_i, whereby 

    T^*=∑_i=1^r∑_j=1^d_p_iλ_iu_iju_ij^T,

where u_ij is the jth normalized orthogonal eigen-vector of T^*
corresponding to eigenvalue λ_i. 

It is easy to see that, at a local minimum, we have ∑_i=1^rd_p_i=d_p,
otherwise, there is a descent direction by adding a rank 1 matrix
to T^* corresponding to one positive eigenvalue. If there exists i_1,i_2,
such that i_1<i_2, d_p_i_1<m_i_1, and d_p_i_2≥1,
then, there exists u̅_i_1, such that u̅_i_1⊥ u_i_1j
for j=1,⋯ d_p_i_1. Let 

    T(θ) :=     T^*-λ_i_2u_i_21u_i_21^T
    +(λ_i_1sin^2θ +λ_i_2cos^2θ) 
       (u_i_21cosθ + u̅_i_1sinθ)(u_i_21cosθ +u̅_i_1sinθ )^T.


Then, (T(θ))=(T^*)=d_p, T(0)=T^* and 
    H(T(θ))=H(T^*)+λ_1^2+λ_2^2-(λ_1sin^2θ+λ_2cos^2θ)^2 .

It is easy to check that H(T(θ)) is monotonically decreasing with
θ, which gives a descent direction at T^*, contradicting with
that T^* is a local minimum. Therefore, there is no such
i_1 and i_2, which shows that T^* is a global minimum. 









 §.§ Proof of Theorem <ref>

The statement follows from Theorem <ref> and <ref>. 




§ CONCLUSION

We have proven that, even though depth creates a non-convex loss surface, it does not create new bad local minima. Based on this new insight, we have successfully proposed a new simple proof for the fact that all of the local minima of feedforward deep linear neural networks are global minima as a corollary. 

The benefits of this new results are not limited to the simplification of the previous proof. For example, our results apply  to problems beyond square loss. Let us consider the shallow problem (S) L(R)  s.t.  rank(R) ≤ d_p, and and the deep parameterization counterpart (D) L(W_H W_H-1⋯ W_1).
Our analysis shows that for any function L, as long as L satisfies Theorem 3.2, any local minimum of (D) corresponds to a local minimum of (S). This is not limited to when L is least square loss, and this is why we say depth creates no bad local minima.

In addition, our analysis can directly apply to matrix completion unlike previous results.  <cit.> show that local minima of the symmetric matrix completion problem are global with high probability. This should be able to extend to asymmetric case. Denote
f(W) := ∑_i,j ∈Ω (Y - W_2 W_1)_i,j,
then local minimum of f(W) is global with high probability, where Ω is the observed entries. Then, our analysis here can directly show that the result can be extended for deep linear parameterization: for
h(W) := ∑_i,j ∈Ω (Y - W_H W_H-1⋯ W_1)_i,j,
any local minimum of h(W) is global with high probability.      





§ ACKNOWLEDGEMENTS
 
The authors would like to thank Professor Robert M. Freund, Professor Leslie Pack Kaelbling for their generous
support. We also want to thank Cheng Mao for helpful discussions.



apalike

