Recent theoretical work has demonstrated that deep neural networks have superior performance over shallow networks, but their training is more difficult, e.g., they suffer from the vanishing gradient problem. This problem can be typically resolved by the rectified linear unit (ReLU) activation. However, here we show that even for such activation, deep and narrow neural networks (NNs) will converge to erroneous mean or median states of the target function depending on the loss with high probability. Deep and narrow NNs are encountered in solving partial differential equations with high-order derivatives. We demonstrate this collapse of such NNs both numerically and theoretically, and provide estimates of the probability of collapse. We also construct a diagram of a safe region for designing NNs that avoid the collapse to erroneous states. Finally, we examine different ways of initialization and normalization that may avoid the collapse problem. Asymmetric initializations may reduce the probability of collapse but do not totally eliminate it. The best-known universal approximation theorems of neural networks (NNs) were obtained almost three decades ago by BID5 and BID18 , stating that every measurable function can be approximated accurately by a single-hidden-layer neural network, i.e., a shallow neural network. Although powerful, these results do not provide any information on the required size of a neural network to achieve a pre-specified accuracy. In BID2 , the author analyzed the size of a neural network to approximate functions using Fourier transforms. Subsequently, in BID27 , the authors considered optimal approximations of smooth and analytic functions in shallow networks, and demonstrated that −d/n neurons can uniformly approximate any C n -function on a compact set in R d with error . This is an interesting result and it shows that to approximate a three-dimensional function with accuracy 10 −6 we need to design a NN with 10 18 neurons for a C 1 function, but for a very smooth function, e.g., C 6 , we only need 1000 neurons. In the last 15 years, deep neural networks (i.e., networks with a large number of layers) have been used very effectively in diverse applications.After some initial debate, at the present time, it seems that deep NNs perform better than shallow NNs of comparable size, e.g., a 3-layer NN with 10 neurons per layer may be a better approximator than a 1-layer NN with 30 neurons. From the approximation point of view, there are several theoretical results to explain this superior performance. In BID9 , the authors showed that a simple approximately radial function can be approximated by a small 3-layer feed-forward NN, but it cannot be approximated by any 2-layer network with the same accuracy irrespective of the activation function, unless its width is exponential in the dimension (see ; BID29 ; BID6 for further discussions). In BID24 (see also Yarotsky (2017) ), the authors claimed that for -approximation of a large class of piecewise smooth functions using the rectified linear unit (ReLU) max(x, 0) activation function, a multilayer NN using Θ(log(1/ )) layers only needs O(poly log(1/ )) neurons, while Ω(poly(1/ )) neurons are required by NNs with o(log(1/ )) layers. That is, the number of neurons required by a shallow network to approximate a function is exponentially larger than the corresponding number of neurons needed by a deep network for a given accuracy level of function approximation. In BID33 , the authors studied approximation theory of a class of (possibly discontinuous) piecewise C β functions for ReLU NN, and they found that no more than O( −2(d−1)/β ) nonzero weights are required to approximate the function in the L 2 sense, which proves to be optimal. Under this optimality condition, they also show that a minimum depth (up to a multiplicative constant) is given by β/d to achieve optimal approximation rates. As for the expressive power of NNs in terms of the width, BID25 showed that any Lebesgue integrable function from R d to R can be approximated by a ReLU forward NN of width d + 4 with respect to L 1 distance, and cannot be approximated by any ReLU NN whose width is no more than d. BID14 showed that any continuous function can be approximated by a ReLU forward NN of width d in + d out , and they also give a quantitative estimate of the depth of the NN; here d in and d out are the dimensions of the input and output, respectively. For classification problems, networks with a pyramidal structure and a certain class of activation functions need to have width larger than the input dimension in order to produce disconnected decision regions BID31 .With regards to optimum activation function employed in the NN approximation, before 2010 the two commonly used non-linear activation functions were the logistic sigmoid 1/(1 + e −x ) and the hyperbolic tangent (tanh); they are essentially the same function by simple re-scaling, i.e., tanh(x) = 2 sigmoid(2x) − 1. The deep neural networks with these two activations are difficult to train BID11 . The non-zero mean of the sigmoid induces important singular values in the Hessian BID23 , and they both suffer from the vanishing gradient problem, especially through neurons near saturation BID11 . In 2011, ReLU was proposed, which avoids the vanishing gradient problem because of its linearity, and also results in highly sparse NNs BID12 . Since then, ReLU and its variants including leaky ReLU (LReLU) BID26 , parametric ReLU (PReLU) BID15 and ELU BID4 are favored in almost all deep learning models. Thus, in this study, we focus on the ReLU activation.While the aforementioned theoretical results are very powerful, they do not necessarily coincide with the results of training of NNs in practice which is NP-hard (Šíma, 2002) . For example , while the theory may suggest that the approximation of a multi-dimensional smooth function is accurate for NN with 10 layers and 5 neurons per layer, it may not be possible to realize this NN approximation in practice. BID10 first proved that existence of local minima poses a serious problem in learning of NNs. After that, more work has been done to understand bad local minima under different assumptions (Zhou & Liang, 2017; BID7 BID36 Wu et al., 2018; Yun et al., 2018) . Besides local minima, singularity BID0 and bad saddle points BID20 ) also affect training of NNs. Our paper focuses on a particular kind of bad local minima, i.e., those encountered in deep and narrow neural networks collapse with high probability. This is the topic of our work presented in this paper. Our results are summarized in FIG9 , which shows a diagram of the safe region of training to achieve the theoretically expected accuracy. As we show in the next section through numerical simulations as well as in subsequent sections through theoretical results, there is very high probability that for deep and narrow ReLU NNs will converge to an erroneous state, which may be the mean value of the function or its partial mean value. However, if the NN is trained with proper normalization techniques, such as batch normalization BID19 , the collapse can be avoided. Not every normalization technique is effective, for example, weight normalization BID37 leads to the collapse of the NN. We consider here ReLU neural networks for approximating multi-dimensional functions of different regularity, and in particular we focus on deep and narrow NNs due to their reportedly good approximation properties. However, we found that training such NNs is problematic because they converge to erroneous means or partial means or medians of the target function. We demonstrated this collapse problem numerically using one-and two-dimensional functions with C 0 , C ∞ and L 2 regularity. These numerical results are independent of the optimizers we used; the converged state depends on the loss but changing the loss function does not lead to correct answers. In particular, we have observed that the NN with MSE loss converges to the mean or partial mean values while the NN with MAE loss converges to the median values. This collapse phenomenon is induced by the symmetric random initialization, which is popular in practice because it maintains the length of the outputs of each layer as we show theoretically in Section 3.We analyze theoretically the collapse phenomenon by first proving that if a NN is a constant function then there must exist a layer with output 0 and the gradients of weights and biases in all the previous layers vanish (Lemma 1, Corollary 2, and Lemma 3). Subsequently, we prove that if such conditions are met, then the NN will converge to a constant value depending on the loss function (Theorem 4). Furthermore, if the output of NN is equal to the mean value of the target function, the gradients of weights and biases vanish (Corollaries 5 and 6). In Lemma 7 and Theorem 8 and Proposition 9, we derive estimates of the probability of collapse for general cases, and in Proposition 10, we derive a more precise estimate for deep NNs with width 2. These theoretical estimates are verified numerically by tests using NNs with different layers and widths. Based on these results, we construct a diagram which can be used as a practical guideline in designing deep and narrow NNs that do not suffer from the collapse phenomenon.Finally, we examine different methods of preventing deep and narrow NNs from converging to erroneous states. In particular, we find that asymmetric initializations including orthogonal initialization and LSUV cannot be used to avoid this collapse. However, some normalization techniques such as batch normalization and SELU can be used successfully to prevent the collapse of deep and narrow NNs; on the other hand, weight normalization fails. Similarly, we examine the effect of dropout which, however, also fails. DISPLAYFORM0 DISPLAYFORM1 is a summation of independent Gaussian random variables and thus is a Gaussian distribution. If l ≥ 3, by central limit theorem, DISPLAYFORM2 2 is the standard Gaussian measure. Therefore, DISPLAYFORM3 B PROOF OF LEMMA 1Lemma 11. Let A ∈ R n×m be a random matrix, where {A ij } i∈{1,2,...,n},j∈{1,2,...,m} are random variables, and the joint distribution of (A i1 , A i2 , . . . , A im ) is absolutely continuous for i = 1, 2, . . . , n. If x ∈ R m is a nonzero column vector, then P(Ax = 0) = 0.Proof. Let us consider the first value of Ax, i.e., Proof. By assumption A2 and Lemma 11, DISPLAYFORM4 is a constant function with respect to x 0 . So we can assume that there is ReLU in the last layer, and prove that there exists a layer l ∈ {1, . . . , L}, s.t., h l ≤ 0 and x l = 0 wp1 for every x 0 ∈ Ω. We proceed in two steps. DISPLAYFORM5 Because Ω ⊂ R din is a connected space with at least two points, then Ω has no isolated points, which impliesx 0 is not an isolated point. Since the neural network is a continuous map, DISPLAYFORM6 , which contradicts the fact that x 1 is a constant function. Therefore, h ≤ 0 and x 1 = 0.ii) Assume the theorem is true for L. Then for L + 1, if x 1 = 0, choose l = 1 and we are done; otherwise, consider the NN without the first layer with x 1 ∈ Ω 1 as the input, denoted N 1 . By i, Ω 1 is a connected space with at least two points. Because N 1 is a constant function of x 1 and has L layers, by induction, there exists a layer whose output is zero. Therefore, for the original neural network N , the output of such layer is also zero.By i and ii, the statement is true for any L.
Deep and narrow neural networks will converge to erroneous mean or median states of the target function depending on the loss with high probability. This paper studies failure modes of deep and narrow networks, focusing on as small as possible models for which the undesired behavior occurs. This paper shows that the training of deep ReLU neural networks will converge to a constant classifier with high probability over random initialization if hidden layer widths are too small.