We investigate the loss surface of neural networks. We prove that even for one-hidden-layer networks with "slightest" nonlinearity, the empirical risks have spurious local minima in most cases. Our results thus indicate that in general "no spurious local minim" is a property limited to deep linear networks, and insights obtained from linear networks may not be robust. Specifically, for ReLU(-like) networks we constructively prove that for almost all practical datasets there exist infinitely many local minima. We also present a counterexample for more general activations (sigmoid, tanh, arctan, ReLU, etc.), for which there exists a bad local minimum. Our results make the least restrictive assumptions relative to existing results on spurious local optima in neural networks. We complete our discussion by presenting a comprehensive characterization of global optimality for deep linear networks, which unifies other results on this topic. Neural network training reduces to solving nonconvex empirical risk minimization problems, a task that is in general intractable. But success stories of deep learning suggest that local minima of the empirical risk could be close to global minima. BID5 use spherical spin-glass models from statistical physics to justify how the size of neural networks may result in local minima that are close to global. However, due to the complexities introduced by nonlinearity, a rigorous understanding of optimality in deep neural networks remains elusive.Initial steps towards understanding optimality have focused on deep linear networks. This area has seen substantial recent progress. In deep linear networks there is no nonlinear activation; the output is simply a multilinear function of the input. BID1 prove that some shallow networks have no spurious local minima, and Kawaguchi (2016) extends this result to squared error deep linear networks, showing that they only have global minima and saddle points. Several other works on linear nets have also appeared (Lu & Kawaguchi, 2017; Freeman & Bruna, 2017; Yun et al., 2018; Zhou & Liang, 2018; Laurent & Brecht, 2018a; b) .The theory of nonlinear neural networks (which is the actual setting of interest), however, is still in its infancy. There have been attempts to extend the "local minima are global" property from linear to nonlinear networks, but recent results suggest that this property does not usually hold (Zhou & Liang, 2018) . Although not unexpected, rigorously proving such results turns out to be non-trivial, forcing several authors (e.g., Safran & Shamir (2018) ; BID8 ; Wu et al. (2018) ) to make somewhat unrealistic assumptions (realizability and Gaussianity) on data.In contrast, we prove existence of spurious local minima under the least restrictive (to our knowledge) assumptions. Since seemingly subtle changes to assumptions can greatly influence the analysis as well as the applicability of known results, let us first summarize what is known; this will also help provide a better intuitive perspective on our results (as the technical details are somewhat involved). We use the shorthandX := X (C1. DISPLAYFORM0 3) The activation function h ish s+,s− .(C1.4 ) The hidden layer has at least width 2: DISPLAYFORM1 Then, there is a spurious local minimum whose risk is the same as linear least squares model. Moreover , due to nonnegative homogeneity ofh s+,s− , there are infinitely many such local minima.Noticing that most real world datasets cannot be perfectly fit with linear models, Theorem 1 shows that when we use the activationh s+,s− , the empirical risk has bad local minima for almost all datasets that one may encounter in practice. Although it is not very surprising that neural networks have spurious local minima, proving this rigorously is non-trivial. We provide a constructive and deterministic proof for this problem that holds for general datasets, which is in contrast to experimental results of Safran & Shamir (2018) . We emphasize that Theorem 1 also holds even for "slightest" nonlinearities, e.g., when s + = 1 + and s − = 1 where > 0 is small. This suggests that the "local min is global" property is limited to the simplified setting of linear neural networks.Existing results on squared error loss either provide one counterexample (Swirszcz et al., 2016; Zhou & Liang, 2018) , or assume realizability and Gaussian input (Safran & Shamir, 2018; BID8 . Realizability is an assumption that the output is generated by a network with unknown parameters. In real datasets , neither input is Gaussian nor output is generated by neural networks; in contrast, our result holds for most realistic situations, and hence delivers useful insight.There are several results proving sufficient conditions for global optimality of nonlinear neural networks (Soudry & Carmon, 2016; Xie et al., 2016; Nguyen & Hein, 2017) . But they rely on assumptions that the network width scales with the number of data points. For instance, applying Theorem 3.4 of Nguyen & Hein (2017) to our network proves that ifX has linearly independent columns and other assumptions hold, then any critical point with W 2 = 0 is a global minimum. However, linearly independent columns already imply row(X) = R m , so even linear models RX can fit any Y ; i.e., there is less merit in using a complex model to fit Y . Theorem 1 does not make any structural assumption other than d 1 ≥ 2, and addresses the case where it is impossible to fit Y with linear models, which is much more realistic.It is worth comparing our result with Laurent & Brecht (2018a) , who use hinge loss based classification and assume linear separability to prove "no spurious local minima" for Leaky-ReLU networks. Their result does not contradict our theorem because the losses are different and we do not assume linear separability.One might wonder if our theorem holds even with d 1 ≥ m. Venturi et al. (2018) showed that onehidden-layer neural networks with d 1 ≥ m doesn't have spurious valleys, hence there is no strict spurious local minima; however, due to nonnegative homogeneity ofh s+,s− we only have non-strict local minima. Based on BID2 , one might claim that with wide enough hidden layer and random W 1 and b 1 , one can fit any Y ; however, this is not the case, by our assumption that linear models RX cannot fit Y . Note that for any d 1 , there is a non-trivial region (measure > 0) in the parameter space where entry-wise) . In this region, the output of neural networkŶ is still a linear combination of rows ofX, soŶ cannot fit Y ; in fact, it can only do as well as linear models. We will see in the Step 1 of Section 2.2 that the bad local minimum that we construct "kills" d 1 − 1 neurons; however, killing many neurons is not a necessity, and it is just to simply the exposition. In fact, any local minimum in the region W 1 X + b 1 1 T m > 0 is a spurious local minimum. DISPLAYFORM2 We are now ready to state our first main theorem, whose proof is deferred to Appendix A7. Theorem 4. Suppose that for all j, d j ≥ min{d x , d y }, and that the loss is given by (4), where 0 is differentiable on R dy×dx . For any critical point (Ŵ j ) H+1 j=1 of the loss , the following claims hold: DISPLAYFORM0 j=1 is a saddle of . DISPLAYFORM1 j=1 is a local min (max) of ifŴ H+1:1 is a local min (max) of 0 ; moreover, DISPLAYFORM2 j=1 is a global min (max) of if and only ifŴ H+1:1 is a global min (max) of 0 .3. If there exists j * ∈ [H + 1] such thatŴ H+1:j * +1 has full row rank andŴ j * −1:1 has full column rank, then ∇ 0 (Ŵ H+1:1 ) = 0, so 2(a ) and 2(b ) hold. Also , DISPLAYFORM3 j=1 is a local min (max) of .Let us paraphrase Theorem 4 in words. In particular, it states that if the hidden layers are "wide enough" so that the product W H+1:1 can attain full rank and if the loss assumes the form (4) for a differentiable loss 0 , then the type (optimal or saddle point) of a critical point (Ŵ j ) H+1 j=1 of is governed by the behavior of 0 at the productŴ H+1:1 .Note that for any critical point (Ŵ j ) H+1 j=1 of the loss , either ∇ 0 (Ŵ H+1:1 ) = 0 or ∇ 0 (Ŵ H+1:1 ) = 0. Parts 1 and 2 handle these two cases. Also observe that the condition in Part 3 implies ∇ 0 = 0, so Part 3 is a refinement of Part 2. A notable fact is that a sufficient condition for Part 3 isŴ H+1:1 having full rank. For example , if d x ≥ d y , full-rankŴ H+1:1 implies rank(Ŵ H+1:2 ) = d y , whereby the condition in Part 3 holds with j * = 1.IfŴ H+1:1 is not critical for 0 , then (Ŵ j ) H+1 j=1 must be a saddle point of . IfŴ H+1:1 is a local min/max of 0 , (Ŵ j ) H+1 j=1 is also a local min/max of . Notice, however , that Part 2(a) does not address the case of saddle points; whenŴ H+1:1 is a saddle point of 0 , the tuple (Ŵ j ) H+1 j=1 can behave arbitrarily. However, with the condition in Part 3, statements 2(a) and 3(a) hold at the same time, so thatŴ H+1:1 is a local min/max of 0 if and only if (Ŵ j ) H+1 j=1 is a local min/max of . Observe that the same "if and only if" statement holds for saddle points due to their definition; in summary, the types (min/max/saddle) of the critical points (Ŵ j ) H+1 j=1 andŴ H+1:1 match exactly. Although Theorem 4 itself is of interest, the following corollary highlights its key implication for deep linear networks. Corollary 5. In addition to the assumptions in Theorem 4, assume that any critical point of 0 is a global min (max). For any critical point (Ŵ j ) Corollary 5 shows that for any differentiable loss function 0 whose critical points are global minima, the loss has only global minima and saddle points, therefore satisfying the "local minima are global" property. In other words, for such an 0 , the multilinear re-parametrization introduced by deep linear networks does not introduce any spurious local minima/maxima; it only introduces saddle points. Importantly, Corollary 5 also provides a checkable condition that distinguishes global minima from saddle points. Since is nonconvex, it is remarkable that such a simple necessary and sufficient condition for global optimality is available. DISPLAYFORM4 Our result generalizes previous works on linear networks such as Kawaguchi FORMULA2 ; Yun et al. (2018) ; Zhou & Liang (2018) , because it provides conditions for global optimality for a broader range of loss functions without assumptions on datasets. Laurent & Brecht (2018b) proved that if DISPLAYFORM5 j=1 is a local min of , thenŴ H+1:1 is a critical point of 0 . First, observe that this result is implied by Theorem 4.1. So our result, which was proved in parallel and independently, is strictly more general. With additional assumption that critical points of 0 are global minima, Laurent & Brecht (2018b) showed that "local min is global" property holds for linear neural networks; our Corollay 5 gives a simple and efficient test condition as well as proving there are only global minima and saddles, which is clearly stronger. We investigated the loss surface of deep linear and nonlinear neural networks. We proved two theorems showing existence of spurious local minima on nonlinear networks, which apply to almost all datasets (Theorem 1) and a wide class of activations (Theorem 2). We concluded by Theorem 4, showing a general result studying the behavior of critical points in multilinearly parametrized functions, which unifies other existing results on linear neural networks. Given that spurious local minima are common in neural networks, a valuable future research direction will be investigating how far local minima are from global minima in general, and how the size of the network affects this gap. Another thing to note is that even though we showed the existence of spurious local minima in the whole parameter space, things can be different in restricted sets of parameter space (e.g., by adding regularizers). Understanding the loss surface in such sets would be valuable. Additionally, one can try to show algorithmic/trajectory results of (stochastic) gradient descent. We hope that our paper will be a stepping stone to such future research. A2 PROOF OF THEOREM 1, STEP 2, CASE 2
We constructively prove that even the slightest nonlinear activation functions introduce spurious local minima, for general datasets and activation functions.
{"src": "scitldr-AIC_train", "paper_id": "rke_YiRct7"}