The loss surface of deep and wide neural networks

Introduction

The application of deep learning (LeCun et al., 2015) has in recent years lead to a dramatic boost in performance in many areas such as computer vision, speech recognition or natural language processing. Despite this huge empirical success, the theoretical understanding of deep learning is still limited. In this paper we address the non-convex optimization problem of training a feedforward neural network. This problem turns out to be very difficult as there can be exponentially many distinct local minima (Auer et al., 1996; Safran & Shamir, 2016). It has been shown that the training of a network with a single neuron with a variety of activation functions turns out to be NP-hard (Sima, 2002).

In practice local search techniques like stochastic gradient descent or variants are used for training deep neural networks. Surprisingly, it has been observed (Dauphin et al., 2014; Goodfellow et al., 2015) that in the training of state-of-the-art feedforward neural networks with sparse connectivity like convolutional neural networks (LeCun et al., 1990; Krizhevsky et al., 2012) or fully connected ones one does not encounter problems with suboptimal local minima. However, as the authors admit themselves in (Goodfellow et al., 2015), the reason for this might be that there is a connection between the fact that these networks have good performance and that they are easy to train.

On the theoretical side there have been several interesting developments recently, see e.g. (Brutzkus & Globerson, 2017; Lee et al., 2016; Poggio & Liao, 2017; Rister & Rubin, 2017; Soudry & Hoffer, 2017; Zhou & Feng, 2017). For some class of networks one can show that one can train them globally optimal efficiently. However, it turns out that these approaches are either not practical (Janzamin et al., 2016; Haeffele & Vidal, 2015; Soltanolkotabi, 2017) as they require e.g. knowledge about the data generating measure, or they modify the neural network structure and objective (Gautier et al., 2016). One class of networks which are simpler to analyze are deep linear networks for which it has been shown that every local minimum is a global minimum (Baldi & Hornik, 1988; Kawaguchi, 2016). While this is a highly non-trivial result as the optimization problem is non-convex, deep linear networks are not interesting in practice as one efficiently just learns a linear function. In order to characterize the loss surface for general networks, an interesting approach has been taken by (Choromanska et al., 2015a). By randomizing the nonlinear part of a feedforward network with ReLU activation function and making some additional simplifying assumptions, they can relate it to a certain spin glass model which one can analyze. In this model the objective of local minima is close to the global optimum and the number of bad local minima decreases quickly with the distance to the global optimum. This is a very interesting result but is based on a number of unrealistic assumptions (Choromanska et al., 2015b). It has recently been shown (Kawaguchi, 2016) that if some of these assumptions are dropped one basically recovers the result of the linear case, but the model is still unrealistic.

In this paper we analyze the case of overspecified neural networks, that is the network is larger than what is required to achieve minimum training error. Under overspecification (Safran & Shamir, 2016) have recently analyzed under which conditions it is possible to generate an initialization so that it is in principle possible to reach the global optimum with descent methods. However, they can only deal with one hidden layer networks and have to make strong assumptions on the data such as linear independence or cluster structure. In this paper overspecification means that there exists a very wide layer, where the number of hidden units is larger than the number of training points. For this case, we can show that a large class of local minima is globally optimal. In fact, we will argue that almost every critical point is globally optimal. Our results generalize previous work of (Yu & Chen, 1995), who have analyzed a similar setting for one hidden layer networks, to networks of arbitrary depth. Moreover, it extends results of (Gori & Tesi, 1992; Frasconi et al., 1997) who have shown that for certain deep feedforward neural networks almost all local minima are globally optimal whenever the training data is linearly independent. While it is clear that our assumption on the number of hidden units is quite strong, there are several recent neural network structures which contain a quite wide hidden layer relative to the number of training points e.g. in (Lin et al., 2016) they have 50,000 training samples and the network has one hidden layer with 10,000 hidden units and (Ba & Caruana, 2014) have 1.1 million training samples and a layer with 400,000 hidden units. We refer to (Ciresan et al., 2010; Neyshabur et al., 2015; Vincent et al., 2010; Caruana et al., 2001) for other examples where the number of hidden units of one layer is on the order of the number of training samples. We conjecture that for these kind of wide networks it still holds that almost all local minima are globally optimal. The reason is that one can expect linear separability of the training data in the wide layer. We provide supporting evidence for this conjecture by showing that basically every critical point for which the training data is linearly separable in the wide layer is globally optimal. Moreover, we want to emphasize that all of our results hold for neural networks used in practice. There are no simplifying assumptions as in previous work.

Feedforward Neural Networks and Backpropagation

The idea of backpropagation is the core of our theoretical analysis. Lemma 2.1 below shows well-known relations for feed-forward neural networks, which are used throughout the paper. The derivative of the loss w.r.t. the value of unit $j$ at layer $k$ evaluated at a single training sample $x_{i}$ is denoted as $\delta_{kj}(x_{i})=\frac{\partial\Phi}{\partial g_{kj}(x_{i})}.$ We arrange these vectors for all training samples into a single matrix $\Delta_{k}$, defined as

$\Delta_{k}=\begin{cases}l^{\prime}(F_{L}-Y)\circ\sigma^{\prime}(G_{L}),&k=L\\ (\Delta_{k+1}W_{k+1}^{T})\circ\sigma^{\prime}(G_{k}),&k\in[L-1]\end{cases}$

$\nabla_{W_{k}}\Phi=\begin{cases}X^{T}\Delta_{1},&k=1\\ F_{k-1}^{T}\Delta_{k},&k\in[2,L]\end{cases}$

$\nabla_{b_{k}}\Phi=\Delta_{k}^{T}\mathbf{1}_{N}$ $\forall\,k\in[L]$

By definition, it holds for every $i\in[N],j\in[n_{L}]$ that

and hence, $\Delta_{L}=l^{\prime}(F_{L}-Y)\circ\sigma^{\prime}(G_{L}).$

For every $k\in[L-1]$, the chain rule yields for every $i\in[N],j\in[n_{k}]$ that

and hence $\Delta_{k}=(\Delta_{k+1}W_{k+1}^{T})\circ\sigma^{\prime}(G_{k}).$

and hence $\nabla_{W_{1}}\Phi=X^{T}\Delta_{1}.$

For every $k\in[2,L],r\in[n_{k-1}],s\in[n_{k}],$ one obtains

and hence $\nabla_{W_{k}}\Phi={F_{k-1}^{T}}\Delta_{k}.$

For every $k\in[1,L]$, $s\in[n_{k}]$ it holds

and hence $\nabla_{b_{k}}\Phi=\Delta_{k}^{T}\mathbf{1}_{N}.$

Main Result

We first discuss some prior work and present then our main result together with extensive discussion. For improved readability we postpone the proof of the main result to the next section which contains several intermediate results which are of independent interest.

Then every critical point $(W_{l},b_{l})_{l=1}^{L}$ of $\Phi$ which satisfies the conditions

$\operatorname{\textit{rank}}(W_{l})=n_{l}$ for all $l\in[2,L]$,

$[X,\mathbf{1}_{N}]^{T}\Delta_{1}=0$ implies $\Delta_{1}=0$

While this result is already for general multi-layer networks, the condition “$[X,\mathbf{1}_{N}]^{T}\Delta_{1}=0$ implies $\Delta_{1}=0$” is the main caveat. It is already noted in (Gori & Tesi, 1992), that “it is quite hard to understand its practical meaning” as it requires prior knowledge of $\Delta_{1}$ at every critical point. Note that this is almost impossible as $\Delta_{1}$ depends on all the weights of the network. For a particular case, when the training samples (biases added) are linearly independent, i.e. $\operatorname{\textit{rank}}([X,\mathbf{1}_{N}])=N$, the condition holds automatically. This case is discussed in the following Theorem 3.4, where we consider a more general class of loss and activation functions.

2 First Main Result and Discussion

There are no identical training samples, i.e. $x_{i}\neq x_{j}$ for all $i\neq j$,

there are positive $\rho_{1},\rho_{2},\rho_{3},\rho_{4}$, s.t. $|\sigma(t)|\leq\rho_{1}e^{\rho_{2}t}$ for $t<0$ and $|\sigma(t)|\leq\rho_{3}t+\rho_{4}$ for $t\geq 0$

These conditions are not always necessary to prove some of the intermediate results presented below, but we decided to provide the proof under the above strong assumptions for better readability. For instance, all of our results also hold for strictly monotonically decreasing activation functions. Note that the above conditions are not restrictive as many standard activation functions satisfy them.

Finally, we note that $\sigma_{1}$,$\sigma_{2},\sigma_{3}$ are strictly monotonically increasing. Since $\sigma_{1}$,$\sigma_{2}$ are bounded, they both satisfy Assumption 3.2. For $\sigma_{3}$, we note that $1+e^{\alpha t}\leq 2e^{\alpha t}$ for $t\geq 0$, and thus it holds for every $t\geq 0$ that

which implies that $\sigma_{3}$ satisfies Assumption 3.2 for $\rho_{1}=1/\alpha,\rho_{2}=\alpha,\rho_{3}=1,\rho_{4}=\log(2)/\alpha.$ $\Box$ The conditions on $l$ are satisfied for any twice continuously differentiable convex loss function. A typical example is the squared loss $l(a)=a^{2}$ or the Pseudo-Huber loss (Hartley & Zisserman, 2004) given as $l_{\delta}(a)=2\delta^{2}(\sqrt{1+a^{2}/\delta^{2}}-1)$ which approximates $a^{2}$ for small $a$ and is linear with slope $2\delta$ for large $a.$ But also non-convex loss functions satisfy this requirement, for instance:

Blake-Zisserman: $l(a)=-\log(\exp(-a^{2})+\delta)$ for $\delta>0.$ For small $a$, this curve approximates $a^{2}$, whereas for large $a$ the asymptotic value is $-\log(\delta).$

for $\alpha\in,w>0.$ This function computes the negative log-likehood of a gaussian mixture model.

Cauchy: $l(a)=\delta^{2}\log(1+a^{2}/\delta^{2})$ for $\delta\neq 0.$ This curve approximates $a^{2}$ for small $a$ and the value of $\delta$ determines for what range of $a$ this approximation is close.

We refer to (Hartley & Zisserman, 2004) (p.617-p.619) for more examples and discussion on robust loss functions.

As a motivation for our main result, we first analyze the case when the training samples are linearly independent, which requires $N\leq d+1.$ It can be seen as a generalization of Corollary 1 in (Gori & Tesi, 1992).

The main restriction in the assumptions of Theorem 3.4 is the linear independence of the training samples as it requires $N\leq d+1$, which is very restrictive in practice. We prove in this section a similar guarantee in our main Theorem 3.8 by implicitly transporting this condition to some higher layer. A similar guarantee has been proven by (Yu & Chen, 1995) for a single hidden layer network, whereas we consider general multi-layer networks. The main ingredient of the proof of our main result is the observation in the following lemma.

$\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N$

$\operatorname{\textit{rank}}(W_{l})=n_{l},\,l\in[k+2,L]$

\nabla_{W_{k+1}}\Phi\Big{(}(W_{l},b_{l})_{l=1}^{L}\Big{)}=0 \nabla_{b_{k+1}}\Phi\Big{(}(W_{l},b_{l})_{l=1}^{L}\Big{)}=0

then $(W_{l},b_{l})_{l=1}^{L}$ is a global minimum.

which implies $[F_{k},\mathbf{1}_{N}]^{T}\Delta_{k+1}=0.$ By our assumption, $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N$ it holds that $\Delta_{k+1}=0.$ Since $\operatorname{\textit{rank}}(W_{l})=n_{l},l\in[k+2,L]$, we can apply a similar induction argument as in the proof of Theorem 3.4, to arrive at $\Delta_{L}=0$ and thus a global minimum. $\Box$ The first condition of Lemma 3.5 can be seen as a generalization of the requirement of linearly independent training inputs in Theorem 3.4 to a condition of linear independence of the feature vectors at a hidden layer. Lemma 3.5 suggests that if we want to make statements about the global optimality of critical points, it is sufficient to know when and which critical points fulfill these conditions. The third condition is trivially satisfied by a critical point and the requirement of full column rank of the weight matrices is similar to Theorem 3.4. However, the first one may not be fulfilled since $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])$ is dependent not only on the weights but also on the architecture. The main difficulty of the proof of our following main theorem is to prove that this first condition holds under the rather simple requirement that $n_{k}\geq N-1$ for a subset of all critical points.

But before we state the theorem we have to discuss a particular notion of non-degenerate critical point.

We use this to introduce a slightly more general notion of non-degenerate critical point.

$x$ is non-degenerate for a subset of variables $S\subseteq\left\{x_{1},\ldots,x_{n}\right\}$ if $\nabla^{2}_{S}f(x)$ is non-singular.

$x$ is non-degenerate if $\nabla^{2}f(x)$ is non-singular.

Note that a non-degenerate critical point might not be non-degenerate for a subset of variables, and vice versa, if it is non-degenerate on a subset of variables it does not necessarily imply non-degeneracy on the whole set. For instance,

Clearly, $\mathop{\rm det}\nolimits{\nabla^{2}f(x)}=0$ but $\mathop{\rm det}\nolimits{\nabla^{2}_{\left\{x_{1},x_{2}\right\}}}f(x)\neq 0,$ and $\mathop{\rm det}\nolimits{\nabla^{2}f(y)}\neq 0$ but $\mathop{\rm det}\nolimits{\nabla^{2}_{\left\{y_{3},y_{4}\right\}}}f(y)=0.$ The concept of non-degeneracy on a subset of variables is crucial for the following statement of our main result.

$(W^{*}_{l},b^{*}_{l})_{l=1}^{L}$ is non-degenerate on $\left\{(W_{l},b_{l})\mathrel{\left|\vphantom{(W_{l},b_{l})l\in\mathcal{I}}\right.}l\in\mathcal{I}\right\}$, for some subset $\mathcal{I}\subseteq\left\{k+1,\ldots,L\right\}$ satisfying $\left\{k+1\right\}\in\mathcal{I},$

$(W^{*}_{l})_{l=k+2}^{L}$ has full column rank, that is, $\operatorname{\textit{rank}}(W^{*}_{l})=n_{l}$ for $l\in[k+2,L]$,

First of all we note that the full column rank condition of $(W_{l})_{l=k+2}^{L}$ in Theorem 3.4, and 3.8 implicitly requires that $n_{k+1}\geq n_{k+2}\geq\ldots\geq n_{L}.$ This means the network needs to have a pyramidal structure from layer $k+2$ to $L$. It is interesting to note that most modern neural network architectures have a pyramidal structure from some layer, typically the first hidden layer, on. Thus this is not a restrictive requirement. Indeed, one can even argue that Theorem 3.8 gives an implicit justification as it hints on the fact that such networks are easy to train if one layer is sufficiently wide.

Note that Theorem 3.8 does not require fully non-degenerate critical points but non-degeneracy is only needed for some subset of variables that includes layer $k+1$. As a consequence of Theorem 3.8, we get directly a stronger result for non-degenerate local minima.

Proof: The Hessian at a non-degenerate local minimum is positive definite and every principal submatrix of a positive definite matrix is again positive definite, in particular for the subset of variables $(W_{l},b_{l})_{l=k+1}^{L}$. Then application of Theorem 3.8 yields the result. $\Box$

Let us discuss the implications of these results. First, note that Theorem 3.8 is slightly weaker than Theorem 3.4 as it requires also non-degeneracy wrt to a set of variables including layer $k+1$. Moreover, similar to Theorem 3.4 it does not exclude the possibility of suboptimal local minima of low rank in the layers “above” layer $k+1$. On the other hand it makes also very strong statements. In fact, if $n_{k}\geq N-1$ for some $k\in[L-1]$ then even degenerate saddle points/local maxima are excluded as long as they are non-degenerate with respect to any subset of parameters of upper layers that include layer $k+1$ and the rank condition holds. Thus given that the weight matrices of the upper layers have full column rank , there is not much room left for degenerate saddle points/local maxima. Moreover, for a one-hidden-layer network for which $n_{1}\geq N-1$, every non-degenerate critical point with respect to the output layer parameters is a global minimum, as the full rank condition is not active for one-hidden layer networks.

Concerning the non-degeneracy condition of main Theorem 3.8, one might ask how likely it is to encounter degenerate points of a smooth function. This is answered by an application of Sard’s/Morse theorem in (Milnor, 1965).

As we argued for Theorem 3.4 our main Theorem 3.8 does not exclude the possibility of suboptimal degenerate local minima or suboptimal local minima of low rank. However, we conjecture that the second case cannot happen as every neighborhood of the local minima contains full rank matrices which increase the expressiveness of the network and this additional flexibility can be used to reduce the loss which contradicts the definition of a local minimum.

As mentioned in the introduction the condition $n_{k}\geq N-1$ looks at first sight very strong. However, as mentioned in the introduction, in practice often networks are used where one hidden layer is rather wide, that is $n_{k}$ is on the order of $N$ (typically it is the first layer of the network). As the condition of Theorem 3.8 is sufficient and not necessary, one can expect out of continuity reasons that the loss surface of networks where the condition is approximately true, is still rather well behaved, in the sense that still most local minima are indeed globally optimal and the suboptimal ones are not far away from the globally optimal ones.

Proof of Main Result

For better readability, we first prove our main Theorem 3.8 for a special case where $\mathcal{I}$ is the whole set of upper layers, i.e. $\mathcal{I}=\left\{k+1,\ldots,L\right\},$ and then show how to extend the proof to the general case where $\mathcal{I}\subseteq\left\{k+1,\ldots,L\right\}.$ Our proof strategy is as follows. We first show that the output of each layer are real analytic functions of network parameters. Then we prove that there exists a set of parameters such that $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N.$ Using properties of real analytic functions, we conclude that the set of parameters where $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])<N$ has measure zero. Then with the non-degeneracy condition, we can apply the implicit-function theorem to conclude that even if $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N$ is not true at a critical point, then still in any neighborhood of it there exists a point where the conditions of Lemma 3.5 are true and the loss is minimal. By continuity of $\Phi,$ this implies that the loss must also be minimal at the critical point.

If the Assumptions 3.2 hold, then the output of each layer $f_{l}$ for every $l\in[L]$ are real analytic functions of the network parameters on $\mathcal{\mathcal{P}}.$

Proof: Any linear function is real analytic and the set of real analytic functions is closed under addition, multiplication and composition, see e.g. Prop. 2.2.2 and Prop. 2.2.8 in (Krantz & Parks, 2002). As we assume that the activation function is real analytic, we get that all the output functions of the neural network $f_{k}$ are real analytic functions of the parameters as compositions of real analytic functions. $\Box$

The concept of real analytic functions is important in our proofs as these functions can never be “constant” in a set of the parameter space which has positive measure unless they are constant everywhere. This is captured by the following lemma.

In the next lemma we show that there exist network parameters such that $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N$ holds if $n_{k}\geq N-1$. Note that this is only possible due to the fact that one uses non-linear activation functions. For deep linear networks, it is not possible for $F_{k}$ to achieve maximum rank if the layers below it are not sufficiently wide. To see this, one considers $F_{k}=F_{k-1}W_{k}+\mathbf{1}_{N}b_{k}^{T}$ for a linear network, then $\operatorname{\textit{rank}}(F_{k})\leq\mathop{\rm min}\nolimits\{\operatorname{\textit{rank}}(F_{k-1}),\operatorname{\textit{rank}}(W_{k})\}+1$ since the addition of a rank-one term does not increase the rank of a matrix by more than one. By using induction, one gets $\operatorname{\textit{rank}}(F_{k})\leq\operatorname{\textit{rank}}(W_{l})+k-l+1$ for every $l\in[k].$

The existence of network parameters where $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N$ together with the previous lemma will then be used to show that the set of network parameters where $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])<N$ has measure zero.

If the Assumptions 3.2 hold and $n_{k}\geq N-1$ for some $k\in[L-1]$, then there exists at least one set of parameters $(W_{l},b_{l})_{l=1}^{k}$ such that $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N.$

Proof: We first show by induction that there always exists a set of parameters $(W_{l},b_{l})_{l=1}^{k-1}$ s.t. $F_{k-1}$ has distinct rows. Indeed, we have $F_{1}=\sigma(XW_{1}+\mathbf{1}_{N}b_{1}^{T})$. The set of $(W_{1},b_{1})$ that makes $F_{1}$ to have distinct rows is characterized by

Note, that $\sigma$ is strictly monotonic and thus bijective on its domain. Thus this is equivalent to

Let us denote the first column of $W_{1}$ by $a$, then the existence of $a$ for which

By construction $f_{p-1}(x_{i})\neq f_{p-1}(x_{j})$ and thus with the same argument as above we can choose $W_{p}$ such that this condition holds. As a result, there exists a set of parameters $(W_{l},b_{l})_{l=1}^{k-1}$ so that $F_{k-1}$ has distinct rows.

Let $E(\alpha)=[\mathbf{1}_{N},A(\alpha)]$ then it holds

Let $\hat{E}(\alpha)$ be a modified matrix where one subtracts every row $i$ by row $(i-1)$ of $E(\alpha)$, in particular, let

where $S_{N}$ is the set of all $N!$ permutations of the set $\{1,\ldots,N\}$ and we used the fact that the last column of $E(\alpha)$ is equal to the all ones vector. Define the permutation $\gamma$ as $\gamma(j)=j$ for $j\in[N].$ Then we have

The idea now is to show that $\prod_{j=1}^{N-1}E(\alpha)_{\pi(j)j}$ goes to zero for every permutation $\pi\neq\gamma$ as $\alpha$ goes to infinity. And since the whole summation goes to zero while $\sigma(\beta)\neq 0$, the determinant would be non-zero as desired. With that, we first note that for any permutation $\pi\neq\gamma$ there has to be at least one component $\pi(j)$ where $\pi(j)>j$, in which case, $\delta_{j}=(z_{j}-z_{\pi(j)})^{T}a<0$ and thus for sufficiently large $\alpha$, it holds $\alpha\delta_{j}+\beta<0$. Thus

If $\pi(j)=j$ then $E(\alpha)_{\pi(j)j}=\sigma(\beta).$ In cases where $\pi(j)<j(j\neq N)$ it holds that $\delta_{j}=(z_{j}-z_{\pi(j)})^{T}a>0$ and thus for sufficiently large $\alpha$, it holds $\alpha\delta_{j}+\beta>0$ and we have

So far, we have shown that $|E(\alpha)_{\pi(j)j}|$ can always be upper-bounded by an exponential function resp. affine function of $\alpha$ when $\pi(j)>j$ resp. $\pi(j)<j$ or it is just a constant when $\pi(j)=j.$ The above observations imply that there exist positive constants $P,Q,R,S,T$ such that it holds for every $\pi\in S_{N}\setminus\left\{\gamma\right\},$

As $\alpha\rightarrow\infty$ the upper bound goes to zero. As there are only finitely many such terms, we get

and thus with the same argument as before we can argue that there exists a finite $\alpha_{0}$ for which $E(\alpha)$ has full rank.

$\Box$ Now we combine the previous lemma with Lemma 4.2 to conclude the following.

If the Assumptions 3.2 hold and $n_{k}\geq N-1$ for some $k\in[L-1]$ then the set S\mathrel{\mathop{:}}=\left\{\big{(}W_{l},b_{l}\big{)}_{l=1}^{k}\mathrel{\left|\vphantom{\big{(}W_{l},b_{l}\big{)}_{l=1}^{k}\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])<N}\right.}\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])<N\right\} has Lebesgue measure zero.

If the Assumptions 3.2 hold and $n_{k}\geq N-1$ for some $k\in[L-1]$, then for any given $(W^{0}_{l},b^{0}_{l})_{l=1}^{k}$ and for every $\epsilon>0$, there exists at least one \big{(}W_{l},b_{l}\big{)}_{l=1}^{k}\in B\Big{(}\big{(}W^{0}_{l},b^{0}_{l}\big{)}_{l=1}^{k},\epsilon\Big{)} s.t. $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N.$

Proof: Let S\mathrel{\mathop{:}}=\left\{\big{(}W_{l},b_{l}\big{)}_{l=1}^{k}\mathrel{\left|\vphantom{\big{(}W_{l},b_{l}\big{)}_{l=1}^{k}\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])<N}\right.}\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])<N\right\}. The ball B\Big{(}\big{(}W_{l},b_{l}\big{)}_{l=1}^{k},\epsilon\Big{)} has positive Lebesgue measure while $S$ has measure zero due to Lemma 4.4. Thus, for every \big{(}W_{l},b_{l}\big{)}_{l=1}^{k}\in B\Big{(}\big{(}W^{0}_{l},b^{0}_{l}\big{)}_{l=1}^{k},\epsilon\Big{)}\setminus S it holds $\operatorname{\textit{rank}}([F_{k},\mathbf{1}_{N}])=N.$ $\Box$ The final proof of our main Theorem 3.8 is heavily based on the implicit function theorem, see e.g. (Marsden, 1974).

With all the intermediate results proven above, we are finally ready for the proof of the main result.

By assumption we have $\operatorname{\textit{rank}}(W^{*}_{l})=n_{l},l\in[k+2,L]$, that is the weight matrices of the “upper” layers have full column rank. Note that $(W^{*}_{l})_{l=k+2}^{L}$ corresponds to the weight matrix part of $v^{*}$ where one leaves out $W^{*}_{k+1}$. Thus there exists a sufficiently small $\epsilon$ such that for any $v\in B(v^{*},\epsilon)$, the weight matrix part $(W_{l})_{l=k+2}^{L}$ of $v$ has full column rank. In particular, this, combined with the continuity of $\alpha$, implies that for a potentially smaller $0<\delta_{2}\leq\delta_{1}$, it holds for all $u\in B(u^{*},\delta_{2})$ that

Proof of Theorem 3.8 for general case

In the general case $\mathcal{I}\subseteq\left\{k+1,\ldots,L\right\}$, the previous proof can be easily adapted. The idea is that we fix all layers in $\left\{k+1,\ldots,L\right\}\setminus\mathcal{I}.$ In particular, let

The only difference is that all the layers from $\left\{k+1,\ldots,L\right\}\setminus\mathcal{I}$ are hold fixed. They are not contained in the arguments of $\Psi$, thus will not be involved in our perturbation analysis. In this way, the full rank property of the weight matrices of these layers are preserved, which is needed to obtain the global minimum.

Relaxing the Condition on the Number of Hidden Units

We have seen that $n_{k}\geq N-1$ is a sufficient condition which leads to a rather simple structure of the critical points, in the sense that all local minima which have full rank in the layers $k+2$ to $L$ and for which the Hessian is non-degenerate on any subset of upper layers that includes layer $k+1$ are automatically globally optimal. This suggests that suboptimal locally optimal points are either completely absent or relatively rare. We have motivated before that networks with a certain wide layer are used in practice, which shows that the condition $n_{k}\geq N-1$ is not completely unrealistic. On the other hand we want to discuss in this section how it could be potentially relaxed. The following result will provide some intuition about the case $n_{k}<N-1$, but will not be as strong as our main result 3.8 which makes statements about a large class of critical points. The main idea is that with the condition $n_{k}\geq N-1$ the data is linearly separable at layer $k$. As modern neural networks are expressive enough to represent any function, see (Zhang et al., 2017) for an interesting discussion on this, one can expect that in some layer the training data becomes linearly separable. We prove that any critical point, for which the “learned” network outputs at any layer are linearly separable (see Definition 5.1) is a global minimum of the training error.

where the loss function now takes the new form

where $l_{1},l_{2}$ penalize the deviation from the label encoding for the true class resp. wrong classes. We assume that the minimum of $\Phi$ is attained over $\mathcal{P}.$ Note that $\Phi$ is bounded from below by zero as $l_{1}$ and $l_{2}$ are non-negative loss functions. The results of this section are made under the following assumptions on the activation and loss function.

In classification tasks, this loss function encourages higher values for the true class and lower values for wrong classes. An example of the loss function that satisfies Assumption 5.2 is given as (see Figure 2):

Note that for a $\{+1,-1\}$-label encoding, $+1$ for the true class and $-1$ for all wrong classes, one can rewrite (4) as

which is similar to the truncated squared loss (also called squared hinge loss) used in the SVM for binary classification.

Since $\sigma$ and $l$ are continuously differentiable, all the results from Lemma 2.1 still hold.

Our main result in this section is stated as follows.

Every critical point of $\Phi$ for which the feature vectors contained in the rows of $F_{k}$ are linearly separable and all the weight matrices $(W_{l})_{l=k+2}^{L}$ have full column rank is a global minimum.

If the training inputs are linearly separable then every critical point of $\Phi$ for which all the weight matrices $(W_{l})_{l=2}^{L}$ have full column rank is a global minimum.

Note that under the assumptions on the loss and activation function and since the features are separable, the terms in both sums are non-positive and thus the sum can only vanish if all terms vanish which implies

where the last inequality is implied by (6) as $W_{L}$ has full column rank $n_{L}=m$. Since the above product of matrices is a non-zero matrix, there must exist a non-zero column, say $p\in[n_{L-1}]$, then

Since $i_{L-1}$ is arbitrary, pick $i_{L-1}=p$ one obtains

Compared to (6), we have reduced the product from $\prod_{l=k+1}^{L-1}$ to $\prod_{l=k+1}^{L-2}$, By induction, one can easily show that

This in turn implies \Phi\Big{(}(W_{l},b_{l})_{l=1}^{L}\Big{)}=0. Thus the critical point $(W_{l},b_{l})_{l=1}^{L}$ is a global minimum.

This can be seen as a special case of the first statement. In particular, assume one has a zero-layer which coincides with the training inputs, namely $F_{0}=X$, then the result follows immediately.

$\Box$ Note that the second statement of Theorem 5.3 can be considered as a special case of the first statement. In the case where $L=2$ and training inputs are linearly separable, the second statement of our Theorem 5.3 recovers the similar result of (Gori & Tesi, 1992; Frasconi et al., 1997) for one-hidden layer networks.

Even though the assumptions of Theorem 3.4 and Theorem 5.3 are different in terms of class of activation and loss functions, their results are related. In fact, it is well known that if a set of vectors is linearly independent then they are linearly separable, see e.g. p.340 (Barber, 2012). Thus Theorem 5.3 can be seen as a direct generalization of Theorem 3.4. The caveat, which is also the main difference to Theorem 3.8, is that Theorem 5.3 makes only statements for all the critical points for which the problem has become separable at some layer, whereas there is no such condition in Theorem 3.8. However, we still think that the result is of practical relevance, as one can expect for a sufficiently large network that stochastic gradient descent will lead to a network structure where the data becomes separable at a particular layer. When this happens all the associated critical points are globally optimal. It is an interesting question for further research if one can show directly under some architecture condition that the network outputs become linearly separable at some layer for any local minimum and thus every local minimum is a global minimum.

Discussion

Our results show that the loss surface becomes well-behaved when there is a wide layer in the network. Implicitly, such a wide layer is often present in convolutional neural networks used in computer vision. It is thus an interesting future research question how and if our result can be generalized to neural networks with sparse connectivity. We think that the results presented in this paper are a significant addition to the recent understanding why deep learning works so efficiently. In particular, since in this paper we are directly working with the neural networks used in practice without any modifications or simplifications.

Acknowledgment

The authors acknowledge support by the ERC starting grant NOLEPRO 307793.

References