Background: Statistical mechanics results (Dauphin et al. (2014); Choromanska et al. (2015)) suggest that local minima with high error are exponentially rare in high dimensions. However, to prove low error guarantees for Multilayer Neural Networks (MNNs), previous works so far required either a heavily modified MNN model or training method, strong assumptions on the labels (e.g., “near” linear separability), or an unrealistically wide hidden layer with \Omega\(N) units. 

 Results: We examine a MNN with one hidden layer of piecewise linear units, a single output, and a quadratic loss. We prove that, with high probability in the limit of N\rightarrow\infty datapoints, the volume of differentiable regions of the empiric loss containing sub-optimal differentiable local minima is exponentially vanishing in comparison with the same volume of global minima, given standard normal input of dimension d_0=\tilde{\Omega}(\sqrt{N}), and a more realistic number of d_1=\tilde{\Omega}(N/d_0) hidden units. We demonstrate our results numerically: for example, 0% binary classification training error on CIFAR with only N/d_0 = 16 hidden neurons. Motivation. Multilayer Neural Networks (MNNs), trained with simple variants of stochastic gradient descent (SGD), have achieved state-of-the-art performances in many areas of machine learning . However, theoretical explanations seem to lag far behind this empirical success (though many hardness results exist, e.g., BID44 BID42 ). For example, as a common rule-of-the-thumb, a MNN should have at least as many parameters as training samples. However, it is unclear why such over-parameterized MNNs often exhibit remarkably small generalization error (i.e., difference between "training error" and "test error"), even without explicit regularization BID54 .Moreover , it has long been a mystery why MNNs often achieve low training error BID10 . SGD is only guaranteed to converge to critical points in which the gradient of the expected loss is zero BID3 , and, specifically, to local minima BID35 ) (this is true also for regular gradient descent BID29 ). Since loss functions parameterized by MNN weights are non-convex, it is unclear why does SGD often work well -rather than converging to sub-optimal local minima with high training error, which are known to exist BID16 BID50 . Understanding this behavior is especially relevant in important cases where SGD does get stuck BID20 ) -where training error may be a bottleneck in further improving performance.Ideally, we would like to quantify the probability to converge to a local minimum as a function of the error at this minimum, where the probability is taken with the respect to the randomness of the initialization of the weights, the data and SGD. Specifically, we would like to know, under which conditions this probability is very small if the error is high, as was observed empirically (e.g., BID10 BID17 ). However, this seems to be a daunting task for realistic MNNs, since it requires a characterization of the sizes and distributions of the basins of attraction for all local minima.Previous works BID10 BID7 , based on statistical physics analogies, suggested a simpler property of MNNs: that with high probability, local minima with high error diminish exponentially with the number of parameters. Though proving such a geometric property with realistic assumptions would not guarantee convergence to global minima, it appears to be a necessary first step in this direction (see discussion on section 6). It was therefore pointed out as an open problem at the Conference of Learning Theory (COLT) 2015. However, one has to be careful and use realistic MMN architectures, or this problem becomes "too easy".For example, one can easily achieve zero training error (Nilsson, 1965; BID2 -if the MNN's last hidden layer has more neurons than training samples. Such extremely wide MNNs are easy to optimize (Yu, 1992; BID23 BID31 BID19 BID43 Nguyen & Hein, 2017) . In this case, the hidden layer becomes linearly separable in classification tasks, with high probability over the random initialization of the weights. Thus, by training the last layer we get to a global minimum (zero training error). However, such extremely wide layers are not very useful, since they result in a huge number of weights, and serious overfitting issues. Also, training only the last layer seems to take little advantage of the inherently non-linear nature of MNNs.Therefore, in this paper we are interested to understand the properties of local and global minima, but at a more practical number of parameters -and when at least two weight layers are trained. For example, Alexnet BID27 is trained using about 1.2 million ImageNet examples, and has about 60 million parameters -16 million of these in the two last weight layers. Suppose we now train the last two weight layers in such an over-parameterized MNN. When do the sub-optimal local minima become exponentially rare in comparison to the global minima?Main contributions. We focus on MNNs with a single hidden layer and piecewise linear units, optimized using the Mean Square Error (MSE) in a supervised binary classification task (Section 2). We define N as the number of training samples, d l as the width of the l-th activation layer, and g (x)<h (x) as an asymptotic inequality in the leading order (formally: lim x→∞ log g(x)log h(x) < 1). We examine Differentiable Local Minima (DLMs) of the MSE: sub-optimal DLMs where at least a fraction of > 0 of the training samples are classified incorrectly, and global minima where all samples are classified correctly.Our main result, Theorem 10, states that, with high probability, the total volume of the differentiable regions of the MSE containing sub-optimal DLMs is exponentially vanishing in comparison to the same volume of global minima, given that: Assumption 1. The datapoints (MNN inputs) are sampled from a standard normal distribution. 4 N neurons. This improves over previously known results (Yu, 1992; BID23 BID31 BID43 Nguyen & Hein, 2017 ) -which require an extremely wide hidden layer with d 1 ≥ N neurons (and thus N d 0 parameters) to remove sub-optimal local minima with high probability.In section 5 we validate our results numerically. We show that indeed the training error becomes low when the number of parameters is close to N . For example, with binary classification on CIFAR and ImageNet, with only 16 and 105 hidden neurons (about N/d 0 ), respectively, we obtain less then 0.1% training error. Additionally, we find that convergence to non-differentiable critical points does not appear to be very common.Lastly, in section 6 we discuss our results might be extended, such as how to apply them to "mildly" non-differentiable critical points.Plausibility of assumptions. Assumption 1 is common in this type of analysis (Andoni et al. , 2014; BID7 BID53 BID51 BID4 . At first it may appear rather unrealistic, especially since the inputs are correlated in typical datasets. However, this no-correlation part of the assumption may seem more justified if we recall that datasets are many times whitened before being used as inputs. Alternatively, if, as in our motivating question, we consider the input to the our simple MNN to be the output of the previous layers of a deep MNN with fixed random weights, this also tends to de-correlate inputs (Poole et al., 2016, Figure 3) . The remaining part of assumption 1, that the distribution is normal , is indeed strong, but might be relaxed in the future, e.g. using central limit theorem type arguments.In assumption 2 we use this asymptotic limit to simplify our proofs and final results. Multiplicative constants and finite (yet large) N results can be found by inspection of the proofs. We assume a constant error since typically the limit → 0 is avoided to prevent overfitting.In assumption 3, for simplicity we have d 0≤ N , since in the case d 0 ≥ N the input is generically linearly separable, and sub-optimal local minima are not a problem BID18 BID39 . Additionally, we have √ N<d 0 , which seems very reasonable, since for example, d 0 /N ≈ 0.016, 0.061 and 0.055 MNIST, CIFAR and ImageNet, respectively.In assumption 4, for simplicity we have d 1< N , since, as mentioned earlier, if d 1 ≥ N the hidden layer is linearly separable with high probability, which removes sub-optimal local minima. The other bound N log 4 N<d 0 d 1 is our main innovation -a large over-parameterization which is nevertheless asymptotically mild and improves previous results.Previous work. So far, general low (training or test) error guarantees for MNNs could not be found -unless the underlying model (MNN) or learning method (SGD or its variants) have been significantly modified. For example, BID10 made an analogy with high-dimensional random Gaussian functions, local minima with high error are exponentially rare in high dimensions; BID7 BID25 replaced the units (activation functions) with independent random variables; BID36 replaces the weights and error residuals with independent random variables; (Baldi, 1989; BID40 BID20 BID32 BID57 used linear units; BID55 used unconventional units (e.g., polynomials) and very large hidden layers (d 1 = poly (d 0 ), typically N ); BID4 BID11 BID41 used a modified convnet model with less then d 0 parameters (therefore, not a universal approximator BID9 BID22 ); BID51 BID47 BID30 assume the weights are initialized very close to those of the teacher generating the labels; and BID24 BID56 ) use a non-standard tensor method during training. Such approaches fall short of explaining the widespread success of standard MNN models and training practices.Other works placed strong assumptions on the target functions. For example, to prove convergence of the training error near the global minimum, BID18 assumed linearly separable datasets, while BID39 assumed strong clustering of the targets ("near" linear-separability). Also, (Andoni et al., 2014) showed a p-degree polynomial is learnable by a MNN, if the hidden layer is very large ( DISPLAYFORM0 , typically N ) so learning the last weight layer is sufficient. However, these are not the typical regimes in which MNNs are required or used. In contrast, we make no assumption on the target function. Other closely related results BID48 BID53 ) also used unrealistic assumptions, are discussed in section 6, in regards to the details of our main results. Therefore, in contrast to previous works, the assumptions in this paper are applicable in some situations (e.g., Gaussian input) where a MNN trained using SGD might be used and be useful (e.g., have a lower test error then a linear classier). In this paper we examine Differentiable Local Minima (DLMs) of the empiric loss of Multilayer Neural Networks (MNNs) with one hidden layer, scalar output, and LReLU nonlinearities (section 2). We prove (Theorem 10) that with high probability the angular volume (definition 3) of sub-optimal DLMs is exponentially vanishing in comparison to the angular volume of global minima (definition 4), under assumptions 1-4. This results from an upper bound on sub-optimal DLMs (Theorem 6) and a lower bound on global minima (Theorem 9). 2 /5 for 1000 epochs, then decreased the learning rate exponentially for another 1000 epochs. This was repeated 30 times. For all d and repeats, we see that (left) the final absolute value of the minimal neural input (i.e., min i,n w i x (n) ) in the range of 10 −3 − 10 0 , which is much larger then (right) the final MSE error for all d and all repeats -in the range 10 −31 − 10 −7 .Convergence of SGD to DLMs. These results suggest a mechanism through which low training error is obtained in such MNNs. However, they do not guarantee it. One issue is that sub-optimal DLMs may have exponentially large basins of attraction. We see two possible paths that might address this issue in future work, using additional assumptions on y. One approach is to show that, with high probability, no sub optimal DLM falls within the vanishingly small differentiable regions we bounded in Theorem 6. Another approach would be to bound the size of these basins of attraction, by showing that sufficiently large of number of differentiable regions near the DLM are also vanishingly small (other methods might also help here BID15 ). Another issue is that SGD might get stuck near differentiable saddle points, if their Hessian does not have strictly negative eigenvalues (i.e., the strict saddle property ). It should be straightforward to show that such points also have exponentially vanishing angular volume, similar to sub-optimal DLMs. Lastly, SGD might also converge to non-differentiable critical points, which we discuss next.Non-differentiable critical points. The proof of Theorem 6 stems from a first order necessary condition (Lemma 2): (A • X) e = 0, which is true for any DLM. However, non-differentiable critical points, in which some neural inputs are exactly zero, may also exist (though, numerically, they don't seem very common -see FIG1 .2). In this case, to derive a similar bound , we can replace the condition with P (A • X) e = 0, where P is a projection matrix to the subspace orthogonal to the non-differentiable directions. As long as there are not too many zero neural inputs, we should be able to obtain similar results. For example, if only a constant ratio r of the neural inputs are zero, we can simply choose P to remove all rows of (A • X) corresponding to those neurons, and proceed with exactly the same proof as before, with d 1 replaced with (1 − r) d 1 . It remains a theoretical challenge to find reasonable assumptions under which the number of non-differentiable directions (i.e., zero neural inputs) does not become too large.Related results. Two works have also derived related results using the (A • X) e = 0 condition from Lemma 2. In BID48 , it was noticed that an infinitesimal perturbation of A makes the matrix A • X full rank with probability 1 (Allman et al., 2009, Lemma 13 ) -which entails that e = 0 at all DLMs. Though a simple and intuitive approach, such an infinitesimal perturbation is problematic: from continuity, it cannot change the original MSE at sub-optimal DLMs -unless the weights go to infinity, or the DLM becomes non-differentiable -which are both undesirable results. An extension of this analysis was also done to constrain e using the singular values of A•X BID53 , deriving bounds that are easier to combine with generalization bounds. Though a promising approach, the size of the sub-optimal regions (where the error is high) does not vanish exponentially in the derived bounds. More importantly, these bounds require assumptions on the activation kernel spectrum γ m , which do not appear to hold in practice (e.g., BID53 , Theorems 1,3) require mγ m 1 to hold with high probability, while mγ m < 10 −2 in BID53 , FIG9 ).Modifications and extensions. There are many relatively simple extensions of these results: the Gaussian assumption could be relaxed to other near-isotropic distributions (e.g., sparse-land model, (Elad, 2010, Section 9 .2)) and other convex loss functions are possible instead of the quadratic loss. More challenging directions are extending our results to MNNs with multi-output and multiple hidden layers, or combining our training error results with novel generalization bounds which might be better suited for MNNs (e.g., BID14 BID46 BID12 ) than previous approaches BID54 .
"Bad" local minima are vanishing in a multilayer neural net: a proof with more reasonable assumptions than before In networks with a single hidden layer, the volume of suboptimal local minima exponentially decreases in comparison to global minima. This paper aims to answer why standard SGD based algorithms on neural network converge to 'good' solutions.