Deep Learning without Poor Local Minima

Introduction

Deep learning has been a great practical success in many fields, including the fields of computer vision, machine learning, and artificial intelligence. In addition to its practical success, theoretical results have shown that deep learning is attractive in terms of its generalization properties (Livni et al.,, 2014; Mhaskar et al.,, 2016). That is, deep learning introduces good function classes that may have a low capacity in the VC sense while being able to represent target functions of interest well. However, deep learning requires us to deal with seemingly intractable optimization problems. Typically, training of a deep model is conducted via non-convex optimization. Because finding a global minimum of a general non-convex function is an NP-complete problem (Murty & Kabadi,, 1987), a hope is that a function induced by a deep model has some structure that makes the non-convex optimization tractable. Unfortunately, it was shown in 1992 that training a very simple neural network is indeed NP-hard (Blum & Rivest,, 1992). In the past, such theoretical concerns in optimization played a major role in shrinking the field of deep learning. That is, many researchers instead favored classical machining learning models (with or without a kernel approach) that require only convex optimization. While the recent great practical successes have revived the field, we do not yet know what makes optimization in deep learning tractable in theory.

In this paper, as a step toward establishing the optimization theory for deep learning, we prove a conjecture noted in (Goodfellow et al.,, 2016) for deep linear networks, and also address an open problem announced in (Choromanska et al.,, 2015b) for deep nonlinear networks. Moreover, for both the conjecture and the open problem, we prove more general and tighter statements than those previously given (in the ways explained in each section).

Deep linear neural networks

Given the absence of a theoretical understanding of deep nonlinear neural networks, Goodfellow et al., (2016) noted that it is beneficial to theoretically analyze the loss functions of simpler models, i.e., deep linear neural networks. The function class of a linear multilayer neural network only contains functions that are linear with respect to inputs. However, their loss functions are non-convex in the weight parameters and thus nontrivial. Saxe et al., (2014) empirically showed that the optimization of deep linear models exhibits similar properties to those of the optimization of deep nonlinear models. Ultimately, for theoretical development, it is natural to start with linear models before working with nonlinear models (as noted in Baldi & Lu,, 2012), and yet even for linear models, the understanding is scarce when the models become deep.

We consider one of the most widely used loss functions, squared error loss:

where $\|\cdot\|_{F}$ is the Frobenius norm. Note that $\frac{2}{m}\mathcal{\bar{L}}(W)$ is the usual mean squared error, for which all of our results hold as well, since multiplying $\mathcal{\bar{L}}(W)$ by a constant in $W$ results in an equivalent optimization problem.

2 Background

Recently, Goodfellow et al., (2016) remarked that when Baldi & Hornik, (1989) proved Proposition 2.1 for shallow linear networks, they stated Conjecture 2.2 without proof for deep linear networks.

(Baldi & Hornik,, 1989: shallow linear network) Assume that $H=1$ (i.e., $\overline{Y}(W,X)=W_{2}W_{1}X$), assume that $XX^{T}$ and $XY^{T}$ are invertible, assume that $\Sigma$ has $d_{y}$ distinct eigenvalues, and assume that $p<d_{x}$, $p<d_{y}$ and $d_{y}=d_{x}$ (e.g., an autoencoder). Then, the loss function $\mathcal{\bar{L}}(W)$ has the following properties:

It is convex in each matrix $W_{1}$ (or $W_{2}$) when the other $W_{2}$ (or $W_{1}$) is fixed.

(Baldi & Hornik,, 1989: deep linear network) Assume the same set of conditions as in Proposition 2.1 except for $H=1$. Then, the loss function $\mathcal{\bar{L}}(W)$ has the following properties:

For any $k\in\{1,\dotsc,H+1\}$, it is convex in each matrix $W_{k}$ when for all $k^{\prime}\neq k$, $W_{k^{\prime}}$ is fixed.

Baldi & Lu, (2012) recently provided a proof for Conjecture 2.2 (i), leaving the proof of Conjecture 2.2 (ii) for future work. They also noted that the case of $p\geq d_{x}=d_{x}$ is of interest, but requires further analysis, even for a shallow network with $H=1$. An informal discussion of Conjecture 2.2 can be found in (Baldi,, 1989). In Appendix D, we provide a more detailed discussion of this subject.

3 Results

We now state our main theoretical results for deep linear networks, which imply Conjecture 2.2 (ii) as well as obtain further information regarding the critical points with more generality.

(Loss surface of deep linear networks) Assume that $XX^{T}$ and $XY^{T}$ are of full rank with $d_{y}\leq d_{x}$ and $\Sigma$ has $d_{y}$ distinct eigenvalues. Then, for any depth $H\geq 1$ and for any layer widths and any input-output dimensions $d_{y},d_{H},d_{H-1},\dotsc,d_{1},d_{x}\geq 1$ (the widths can arbitrarily differ from each other and from $d_{y}$ and $d_{x}$), the loss function $\mathcal{\bar{L}}(W)$ has the following properties:

Every critical point that is not a global minimum is a saddle point.

If $\operatorname{rank}(W_{H}\cdots W_{2})=p$, then the Hessian at any saddle point has at least one (strictly) negative eigenvalue.If $H=1$, to be succinct, we define $W_{H}\cdots W_{2}=W_{1}\cdots W_{2}\triangleq I_{d_{1}}$, with a slight abuse of notation.

(Effect of deepness on the loss surface) Assume the same set of conditions as in Theorem 2.3 and consider the loss function $\mathcal{\bar{L}}(W)$. For three-layer networks (i.e., $H=1$), the Hessian at any saddle point has at least one (strictly) negative eigenvalue. In contrast, for networks deeper than three layers (i.e., $H\geq 2$), there exist saddle points at which the Hessian does not have any negative eigenvalue.

The assumptions of having full rank and distinct eigenvalues in the training data matrices in Theorem 2.3 are realistic and practically easy to satisfy, as discussed in previous work (e.g., Baldi & Hornik,, 1989). In contrast to related previous work (Baldi & Hornik,, 1989; Baldi & Lu,, 2012), we do not assume the invertibility of $XY^{T}$, $p<d_{x}$, $p<d_{y}$ nor $d_{y}=d_{x}$. In Theorem 2.3, $p\geq d_{x}$ is allowed, as well as many other relationships among the widths of the layers. Therefore, we successfully proved Conjecture 2.2 (ii) and a more general statement. Moreover, Theorem 2.3 (iv) and Corollary 2.4 provide additional information regarding the important properties of saddle points.

Theorem 2.3 presents an instance of a deep model that would be tractable to train with direct greedy optimization, such as gradient-based methods. If there are “poor” local minima with large loss values everywhere, we would have to search the entire space,Typically, we do this by assuming smoothness in the values of the loss function. the volume of which increases exponentially with the number of variables. This is a major cause of NP-hardness for non-convex optimization. In contrast, if there are no poor local minima as Theorem 2.3 (ii) states, then saddle points are the main remaining concern in terms of tractability.Other problems such as the ill-conditioning can make it difficult to obtain a fast convergence rate. Because the Hessian of $\mathcal{\bar{L}}(W)$ is Lipschitz continuous, if the Hessian at a saddle point has a negative eigenvalue, it starts appearing as we approach the saddle point. Thus, Theorem 2.3 and Corollary 2.4 suggest that for 1-hidden layer networks, training can be done in polynomial time with a second order method or even with a modified stochastic gradient decent method, as discussed in (Ge et al.,, 2015). For deeper networks, Corollary 2.4 states that there exist “bad” saddle points in the sense that the Hessian at the point has no negative eigenvalue. However, we know exactly when this can happen from Theorem 2.3 (iv) in our deep models. We leave the development of efficient methods to deal with such a bad saddle point in general deep models as an open problem.

Deep nonlinear neural networks

Now that we have obtained a comprehensive understanding of the loss surface of deep linear models, we discuss deep nonlinear models. For a practical deep nonlinear neural network, our theoretical results so far for the deep linear models can be interpreted as the following: depending on the nonlinear activation mechanism and architecture, training would not be arbitrarily difficult. While theoretical formalization of this intuition is left to future work, we address a recently proposed open problem for deep nonlinear networks in the rest of this section.

where $\bar{\sigma}(b_{ij})=\max(0,b_{ij})$. In practice, we usually set $\sigma_{H+1}$ to be an identity map in the last layer, in which case all our theoretical results still hold true.

2 Background

Following the work by Dauphin et al., (2014), Choromanska et al., (2015a) investigated the connection between the loss functions of deep nonlinear networks and a function well-studied via random matrix theory (i.e., the Hamiltonian of the spherical spin-glass model). They explained that their theoretical results relied on several unrealistic assumptions. Later, Choromanska et al., (2015b) suggested at the Conference on Learning Theory (COLT) 2015 that discarding these assumptions is an important open problem. The assumptions were labeled A1p, A2p, A3p, A4p, A5u, A6u, and A7p.

In this paper, we successfully discard most of these assumptions. In particular, we only use a weaker version of assumptions A1p and A5u. We refer to the part of assumption A1p (resp. A5u) that corresponds only to the model assumption as A1p-m (resp. A5u-m). Note that assumptions A1p-m and A5u-m are explicitly used in the previous work (Choromanska et al.,, 2015a) and included in A1p and A5u (i.e., we are not making new assumptions here).

Choromanska et al., (2015b) noted that A6u is unrealistic because it implies that the inputs are not shared among the paths. In addition, Assumption A5u is unrealistic because it implies that the activation of any path is independent of the input data. To understand all of the seven assumptions (A1p, A2p, A3p, A4p, A5u, A6u, and A7p), we note that Choromanska et al., (2015b, a) used these seven assumptions to reduce their loss functions of nonlinear neural networks to:

(High-level description of a main result in Choromanska et al.,, 2015a) Assume A1p (including A1p-m), A2p, A3p, A4p, A5u (including A5u-m), A6u, and A7p (Choromanska et al.,, 2015b). Furthermore, assume that $d_{y}=1$. Then, the expected loss of each sample datum, $\mathcal{L}_{\text{previous}}(W)$, has the following property: above a certain loss value, the number of local minima diminishes exponentially as the loss value increases.

3 Results

We now state our theoretical result, which partially address the aforementioned open problem. We consider loss functions for all the data points and all possible output dimensionalities (i.e., vectored-valued output). More concretely, we consider the squared error loss with expectation, $\mathcal{L}(W)=\frac{1}{2}\|E_{Z}[\hat{Y}(W,X)-Y]\|_{F}^{2}$.

(Loss surface of deep nonlinear networks) Assume A1p-m and A5u-m. Let $q=\rho^{-1}$. Then, we can reduce the loss function of the deep nonlinear model $\mathcal{L}(W)$ to that of the deep linear model $\mathcal{\bar{L}}(W)$. Therefore, with the same set of conditions as in Theorem 2.3, the loss function of the deep nonlinear model has the following properties:

Every critical point that is not a global minimum is a saddle point.

The saddle points have the properties stated in Theorem 2.3 (iv) and Corollary 2.4.

Comparing Corollary 3.2 and Proposition 3.1, we can see that we successfully discarded assumptions A2p, A3p, A4p, A6u, and A7p while obtaining a tighter statement in the following sense: Corollary 3.2 states with fewer unrealistic assumptions that there is no poor local minimum, whereas Proposition 3.1 roughly asserts with more unrealistic assumptions that the number of poor local minimum may be not too large. Furthermore, our model $\hat{Y}$ is strictly more general than the model analyzed in (Choromanska et al.,, 2015a, b) (i.e., this paper’s model class contains the previous work’s model class but not vice versa).

Proof Idea and Important lemmas

In this section, we provide overviews of the proofs of the theoretical results. Our proof approach largely differs from those in previous work (Baldi & Hornik,, 1989; Baldi & Lu,, 2012; Choromanska et al.,, 2015a, b). In contrast to (Baldi & Hornik,, 1989; Baldi & Lu,, 2012), we need a different approach to deal with the “bad” saddle points that start appearing when the model becomes deeper (see Section 2.3), as well as to obtain more comprehensive properties of the critical points with more generality. While the previous proofs heavily rely on the first-order information, the main parts of our proofs take advantage of the second order information. In contrast, Choromanska et al., (2015a, b) used the seven assumptions to relate the loss functions of deep models to a function previously analyzed with a tool of random matrix theory. With no reshaping assumptions (A3p, A4p, and A6u), we cannot relate our loss function to such a function. Moreover, with no distributional assumptions (A2p and A6u) (except the activation), our Hessian is deterministic, and therefore, even random matrix theory itself is insufficient for our purpose. Furthermore, with no spherical constraint assumption (A7p), the number of local minima in our loss function can be uncountable.

One natural strategy to proceed toward Theorem 2.3 and Corollary 3.2 would be to use the first-order and second-order necessary conditions of local minima (e.g., the gradient is zero and the Hessian is positive semidefinite).For a non-convex and non-differentiable function, we can still have a first-order and second-order necessary condition (e.g., Rockafellar & Wets,, 2009, theorem 13.24, p. 606). However, are the first-order and second-order conditions sufficient to prove Theorem 2.3 and Corollary 3.2? Corollaries 2.4 show that the answer is negative for deep models with $H\geq 2$, while it is affirmative for shallow models with $H=1$. Thus, for deep models, a simple use of the first-order and second-order information is insufficient to characterize the properties of each critical point. In addition to the complexity of the Hessian of the deep models, this suggests that we must strategically extract the second order information. Accordingly, in section 4.2, we obtain an organized representation of the Hessian in Lemma 4.3 and strategically extract the information in Lemmas 4.4 and 4.6. With the extracted information, we discuss the proofs of Theorem 2.3 and Corollary 3.2 in section 4.3.

2 Lemmas

As discussed above, we extracted the first-order and second-order conditions of local minima as the following lemmas. The lemmas provided here are also intended to be our additional theoretical results that may lead to further insights. The proofs of the lemmas are in the appendix.

(Critical point necessary and sufficient condition) $W$ is a critical point of $\mathcal{\bar{L}}(W)$ if and only if for all $k\in\{1,...,H+1\}$,

(Representation at critical point) If $W$ is a critical point of $\mathcal{\bar{L}}(W)$, then

(Block Hessian with Kronecker product) Write the entries of $\nabla^{2}\mathcal{\bar{L}}(W)$ in a block form as

(Hessian semidefinite necessary condition) If $\nabla^{2}\mathcal{\bar{L}}(W)$ is positive semidefinite or negative semidefinite at a critical point, then for any $k\in\{2,...,H+1\},$

If $\nabla^{2}\mathcal{\bar{L}}(W)$ is positive semidefinite or negative semidefinite at a critical point, then for any $k\in\{2,...,H+1\},$

(Hessian positive semidefinite necessary condition) If $\nabla^{2}\mathcal{\bar{L}}(W)$ is positive semidefinite at a critical point, then

3 Proof sketches of theorems

We now provide the proof sketch of Theorem 2.3 and Corollary 3.2. We complete the proofs in the appendix.

By case analysis, we show that any point that satisfies the necessary conditions and the definition of a local minimum is a global minimum.

Case I: $\operatorname{rank}(W_{H}\cdots W_{2})=p$ and $d_{y}\leq p$: If $d_{y}<p$, Corollary 4.5 with $k=H+1$ implies the necessary condition of local minima that $Xr=0$. If $d_{y}=p$, Lemma 4.6 with $k=H+1$ and $k=2$, combined with the fact that $\mathcal{R}(C)\subseteq\mathcal{R}(YX^{T}),$ implies the necessary condition that $Xr=0$. Therefore, we have the necessary condition of local minima, $Xr=0$ . Interpreting condition $Xr=0$, we conclude that $W$ achieving $Xr=0$ is indeed a global minimum.

Case II: $\operatorname{rank}(W_{H}\cdots W_{2})=p$ and $d_{y}>p$: From Lemma 4.6, we have the necessary condition that $C(C^{T}C)^{-}C^{T}=U_{{\bar{p}}}U_{{\bar{p}}}^{T}$ or $Xr=0$. If $Xr=0$, using the exact same proof as in Case I, it is a global minimum. Suppose then that $C(C^{T}C)^{-}C^{T}=U_{{\bar{p}}}U_{{\bar{p}}}^{T}$. From Lemma 4.4 with $k=H+1$, we conclude that $\bar{p}\triangleq\operatorname{rank}(C)=p$. Then, from Lemma 4.2, we write $W_{H+1}\cdots W_{1}=U_{{p}}U_{{p}}^{T}YX^{T}(XX^{T})^{-1}$, which is the orthogonal projection onto the subspace spanned by the $p$ eigenvectors corresponding to the $p$ largest eigenvalues following the ordinary least square regression matrix. This is indeed the expression of a global minimum.

Case III: $\operatorname{rank}(W_{H}\cdots W_{2})<p$: We first show that if $\operatorname{rank}(C)\geq\min(p,d_{y})$, every local minimum is a global minimum. Thus, we consider the case where $\operatorname{rank}(W_{H}\cdots W_{2})<p$ and $\operatorname{rank}(C)<\min(p,d_{y})$. In this case, by induction on $k=\{1,\dotsc,H+1\}$, we prove that we can have $\operatorname{rank}(W_{k}\cdots W_{1})\geq\min(p,d_{y})$ with arbitrarily small perturbation of each entry of $W_{k},\dotsc,W_{1}$ without changing the value of $\mathcal{\bar{L}}(W)$. Once this is proved, along with the results of Case I and Case II, we can immediately conclude that any point satisfying the definition of a local minimum is a global minimum.

We first prove the statement for the base case with $k=1$ by using an expression of $W_{1}$ that is obtained by a first-order necessary condition: for an arbitrary $L_{1}$,

By using Lemma 4.6 to obtain an expression of $C$, we deduce that we can have $\operatorname{rank}(W_{1})\geq\min(p,d_{y})$ with arbitrarily small perturbation of each entry of $W_{1}$ without changing the loss value.

For the inductive step with $k\in\{2,\dotsc,H+1\}$, from Lemma 4.4, we use the following necessary condition for the Hessian to be (positive or negative) semidefinite at a critical point: for any $k\in\{2,\dotsc,H+1\}$,

We use the inductive hypothesis to conclude that the first condition is false, and thus the second condition must be satisfied at a candidate point of a local minimum. From the latter condition, with extra steps, we can deduce that we can have $\operatorname{rank}(W_{k}W_{k-1}\cdots W_{1})\geq\min(p,d_{x})$ with arbitrarily small perturbation of each entry of $W_{k}$ while retaining the same loss value.

We conclude the induction, proving that we can have $\operatorname{rank}(C)\geq\operatorname{rank}(W_{H+1}\cdots W_{1})\geq\min(p,d_{x})$ with arbitrarily small perturbation of each parameter without changing the value of $\mathcal{\bar{L}}(W)$. Upon such a perturbation, we have the case where $\operatorname{rank}(C)\geq\min(p,d_{y})$, for which we have already proven that every local minimum is a global minimum. Summarizing the above, any point that satisfies the definition (and necessary conditions) of a local minimum is indeed a global minimum. Therefore, we conclude the proof sketch of Theorem 2.3 (ii).

3.2 Proof sketch of Theorem 2.3 (i), (iii) and (iv)

We can prove the non-convexity and non-concavity of this function simply from its Hessian (Theorem 2.3 (i)). That is, we can show that in the domain of the function, there exist points at which the Hessian becomes indefinite. Indeed, the domain contains uncountably many points at which the Hessian is indefinite.

We now consider Theorem 2.3 (iii): every critical point that is not a global minimum is a saddle point. Combined with Theorem 2.3 (ii), which is proven independently, this is equivalent to the statement that there are no local maxima. We first show that if $W_{H+1}\cdots W_{2}\neq 0$, the loss function always has some strictly increasing direction with respect to $W_{1}$, and hence there is no local maximum. If $W_{H+1}\cdots W_{2}=0$, we show that at a critical point, if the Hessian is negative semidefinite (i.e., a necessary condition of local maxima), we can have $W_{H+1}\cdots W_{2}\neq 0$ with arbitrarily small perturbation without changing the loss value. We can prove this by induction on $k=2,\dotsc,H+1$, similar to the induction in the proof of Theorem 2.3 (ii). This means that there is no local maximum.

Theorem 2.3 (iv) follows Theorem 2.3 (ii)-(iii) and the analyses for Case I and Case II in the proof of Theorem 2.3 (ii); when $\operatorname{rank}(W_{H}\cdots W_{2})=p$, if $\nabla^{2}\mathcal{\bar{L}}(W)\succeq 0$ at a critical point, $W$ is a global minimum.

3.3 Proof sketch of Corollary 3.2

Since the activations are assumed to be random and independent, the effect of nonlinear activations disappear by taking expectation. As a result, the loss function $\mathcal{L}(W)$ is reduced to $\mathcal{\bar{L}}(W)$.

Conclusion

In this paper, we addressed some open problems, pushing forward the theoretical foundations of deep learning and non-convex optimization. For deep linear neural networks, we proved the aforementioned conjecture and more detailed statements with more generality. For deep nonlinear neural networks, when compared with the previous work, we proved a tighter statement (in the way explained in section 3) with more generality ($d_{y}$ can vary) and with strictly weaker model assumptions (only two assumptions out of seven). However, our theory does not yet directly apply to the practical situation. To fill the gap between theory and practice, future work would further discard the remaining two out of the seven assumptions made in previous work. Our new understanding of the deep linear models at least provides the following theoretical fact: the bad local minima would arise in a deep nonlinear model but only as an effect of adding nonlinear activations to the corresponding deep linear model. Thus, depending on the nonlinear activation mechanism and architecture, we would be able to efficiently train deep models.

The author would like to thank Prof. Leslie Kaelbling, Quynh Nguyen, Li Huan and Anirbit Mukherjee for their thoughtful comments on the paper. We gratefully acknowledge support from NSF grant 1420927, from ONR grant N00014-14-1-0486, and from ARO grant W911NF1410433.

References

Appendix A Proofs of lemmas and corollary in Section 4.2

We complete the proofs of the lemmas and corollary in Section 4.2.

Since $\mathcal{\bar{L}}(W)=\frac{1}{2}\|\overline{Y}(W,X)-Y\|^{2}_{F}=\frac{1}{2}\operatorname{vec}(r)^{T}\operatorname{vec}(r)$,

By setting $\left(\mathcal{D}_{\operatorname{vec}(W_{k}^{T})}\mathcal{\bar{L}}(W)\right)^{T}=0$ for all $k\in\{1,...,H+1\}$, we obtain the statement of Lemma 4.1. For the boundary cases (i.e., $k=H+1$ or $k=1$), it can be seen from the second to the third lines that we obtain the desired results with the definition, $W_{k}\cdots W_{k+1}\triangleq I_{d_{k}}$ (i.e., $W_{H+1}\cdots W_{H+2}\triangleq I_{d_{y}}$ and $W_{0}\cdots W_{1}\triangleq I_{d_{x}}$). $\square$

A.2 Proof of Lemma 4.2

From the critical point condition with respect to $W_{1}$ (Lemma 4.1),

which is true if and only if $XrW_{H+1}\cdots W_{2}=0$. By expanding $r$, $0=XX^{T}W_{1}^{T}C^{T}C-XY^{T}C$. By solving for $W_{1}$,

for an arbitrary matrix $L$. Due to the property of any generalized inverse (Zhang,, 2006, p. 41), we have that $C(C^{T}C)^{-}C^{T}C=C$. Thus,

A.3 Proof of Lemma 4.3

For the diagonal blocks: the entries of diagonal blocks are obtained simply using the result of Lemma 4.1 as

Using the formula of $\mathcal{D}_{\operatorname{vec}(W_{k}^{T})}\operatorname{vec}(r)$ computed in the proof of of Lemma 4.1 yields the desired result.

For the off-diagonal blocks with $k=2,...,H$:

The first term above is reduced to the first term of the statement in the same way as the diagonal blocks. For the second term,

where $A_{k}=W_{H+1}\cdots W_{k+1}$ and $B_{k}=W_{k-1}\cdots W_{2}$. The third line follows the fact that $(W_{H+1,j}W_{H}\cdots W_{2})^{T}=\operatorname{vec}(W_{2}^{T}\cdots W_{H}^{T}W_{H+1,j}^{T})=(W_{H+1,j}\cdots W_{k+1}\otimes W_{2}^{T}\cdots W_{k-1}^{T})\operatorname{vec}(W_{k}^{T})$. In the last line, we have the desired result by rewriting $\sum_{i=1}^{m}\sum_{j=1}^{d_{y}}r_{i,j}(A_{k})_{j,t}X_{i}=X(rW_{H+1}\cdots W_{k+1})_{\cdot,t}$.

For the off-diagonal blocks with $k=H+1$: The first term in the statement is obtained in the same way as above (for the off-diagonal blocks with $k=2,...,H$). For the second term, notice that $\operatorname{vec}(W_{H+1}^{T})=\begin{bmatrix}(W_{H+1})_{1,\cdot}^{T}&\ldots&(W_{H+1})_{d_{y},\cdot}^{T}\\ \end{bmatrix}^{T}$ where $(W_{H+1})_{j,\cdot}$ is the $j$-th row vector of $W_{H+1}$ or the vector corresponding to the $j$-th output component. That is, it is conveniently organized as the blocks, each of which corresponds to each output component (or rather we chose $\operatorname{vec}(W^{T}_{k})$ instead of $\operatorname{vec}(W_{k})$ for this reason, among others). Also,

For each block entry $t=1,\dotsc,d_{y}$ in the above, similarly to the case of $k=2,...,H$,

Here, we have the desired result by rewriting $\sum_{i=1}^{m}r_{i,t}(A_{H+1})_{j,1}X_{i}=X(rI_{d_{y}})_{\cdot,t}=Xr_{\cdot,t}$. $\square$

A.4 Proof of Lemma 4.4

Note that a similarity transformation preserves the eigenvalues of a matrix. For each $k\in\{2,\dotsc,H+1\}$, we take a similarity transform of $\nabla^{2}\mathcal{\bar{L}}(W)$ (whose entries are organized as in Lemma 4.3) as

Here, the first implication follows the necessary condition with any principal submatrix and the second implication follows the necessary condition with the Schur complement (Zhang,, 2006, theorem 1.20, p. 44).

Note that $\mathcal{R}(M^{\prime})\subseteq\mathcal{R}(M)\Leftrightarrow(I-MM^{-})M^{\prime}=0$ (Zhang,, 2006, p. 41). Thus, by plugging in the formulas of $\mathcal{D}_{\operatorname{vec}(W_{k}^{T})}(\mathcal{D}_{\operatorname{vec}(W_{1}^{T})}\mathcal{\bar{L}}(W))^{T}$ and $\mathcal{D}_{\operatorname{vec}(W_{1}^{T})}(\mathcal{D}_{\operatorname{vec}(W_{1}^{T})}\mathcal{\bar{L}}(W))^{T}$ that are derived in Lemma 4.3, $\nabla^{2}\mathcal{\bar{L}}(W)\succeq 0\Rightarrow\forall k\in\{2,\dotsc,H+1\},$

where $A_{k}=W_{H+1}\cdots W_{k+1}$ and $B_{k}=W_{k-1}\cdots W_{2}$. Here, we can replace $(C^{T}C\otimes(XX^{T}))^{-}$ by $((C^{T}C)^{-}\otimes(XX^{T})^{-1})$ (see Appendix A.7). Thus, $I-(C^{T}C\otimes(XX^{T}))(C^{T}C\otimes(XX^{T}))^{-}$can be replaced by $(I_{d_{1}}\otimes I_{d_{y}})-(C^{T}C(C^{T}C)^{-}\otimes I_{d_{y}})=(I_{d_{1}}-C^{T}C(C^{T}C)^{-})\otimes I_{d_{y}}$. Accordingly, the first term is reduced to zero as

since $C^{T}C(C^{T}C)^{-}C^{T}=C^{T}$ (Zhang,, 2006, p. 41). Thus, with the second term remained, the condition is reduced to

which concludes the proof for the positive semidefinite case. For the necessary condition of the negative semidefinite case, we obtain the same condition since

A.5 Proof of Corollary 4.5

From the first condition in the statement of Lemma 4.4,

The first implication follows the fact that the rank of a product of matrices is at most the minimum of the ranks of the matrices, and the fact that the column space of $W_{2}^{T}\cdots W_{H+1}^{T}$ is subspace of the column space of $W_{2}^{T}\cdots W_{k-1}^{T}$. $\square$

A.6 Proof of Lemma 4.6

For the $(Xr=0)$ condition: Let $M_{H+1}$ be the principal submatrix as defined in the proof of Lemma 4.4 (the principal submatrix of $P_{H+1}^{-1}\nabla^{2}\mathcal{\bar{L}}(W)P_{H+1}$ that consists of the first four blocks of it). Let $B_{k}=W_{k-1}\cdots W_{2}$. Let $F=B_{H+1}W_{1}XX^{T}W_{1}^{T}B_{H+1}^{T}$. Using Lemma 4.3 for the blocks corresponding to $W_{1}$ and $W_{H+1}$,

where $E=\begin{bmatrix}B_{H+1}^{T}\otimes Xr_{\cdot,1}&\ldots&B_{H+1}^{T}\otimes Xr_{\cdot,d_{y}}\\ \end{bmatrix}$. Then, by the necessary condition with the Schur complement (Zhang,, 2006, theorem 1.20, p. 44), $M_{H+1}\succeq 0$ implies

where the second line follows the fact that $(I_{d_{y}}\otimes F)^{-}$ can be replaced by $(I_{d_{y}}\otimes F^{-})$ (see Appendix A.7). The third line follows the fact that $(I-FF^{-})B_{H+1}W_{1}X=0$ because $\mathcal{R}(B_{H+1}W_{1}X)=\mathcal{R}(B_{H+1}W_{1}XX^{T}W_{1}^{T}B^{T}_{H+1})=\mathcal{R}(F)$. In the fourth line, we expanded $E$ and used the definition of the Kronecker product. It implies

Here, if $Xr=0$, we have obtained the statement of the lemma. Thus, from now on, we focus on the case where $FF^{-}B_{H+1}=B_{H+1}$ and $Xr\neq 0$ to obtain the other condition, $C(C^{T}C)^{-}C^{T}=U_{\bar{p}}U_{\bar{p}}$.

For the $(C(C^{T}C)^{-}C^{T}=U_{\bar{p}}U_{\bar{p}})$ condition: By using another necessary condition of a matrix being positive semidefinite with the Schur complement (Zhang,, 2006, theorem 1.20, p. 44), $M_{H+1}\succeq 0$ implies that

Since we can replace $(C^{T}C\otimes XX^{T})^{-}$ by $(C^{T}C)^{-}\otimes(XX^{T})^{-1}$ (see Appendix A.7), the second term in the left hand side is simplified as

In the third line, the crossed terms – $\left(C(C^{T}C)^{-}\otimes B_{H+1}W_{1}\right)E$ and its transpose – are vanished to 0 because of the following. From Lemma 4.1, $\left(I_{d_{y}}\otimes(W_{H}\cdots W_{1}X)^{T}\right)^{T}\operatorname{vec}(r)=0\Leftrightarrow W_{H}\cdots W_{1}Xr=B_{H+1}W_{1}Xr=0$ at any critical point. Thus, $\left(C(C^{T}C)^{-}\otimes B_{H+1}W_{1}\right)E=\begin{bmatrix}C(C^{T}C)^{-}B_{H+1}^{T}\otimes B_{H+1}W_{1}Xr_{\cdot,1}&\ldots&C(C^{T}C)^{-}B_{H+1}^{T}\otimes B_{H+1}W_{1}Xr_{\cdot,d_{y}}\end{bmatrix}\allowbreak=0.$ The forth line follows

where the last line is due to the fact that $\forall t,(r_{\cdot,t})^{T}X^{T}(XX^{T})^{-1}Xr_{\cdot,t}$ is a scalar and the fact that for any matrix $L$, $r^{T}Lr=$ $\begin{bmatrix}(r_{\cdot,1})^{T}Lr_{\cdot,1}&\cdots&(r_{\cdot,1})^{T}Lr_{\cdot,d_{y}}\\ \vdots&\ddots&\vdots\\ (r_{\cdot,d_{y}})^{T}Lr_{\cdot,1}&\cdots&(r_{\cdot,d_{y}})^{T}Lr_{\cdot,d_{y}}\\ \end{bmatrix}$.

From equations 3 and A.6, $M_{H+1}\succeq 0\Rightarrow$

In the following, we simplify equation 5 by first showing that $\mathcal{R}(C)=\mathcal{R}(U_{\mathcal{I}_{\bar{p}}})$ and then simplifying $r^{T}X^{T}(XX^{T})^{-1}Xr,F$ and $B_{H+1}(C^{T}C)^{-}B_{H+1}^{T}$.

Showing that $\mathcal{R}(C)=\mathcal{R}(U_{\mathcal{I}_{\bar{p}}})$ (following the proof in Baldi & Hornik,, 1989): Let $P_{C}=C(C^{T}C)^{-}C^{T}$ be the projection operator on $\mathcal{R}(C)$. We first show that $P_{C}\Sigma P_{C}=\Sigma P_{C}=P_{C}\Sigma$.

where the first line follows Lemma 4.2, the second line is due to Lemma 4.1 with $k=H+1$ (i.e., $0=W_{H}\cdots W_{1}Xr\Leftrightarrow W_{H+1}\cdots W_{1}XX^{T}W_{1}^{T}\cdots W_{H}^{T}=YX^{T}W_{1}^{T}\cdots W_{H}^{T}$), the third line follows Lemma 4.2, and the fourth line uses the definition of $\Sigma$. Since $P_{C}\Sigma P_{C}$ is symmetric, $\Sigma P_{C}(=P_{C}\Sigma P_{C})$ is also symmetric and hence $\Sigma P_{C}=(\Sigma P_{C})^{T}=P_{C}^{T}\Sigma^{T}=P_{C}\Sigma$. Thus, $P_{C}\Sigma P_{C}=\Sigma P_{C}=P_{C}\Sigma$. Note that $P_{C}=UP_{U^{T}C}U^{T}$ as $P_{U^{T}C}=U^{T}C(C^{T}UU^{T}C)^{-}C^{T}U=U^{T}P_{C}U$. Thus,

which implies that $P_{U^{T}C}\Lambda=\Lambda P_{U^{T}C}$. Since the eigenvalues ($\Lambda_{1,1},\dots,\Lambda_{d_{y},d_{y}}$) are distinct, this implies that $P_{U^{T}C}$ is a diagonal matrix (otherwise, $P_{U^{T}C}\Lambda=\Lambda P_{U^{T}C}$ implies $\Lambda_{i,i}=\Lambda_{j,j}$ for $i\neq j$, resulting in contradiction). Because $P_{U^{T}C}$ is the orthogonal projector of rank $\bar{p}$ (as $P_{U^{T}C}=U^{T}P_{C}U$), this implies that $P_{U^{T}C}$ is a diagonal matrix with its diagonal entries being ones ($\bar{p}$ times) and zeros ($dy-\bar{p}$ times). Thus,

for some index set $\mathcal{I}_{\bar{p}}$. This means that $\mathcal{R}(C)=\mathcal{R}(U_{\mathcal{I}_{\bar{p}}})$.

where $P_{C}=C(C^{T}C)^{-}C^{T}=U_{\mathcal{I}_{\bar{p}}}U_{\mathcal{I}_{\bar{p}}}^{T}$ and the last line follows the facts:

and similarly, $\Sigma P_{C}=U_{\mathcal{I}_{\bar{p}}}^{T}\Lambda_{\mathcal{I}_{\bar{p}}}U_{\mathcal{I}_{\bar{p}}}$.

Simplifying $F$: In the proof of Lemma 4.2, by using Lemma 4.1 with $k=1$, we obtained that $W_{1}=(C^{T}C)^{-}C^{T}YX^{T}(XX^{T})^{-1}+(I-(C^{T}C)^{-}C^{T}C)L$. Also, from Lemma 4.4, we have that $Xr=0$ or $B_{H+1}(C^{T}C)^{-}C^{T}C=(C^{T}C(C^{T}C)^{-}B_{H+1}^{T})^{T}=B_{H+1}$. If $Xr=0$, we got the statement of the lemma, and so we consider the case of $B_{H+1}(C^{T}C)^{-}C^{T}C=B_{H+1}$. Therefore,

Since $F=B_{H+1}W_{1}XX^{T}W_{1}^{T}B_{H+1}^{T}$,

Simplifying $B_{H+1}(C^{T}C)^{-}B_{H+1}^{T}$: From Lemma 4.4, $C^{T}C(C^{T}C)^{-}B_{H+1}=B_{H+1}$ (again since we are done if $Xr=0$). Thus, $B_{H+1}(C^{T}C)^{-}B_{H+1}^{T}=$ $B_{H+1}(C^{T}C)^{-}C^{T}C(C^{T}C)^{-}B_{H+1}^{T}$. As discussed above, we write $C(C^{T}C)^{-}B_{H+1}^{T}=[U_{\mathcal{I}_{\bar{p}}},\mathbf{0}]G_{2}$. Thus,

Putting results together: We use the simplified formulas of $C(C^{T}C)^{-}C^{T}$, $r^{T}X^{T}(XX^{T})^{-1}Xr,F$ and $B_{H+1}(C^{T}C)^{-}B_{H+1}^{T}$ in equation 5, obtaining

Due to Sylvester’s law of inertia (Zhang,, 2006, theorem 1.5, p. 27), with a nonsingular matrix $U\otimes G_{2}^{-1}$ (it is nonsingular because each of $U$ and $G_{2}^{-1}$ is nonsingular), the necessary condition is reduced to

which implies that for all $(i,j)\in\{(i,j)\ |\ i\in\{1,\dotsc,\bar{p}\},\ j\in\{1,\dotsc,(d_{y}-\bar{p})\}\}$, $(\Lambda_{\mathcal{I}_{\bar{p}}})_{i,i}\geq(\Lambda_{-\mathcal{I}_{\bar{p}}})_{j,j}$. In other words, the index set $\mathcal{I}_{\bar{p}}$ must select the largest $\bar{p}$ eigenvalues whatever $\bar{p}$ is. Since $C(C^{T}C)^{-}C^{T}=U_{\mathcal{I}_{\bar{p}}}U_{\mathcal{I}_{\bar{p}}}^{T}$ (which is obtained above), we have that $C(C^{T}C)^{-}C^{T}=U_{\bar{p}}U_{\bar{p}}$ in this case.

Summarizing the above case analysis, if $\nabla^{2}\mathcal{\bar{L}}(W)\succeq 0$ at a critical point, $C(C^{T}C)^{-}C^{T}=U_{\bar{p}}U_{\bar{p}}$ or $Xr=0$. $\square$

A.7 Generalized inverse of Kronecker product

$(A^{-}\otimes B^{-})$ is a generalized inverse of $A\otimes B$.

For a matrix $M$, the definition of a generalized inverse, $M^{-}$, is $MM^{-}M=M$. Setting $M:=A\otimes B$, we check if $(A^{-}\otimes B^{-})$ satisfies the definition: $(A\otimes B)(A^{-}\otimes B^{-})(A\otimes B)=(AA^{-}A\otimes BB^{-}B)=(A\otimes B)$ as desired. $\square$

Here, we are not claiming that $(A^{-}\otimes B^{-})$ is the unique generalized inverse of $A\otimes B$. Notice that the necessary condition that we have in our proof (where we need a generalized inverse of $A\otimes B$) is for any generalized inverse of $A\otimes B$. Thus, replacing it by one of any generalized inverse suffices to obtain a necessary condition. Indeed, choosing Moore$-$Penrose pseudoinverse suffices here, with which we know $(A\otimes B)^{\dagger}=(A^{\dagger}\otimes B^{\dagger})$. But, to give a simpler argument later, we keep more generality by choosing $(A^{-}\otimes B^{-})$ as a generalized inverse of $A\otimes B$.

Appendix B Proof of Theorem 2.3

We complete the proofs of Theorem 2.3. Since we heavily rely on the necessary conditions of local minima, we remind the reader of the elementary logic: for a point to be a local minimum, it must satisfy all the necessary conditions of local minima, but a point satisfying the necessary conditions can be a point that is not a local minimum (in contrast, a point satisfying the sufficient condition of local minimum is a local minimum).

By case analysis, we show that any point that satisfies the necessary conditions and the definition of a local minimum is a global minimum. When we write a statement in the proof, we often mean that a necessary condition of local minima implies the statement as it should be clear (i.e., we are not claiming that the statement must hold true unless the point is the candidate of local minima.).

Case I: $\operatorname{rank}(W_{H}\cdots W_{2})=p$ and $d_{y}\leq p$: Assume that $\operatorname{rank}(W_{H}\cdots W_{2})=p$. We first obtain a necessary condition of the Hessian being positive semidefinite at a critical point, $Xr=0$, and then interpret the condition. If $d_{y}<p$, Corollary 4.5 with $k=H+1$ implies the necessary condition that $Xr=0$. This is because the other condition $p>\operatorname{rank}(W_{H+1})\geq\operatorname{rank}(W_{H}\cdots W_{2})=p$ is false.

If $d_{y}=p$, Lemma 4.6 with $k=H+1$ implies the necessary condition that $Xr=0$ or $\mathcal{R}(W_{H}\cdots W_{2})\subseteq\mathcal{R}(C^{T}C)$. Suppose that $\mathcal{R}(W_{H}\cdots W_{2})\subseteq\mathcal{R}(C^{T}C)$. Then, we have that $p=\operatorname{rank}(W_{H}\cdots W_{2})\leq\operatorname{rank}(C^{T}C)=\operatorname{rank}(C)$. That is, $\operatorname{rank}(C)\geq p$.

From Corollary 4.5 with $k=2$ implies the necessary condition that

Suppose the latter: $XrW_{H+1}\cdots W_{3}=0$. Since $\operatorname{rank}(W_{H+1}\cdots W_{3})\geq\operatorname{rank}(C)\geq p$ and $d_{H+1}=d_{y}=p$, the left null space of $W_{H+1}\cdots W_{3}$ contains only zero. Thus,

Suppose the former: $\operatorname{rank}(C)\geq\operatorname{rank}(I_{d_{1}})$. Because $d_{y}=p$, $\operatorname{rank}(C)\geq p$, and $\mathcal{R}(C)\subseteq\mathcal{R}(YX^{T})$ as shown in the proof of Lemma 4.6, we have that $\mathcal{R}(C)=\mathcal{R}(YX^{T})$.

where the last equality follows the fact that $(Xr)^{T}=C(C^{T}C)^{-1}C^{T}YX^{T}-YX^{T}=0$ since $\mathcal{R}(C)=\mathcal{R}(YX^{T})$ and thereby the projection of $YX^{T}$ onto the range of $C$ is $YX^{T}$. Therefore, we have the condition, $Xr=0$ when $d_{y}\leq p$.

Thus, we have proved that when $\operatorname{rank}(W_{H}\cdots W_{2})=p$ and $d_{y}\leq p$, if $\nabla^{2}\mathcal{\bar{L}}(W)\succeq 0$ at a critical point, it is a global minimum.

Case II: $\operatorname{rank}(W_{H}\cdots W_{2})=p$ and $d_{y}>p$: We first obtain a necessary condition of the Hessian being positive semidefinite at a critical point and then interpret the condition. From Lemma 4.6, we have that $C(C^{T}C)^{-}C^{T}=U_{{\bar{p}}}U_{{\bar{p}}}^{T}$ or $Xr=0$. If $Xr=0$, with the exact same proof as in the case of $d_{y}\leq p$, it is a global minimum. Suppose that $C(C^{T}C)^{-}C^{T}=U_{{\bar{p}}}U_{{\bar{p}}}$. Combined with Lemma 4.2, we have a necessary condition:

From Lemma 4.4 with $k=H+1$, $\mathcal{R}(W_{2}^{T}\cdots W_{H}^{T})\subseteq\mathcal{R}(C^{T}C)=\mathcal{R}(C^{T})$, which implies that $\bar{p}\triangleq\operatorname{rank}(C)=p$ (since $\operatorname{rank}(W_{H}\cdots W_{2})=p$). Thus, we can rewrite the above equation as $W_{H+1}\cdots W_{1}=U_{{p}}U_{{p}}^{T}YX^{T}(XX^{T})^{-1}$, which is the orthogonal projection on to subspace spanned by the $p$ eigenvectors corresponding to the $p$ largest eigenvalues following the ordinary least square regression matrix. This is indeed the expression of a global minimum (Baldi & Hornik,, 1989; Baldi & Lu,, 2012).

Thus, we have proved that when $\operatorname{rank}(W_{H}\cdots W_{2})=p$, if $\nabla^{2}\mathcal{\bar{L}}(W)\succeq 0$ at a critical point, it is a global minimum.

Case III: $\operatorname{rank}(W_{H}\cdots W_{2})<p$: Suppose that $\operatorname{rank}(W_{H}\cdots W_{2})<p$. Let $\hat{p}=\min(p,d_{y})$. Then, if $\operatorname{rank}(C)\geq\hat{p}$, every local minimum is a global minimum because of the following. If $p\leq d_{y}$, $\operatorname{rank}(W_{H}\cdots W_{2})\geq\operatorname{rank}(C)\geq\hat{p}=p$ and thereby we have the case of $\operatorname{rank}(W_{H}\cdots W_{2})=p$ (since we have that $p\geq\operatorname{rank}(W_{H}\cdots W_{2})\geq p$ where the first inequality follows the definition of $p$). For this case, we have already proven the desired statement above. On the other hand, if $p>d_{y}$, we have $\bar{p}\triangleq\ \operatorname{rank}(C)\geq d_{y}$. Thus, $W_{H+1}\cdots W_{1}=U_{\bar{p}}U_{\bar{p}}^{T}YX^{T}(XX^{T})^{-1}=UU^{T}YX^{T}(XX^{T})^{-1}$, which is a global minimum. We can see this in various ways. For example, $Xr=XY^{T}UU^{T}-XY^{T}=0$, which means that it is a global minimum as discussed above.

Thus, in the following, we consider the remaining case where $\operatorname{rank}(W_{H}\cdots W_{2})<p$ and $\operatorname{rank}(C)<\hat{p}$. In this case, we show that we can have $\operatorname{rank}(C)\geq\hat{p}$ with arbitrarily small perturbations of each entry of $W_{H+1},\dotsc,W_{1}$, without changing the loss value. In order to show this, by induction on $k=\{1,\dotsc,H+1\}$, we prove that we can have $\operatorname{rank}(W_{k}\cdots W_{1})\geq\hat{p}$ with arbitrarily small perturbation of each entry of $W_{k},\dotsc,W_{1}$ without changing the value of $\mathcal{\bar{L}}(W)$.

We start with the base case with $k=1$. For convenience, we reprint a necessary condition of local minima that is represented by equation 2 in the proof of Lemmas 4.2: for an arbitrary $L_{1}$,

Again, note that the set of all generalized inverse of $G^{T}_{1}\begin{bmatrix}I_{\bar{p}}&0\\ 0&0\\ \end{bmatrix}G_{1}$ is as follows (Zhang,, 2006, p. 41):

Since equation 6 must necessarily hold for any generalized inverse in order for a point to be a local minimum, we choose a generalized inverse with $L_{1}^{\prime}=L_{2}^{\prime}=L_{3}^{\prime}=0$ to have a weaker yet simpler necessary condition. That is,

By plugging this into equation 6, we obtain the following necessary condition of local minima: for an arbitrary $L_{1}$,

This means that changing the values of the last ($d_{1}-\bar{p}$) rows of $G_{1}L_{1}$ (i.e., $[0\ \ I_{(d_{1}-\bar{p})}]G_{1}L_{1}$) does not change the value of $\mathcal{\bar{L}}(W)$. Thus, we consider the perturbation of each entry of $W_{1}$ as follows:

Thus, we have shown that we can have $\operatorname{rank}(W_{1})\geq\min(d_{1},d_{x})\geq\min(p,d_{y})=\hat{p}$ with arbitrarily small perturbation of each entry of $W_{1}$ with the loss value being unchanged. This concludes the proof for the base case of the induction with $k=1$.

For the inductive stepThe boundary cases with $k=2$ and $k=H+1$ as well pose no problem during the proof for the inductive step: remember our notational definition, $W_{k}\cdots W_{k^{\prime}}\triangleq I_{d_{k}}$ if $k<k^{\prime}$. with $k\in\{2,\dotsc,H+1\}$, we have the inductive hypothesis that we can have $\operatorname{rank}(W_{k-1}\cdots W_{1})\geq\hat{p}$ with arbitrarily small perturbations of each entry of $W_{k-1},\dotsc W_{1}$ without changing the loss value. Here, we want to show that if $\operatorname{rank}(W_{k-1}\cdots W_{1})\geq\hat{p}$, we can have $\operatorname{rank}(W_{k}\cdots W_{1})\geq\hat{p}$ with arbitrarily small perturbation of each entry of $W_{k}$ without changing the value of $\mathcal{\bar{L}}(W)$. Accordingly, suppose that $\operatorname{rank}(W_{k-1}\cdots W_{1})\geq\hat{p}$. From Lemma 4.4, we have the following necessary condition for the Hessian to be (positive or negative) semidefinite at a critical point: for any $k\in\{2,\dotsc,H+1\}$,

where the first condition is shown to imply $\operatorname{rank}(W_{H+1}\cdots W_{k})\geq\operatorname{rank}(W_{k-1}\cdots W_{2})$ in Corollary 4.5. If the former condition is true, $\operatorname{rank}(C)\geq\operatorname{rank}(W_{k-1}\cdots W_{2})\geq\operatorname{rank}(W_{k-1}\cdots W_{1})\geq\hat{p}$, which is false in the case being analyzed (i.e., the case where $\operatorname{rank}(C)<\hat{p}$. If this is not the case, we can immediately conclude the desired statement as it has been already proven for the case where $\operatorname{rank}(C)\geq\hat{p}$). Thus, we suppose that the latter condition is true. Let $A_{k}=W_{H+1}\cdots W_{k+1}$. Then, for an arbitrary $L_{k}$,

where the last two equalities follow Lemmas 4.2 and 4.6 (since if $Xr=0$, we immediately obtain the desired result as discussed above). Taking transpose,

Since $XY^{T}$ is full rank with $d_{y}\leq d_{x}$ (i.e., $\operatorname{rank}(XY^{T})=d_{y}$), there exists a left inverse and the solution of the above linear system is unique as $((XY^{T})^{T}XY^{T})^{-1}(XY^{T})^{T}XY^{T}=I$, yielding,

In other words, $\mathcal{R}(A_{k})=\mathcal{R}(C)=\mathcal{R}(U_{{\bar{p}}})$.

and plugging this into the condition in equation B.1: for an arbitrary $L_{k}$,

which means that changing the values of the last ($d_{k}-\bar{p}$) rows does not change the value of $\mathcal{\bar{L}}(W)$.

We consider the perturbation of each entry of $W_{k}$ as follows. From equation 9, all the possible solutions of $W_{k}$ can be written as: for an arbitrary $L_{0_{k}}$ and $L_{k}$,

where $B_{k}=W_{k-1}\cdots W_{1}$ and $B_{k}^{\dagger}$ is the the Moore–Penrose pseudoinverse of $B_{k}$. We perturb $W_{k}$ as

where $M=M_{\text{ptb}}(B_{k}^{T}B_{k})^{\dagger}B_{k}^{T}B_{k}$. Then,

Thus, we conclude the induction, proving that we can have $\operatorname{rank}(W_{H+1}\cdots W_{1})\geq\hat{p}$ with arbitrarily small perturbation of each parameter without changing the value of $\mathcal{\bar{L}}(W)$. Since $\operatorname{rank}(C)\geq\operatorname{rank}(W_{H+1}\cdots W_{1})\geq\hat{p}$, upon such a perturbation, we have the case where $\operatorname{rank}(C)\geq\hat{p}$, for which we have already proven that a critical point is not a local minimum unless it is a global minimum. This concludes the proof of the case where $\operatorname{rank}(W_{H}\cdots W_{2})<p$.

Summarizing the above, any point that satisfies the definition (and necessary conditions) of a local minimum is a global minimum, concluding the proof of Theorem 2.3 (ii). $\square$

B.2 Proof of Theorem 2.3 (i)

We can prove the non-convexity and non-concavity from its Hessian (Theorem 2.3 (i)). First, consider $\mathcal{\bar{L}}(W)$. For example, from Corollary 4.5 with $k=H+1$, it is necessary for the Hessian to be positive or negative semidefinite at a critical point that $\operatorname{rank}(W_{H+1})\geq\operatorname{rank}(W_{H}\cdots W_{2})$ or $Xr=0$. The instances of $W$ unsatisfying this condition at critical points form some uncountable set. As an example, consider a uncountable set that consists of the points with $W_{H+1}=W_{1}=0$ and with any $W_{H},\dotsc,W_{2}$. Then, every point in the set defines a critical point from Lemma 4.1. Also, $Xr=XY^{T}\neq 0$ as $\operatorname{rank}(XY^{T})\geq 1$. So, it does not satisfy the first semidefinite condition. On the other hand, with any instance of $W_{H}\cdots W_{2}$ such that $\operatorname{rank}(W_{H}\cdots W_{2})\geq 1$, we have that $0=\operatorname{rank}(W_{H+1})\ngeq\ \operatorname{rank}(W_{H}\cdots W_{2})$. So, it does not satisfy the second semidefinite condition as well. Thus, we have proven that in the domain of the loss function, there exist points, at which the Hessian becomes indefinite. This implies Theorem 2.3 (i): the functions are non-convex and non-concave.