Title: LEARNING DEEP MODELS: CRITICAL POINTS AND LOCAL OPENNESS

Abstract: With the increasing interest in deeper understanding of the loss surface of many non-convex deep models, this paper presents a unifying framework to study the local/global optima equivalence of the optimization problems arising from training of such non-convex models. Using the local openness property of the underlying training models, we provide simple sufficient conditions under which any local optimum of the resulting optimization problem is globally optimal. We first completely characterize the local openness of matrix multiplication mapping in its range. Then we use our characterization to: 1) show that every local optimum of two layer linear networks is globally optimal. Unlike many existing results in the literature, our result requires no assumption on the target data matrix Y , and input data matrix X. 2) develop almost complete characterization of the local/global optima equivalence of multi-layer linear neural networks. We provide various counterexamples to show the necessity of each of our assumptions. 3) show global/local optima equivalence of non-linear deep models having certain pyramidal structure. Unlike some existing works, our result requires no assumption on the differentiability of the activation functions and can go beyond "full-rank" cases.

1. INTRODUCTION:

Deep learning models have recently led to significant practical successes in various fields ranging from computer vision to natural language processing. Despite these significant empirical successes, the theoretical understanding of the behavior of these models is still very limited. While some recent works have tried to explain these successes through the lens of expressivity by showing the power of these models in learning large class of mappings, other works find the root of the success in the generalizability of these models from learning perspective.

From optimization perspective, training deep models require solving non-convex optimization problems, where nonconvexity arises from the "deep" structure of the model. In fact, it has been shown by Blum & Rivest (1989) that training neural networks to global optimality is NP-complete in the worst case even for the simple case of three node networks. Despite this worst case barrier, the practical success of deep learning may suggest that most of the local optimal points of these models are close to the global optimal points. In particular, Choromanska et al. (2015) uses spin glass theory and empirical experiments to show that the local optima of deep neural network optimization problem are close to the global optima.

In an effort to better understand the landscape of training deep neural networks, Kawaguchi (2016) ; Lu & Kawaguchi (2017) ; Yun et al. (2017) ; Hardt & Ma (2016) studied the linear neural networks and provided sufficient conditions under which critical points (or local optimal points) of the training optimization problems are globally optimal. For non-linear neural networks, multiple works have shown that when the number of parameters of the model is larger than the data dimension, local optima of the resulting optimization problems can be easily found using local search procedures; see, e.g., Soltanolkotabi et al. (2017) ; Soudry & Carmon (2016) ; Nguyen & Hein (2017) ; Xie et al. (2017) .

Despite the growing interest in studying the landscape of deep optimization problems, many of the results and mathematical analyses are problem specific and cannot be generalized to other problems and network structures easily. As a first step toward reaching a unifying theory for these results, we propose the use of open mappings for characterizing the properties of the local optima of these "deep" optimization problems.

To study the landscape of shallow/deep models, we study the general optimization problem minimize w∈W (F(w)),

where (•) is the loss function and F(•) represents a statistical model with parameter w that needs to be learned by solving the above optimization problem. A simple example is the popular linear regression problem

minimize w Xw -y 2 2 ,

where y is a given constant response vector and X is a given constant feature matrix. In this example, the loss function is the 2 loss, i.e., (z) = zy 2 2 , and the fitted model F is a linear model, i.e., F(w) = Xw. While this linear regression problem is convex and easy, fitting many practical models, such as deep neural networks, requires solving non-trivial non-convex optimization problems.

In this paper, we use the local openness of the mapping F to provide sufficient conditions under which every local optimum of (1) is in fact global optimum. To proceed, let us define our notations that will be used throughout the paper. We use A l,: and A :,l to denote the l th row and column of the matrix A, respectively. The notation I d ∈ R d×d is used to denote the d × d-dimensional identity matrix. Let A , N (A), C(A), rank(A) be respectively the Frobenius norm, null-space, column-space, and the rank of the matrix A. Given subspaces U and V , we say U ⊥ V if U is orthogonal to V , and U = V ⊥ if U is the orthogonal complement of V . We say matrix A ∈ R d1×d0 is rank deficient if rank(A) < min{d 1 , d 0 }, and full rank if rank(A) = min{d 1 , d 0 }. We call a point W = (W h , . . . , W 1 ),

with W i ∈ R di×di-1 , non-degenerate if rank(W h • • • W 1 ) = min 0≤i≤h d i , and degenerate if rank(W h • • • W 1 ) < min 0≤i≤h d i .

We also say a point W is a second order saddle point of an unconstrained optimization problem if the gradient of the objective function is zero at W and the hessian of the objective function at W has a negative eigenvalue. Let us start by briefly explaining the training problem of feedforward neural networks which will also be used as a motivation for our analysis:

Example: Training Feedforward Neural Networks. Consider the following multiple layer feedforward neural network optimization problem:

minimize W 1 2 F h (W ) -Y 2

where F h is defined in a recursive manner:

F k (W ) σ k W k F k-1 (W ) , for k ∈ {2, . . . , h},

with F 1 (W ) σ 1 (W 1 X). Here h is the number of hidden units in our network; σ k (•) denotes the activation function of layer k; the matrix W k ∈ R d k ×d k-1 is the weight of layer k with W (W i ) h i=1 being our optimization variable. The matrix X ∈ R d0×n is the input training data; and Y ∈ R d h ×n is the target training data where n is the number of samples; see, e.g. Goodfellow & Courville (2016) . Notice that this problem is a special case of the optimization problem in (1) which can be obtained simply by setting our loss function to the 2 loss, and setting F = F h .

A special instance of this optimization problem was studied in Nguyen & Hein (2017) which considers the non-linear neural network with pyramidal structure (i.e. d i ≤ d i-1 ∀ i = 1, . . . , h and d 0 ≥ n). Note that this special network structure does not allow wide intermediate layers. (Nguyen & Hein, 2017, Theorem 3.8) shows that under some conditions, among which are the differentiability of the loss function (•) and the activation function σ(•), if W is a critical point with W i 's being full row rank then it is a global minimum. In this paper, we will relax the differentiability assumption on both (•) and σ(•); and we will show any local optimum is a global optimum of the objective function. Another special case is the linear feedforward network where the mapping σ k (•) is the identity map in all layers, which leads to the optimization problem:

EQUATION

)

For this optimization problem, Lu & Kawaguchi (2017) showed that every local optimum of the objective function is globally optimal under some assumptions. More precisely, by using perturbation analysis, (Lu & Kawaguchi, 2017, Theorem 2. 2) prove that when X and Y are full row rank, every local optimum in problem (2) is a local optimum of the following problem: minimum

Z∈R d h ×d 0 1 2 ZX -Y 2 subject to rank(Z) ≤ d p min 0≤i≤h d i .

(3) Moreover, they show that when X is full row rank, every local optimum of problem (3) is a global optimum. Thus, with the sufficient condition that X and Y are both full row rank, every local optimum of problem ( 2) is a global optimum. Another recent work Yun et al. (2017) shows the same result under similar set of assumptions. It is in fact not hard to see that one cannot relax the full rankness assumption of Y due to the following simple counterexample: Other examples: Matrix Factorization and Matrix Completion. In addition to the training of deep neural networks, the matrix completion problem also lies in the category of non-convex problems in (1). For the matrix completion problem, Park et al. (2016) shows that the non-convex matrix factorization formulation of the non-square matrix sensing problem has no spurious local optimum under restricted isometry property (RIP) conditions. Similar results were obtained for the symmetric matrix multiplication problem by Ge et al. (2016) , and the non-convex factorized low-rank matrix recovery problem by Bhojanapalli et al. (2016) . Like the analysis in Ge et al. (2016) , we start with the fully observed matrix completion scenario: minimize

X = I W 3 = 1 0 , W 2 = [ 0 ] , W 1 = [ 1 0 ] , Y = 0 0 0 1 . It is not hard to check that the point W = (W 1 , W 2 , W 3 ) is a

EQUATION

)

This problem, which is also referred to as the low rank matrix estimation problem in Srebro & Jaakkola (2003) , can also be viewed as a 2-layer linear neural network optimization problem with the input data matrix X = I. Clearly, this problem is much simpler than the general matrix completion problem and we only study it as a first step. Moreover, this optimization problem is a special case of (1) with the loss function being the 2 loss, and the mapping F being defined as

F(W 1 , W 2 ) = W 2 W 1 .

In this paper, using our framework, we show that every critical point of ( 4) is either a global minimum or a second-order saddle point. This result can be generalized to general loss function (•) for degenerate critical points.

In addition to these results, one of our main contributions is the complete characterization of the local openness of the matrix multiplication mapping in its range. These results could be used in many other optimization problems for characterizing the local/global equivalence.

2. MATHEMATICAL FRAMEWORK:

As discussed in the previous section, we are interested in solving minimize w∈W (F(w)),

where F : W → S is a mapping and : S → R is a loss function. Here we assume that the set W is closed and the mapping F is continuous. In non-convex scenarios, this optimization problem can only be solved up to "local optimality" by local search procedures; see Lee et al. (2016) for an example. To proceed, let us define the auxiliary optimization problem minimize

EQUATION

)

where S is the range of the mapping F. Since problem (6) minimizes the function (•) over the range of the mapping F, the global optimal objective values for problems (5) and ( 6) are the same. Moreover, there is a clear relation between the global optima of the two optimization problem through the mapping F. However, the connection between the local optima of the two optimization problems is not clear. This connection, in particular, is important when the local optima of (6) are "nice" (e.g. globally optimal or close to optimal). In what follows, we establish the connection between the local optima of the optimization problems ( 5) and ( 6) under some simple sufficient conditions. This connection is then used to study the relation between local and global optima of ( 5) and ( 6) for various deep learning models. Let us first define the following concepts, which will help us state our simple sufficient condition. The following simple intuitive observation, which establishes a connection between the local optima of ( 5) and ( 6), is a major building block of our analyses. where s = F( w). Therefore, (s) ≤ (s), ∀s ∈ B δ (s), which implies s is a local minimum of problem (6).

The above observation can be used to map multiple local optima of the original problem (5) to one local optimum of the auxiliary problem (6); and potentially make the problem easier to understand. This mapping is particularly interesting in neural networks since permuting the weights in each layer does not change the objective function. 

EQUATION

)

and its corresponding auxiliary problem minimize

EQUATION

)

Plots of these two problems can be found in Figure 2a and Figure 2b . Since F(x) w 2 is an open mapping in its range, it follows from Observation 1 that every local minimum in problem ( 7) is a local minimum of problem (8). Thus the two local minima w = -1 and w = +1 in (7) are mapped to a single local minimum z = 1 of problem (8). Moreover, since the optimization problem (8) is convex, the local minimum is global; and hence the original local optima w = -1 and w = +1 should be both global despite non-convexity of (7). 

(W 1 W 2 ).

Then, any point in the set S

{( W1 Q 1 , Q 2 W2 ) with Q 1 Q 2 = I} is also a local minimum. If the matrix product W 1 W 2 is

locally open at the point ( W1 , W2 ), then all points in S are mapped to a single local minimum Z = W 1 W 2 in the corresponding auxiliary problem. A simple one dimensional example is plotted in Figure 3a and Figure 3b .

This motivates us to study the local openness of the matrix multiplication mapping defined as

EQUATION

where R M { Z ∈ R m×n | rank(Z) ≤ min{m, n, k}} is the range of the mapping M.

Although matrix multiplication mappings M(W 1 , W 2 ) naturally appears in deep models and is widely used as a non-convex factorization for rank constrained problems, see Wang et al. (2016) ; Bhojanapalli et al. (2016) ; Ge et al. (2016) ; Srebro & Jaakkola (2003) ; Sun (2015) , to our knowledge, the complete characterization of the local openness of this mapping has not been studied in the optimization literature before.

While the classical open mapping theorem in Rudin (1973) states that surjective continuous linear operators are open, this is not true in general for bilinear mappings such as matrix product. In fact, by providing a simple counterexample of a bilinear mapping that is not open, Horowitz (1975) shows that the linear case cannot be generally extended to multilinear maps. Several papers, see Balcerzak et al. (2013; 2005) ; Behrends (2011) , investigate this bilinear mapping and provide a characterization of the points where this mapping is open. Moreover, Behrends (2017) studies the matrix multiplication mapping M which is a special example of bilinear mappings and provides an almost complete characterization of the points where the mapping is locally open. However, the openness is studied in R m×n ; while the range of the mapping is R M ; and the (relative) local openness should be studied with respect to this range in our framework. This, in particular causes trouble when R m×n = R M , i.e., when k < min{m, n}.

For the above reason, we study the local openness of the mapping M in its range R M and characterize it completely.

An intuitive (and unofficial) definition of local openness of M(•) at ( W1 , W2 ) in R M is as follows. We say the multiplication mapping is locally open at ( W1 , W2 ) if for any small perturbation Z ∈ R M of Z = W1 W2 , there exists a pair

( W 1 , W 2 ), a small perturbation of ( W1 , W2 ), such that Z = W 1 W 2 .

Notice that when k ≥ min{m, n}, we get R M = R m×n . However, in the case where k < min{m, n} the mapping is

definitely not locally open in R m×n , but can still be locally open in R M . As a simple example, consider W1 = 1 2

and W2 = [ 1 1 ].

In this example there does not exist W 1 , W 2 perturbations of W1 and W2 respectively such that W 1 W 2 = Z when Z is a full rank perturbation of Z = W1 W2 ; however, for any rank 1 perturbation Z, we can find a perturbed pair

( W 1 , W 2 ) such that Z = W 1 W 2 .

Motivated by Observation 1, we study in the next section the local openness/openness of the mapping M. We later use these results to analyze the behavior of local optima of deep neural networks.

3. LOCAL OPENNESS OF THE MATRIX MULTIPLICATION MAPPING:

When

W 1 ∈ R m×k and W 2 ∈ R k×n with k ≥ min{m, n}, the range of the mapping M(W 1 , W 2 ) = W 1 W 2

is the entire space R m×n . In this case, which we refer to as the full rank case, (Behrends, 2017, Theorem 2.5 ) provides a complete characterization of the pairs (W 1 , W 2 ) for which the mapping is locally open. However, when k < min{m, n}, which we refer to as the rank-deficient case, the characterization of the set of points for which the mapping is locally open has not been resolved before. We settled this question in Theorem 5 by providing a complete characterization of points (W 1 , W 2 ) for which the mapping M is locally open when k < min{m, n}. We start by restating the main result in Behrends (2017): Proposition 4. (Behrends, 2017, Theorem 2.5 Rephrased) Let M(W 1 , W 2 ) = W 1 W 2 denote the matrix multiplication mapping with W 1 ∈ R m×k and W 2 ∈ R k×n . Assume k ≥ min{m, n}. Then the the following statements are equivalent:

1. M(•, •) is locally open at ( W1 , W2 ). 2.      ∃ W 1 ∈ R m×k such that W 1 W2 = 0 and W1 + W 1 is full row rank. or ∃ W 2 ∈ R k×n such that W1 W 2 = 0 and W2 + W 2 is full column rank. 3. dim N ( W1 ) ∩ C( W2 ) ≤ k -m or n -(rank( W2 ) -dim N ( W1 ) ∩ C( W2 ) ≤ k -rank( W1 ).

The above proposition provides a checkable condition which completely characterizes the local openness of the mapping M at different points when the range of the mapping is the entire space. Now, let us state our result that characterizes the local openness of the mapping M in its range when k < min{m, n}.

Theorem 5. Let M(W 1 , W 2 ) = W 1 W 2 denote the matrix multiplication mapping with W 1 ∈ R m×k and W 2 ∈ R k×n . Assume k < min{m, n}. Then if rank( W1 ) = rank( W2 ), M(•, •) is not locally open at ( W1 , W2 ). Else, if rank( W1 ) = rank( W2 ), then the following statements are equivalent: i) ∃ W 1 ∈ R m×k such that W 1 W2 = 0 and W1 + W 1 is full column rank. ii) ∃ W 2 ∈ R k×n such that W1 W 2 = 0 and W2 + W 2 is full row rank. iii) dim N ( W1 ) ∩ C( W2 ) = 0. iv) dim N ( WT 2 ) ∩ C( WT 1 ) = 0. v) M(•, •) is locally open at ( W1 , W2 ) in its range R M .

Note that the proof of Theorem 5, which can be found in the appendix section, is different than the proof of Proposition 4, as in the former we need to work with the set of low rank matrices. Besides, the conditions in Theorem 5 are different than the ones in Proposition 4. For example, while conditions i) and ii) are equivalent in the rank-deficient case, they are not equivalent in the full-rank case. Moreover, unlike the full-rank case, the condition rank( W1 ) = rank( W2 ) is necessary for local openness in the low rank case.

How much perturbation is needed? As previously mentioned, local openness can be described in terms of perturbation analysis. For example,

M(•, •) is locally open at (W 1 , W 2 ) if for a given > 0, there exists δ > 0 such that for any Z = Z + R δ ∈ R M with R δ ≤ δ, there exists W1 , W2 with W1 ≤ , W2 ≤ , such that Z = (W 1 + W1 )(W 2 + W2 ).

As a perturbation bound on δ, we show that for any locally open pair (W 1 , W 2 ), given an > 0, the chosen δ is of order , i.e., δ = O( ). The details of our analysis can be found in the proof of Theorem 5 in Appendix B.

Remark 1 It follows from Theorem 5 that when W 1 is full column rank, and W 2 is full row rank, the mapping

M(•, •)

is locally open at (W 1 , W 2 ). This result was observed in other works; see, e.g., (Sun, 2015, Proposition 4.2) . Also when k < min{m, n} if only one of the two matrices is full rank, then the mapping is not locally open. We have showed this result in the proof of Theorem 5, and below is a simple example for this phenomenon:

Let 

W 1 = 1 1 , W 2 = [ 0 , 0 ] , W 1 W 2 = 0 0 0 0 , R δ = δ 0 0 0 , then W 1 W 2 + R δ is

(W 1 + W1 )(W 2 + W2 ) = (1 + 1 ) 3 (1 + 1 ) 4 (1 + 2 ) 3 (1 + 2 ) 4 .

Hence, in order for this perturbation to be equal to W 1 W 2 + R δ , we need 3 to be different from zero. But when 3 is different from zero, for small enough 2 , there does not exist such W1 and W2 , or equivalently,

M(•, •) is not locally open at (W 1 , W 2 ).

In the next sections, we use our local openness result to characterize the cases where the local optima of various training optimization problem of the form (5) are globally optimal.

4. NON-LINEAR DEEP NEURAL NETWORK WITH A PYRAMIDAL STRUCTURE::

Consider the non-linear deep neural network optimization problem with a pyramidal structure minimize

EQUATION

) for i ∈ [2, h],

where σ i (•) is the activation function applied component-wise to the entries of each layer, i.e., σ i (A) = [σ i (A ij )] i,j with σ i : R → R being continuous and strictly monotone. Here W = W i h i=1 where W i ∈ R di×di-1 is the weight matrix of layer i, and X ∈ R d0×n is the input training data. In this section, we consider the pyramidal network structure with d 0 > n and d i ≤ d i-1 for 1 ≤ i ≤ h; see Nguyen & Hein (2017) for more details on these types of networks.

First notice that when X is full column rank and the functions σ i 's are all continuous and strictly monotone, the image of the mapping F h is convex and hence every local optimum of the auxiliary optimization problem ( 6) is global. We now show that when W i 's are all full row rank and the functions σ i are all strictly monotone, the mapping F h is locally open at W . Lemma 6. Assume the functions σ i (•) : R → R are all continuous strictly monotone. Then the mapping F h defined in ( 10) is locally open at the point W = (W 1 , . . . , W h ) if W i 's are all full row rank.

Before proving this result, we would like to remark that many of the popular activation functions such as logsitic, tangent hyperbolic, and leaky ReLu are strictly monotone and satisfy the assumptions of this lemma.

Proof. Let us prove by induction. Since linear mappings are open, and since σ 1 (•) is strictly monotone; by using the composition property of open maps, we get that F 1 is open.

Assume F k-1 W i k-1 i=1

is locally open at W i k-1 i=1 , then using Proposition 4, due to the full row rankness of W k , the mapping 

W k F k-1 W i k-1 i=1 is locally open at W k , (W i ) k-1 i=1 .

5. TWO-LAYER LINEAR NEURAL NETWORK:

Consider the two layer linear neural network optimization problem minimize

W 1 2 W 2 W 1 X -Y 2 (11)

where W 2 ∈ R d2×d1 and W 1 ∈ R d1×d0 are weight matrices, X ∈ R d0×n is the input data, and Y ∈ R d2×n is the target training data. Using our transformation, the corresponding auxiliary optimization problem can be written as

minimum Z 1 2 ||ZX -Y || 2 subject to rank(Z) ≤ min{d 2 , d 1 , d 0 } (12) (Lu & Kawaguchi, 2017, Theorem 2.2)

shows that when X is full rank, every local minimum of problem ( 12) is global. By using local openness, we first show that this result holds without any assumption on X or Y . The proof of Lemma 7 can be found in Appendix A.3 Lemma 7. Every local minimum of problem ( 12) is global.

Lemma 7 uses local openness to simplify the proof of (Lu & Kawaguchi, 2017 , Theorem 2.2) and relax the full rankness assumption on X. In another related work, (Kawaguchi, 2016, Theorem 2.3) shows that when XX T and Y X T are full rank, d 2 ≤ d 0 , and when Y X T (XX T ) -1 XY T has d 2 distinct eigenvalues, every local optimum is global and all saddle points are second order saddles. While the local/global equivalence result holds for deeper networks, the property that all saddles are second order does not hold in that case. Another result by (Yun et al., 2017, Theorem 2.2) shows that when XX T , Y X T , and Y X T (XX T ) -1 XY T are full rank, every local optimum of a linear deep network is global. Moreover, they provide necessary and sufficient conditions for a critical point to be a global minimum. However, in their proof, the full rankness assumption of Y X T was not used in showing the result for non-degenerate critical points and thus can be relaxed in that case. In this section, without any assumptions on both X and Y , we reconstruct the proof that shows the latter result for 2-layer networks using local openness, and then show a similar result for the degenerate case. The result for the degenerate case holds when replacing the square loss error by a general convex loss function as we will see in Colorollary 9. The proofs of the theorem and corollary stated below can be found in Appendices A.1 and A.2, respectively. Theorem 8. Every local minimum of problem ( 11) is global. Moreover, every degenerate saddle point of problem ( 11) is a second order saddle. Corollary 9. Let the square loss error in (11) be replaced by a general convex loss function (•). Then every degenerate critical point is either a global minimum or a second order saddle.

Baldi & Hornik (1989) and Srebro & Jaakkola (2003) show the same result when both X and Y are full row rank. Theorem 8 generalizes their results by relaxing the assumptions on both X and Y .

6. MULTI-LAYER LINEAR NEURAL NETWORK:

Consider the training problem of multi-layer deep linear neural networks:

EQUATION

)

Here

W = W i h i=1 , W i ∈ R di×di-1

are the weight matrices, X ∈ R d0×n is the input training data, and Y ∈ R d h ×n is the target training data. Based on our general framework, the corresponding auxiliary optimization problem is given by minimum

EQUATION

Paper Lu & Kawaguchi (2017) showed that when X and Y are full row rank, every local minimum of ( 13) is global.

We now relax the full rankness assumption and reproduce similar results. However, as we will see, the local/global equivalence does not always follow if we relax the full rankness. In such cases, we will provide detailed counter examples. Before proceeding to the proof we define the following mapping:

M i,j (W i , . . . , W j ) : {W i , . . . , W j } → R Mi,j {Z = W i . . . W j ∈ R di×dj-1 | rank(Z) ≤ min j-1≤l≤i d l } for i > j

Now we state Theorem 3.1 of Lu & Kawaguchi (2017) using our notation. The proof of the lemma stated below can be found in Appendix A.4.

Lemma 10. If W is non-degenerate, then M h,1 (W ) = W h • • • W 1 is locally open at W .

We now demonstrate our main results for this optimization problem which shows that under a set of necessary conditions, every local minimum of problem ( 13) is global. Although the result for the non-degenerate case directly follows from (Yun et al., 2017 

d 2 < d 1 then ∃ b = 0 such that b ∈ N W2 d 0 < d 1 then ∃ b = 0 such that b ∈ N W T 1 d 1 ≤ d 2 , and d 1 ≤ d 0 then either W2 is rank deficient and ∃ b = 0 such that b ∈ N W2 or W1 is rank deficient and ∃ b = 0 such that b ∈ N W T 1 So in all cases either N W2 = ∅ or N W T 1 = ∅. Also, let ∆ = W2 W1 X -Y . If ∆X T = 0,

then by convexity of the square loss error function, the point ( W2 , W1 ) is a global minimum of (11). Else, there exists (i, j) such that X i,: , ∆ j,: = 0. We now use first and second order optimality conditions to construct a descent direction when the current critical point is not global.

First order optimality condition: By considering perturbation in the directions A ∈ R d2×d1 and B ∈ R d1×d0 for the optimization problem

minimize t 1 2 (W 2 + tA)(W 1 + tB)X -Y 2 (15) we obtain A W1 X + W2 BX , ∆ = 0, ∀A ∈ R d2×d1 , B ∈ R d1×d0

Second order optimality condition:

2 ABX, ∆ + A W1 X + W2 BX 2 ≥ 0 ∀A ∈ R d2×d1 , B ∈ R d1×d0

Suppose ( W2 , W1 ) is a critical point and there exists b = 0, b ∈ N ( W2 ). We define

B :,l αb if l = i, 0 otherwise A l,: b T if l = j, 0 otherwise

where α is a scalar constant. Then, using the second order optimality condition, for c = A W1 X 2 , we get

α b 2 =0 X i,: , ∆ j,: =0 + c ≥ 0

Since this is true for every value of α, b should be zero which contradicts the assumption on the choice of b. Hence N ( W2 ) = ∅.

Similarly, suppose ( W2 , W1 ) is a critical point and there exists a T = 0, a T ∈ N ( WT 1 ). Let

A l,: αa T if l = j, 0 otherwise B :,l a if l = i, 0 otherwise

where α is a constant.Then, for c = W2 BX 2 , we get

α a 2 =0 X i,: , ∆ j,: =0 + c ≥ 0

Using the same argument, we can show that ( W2 , W1 ) is a second order saddle point of problem (11).

We now show the result for the non-degenerate case. Let ( W2 , W1 ) be a non-degenerate local minimum, i. A.2 PROOF OF COROLLARY 9

Proof. We follow the same steps used in the proof of Theorem 8 to show the result.

First order optimality condition: By considering perturbation in the directions A ∈ R d2×d1 and B ∈ R d1×d0 for the optimization problem minimize

t (W 2 + tA)(W 1 + tB)X -Y (16) we obtain A W1 X + W2 BX, ∇ ( W2 W1 X -Y ) = 0 ∀A ∈ R d2×d1 , B ∈ R d1×d0

Second order optimality condition:

2 ABX, ∇ ( W2 W1 X -Y ) + h A W1 X, W2 BX, W2 W1 X) ≥ 0 ∀A ∈ R d2×d1 , B ∈ R d1×d0

where h(•) is a function that has a tensor representation. But we only need to know that it is a function of A W1 X, W2 BX, and W2 W1 X.

If ∇ ( W2 W1 X -Y )X T , then by convexity of (•), ( W2 , W1 ) is a global minimum. Otherwise, there exists (i, j) such that X i,: , ∇ ( W2 W1 X -Y ) j,: = 0. Using the same former argument in proof of Theorem 8, we choose A and B such that h(A W1 X, W2 BX, W2 W1 X) is some constant that does not depend on α, and

ABX, ∇ ( W2 W1 X -Y ) = α X i,: , ∇ ( W2 W1 X -Y ) j,: = 0 =0

. Then by proper choice of α we show that the point ( W2 , W1 ) is a second order saddle point.

A.3 PROOF OF LEMMA 7:

Proof. Let r X = rank(X) and

U X Σ X V T X with U X ∈ R d0×d0 , Σ X ∈ R d0×n , V X ∈ R n×n be a singular value decomposition of X. Then ZX -Y 2 = ZU X Σ X :,1:r X 0 -Y V X 2 = ZU X Σ X :,1:r X -Y V X :,1:r X 2 + Y V X :,r X +1:n 2 constant in problem (12)

.

Since U X Σ X :,1:r X is full column rank, then the linear mapping ZU X Σ X :,1:r X is open, and

rank(ZU X Σ X :,1:r X ) ≤ min{rank(Z), r X } = min{d 2 , d 1 , d 0 , r X }.

Consequently, every local minimum in problem ( 12) corresponds to a local minimum in problem minimum

EQUATION

where Ȳ = Y V X :,1:r X . The result follows using (Lu & Kawaguchi, 2017 , Theorem 2.2).

A.4 PROOF OF LEMMA 10:

Proof. We construct a proof by induction on h to show the desired result. When h = 2, we either have d 1 < min{d 2 , d 0 } or d 1 ≥ min{d 2 , d 0 }. In the first case,

d 1 = rank(W 2 W 1 ) ≤ rank(W 1 ) ≤ d 1 ⇔ rank(W 1 ) = d 1 , and d 1 = rank(W 2 W 1 ) ≤ rank(W 2 ) ≤ d 1 ⇔ rank(W 2 ) = d 1 .

Since W 1 is full column rank and W 2 is full column rank, then by Theorem 5, M 2,1 (•) is locally open at (W 2 , W 1 ).

In the second case, either

d 2 = rank(W 2 W 1 ) ≤ rank(W 2 ) ≤ d 2 ⇔ rank(W 2 ) = d 2 , or d 0 = rank(W 2 W 1 ) ≤ rank(W 1 ) ≤ d 0 ⇔ rank(W 1 ) = d 0

Thus, either W 2 is full row rank or W 1 is full row rank, then by Proposition 4, M 2,1 (•) is locally open at (W 2 , W 1 ).

Now assume the result holds for the product of h matrices M h,1 (W ), we show it is true for M h+1,1 (W ).

Since Then by induction hypothesis, the product mapping 

d p = rank(W h . . . W 1 ) ≤ rank(W p+1 W p ) ≤ d p ⇔ rank(W p+1 W p ) =

M h+1,1 = W h+1 • • • W p+2 Z p W p-1 • • • W 1 is

B PROOF OF THEOREM 5:

In this section, we prove Theorem 5. This theorem provides a complete characterization of points ( W1 , W2 ) ∈ R m×k × R k×n for which the matrix multiplication mapping M(•, •) is locally open for the case of k < min{m, n}. In particular, we show that if rank( W1 ) = rank( W2 ), M(•, •) is not locally open at ( W1 , W2 ). Else, if rank( W1 ) = rank( W2 ), then the following statements are equivalent:

i) ∃ W 1 ∈ R m×k such that W 1 W2 = 0 and W1 + W 1 is full column rank. ii) ∃ W 2 ∈ R k×n such that W1 W 2 = 0 and W2 + W 2 is full row rank. iii) dim N ( W1 ) ∩ C( W2 ) = 0. iv) dim N ( WT 2 ) ∩ C( WT 1 ) = 0. v) M(•, •) is locally open at ( W1 , W2 ) in its range R M = {Z ∈ R m×n with rank(Z) ≤ min{m, k, n}}.

To prove this result, we first show that the local openness of

M(•, •) at (W 1 , W 2 ) is equivalent to the local openness of M(•, •) at (U T W 1 , W 2 V )

where the columns ofU ∈ R m×m and the columns of V ∈ R n×n are the left and right singular vectors of the product W 1 W 2 , respectively. This allows us to focus our study on the local openness of the mapping M to matrix pairs whose product is a diagonal matrix. We then show in Lemma 16 that when rank(W 1 ) = rank(W 2 ), the statements i, ii, ii, and iv are equivalent. Finally, we show in Proposition 18, that these conditions hold if and only if the mapping M(•, •) is locally open at (W 1 , W 2 ). Before proceeding we state and prove Lemma 13 that will be used later in the proof. Lemma 13. Let V ∈ R m×n be a matrix with rank(V ) = r < m. Then there exist an index set B = {i 1 , . . . , i r } ⊆ {1, . . . , m} and a matrix A ∈ R (m-r)×r such that

A ∞ = max i,j |A ij | ≤ 2 m-r-1 and V B c = AV B ,

where V B ∈ R r×n is a matrix with rows {V i,: } i∈B and V B c ∈ R (m-r)×n is a matrix with rows {V i,: } i∈B c .

Notice that in the above lemma, the bound on the norm of matrix A is independent of the dimension n and it also does not depend on the choice of matrix V.

Proof. To ease the notation, we denote the i th row of V by v i . We use induction on m to show that there exists a basis B = {i 1 , . . . , i r } and a vector a j ∈ R r such that ∀ j ∈ B c ,

v j = i∈B a j,i v i with |a j,i | ≤ 2 m-r-1 ∀ i ∈ B.

• Induction Base Case m = r + 1: Without loss of generality, assume B = {1, . . . , r}. Since the case of v r+1 = 0 trivially holds, we consider v r+1 = 0. By the property of basis, there exists a non-zero vector a r+1 ∈ R r such that

v r+1 = r i=1 a r+1,i v i . Let i * = arg max i∈B |a r+1,i |. If |a r+1,i * | ≤ 1, then the induction hypothesis is true. Otherwise, when |a r+1,i * | > 1, we have v i * = 1 a r+1,i * ār+1,r+1 v r+1 - r i=1; i =i * a r+1,i a r+1,i * ār+1,i v i = i∈B * ār+1,i v i where B * = (B ∪ {r + 1}) \{i * },

i.e., we remove the item i * from B and include the item r + 1 instead. Since |ā r+1,i | ≤ 1, the induction base holds.

• Inductive Step: Assume the induction hypothesis is true for m > r, we show it is also true for m + 1. Without loss of generality we can assume that B = {1, . . . , r}. By induction hypothesis,

v j = r i=1 a j,i v i with |a j,i | ≤ 2 m-r-1 , ∀ j = {r + 1, . . . , m}.

Since the case of v m+1 = 0 trivially holds, we consider v m+1 = 0. Since B is a basis, there exists a m+1 = 0 such that

v m+1 = r i=1 a m+1,i v i . Let i * = argmax i∈B |a m+1,i |. If |a m+1,i * | ≤ 2 m-r

, the induction step is done. Otherwise, for the case of |a m+1,i * | > 2 m-r , we have

v i * = 1 a m+1,i * ām+1,m+1 v m+1 - r i=1; i =i * a m+1,i a m+1,i * ām+1,i v i = i∈B * ām+1,i v i ,

where B * = (B ∪ {m + 1}) \{i * } and clearly |ā m+1,i | ≤ 1, ∀ i ∈ B * according to the definition of i * . For all j ∈ {r + 1, . . . , m}

v j = r i=1; i =i * a j,i v i + a j,i * v i * = r i=1; i =i * a j,i v i + a j,i * a m+1,i * v m+1 - r i=1; i =i * a m+1,i a j,i * a m+1,i * v i = r i=1; i =i * a j,i - a j,i * a m+1,i a m+1,i * āj,i v i + a j,i * a m+1,i * āj,m+1 v m+1 = i∈B * āj,i v i .

It remains to show that |ā j,i | ≤ 2 m-r for all i ∈ B * , j ∈ {r + 1, . . . , m}. Let us first consider i ∈ B * \{m + 1} and j ∈ {r + 1, . . . , m}:

|ā j,i | ≤ |a j,i | + a j,i * a m+1,i a m+1,i * by triangular inequality ≤ 2 m-r-1 + 2 m-r-1 a m+1,i a m+1,i * by induction hypothesis ≤ 2 m-r

by definition of i * .

For i = m + 1, |ā j,m+1 | = a j,i * a m+1,i * ≤ 2 m-r-1 a m+1,i * ≤ 2 m-r

. This concludes the inductive step and completes our proof.

Lemma 14. Let W 1 ∈ R m×k and W 2 ∈ R k×n . Assume further that W 1 W 2 = U ΣV T is a singular value decomposition of the matrix product W 1 W 2 with U ∈ R m×m , V ∈ R n×n , and Σ ∈ R m×n . Then M(•, •) is locally open at (W 1 , W 2 ) ⇔ M(•, •) is locally open at (U T W 1 , W 2 V ).

Proof. We first show the direction " ⇒ ". Suppose M(•, •) is locally open at (W 1 , W 2 ), then by definition of local openness, for any given > 0, there exists δ > 0 such that

EQUATION

)

We now show that

IB δ (U T W 1 W 2 V ) ∩ R M ⊆ M IB (U T W 1 ), IB (W 2 V ) . Consider Σ ∈ IB δ (U T W 1 W 2 V ) ∩ R M , i.e., Σ = U T W 1 W 2 V +R δ with rank( Σ) ≤ min{m, k, n} and R δ ≤ δ.

Since U and V are unitary matrices, we get

U ΣV T = W 1 W 2 + U R δ V T with rank(U ΣV T ) = rank( Σ) ≤ min{m, k, n} and U R δ V T = R δ ≤ δ.

According to (18), we have

U ΣV T ∈ IB δ (W 1 W 2 ) ∩ R M ⊆ {(W 1 + W 1 )(W 2 + W 2 ) | W 1 ≤ , W 2 ≤ }.

which implies,

Σ ∈ {(U T W 1 + U T W 1 )(W 2 V + W 2 V ) | W 1 ≤ , W 2 ≤ } = {(U T W 1 + U T W 1 )(W 2 V + W 2 V ) | U T W 1 ≤ , W 2 V ≤ }.

Since Σ was arbitrarily chosen, we get

IB δ (U T W 1 W 2 V ) ∩ R M ⊆ M IB (U T W 1 ), IB (W 2 V ) .

Proving the converse direction " ⇐ " is similar. Suppose M(•, •) is locally open at (U T W 1 , W 2 V ), then by definition of local openness, for any given > 0, there exists δ > 0 such that

EQUATION

)

We now show that

IB δ (W 1 W 2 ) ∩ R M ⊆ M IB (W 1 ), IB (W 2 ) . Consider Z ∈ IB δ (W 1 W 2 ) ∩ R M , i.e. Z = W 1 W 2 + R δ with rank( Z) ≤ min{m, k, n} and R δ ≤ δ. Since U and V are unitary matrices we get U T ZV = U T W 1 W 2 V + U T R δ V with rank(U T ZV ) = rank( Z) ≤ min{m, k, n} and U T R δ V = R δ ≤ δ.

According to (19), we have

U T ZV ∈ IB δ (U T W 1 W 2 V ) ∩ R M ⊆ M IB (U T W 1 ), IB (W 2 V ) .

which implies,

Z ∈ {(W 1 + U W 1 )(W 2 + W 2 V T ) | W 1 ≤ , W 2 ≤ } = {(W 1 + U W 1 )(W 2 + W 2 V T ) | U W 1 ≤ , W 2 V T ≤ }.

We now show the other direction "ii ⇐ iii". Without loss of generality, let W 2 = (W 2 ) k×r A r×n-r (W 2 ) k×r where columns of W 2 are linearly independent and let W 2 = w 1 1 , . . . , w k-r 1 , 0, . . . , 0 ∈ R k×n be a rank k-r matrix where w i 1 are unit basis of N ( W 1 ) which yields C( W 2 ) = N ( W 1 ). Then since dim N (W 1 ) ∩ C(W 2 ) = 0, we get rank(W 2 + W 2 ) = k for generic choice of . This completes the proof.

Note that by setting W 1 = W T 2 and W 2 = W T 1 , the same proof can be used to show i ⇔ iv. Next, we will prove the equivalence iii ⇔ iv. Notice that

dim span N ( W 1 ) ∪ C( W 2 ) = dim N ( W 1 ) + dim C( W 2 ) -dim N ( W 1 ) ∩ C( W 2 ) = k -r + r -dim N ( W 1 ) ∩ C( W 2 ) = k -dim N ( W 1 ) ∩ C( W 2 ) . Thus, dim N ( W 1 ) ∩ C( W 2 ) = 0 ⇔ dim span N ( W 1 ) ∪ C( W 2 ) < k ⇔ ∃ a = 0 such that a ⊥ C( W 2 ), and a ⊥ N ( W 1 ) ⇔ ∃ a = 0 such that a ∈ N ( W T 2 ), and a ∈ C( W T 1 ) ⇔ dim N ( W T 2 ∩ C( W T 1 ) = 0, which completes the proof.

The next result shows that if the conditions in Lemma 16 hold, then rank(W 1 ) = rank(W 2 ). Moreover, for r rank (W 1 W 2 ), the last n -r rows of U T W 1 and last n -r columns of W 2 V are all zeros, where the columns of U ∈ R m×m and the columns of V ∈ R n×n are respectively the left and right singular vectors of the product

W 1 W 2 . Lemma 17. Let W 1 ∈ R m×k , W 2 ∈ R k×n with k < min{m, n} and let r rank(W 1 W 2 ). Assume further that W 1 W 2 = U ΣV T is an SVD decomposition of W 1 W 2 with U ∈ R m×m , and V ∈ R n×n , and Σ ∈ R m×n . If      i) ∃ W 1 ∈ R m×k such that W 1 W 2 = 0 and W 1 + W 1 is full column rank. and ii) ∃ W 2 ∈ R k×n such that W 1 W 2 = 0 and W 2 + W 2 is full row rank.

then rank(W 1 ) = rank(W 2 ), W 2 V :,r+1:n = 0, and U T W 1 r+1:n,: = 0.

Proof. Suppose that ii) holds, then

EQUATION

Also,

EQUATION

From inequalities ( 22) and ( 23), we get

EQUATION

Similarly, condition i) implies

EQUATION

Also,

k = rank(W 1 + W 1 ) ≤ rank(W 1 ) + rank( W 1 ).

(26) From inequalities ( 25) and ( 26), we get

k -rank(W 1 ) ≤ rank( W 1 ) ≤ k -rank(W 2 ) ⇒ rank(W 1 ) ≥ rank(W 2 ).

(27) From inequalities ( 24) and ( 27), we get rank(W 1 ) = rank(W 2 ), which combined with Lemma 16 implies dim

N ( W 1 ) ∩ C( W 2 ) = 0. Let r rank(W 1 W 2 ). It directly follows from the SVD decomposition of the matrix W 1 W 2 , that U T W 1 W 2 V ) :,r+1:n = Σ :,r+1:n = 0, or equivalently W 1 W 2 V :,r+1:n = 0. On the other hand, since C W 2 V :,r+1:n ⊂ C W 2 and N W 1 ∩ C W 2 = ∅, we conclude that W 2 V ) :,r+1:n = 0.

Similarly, one can show that U T W 1 ) r+1:n,: = 0.

Proposition 18. Let M(W 1 , W 2 ) = W 1 W 2 be the matrix product mapping with W 1 ∈ R m×k , W 2 ∈ R k×n , and k < min{m, n}. Then, M(•, •) is locally open in its range R M

{Z ∈ R m×n : rank(Z) ≤ k} at the point ( W1 , W2 ) if and only if the following two conditions are satisfied:

     i) ∃ W 1 ∈ R m×k such that W 1 W2 = 0 and W1 + W 1 is full column rank. and ii) ∃ W 2 such that W1 W 2 = 0 and W2 + W 2 is full row rank.

Proof. First of all, according to Lemma 14 and Lemma 15, without loss of generality we can assume that the matrix product W1 W2 is of diagonal form.

Let us start by first proving the "only if" direction. Notice that the result clearly holds when rank( W1 ) = rank( W2 ) = k by choosing W 1 = W 2 = 0. Moreover, the mapping M(•, •) cannot be locally open if only one of the matrices W1 or W2 is rank deficient. To see this, let us assume that W1 is full column rank, while W2 is rank deficient. Assume further that the mapping M(•, •) is locally open at ( W1 , W2 ), it follows from the definition of openness that the mapping

EQUATION

2 ) where W1 2 ( W2 ) :,1:k only contains the first k columns of W2 . Since the range of the mapping M 1 at ( W1 , W1

2 ) is the entire space R m×k , Proposition 4 implies that

     ∃ W 1 such that W 1 W1 2 = 0 and W1 + W 1 is full row rank. or ∃ W 1 2 such that W1 W 1 2 = 0 and W1 2 + W 1 2 is full rank.

Moreover, since W1 ∈ R m×k and m > k, it is impossible for W 1 + W1 to be full row rank. On the other hand, since W1 is full column rank, W1 W 1 2 = 0 implies that W 1 2 = 0; and hence W1 2 + W 1 2 is not full column rank. Hence none of the above two conditions can hold and consequently, M(•, •) cannot be open at the point ( W1 , W 1 2 ) in this case. Similarly, we can show that when W1 is rank deficient and W2 is full row rank, the mapping M(•, •) cannot be locally open. Hence, if W1 and W2 are not both full rank, then they both should be rank deficient.

Assume that the matrices W1 and W2 are both rank deficient and

EQUATION

2 ). By Proposition 4, and since there does not exist

W 1 such that W1 + W 1 is full row rank, there should exist W 1 2 such that W1 W 1 2 = 0 and W1 2 + W 1 2 is full rank. Defining W 2

W 1 2 0 , we satisfy the desired condition ii).

Similarly, by looking at the transpose of the mapping M, we can show that condition i) is true when M is locally open.

We now prove the "if" direction. Suppose i) and ii) hold, i.e.,   

 :

∃ W 1 such that W 1 W2 = 0 and W1 + W 1 is full column rank. and ∃ W 2 such that W1 W 2 = 0 and W2 + W 2 is full row rank.

Let Σ = W1 W2 = [ Σ :,1:r 0 ] be a rank r matrix. Lemma 17 implies that rank( W1 ) = rank( W2 ), and the last n -r columns of W2 are all zeros. We need to show that for any given > 0, there exists δ > 0, such that

IB δ W1 W2 ∩ R M ⊆ M IB W1 , IB W2 .

Consider a perturbed matrix Σ ∈ IB δ Σ ∩ R M , we show that Σ ∈ M IB W1 , IB W2 . Without loss of generality, and by permuting the columns of Σ if necessary, Σ can be expressed as

Σ = Σ :,1:r + R 1 δ m×r R 2 δ m×(k-r) (Σ :,1:r + R 1 δ )A 1 + R 2 δ A 2 m×(n-k)

.

Here

A 1 ∈ R r×(n-k) and A 2 ∈ R (k-r)×(n-k) exist since rank( Σ)≤ k. Moreover, Σ -Σ ≤ δ implies that the perturbed matrix R δ R 1 δ R 2 δ (Σ :,1:r + R 1 δ )A 1 + R 2 δ A 2 has norm less than or equal δ, i.e. R δ ≤ δ.

Since rank( W2 + W 2 ) = k, there exist a unitary basis set { w1 2 , . . . , wk-r 2 } for W 2 such that span{ w1 2 , . . . , wk-r

EQUATION

and let us form the matrix W1 2 ∈ R k×k using the first k columns of W2 . Since the last n -r columns of the matrix

W2 are zero, W 1 2 + W1 2 is a full rank k × k matrix and W1 W 1 2 = 0. Let us define W0 1 R 1 δ R 2 δ ( W 1 2 + W1 2 ) -1 , and W0 2 W 1 2 W1 2 + W 1 2 :,1:r A 1 + W1 2 + W 1 2 :,r+1:k A 2 .

Using this definition, we have

EQUATION

)

To complete the proof, it remains to show that for any > 0, we can choose δ small enough such that W0 1 ≤ and W0 2 ≤ . In other words, we will show Σ ∈ M IB W1 , IB W2 .

Let r, with k ≥ r ≥ r, be the rank of Σ. According to Lemma 13 and by possibly permuting the columns, Σ can be expressed as

Σ = Σ1 Σ1 Ā ,

where Σ1 ∈ R m×r is full column rank, and Ā has a bounded norm Ā ≤ n2 n-r-1 . Notice that for given W0 1 and W0

2 satisfying (29), permuting the columns of Σ corresponds to permuting the columns of ( W2 + W0

2 ). If we can show that the first r columns are not among the permuted ones, then using the fact that W2 has only its first r columns non-zero, it follows that the permutation of the columns of Σ corresponds to the same permutation of the columns of W0

2 . Moreover, if the first r columns are not among the permuted ones, then without loss of generality we can express the perturbed matrix

Σ = Σ :,1:r + R 1 δ m×r R 2 δ m×(k-r) (Σ :,1:r + R 1 δ ) Ā1 + R 2 δ Ā2 m×(n-k)

, and the perturbation matrix

R δ = R 1 δ m×r R 2 δ m×(k-r) (Σ :,1:r + R 1 δ ) Ā1 + R 2 δ Ā2 m×(n-k)

, where Ā1 Ā2 = Ā has a bounded norm.

We now show that the first r columns of Σ before permutation Σ :,1:r + R 1 δ ⊆ Σ1 . Assume the contrary, then there exists at least a column Σ :,j + R 1 δ :,j that is not a column of Σ1 , which implies Σ :,j + R 1 δ :,j is a column of Σ1 Ā. Without loss of generality let Σ :,j + R 1 δ :,j = Σ1 Ā:,1 . It follows that Σ j,j + R 1 δ j,j = ( Σ1 ) j,: Ā:,1 .

But since Σ j,j + R 1 δ j,j is a non-zero perturbed singular value, and since elements of ( Σ1 ) j,: are all of order δ, then by choosing δ sufficiently small, we get Ā > 2 n-r-1 , which contradicts the bound we have on Ā.

We now obtain an upper-bound on W0

2 . Since the norm of Ā is bounded, the norm of Ā2 is also bounded by some constant K n2 n > n2 n-r-1 . Hence,

δ ≥ R δ ≥ (Σ :,1:r + R 1 δ ) Ā1 + R 2 δ Ā2 ≥ (Σ :,1:r + R 1 δ ) Ā1 -R 2 δ Ā2 ≥ (Σ :,1:r + R 1 δ ) Ā1 -Kδ ≥ σ min 2 Ā1 -Kδ,

where σ min is the minimum singular value of the full column rank matrix Σ :,1:r which is bounded away from zero.

Here, we have chosen δ < σ min /2 so that (Σ :,1:r + R 1 δ ) Ā1 ≤ σ min 2 Ā1 . Rearranging the terms, we obtain

Ā1 ≤ 2(1 + K)δ σ min .

Thus, for some constant C W1 2 , we obtain

W0 2 2 ≤ W 1 2 2 + W1 2 2 Ā1 2 + W 1 2 2 Ā2 2

(by triangular inequality and Cauchy Shwarz)

≤ 2 4n 2 2 2n + 2 K 2 4n 2 2 2n + δ 2 C 2 2 + 2K σ min 2 ≤ 2 4K 2 + 2 K 2 4K 2 + δ 2 C 2 2 + 2K σ min 2 ≤ 2 /2 + δ 2 C 2 2 + 2K σ min 2 .

For a given > 0, choose

δ ≤ min            1 + max ( W1 2 + W 1 2 ) -1 , √ 2 C 2 + 2K σ min , σ min /2            . This choice of δ leads to W0 2 ≤ . Moreover, W0 1 ≤ R δ (W 1 2 + W 1 2 ) -1 ≤ δ (W 1 2 + W 1 2 ) -1 ≤ (W 1 2 + W 1 2 ) -1 1 + (W 1 2 + W 1 2 ) -1 ≤ ,

which completes the proof.

We now use Proposition 18, Lemma 16, and Lemma 17 to complete the proof of Theorem 5 restated below.

Theorem 5 [Restated]: Let M(W 1 , W 2 ) = W 1 W 2 denote the matrix multiplication mapping with W 1 ∈ R m×k and W 2 ∈ R k×n . Assume k < min{m, n}. Then if rank( W1 ) = rank( W2 ), M(•, •) is not locally open at ( W1 , W2 ). Else, if rank( W1 ) = rank( W2 ), then the following statements are equivalent:

i) ∃ W 1 ∈ R m×k such that W 1 W2 = 0 and W1 + W 1 is full column rank. ii) ∃ W 2 ∈ R k×n such that W1 W 2 = 0 and W2 + W 2 is full row rank. iii) dim N ( W1 ) ∩ C( W2 ) = 0. iv) dim N ( WT 2 ) ∩ C( WT 1 ) = 0. v) M(•, •) is locally open at ( W1 , W2 ) in its range R M = {Z ∈ R m×n with rank(Z) ≤ min{m, k, n}}.

Proof. First of all, if M(•, •) is locally open at ( W1 , W2 ), according to Proposition 18, the conditions i) and ii) must hold; and hence rank( W1 ) = rank( W2 ) due to Lemma 17. Thus, M(•, •) cannot be locally open if rank( W1 ) = rank( W2 ). On the other hand, when rank( W1 ) = rank( W2 ), the conditions i), ii), iii), and iv) are equivalent due to Lemma 16. Moreover, these conditions imply local openness according to Proposition 18.

matrices Āv for every v ∈ V. For instance, if h = 5 and V = {2, 3, 5}, then f ( ĀV , W-V ) = Ā5 W4 Ā3 Ā2 W1 X.

We now determine index sets V, with |V| ≥ 1, that correspond to non-zero f ( ĀV , W-V ). First note by definition of Ā, if V ∩ {k * -1, . . . , 2} = ∅, then f ( ĀV , W-V ) = 0. Also by (34), for any k

* ≤ v ≤ h -1, if v ∈ V then either {k * , . . . , h} ∈ V or f ( ĀV , W-V ) = 0. This directly imply that Āh • • • Āk * Wk * -1 • • • W1 X and Āh • • • Āk * Wk * -1 • • • W2 Ā1

X are the only terms that can take non-zero values. Using the definition equation ( 32) we obtain

g(t) = 1 2 t h-k * +1 Āh • • • Āk * Wk * -1 • • • W1 X + t h-k * +2 Āh • • • Āk * Wk * -1 • • • W2 Ā1 X + ∆ 2 . It follows that ∂ r g(t) ∂t r t=0 = 0 for all r ≤ h -k * . and ∂ h-k * +1 g(t) ∂t h-k * +1 t=0 = (h -k * + 1)! Āh • • • Āk * Wk * -1 • • • W1 X, ∆ . If Āh • • • Āk * Wk * -1 • • • W1 X, ∆ = 0, then by properly choosing the sign of α h such that Āh • • • Āk * Wk * -1 • • • W1 X, ∆ < 0, we get a descent direction. Otherwise, we examine ∂ h-k * +2 g(t) ∂t h-k * +2 t=0 = (h -k * + 2)! Āh • • • Āk * Wk * -1 • • • W2 Ā1 X, ∆ + h( Āh • • • Āk * Wk * -1 • • • W1 X). where h(•) is a function of Āh • • • Āk * Wk * -1 • • • W1 X.

We now evaluate the term Āh

• • • Āk * Wk * -1 • • • W2 Ā1 X, ∆ . Since ( Āh ) l,:

= 0 for all l = j and ( Ā1 ) :,l = 0 for all l = i, we only need to compute the (j

, i) index Āh • • • Āk * Wk * -1 • • • W2 Ā1 (j,i) as all other indices are zero. For some constant c = p T h b h-1 p T h-1 b h-2 • • • p T k * +1 b k * b T b, we obtain Āh • • • Āk * Wk * -1 • • • W2 Ā1 (j,i) = α h α 1 p T h b h-1 p T h-1 b h-2 • • • p T k * +1 b k * b T Wk * -1 • • • W2 b 1 = α h α 1 p T h b h-1 p T h-1 b h-2 • • • p T k * +1 b k * b T b = α h α 1 c,

where c is non-zero by our choice of b, p k and b k-1 for h ≤ k ≤ k * -1 as defined in (33). For a fixed α

h = 0, h( Āh • • • Āk * Wk * -1 • • • W1 X)

is a constant scalar we denote by c α . Then by properly choosing α 1 such that

α h =0 α 1 c =0 X i,: , ∆ j,: =0 +c α < 0,

we get a descent direction. This completes the first case.

Case b: Assume K is empty. We consider

( Āh ) l,: α h p T h if l = j, 0 otherwise ( Ā1 ) :,l α 1 b 1 if l = i, 0 otherwise Āk b k p T k if 3 ≤ k ≤ h -1 b k b T 1 if k = 2,

where α h and α 1 are scalar constants, b 1 ∈ N W2 , and

EQUATION

For this particular choice of Ā = ( Āh , . . . , Ā1 ), we obtain

Wk+1 Āk = 0 for 2 ≤ k ≤ h -1 and Āk Wk-1 • • • W2 = 0 for 3 ≤ k ≤ h.

We now determine index sets V, with V ≥ 1, that correspond to non-zero f ( ĀV , W-V ). By (35), for any 2 ≤ v ≤ h -1, if v ∈ V then either {2, . . . , h} ∈ V or f ( ĀV , W-V ) = 0. This directly imply that Āh • • • Ā2 W1 X and Āh • • • Ā1 X are the only terms that can take non-zero values. Using the definition of equation ( 32) we obtain

g(t) = 1 2 t h-1 Āh • • • Ā2 W1 X + t h Āh • • • Ā1 X + ∆ 2 . It follows that ∂ r g(t) ∂t r t=0 = 0 for all r ≤ h -2. and ∂ h-1 g(t) ∂t h-1 t=0 = (h -1)! Āh • • • Ā2 W1 X, ∆ .

If Āh • • • Ā2 W1 X, ∆ = 0, then by properly choosing the sign of α h such that Āh • • • Ā2 W1 X, ∆ < 0, we get a descent direction. Otherwise, we examine

∂ h g(t) ∂t h t=0 = Āh • • • Ā1 X, ∆ + h( Āh • • • Ā2 W1 X), where h(•) is a function of Āh • • • Ā2 W1 X.

We now evaluate the term Āh • • • Ā1 X, ∆ . Since ( Āh ) l,: = 0 for all l = j and ( Ā1 ) :,l = 0 for all l = i, we only need to compute the (j, i) index Āh • • • Ā1 (j,i) as all other indices are zero. For some constant c

= p T h b h-1 p T h-1 b h-2 • • • p T 3 b 2 b T 1 b 1 , we obtain Āh • • • Ā1 (j,i) = α h α 1 p T h b h-1 p T h-1 b h-2 • • • p T 3 b 2 b T 1 b 1 = α h α 1 c,

where c is non-zero by our choice of b, p k and b k-1 for 3 ≤ k ≤ h as defined in (35). For a fixed α h = 0, h( Āh • • • Ā2 W1 X) is a constant scalar we denote by c α . Then by properly choosing α 1 such that

α h =0 α 1 c =0 X i,: , ∆ j,: =0 +c α < 0,

we get a descent direction. This completes the second case.

Now if N WT:

1 is non-empty, we define the set

K {k | 1 ≤ k ≤ h -2, N ( Wh-1 • • • Wk+1 ) ⊥ N ( WT k )}

, and use a similar proof scheme to show the result. More specifically, we split the proof into two cases that correspond to K being empty and non-empty. 

EQUATION

we examine the optimality conditions for a specific direction where the last equality holds since the last row (d th h row) of Z3 and the last column (d th 0 column) of Z1 are both zeros. Then for Ā2 = 0, it follows from the second-order optimalty condition that the point is a local minimum, and if Ā2 = 0 we get g(t) = 1 2 Ȳ = 1 2 which implies ( Z3 , Z2 , Z1 ) is a local optimum that is not global.

Note that the same method used to construct the example above can be used to find a local minimum that is not global whenever the rank(Y ) ≤ min{d h -d p2 , d 0 -d p1 }. When Y is full rank, we know from the results of Lu & Kawaguchi (2017) ; Yun et al. (2017) that every local minimum is global. To have a complete characterization of problems for which every local minimum is global, it remains to either prove or disprove the statement when Y is a rank deficient matrix with rank(Y ) > min{d h -d p2 , d 0 -d p1 }. We now provide a counterexample that disproves the statement. In particular, we construct a three layer network with input X and output Y with rank(Y ) > min{d h -d p2 , d 0 -d p1 }, and then find a local minimum ( W3 , W2 , W1 ) that is not global. Let X = I, 

EQUATION

= W3 W2 A 1 + W3 A 2 W1 + A 3 W2 W1 , ∆ = 0,

where the last equality is directly implied from (46). Also

g (2) (0, A) ∂ 2 g(t, A) ∂t 2 t=0 = 2 A 3 A 2 W1 + A 3 W2 A 1 + W3 A 2 A 1 , ∆ + W3 W2 A 1 + W3 A 2 W1 + A 3 W2 W1 2 = 2 A 3 W2 A 1 , ∆ + W3 W2 A 1 + W3 A 2 W1 + A 3 W2 W1 2 .

which is a quadratic function of A we denote

f A 1 2 a T H A a.

Here a ∈ R 16×1 is a vectorization of matrices A 3 , A 2 , and A 1 , and H A is the hessian of f A . By computing the eigenvalues of H A we get that H A 0 which directly implies g (2) (0, A) ≥ 0 ∀A.

Moreover, let a opt be the optimal solution set of the problem minimize a f A .

Then a opt = {a | a ∈ N (H a }. We notice that for any ā ∈ a opt , the corresponding direction Ā has W3 W2 Ā1 + W3 Ā2 W1 + Ā3 W2 W1 = 0 and Ā3 Ā2 Ā1 , ∆ = 0.

Then, it follows that If Ā3 Ā2 W1 + Ā3 W2 Ā1 + W3 Ā2 Ā1 = 0, then using the fourth order optimality conditions ( W3 , W2 , W1 ) is a local minimum. Otherwise, we get g (5) (0, Ā) ∂ 5 g(t, Ā) ∂t 5 t=0 = 0, and g (6) (0, Ā) ∂ 5 g(t, Ā) ∂t 5 t=0 = Ā3 Ā2 Ā1 2 ≥ 0, which also implies that ( W3 , W2 , W1 ) is a local minimum.

We now show that if d p * 2 ≥ min{d h , d 0 }, every local minimum of (30) is global. In particular, we show that for any X and Y , if W is not a global minimum, we can construct a descent direction.

First notice that if for some 1 ≤ i ≤ h -1, Wi is full column rank, then using Proposition 4, M i+1,i (•) is locally open at ( Wi+1 , Wi ) and Wi+1 Wi ∈ R di+1×di-1 . Using Observation 1, we conclude that any local minimum of problem (30) is a local minimum of the problem obtained by replacing Wi+1 Wi by Zi+1,i ∈ R di+1×di-1 . By a similar argument, we conclude that if Wi is a full row rank for some 2 ≤ i ≤ h, any local minimum of problem ( 30) is a local minimum of the problem obtained by replacing Wi Wi-1 by Zi,i-1 ∈ R di×di-2 . Thus, if W = ( Wh , . . . , W1 ) is a local minimum of problem (30), the new point Z = ( Z h , . . . , Z 1 ), where Zi ∈ R d i ×d i-1 and h ≤ h, is a local minimum of the problem attained by applying the replacements discussed above. If h = 1, we get the desired result from Lemma 7. Else, if h = 2, the auxiliary problem becomes a two layer linear network for which Theorem 8 provides the desired result. 

:



Figures and Tables:

Observation 1. Suppose F(•) is locally open at w. If w is a local minimum of problem (5), then s = F( w) is a local minimum of problem (6).

Figure 1: Sketch of the Proof of Observation 1.

Figure 2: Two local minima w = -1 and w = +1 in (a) are mapped to a single local minimum z = 1 in (b).

Figure 3: All the points in the set {(w 1 , w 2 ) | w 1 w 2 = 1} are local minima in (a) and are mapped to a single local minimum z = 1 in (b).

rank one and hence feasible perturbation. However, for any perturbation W1 = 1 2 and W2 = [ 3 , 4 ], we have

e. rank( W2 W1 ) = min{d 2 , d 1 , d 0 }. Then it follows by Lemma 10 that the matrix multiplication M(•, •) is locally open at ( W2 , W1 ). Then by Observation 1, Z = W2 W1 is a local optimum of problem (12) which is in fact global by Lemma 7.

locally open at W . Since the composition of locally open maps is locally open, the result follows.

Case a: Assume K is non-empty. We define k * minimum k∈K k.By definition of the set K and choice of k * , the null space N WT

k

Z3 Ā2 Z1 , -Ȳ = -Z3 Ā2 Z1 d h ,d0 Ȳd h ,d0 = 0,(44)where the last equality holds since the last row (d th h row) of Z3 is zero. Also, -2 Z3 Ā2 Ā1 d h ,d0 Ȳd h ,d0 -2 Ā3 Ā2 Z1 d h ,d0 Ȳd h ,d0 + Z3 Ā2 Z1

local optimum of a 3-layer deep linear model problem (2) with h = 3 that is not a global optimum. However, we will show that if a given local optimum is non-degenerate (which is a simple checkable condition), the full rankness of Y can be relaxed. Moreover, for degenerate local optima, we show that if there exist 1 ≤ p 1 < p 2 ≤ h -1 with d h > d p2 and d 0 > d p1 , we can find Y and X such that problem (2) has a local minimum that is not global. Otherwise, given any X and Y , we present a method for constructing a descent direction from any given degenerate critical point that is not a global optimum; thus we show every degenerate local minimum is global.

Table content: <table/>

Open mapping: A mapping F : W → S is said to be open, if for every open set U ∈ W, F(U ) is (relatively) open in S. • Locally open mapping: A mapping F(•) is said to be locally open at w if for every > 0, there exists δ > 0 such that B δ F(w) ⊆ F B (w) . Here B δ (w) ⊆ W is an open ball with radius δ centered at w, and B (F(w)) ⊆ S is the ball of radius centered at F(w). definition, openness of a mapping is stronger than local openness. Furthermore, it is not hard to see that a mapping is locally open everywhere if and only if it is open. A useful property of (locally) open mappings is that the composition of two (locally) open maps is (locally) open.

Table content: <table><tr><td>By</td></tr></table>

Using the composition property of open maps and strict monotonicity of σk (•), we get F k (W i ) ki=1 is locally open at W i

Table content: <table><tr><td>k i=1 .</td></tr></table>

, Theorem 2.2), we provide in Lemma 11 a more intuitive proof that uses local openness of M. Moreover, Theorem 12 extends the result to degenerate critical points. Lemma 11. Every non-degenerate local minimum of (13) is global minimum.Proof. Suppose W = (W h , . . . , W 1 ) is a non-degenerate local minimum. Then it follows by Lemma 10 that M h,1 is locally open at W . Then by Lemma 1, Z = M h (W h , . . . , W 1 ) is a local optimum of problem (14) which is in fact global by Lemma 7. If d p2 * < min{d h , d 0 }, we can find a rank deficient Y such that problem (30) has a local minimum that is not global. Otherwise, given any X and Y , every local minimum of problem (30) is a global minimum.The proof of Theorem 12 can be found in Appendix C.Proof. The proof for the degenerate case is done by constructing a descent direction if the point is critical but not global. Let ( W2 , W1 ) be a degenerate critical point, i.e. rank( W2 W1 ) < min{d 2 , d 1 , d 0 }. Then, based on the dimensions of d 0 , d 1 , and d 2 , we have one of the following cases:

Table content: <table><tr><td>We now state the desired result for degenerate critical points. Theorem 12. Let p  *  1 argmin 0≤i≤h d i and p  *  2 argmin 1 j =p  *  A PROOF OF THEOREM 8, COROLLARY 9 AND LEMMA 10 d j . Appendix A.1 PROOF OF THE THEOREM 8</td></tr></table>

d p , then using Proposition 4, we get M p+1,p (•) is locally open at (W p+1 , W p ). So we can replace W p+1 W p by a new matrix Z p with rank d p .

Table content: <table/>

Ā.of open maps, the matrix product mapping M p2,p1+1 is locally open at ( Wp2 , . . . , Wp1+1 ). It follows by Observation1 that if W is a local minimum of minimize • • • W 1 -Ȳ 2 . (41) then ( Z3 , Z2 , Z1 ) is a local minimum of minimize Z3∈R d h ×dp 2 , Z2∈R dp 2 ×dp 1 , Z1∈R dp 1 ×d 0 Z2 = 0, and Z1 = Wp1 • • • W1 = I dp 1 0 .The point ( Z3 , Z2 , Z1 ) is obviously not global, we show using optimality conditions that the point is a local minimum. By considering perturbations in the directions Ā = ( Ā3 , Ā2 , Ā1 ) for the optimization problem

Table content: <table><tr><td/><td>W</td><td>1 2</td><td>W h 1 2</td><td>Z 3 Z 2 Z 1 -Ȳ 2 .</td><td>(42)</td></tr><tr><td>where</td><td/><td/><td/><td/></tr><tr><td colspan="5">Z3 = Wh • • • Wp2+1 = , minimize I dp 2 0 t g(t) 1 2 ( Z3 + t Ā3 )( Z2 + t Ā2 )( Z1 + t Ā1 ) -Ȳ 2</td></tr><tr><td/><td/><td/><td/><td/><td>(43)</td></tr><tr><td>=</td><td>1 2</td><td colspan="3">t( Z3 + t Ā3 ) Ā2 ( Z1 + t Ā1 ) -Ȳ 2 .</td></tr><tr><td>It follows that</td><td/><td/><td/><td/></tr><tr><td>∂g(t)</td><td/><td/><td/><td/></tr><tr><td>∂t</td><td/><td/><td/><td/></tr></table>

By considering perturbations in the directionsA = (A 3 , A 2 , A 1 ) for the optimization problem tA 3 )( W3 + tA 2 )( W1 + tA 1 ) -Y 2 ,

Table content: <table><tr><td colspan="2">minimize t ( W3 + it follows that g(t, A) 1 2</td><td/></tr><tr><td>∂g(t, A)</td><td/><td/></tr><tr><td>∂t</td><td>t=0</td><td/></tr><tr><td/><td>1 1 1</td><td>, and W1</td><td>WT 3 .</td></tr></table>

When h > 2, examine d h , d h -1 , d 1 and d 0 . If d h > d h -1 and d 0 > d 1 , then d p * 2 < min{d h , d 0 } which contradicts our assumption. It follows by construction of Zi , that either d h ≤ d h -1 and Z h is not full row rank or d 0 ≤ d 1 and Z 1 is not full column rank; thus at least one of the null spaces N ( Z h ) T , N Z 1 is non empty. Moreover, Zi has non-empty right and left null spaces for 2 ≤ i ≤ h -1. The result follows using Lemma 19.

Table content: <table/>

Peer review (iclr2018):
 Summary: The paper focuses on the characterization of the landscape of deep neural networks; i.e., when and why local minima are global, what are the conditions for saddle critical points, etc. The paper covers a somewhat wide range of deep nets (from shallow with linear activation to deeper with non-linear activation); it focuces only on feed forward neural networks. As the authors state, this paper provides a unifying perspective to the subject (it justifies the results of others through this unifying theory, but also provides new results; e.g., there are results that do not depend on assumptions on the target data matrix Y). Originality: The paper provides similar results to previous work, while removing some of the assumptions made in previous work. In that sense, the originality of the results is weak, but definitely there is some novelty in the methodology used to get to these results. Thus, I would say original. Importance: The paper deals with the important problem of when and why training algorithms might get to global/local/saddle critical points. While there are no direct connections with generalization properties, characterizing the landscape of neural networks is an important topic to make further steps into better understanding of deep learning. It will attract some attention at the conference. Clarity: The paper is well-written - some parts need improvement, but overall I*m satisfied with the current version. Comments: 1. If problem (4) is not considered at all in this paper (in its full generality that considers matrix completion and matrix sensing as special cases), then the authors could just start with the model in (5). 2. Remark 1 has a nice example - could this example be shown with Y not being the all-zeros vector? 3. In section 5, the authors make a connection with the work of Ge et al. 2016. They state that the problems in (10)-(11) constitute generalizations of the symmetric matrix completion case, considered in Ge et al. 2016. However, in that work, the main difficulty of proving global optimality comes from the randomness of the sampling mask operator (which introduces the notion of incoherence and requires results in expectation). It is not clear, and maybe it is an overstatement, that the results in section 5 generalize that work. If that is the case, could the authors describe this a bit further?