Title: WHAT ILLNESS OF LANDSCAPE CAN OVER-PARAMETERIZATION ALONE CURE?

Abstract: Over-parameterized networks are widely believed to have nice landscape, but what rigorous results can we prove? In this work, we prove that: (i) from underparameterized to over-parameterized networks, there is a phase transition from having sub-optimal basins to no sub-optimal basins; (ii) over-parameterization alone cannot eliminate bad non-strict local minima. Specifically, we prove that for any continuous activation functions, the loss surface of a class of over-parameterized networks has no sub-optimal basin, where "basin" is defined as the setwise strict local minimum. Furthermore, for under-parameterized network, we construct loss landscape with strict local minimum that is not global. We then show that it is impossible to prove "all over-parameterized networks have no sub-optimal local minima", by giving counter-examples for 1-hidden-layer networks with a class of neurons. Viewing various bad patterns of landscape as illnesses (bad basins, flat regions, etc.), our results indicate that over-parameterization is not a panacea for every "illness" of the landscape, but it can cure one practically annoying illness (bad basins).

1. INTRODUCTION:

It is empirically observed that over-parameterized networks can achieve small training error Bengio et al. (2006) ; Zhang et al. (2017) ; Livni et al. (2014) ; Neyshabur et al. (2017) ; Geiger et al. (2018) . These observations are often explained by the intuition that more parameters can "smooth the landscape" Livni et al. (2014) ; Lopez-Paz & Sagun (2018) . While the intuition looks reasonable, can we provide some rigorous theory to formalize this intuition that "over-parameterized networks have nice landscape"? Before answering this question, we would like to draw an analogy to the deep learning landscape. If we view the landscape as a human body, the bad properties (e.g., sub-optimal minima, saddle points, flat regions) can be regarded as different types of illness. Then, the aforementioned question become: Can over-parameterization cure all these diseases? If not, which specific type of illness can over-parameterization cure?

In this work, we aim at clearly identifying the "pharmacodynamics" of over-parameterization alone. To this end, we derive a serial of results on the loss landscape. Interestingly, our results are established in a way similar to a scientific experiment.

First, we hope to find out a property that holds for over-parameterized networks but not underparameterized networks. Here the over-parameterized networks are like the treatment groups, while the under-parameterized networks are like the control group. In this way, we can claim that overparameterization does really benefit the landscape.

Second, our theory should has minimal assumptions on other aspects except over-parameterization. Potentially, there are many other factors that affects the landscape. For example, with linear neurons Kawaguchi (2016) "no bad local inima" can be proved, implying that the choice of activation functions can impact the landscape. Thus, we should treat factors like activation function, loss function and training data as "control variables". We would like to minimize the effect of these factors, and see how far we can go based on merely the condition of over-parameterization. To conclude, in this work we endeavor to explore the "true benefit of over-parameterization alone".

• "True": In terms of "true", we specify that the advantage of over-parameterization is not the commonly-believed "elimination of bad local minima", but "elimination of bad basin". On the positive side, we prove that bad basin does not exist in over-parameterized neural networks. On the negative side, we show that bad local minima do exist.

• "Benefit": In terms of "benefit", we emphasize that "elimination of bad basin" is indeed a property brought by over-parameterization. To demonstrate this, we give an example to show that bad strict local minima exist in "exactly" under-parameterized neural networks, and analyze how over-parameterization makes a difference in the landscape of loss surface.

• "Alone": In terms of "alone", we want to remove other confounding factors that may help the landscape. For instance, linear networks are known to have nice landscape, implying that activation functions can have a large impact on the landscape. Thus we want to reduce the impact of neuron activations by imposing mild condition on the activations.

More details are given in the next subsection.

1.1. MAIN CONTRIBUTIONS:

We first explain some geometrical concepts. A function is called "global function" if no sub-optimal local minimum exists. A function is called "weakly global function" if it admits no setwise bad strict local minima (defined in Josz et al. (2018) ), as illustrated in Figure 1 A key geometrical property studied in our paper is called "Property PT": at any point, after a small perturbation there is a strictly decreasing path to the global minima. Property PT was proposed in the early work Yu & Chen (1995) , and was claimed to imply "no bad local minima", but we provide a counter-example to show that this is not true. We show that Property PT actually implies "no bad setwise strict local minima" (i.e. weakly global function).

Our first result roughly states that for any continuous activation function, the loss function of overparameterized networks (with a wide last hidden layer) is a weakly global function. Therefore, over-parameterized networks have nice landscape in the sense that truly bad local minima do not exist. We also extend this result to the case with one wide layer (not necessarily the last hidden layer) 1 , though with extra assumptions on the structure and some neurons (see Assumption 2).

Last but not least, we show by counter-example that, with other assumptions unchanged, underparameterized networks may have sub-optimal basins, i.e, not weakly global.

We provide a brief summary of our contributions as follows:

• We give an example to show over-parameterized neural networks can have bad local minima for a large class of neurons (Section 6.2), which reveals the limitation of over-paramterized networks.

• We give an example to show that Property PT does not imply "no bad local minima" (Section 6.1). This shows that the proof of a classical work Yu & Chen (1995) on overparamterized networks is incorrect. This example improves our geometrical understanding of the landscape.

• When the last hidden layer has at least N neurons (N is the number of samples), for any continuous activations, we prove that the loss function is weakly global (Theorem 1).

• When there is one wide layer with at least N neurons, under extra assumptions the loss function is a weakly global function (Theorem 2).

• We show that under-parameterized neural networks do have bad strict local minima, for any number of neurons and any generic data x. Our results clarify the role of overparameterization in eliminating bad strict local minima.

1.2. PAPER ORGANIZATION:

This paper is organized as follows. We first provide a geometric explanation of our main idea in Section 2 and review some related works in Section 3. In Section 4, we present the main results.

In Section 5, we highlight the main proof ideas. Section 6 provides various examples of bad local minima. Conclusions are presented in Section 7.

2. GEOMETRIC EXPLANATION:



2.1. LANDSCAPE ANALYSIS OF THE 1-DIMENSIONAL CASE:

Simple examples can go far: the phenomenons revealed by simple examples can often offer great insight about very general problems. One good example is min v,w∈R (vw -1) 2 : it is a non-convex function but it does not have bad local-min as the reparameterization does not destroy the nice landscape of the outer function. This insight can be extended to even the general deep linear networks Kawaguchi (2016) . In this part, we discuss the 1-dim non-linear problem (1 -vσ(w)) 2 . Interestingly, the geometrical phenomenons for this general 1-dim case still occur in deep over-parameterized networks (but not in under-parameterized networks). Therefore, to understand the major geometrical properties discussed in this paper, one only needs to understand this 1-dimensional example.

Consider a 1-hidden-layer-1-neuron network with network output ŷ = vσ(wx). Assume that only one data sample pair (x, y) = (1, 1) is given and the quadratic loss is employed. Thus, the empirical loss is given by E(w, v) = (y -ŷ) 2 . Then, with the given sample pair, the empirical loss is represented by

(1 -vσ(w)) 2 .

The landscape of the considered network is determined by the activation function. In particular, we discuss the following three cases:

1. The activation function is linear, i.e., σ(z) = z. The empirical loss is thus (1 -uv) 2 , which obviously does not contain bad local minima.

2. The activation function is nonlinear and strictly monotone. Bad local minima also do not exist in this case.

3. The activation function is nonlinear and non-monotone. In this case, bad local minima may exist. For example, the activation function is quadratic, i.e. , σ(z) = z2 . Points on line segment l : {(w, v) | w = 0, v < 0} are all spurious local minima with a loss of 1. To see this, note that vw 2 is non-positive in the neighborhood of line segment l, so (1 -vw 2 ) 2 is always at least 1. One important feature in this example is that w = 0 is a local minimum of σ(w). This means that after perturbing w, σ(w) can only move in one direction so that the sign of vw 2 can be controlled.

Case 1 is generalizable to deep networks: as mentioned earlier, the geometrical property of deep linear networks is similar to 1-dim linear problem. Which case can reflect the geometrical property of a deep non-linear over-parameterized networks? Currently, it seems that Case 2 cannot be extended:

it is still open whether increasing activation can eliminate bad local-min 2 . This is why we do not want to focus on increasing activations since there is a gap between the simplest case and the general case.

Our paper intends to show that Case 3 captures the major geometrical properties of a general deep non-linear over-parameterized networks: it has bad non-strict local-min, but it has no bad basin. The intuition comes as the following: in the example constructed, we can find that these bad local minima in fact lie in a plateau (so they are non-strict). Moreover, at the boundary of the plateau there is a decreasing direction. This implies that these bad local minima do not lie in a basin, so theoretically they are possible to escape with algorithms like noisy GD. In the rest of this paper, we will show that this is the case for all deep over-parameterized neural networks, i.e., all deep over-parameterized neural networks do not contain bad basins. This result characterizes what benefits over-parameterization alone brings to general neural networks.

2.2. STRICT LOCAL MINIMUM EXISTS FOR UNDER-PARAMETERIZED NEURAL NETWORKS:

One may wonder whether the previous 1-dim example actually reveals the insight of all networks, not just over-parameterized networks. We show that the answer is no: for under-parameterized networks, strict bad local-min exists for fairly general settings. Our examples also explains the geometrical reasons how over-parameterization "cures" the illenss of bad basins.

Suppose there are two sample pairs

(x 1 , y 1 ) = (1, 2), (x 2 , y 2 ) = (2, 0). Consider a 1-hidden-layer- 1-neuron neural network ŷ = vσ(wx). Let (v, w) = (1, 0) and σ(z) = z 2 (1 -z 2 ) + 1. Then (ŷ 1 , ŷ2 ) = (1, 1

). We plot the figure of the output data and activation function σ(•) separately.

We will now show that (v, w) = (1, 0) is a bad strict local minimum through these two figures.

In Figure 2 (a), we mark out the true data (y 1 , y 2 ) = (2, 0) and the current output (ŷ 1 , ŷ2 ) = (1, 1). Note that σ(wx 1 ) = σ(wx 2 ) = σ(0) = 1, if we change only v and not w, (ŷ 1 , ŷ 2 ) = (v σ(wx 1 ), v σ(wx 2 )) = (v , v ) . This means that if we only perturb v, the new output (ŷ 1 , ŷ 2 ) will move along line h = {(e 1 , e 2 ) : e 1 = e 2 } (illustrated as the red line in Figure 2 (a)). On the other hand, (ŷ 1 , ŷ2 ) = (1, 1) is exactly the projection of (y 1 , y 2 ) to line h. Consequently, perturbing v alone will move the new output (ŷ 1 , ŷ 2 ) away from the true data (y 1 , y 2 ), thus strictly increasing the empirical loss (distance).

What if we perturb w simultaneously? In Figure 2 (b) we plot the value of σ(wx) before and after perturbation. Before perturbation, σ(wx 1 ) = σ(wx 2 ) = 1. After perturbation, both σ(w x 1 ) and σ(w x 2 ) rise above 1. However, since x 2 = 2 > 1 = x 1 , σ(w x 2 ) is always larger than σ(w x 1 ) due to the special landscape of σ(•). This implies that we always have ŷ 2 = v σ(w x 2 ) > v σ(w x 1 ) = ŷ 1 . Therefore, the feasible region of (ŷ 1 , ŷ 2 ) is above line h (illustrated as the cyan region in Figure 2 (a)), and hence any perturbation of (v, w) will result in a larger distance between (ŷ 1 , ŷ 2 ) and (y 1 , y 2 ), increasing the empirical loss.

From the analysis above, we can conclude that a bad strict local minimum occurs when

• Due to under-parameterization, the perturbation direction provided by the last hidden-layer lies in a hyperplane of the whole space.

• Due to landscape of activation function, the perturbation direction provided by the previous hidden layers lies in a halfspace.

The first condition demonstrates the key difference between under-parameterized and overparameterized neural networks. For over-parameterized networks, one of the following two circumstances happens: a) the perturbation direction provided by the last hidden-layer is the whole space, implying that a decreasing path exists if the current point is not a global minimum; (b) the perturbation direction provided by the last hidden-layer still lies in a hyperplane of the whole space.

In this circumstance, since neurons are over-parameterized, the input of the last hidden layer is linearly dependent. Hence, there must exist a perturbation of the last hidden layer that keeps the objective function value unchanged, eliminating bad strict local minimum. Thus over-parameterized networks can not have bad strict local minimum. In contrast, for under-parameterized networks, even if the the input of the last hidden layer is linearly independent, the perturbation direction provided by the last hidden-layer still lies in a hyperplane of the whole space. If the true data does not lie in this hyperplane, bad strict local minimum may exist.

The second condition demonstrates that existence of bad local minimum is highly related to the perturbation direction determined by the landscape of activation function. The landscape that leads to a restricted perturbation direction, as analyzed in the proof, is in fact rather common and not specified to particular activation functions. This finding implies that existence of bad strict local minimum is commonly seen in under-parameterization networks. It is noteworthy that over-parameterization, on the contrary, does not play a decisive role in perturbation direction. That's why bad local minimum still exists in over-parameterization networks. However, due to the first condition, bad strict local minimum is eliminated by over-parameterization.

Finally, this example can be generalized to under-parameterized neural networks with any width through the following proposition:

Proposition 1 For any N input data x 1 , • • • , x N ∈ R with x n = x n , ∀n = n , there exists N output data y 1 , • • • , y N ∈ R

and a 1-hidden-layer neural network with N -1 neurons such that the empirical loss E(•) has bad strict local minimum.

It is noteworthy that the requirement for σ(•) is quite mild. We only need to characterize first-order and second-order derivatives of σ(•) at specific points rather than in the whole domain of R. This implies that such σ(•) we construct can possess good properties such as monotonicity. Furthermore, we can relax the requirement for the second-order derivative to be

N i=1 x 2 i • a i σ (w j x i ) > 0 for all j = 1, • • • , N -1.

With this relaxed requirement, σ(•) can even be convex.

3. RELATED WORKS AND DISCUSSIONS:

We notice that our results may have a strong connection to the "lottery ticket hypothesis" Frankle & Carbin (2019) . It was found in Frankle & Carbin (2019) that a large (and generally over-parameterized) feedforward network contains a subnetwork that, when properly initialized, can be trained to achieve similar performance to the original network, i.e., the "wining ticket". However, if such subnetwork is randomly initialized, it no longer matches the performance of the original network. This experiment is nice as it rules out the effect of representation power, and indicates that the worse performance of small networks is due to optimization, not due to representation power. Which part of the optimization makes the difference? Early works Dauphin et al. (2014) conjectured that saddle points cause bad performance, but there is no clear evidence that saddle points exist in small networks but not in large networks. Our result proved rigorously that at least bad basin is a difference between small and big networks. Thus based on our result, we conjectured that the lottery tickets are due to bad basins. The verification of this conjecture is beyond the scope of this paper (since checking basins is computatationally expensive), and we leave it to future work.

The loss surface of neural networks has been extensively studied in recent years Du & Lee (2018) Li & Liang (2018) . Most works are only about one-hidden-layer networks (many assume second layer weights are fixed, and many have strong assumptions on data distributions). There are some works on deep neural networks, but they either only show a subset of local minima are global minima Haeffele et al. (2014) ; Haeffele & Vidal (2015) ; Soudry & Carmon (2016) ; Nguyen & Hein (2017a; b) ; Shamir (2018) , or require special neurons such as linear neurons Baldi & Hornik (1989) ; Kawaguchi (2016) ; Freeman & Bruna (2016) ; Hardt & Ma (2017) ; Yun et al. (2017) . Some very recent works Du et al. (2018a) ; Allen-Zhu et al. (2018) ; Zou et al. (2018) prove that GD (gradient descent) converges to global minima at a linear rate for deep neural networks, which extend earlier works on 1-hidden-layer networks Li & Liang (2018) ; Du et al. (2018b) . Their conclusions are stronger than our landscape analysis since they can prove linear convergence, but their assumption is also stronger. In particular, these works require a large number of neurons, e.g. at least O(n k ) neurons in every layer for deep networks, where n is the number of samples and k is a certain integer such as k = 24 in Allen- Zhu et al. (2018) . In practical neural networks such as VGG and ResNet, the number of neurons is in the order of O(n), and even O(n 2 ) neurons is difficult to implement in practice. It will be interesting to prove results that combine the strengths of those works and our landscape analysis.

Moreover, two recent works Nguyen et al. (2018) ; Liang et al. (2018b) have addressed similar issues to our work. Specifically, Nguyen et al. (2018) covers a rather broad range of network structures, but only holds for a limited family of activation functions, which does not include activation functions such as ReLU, leaky ReLU, quadratic and Swish activation Ramachandran et al. (2018) . Liang et al. (2018b) eliminates bad local minima by adding a special type of exponential neuron. In contrast, our result holds for any continuous activation function, so is closer to practical settings in this sense. In addition, these works do not show a phase transition from under-parameterized to over-parameterized networks.

Finally, landscape analysis is just one part of the deep learning theory, which includes representation, optimization and generalization. In terms of generalization, many recent works Neyshabur et al. (2017) ; Bartlett et al. (2017) ; Poggio et al. (2018) try to understand why over-parameteriztion does not cause overfitting. This is a very interesting line of research, but its underlying assumption that over-parameterization can lead to small training error still requires rigorous justification. Our study is orthogonal and complimentary to the research on generalization error.

4. MAIN THEOREMS:



4.1. NETWORK MODEL:

We consider a fully-connected neural network f W : R dx → R dy that maps an input data x ∈ R dx to a predicted output ŷ ∈ R dy . Specifically, the network output is given by

ŷ = f W (x) = W H+1 σ H (W H • • • σ 2 (W 2 σ 1 (W 1 x))) (1)

where H is the number of hidden layers, σ : R h → R is the neuron activation function (sometimes simply called "activation" or "neuron") of the h-th hidden layer,

W h ∈ R d h ×d h-1 is the weight matrix to the h-th hidden layer for h = 1, • • • , H, W H ∈ R d H+1 ×d

H is the weight matrix to the output layer. Note that we define d 0 = d x and d H+1 = d y , and the scalar function σ h is applied entry-wise if its input is a vector or a matrix. Throughout the paper, we omit the "bias" term in the expression of neural networks for simplicity of presentation.

Let W = (W 1 , • • • , W H ) denote the collection of all network weights. Given N pairs of training data (x (n) , y (n) ), n = 1, • • • , N

, the empirical loss of the considered network as

EQUATION

where  and l(•, •) is the loss function. Then, the training problem of the considered network is to find W that minimize the empirical loss E(W ).

Y [y (1) , • • • , y (N ) ] ∈ R dy×N , Ŷ [f W (x (1) ), • • • , f W (x (N ) )] ∈ R dy×N ,

In this section, we present our main result on the absence of sub-optimal basin on the loss surface. Specifically, we define "basin" as the setwise strict local minimum, a notion borrowed from Josz et al. (2018) .

Definition 1 (Setwise strict local minimum) We say that a compact subset X ∈ S is a strict local minimum of f : S → R in the sense of sets if there exists ε > 0 such that for all x ∈ X and for all y ∈ S \ X satisfying x -y 2 ≤ ε, it holds that f (x) < f (y).

Definition 1 generalizes the notion of strict local minimum from the sense of points to the sense of sets. Any strict local minimum must be setwise strict local minimum, but not vice versa. A pleateau at the bottom of a basin, as shown in the right part of Figure 1 , is also a setwise strict local minimum.

Definition 2 (Weakly global function) We say that f : S → R is a weakly global function if it is continuous and all setwise strict local minima are setwise global minima.

Definition 2 introduces an important class of continuous functions, termed weakly global functions, which admits no bad strict local minima in the sense of sets, and hence no sub-optimal basin. Now we specify our assumptions for the first theorem. on the training dataset, the loss functions, the over-parameterization, and the activation functions.

Assumption 1 A1 There exists a dimension k such that x

(n) k = x (n ) k , ∀n = n ; A2 The loss function l(Y, Ŷ ) is convex respect to Ŷ ; A3 d H ≥ N ; A4 The activation function σ h is continuous for all h = 1, • • • , H.

Assumption A1 implies that the input data samples need to be distinguished with each other in one dimension. This can be always achieved if we allow an arbitrarily small perturbation on data. Assumption A2 is satisfied for almost all commonly-used loss functions, including quadratic, cross entropy, etc. Assumption A3 is the over-parameterization assumption, which only requires the last hidden layer to be wide. There is no assumption on the width of all other hidden layers. Assumption A4 is a very mild assumption on the neuron activation that it should be continuous.

We are now ready to present the first main theorem.

Theorem 1 Suppose that a fully connected neural network satisfies Assumption 1. Then, the empirical loss E(W ) is a weakly global function.

Theorem 1 states that the empirical loss function of an over-parameterized neural network is weakly global as long as the activation function is continuous. Note that the notion of weakly global function is distinct from that of "no bad local valleys" used in Nguyen et al. (2018) ; Venturi et al. (2018) , but they both guarantee non-existence of bad strict local minimum. Formally, we have the following corollary.

Corollary 1 The loss surface of a fully connected neural network satisfying Assumption 1 has no bad strict local minimum.

Theorem 1 requires that the last hidden layer is sufficiently "wide". Next, we show that if we add a pyramid structure after the "wide" hidden layer, the resulting loss surface still has no sub-optimal basin. We specify such pyramid structure by the the following assumption.

Assumption 2 There exists 1 ≤ h 0 ≤ H such that B1 d h0 ≥ N , d h0 ≥ d h0+1 ≥ • • • ≥ d H+1 ;

B2 For all h 0 + 1 ≤ h ≤ H, the activation function σ h is non-increasing or non-decreasing over R.

Then it can be shown that our main result still holds after adding the pyramid architecture:

Theorem 2 Suppose that a fully connected neural network satisfies Assumption A1, A2, A4, and 2.

Then, the empirical loss E(W ) is a weakly global function.

Corollary 2:

The loss surface of a fully connected neural network satisfying Assumption A1, A2, A4, and 2 has no bad strict local minimum.

5. PROOF IDEAS:



5.1. PROPERTY THAT ELIMINATES BAD STRICT LOCAL MINIMUM:

Consider a 1-hidden-layer network with d input dimensions and m hidden-layer neurons. The output of the network is given by t

= v σ(W X) ∈ R 1×N , where X = [x 1 , x 2 , • • • , x N ] ∈ R d×N

is the input data matrix consisting of N data samples, W ∈ R m×d is the weights to the hidden layer, v ∈ R m is the weights to the output layer. The loss function is quadratic, i.e., l(y, t) = ||t -y|| 2 2 . The network is assumed to be over-parameterized, i.e., m > N . Now we denote Z = σ(W X) ∈ R m×N as the output matrix of the hidden layer. The training of the considered network can be formulated as

min v,W t -v Z 2 (3)

A simple but important observation Gori & Tesi (1992) is that if Z is of full column rank, i.e., rank-N , problem equation 3 (with fixed W ) is strongly convex with respect to v. Then, we can find a strictly decreasing path to the global infimum (with respect to v) of equation 3. Moreover, for any t, there exists v such that v Z = t, so the infimum equals 0, which is the global infimum ofequation 3. Thus, there is a strictly decreasing path to the global infimum of equation 3, and hence the network parameter (W, v) cannot be a bad local minimum if the corresponding Z is rank-N .

It is noteworthy that when Z is not full rank, the infimum (with respect to v) of equation 3 may not be equal to the global infimum of equation 3, so the previous decreasing-path approach does not work. (Obviously, matrix Z is not always rank-N . For example, if W is a zero matrix, the corresponding Z is at most rank-1 regardless of the number of hidden neurons and activation function.) Regarding this, we introduce a property that can eliminate all bad setwise strict local minima on the loss surface.

Property PT: After a generic perturbation of any initial weight, there exists a strictly decreasing path to the global infimum.

We claim that if Property PT holds, the loss function with respect to (v, W ) is a weakly global function, which admits no setwise bad strict local minimum. Note that weakly global function also implies the non-existence of (point-wise) bad strict local minimum.

Whether Property PT holds highly depends on the activation function. In this paper, we identify a class of activation functions that guarantee Property PT. Specifically, we show that if the activation function is analytic and has non-vanishing derivatives at zero up to N -th order, Property PT holds. This enables us to prove that the loss surface is weakly global. However, to extend this result to all continuous activation functions remains a challenging task.

5.2. NO BAD STRICT LOCAL MINIMUM FOR CONTINUOUS ACTIVATIONS:

So far, we have identified a class of analytic activation functions such that the loss functions have Property PT. Although these functions do not cover many commonly used activations like quadratic, sigmoid, ReLU, etc, they constitute a dense set in the space of continuous functions. That is, for any continuous function f , there exists a sequence of analytic functions that uniformly converges to f , and each of the analytic functions has non-vanishing derivatives at zero up to N -th order. Further, we show that the uniform convergence of activation function implies the compact convergence of loss function. As the property of weakly global is preserved under compact convergence, we prove that the loss surface weakly global for any continuous activation.

To summarize, our proof can be sketched in the following three steps:

Step 1: If the activation function has non-vanishing derivatives at zero up to N -th order, then Property PT holds, and the loss surface is a weakly global function.

Step 2: The set of activation functions in Step 1 are dense in the space of continuous functions.

Step 3: By the "closedness" of weakly global functions, the loss surface for any continuous activation is a weakly global function.

We note that in Step 3, the "closedness" of weakly global functions means that if a sequence of weakly global functions converges compactly to a function, then that function is also weakly global. This is a slight extension of a proposition in Josz et al. (2018) .

6. EXAMPLES OF BAD LOCAL MINIMA:

In this section, we will give some counter-examples to illustrate the "tightness" of our conditions (cannot be weakened too much) and conclusion (cannot be strengthened under the current setting).

6.1. PROPERTY PT DOES NOT IMPLY "NO BAD LOCAL MINIMA":

It is worth mentioning that our result only implies the non-existence of bad strict local minima, instead of bad local minima. This is in constrast with what Yu et al. claimed in Yu & Chen (1995) that if Property PT holds, an over-parameterized single-hidden-layer neural network has no bad local minimum (i.e., Theorem 3 in Yu & Chen (1995) ). While this claim seems correct (in fact, it is correct in one dimensional case), we could not provide a rigorous proof to this claim. Later, we found a counter-example to this claim, which implies that Property PT can only eliminate bad strict local minima, but cannot eliminate bad local minima. This counter-example is drawn in Fig. 3 , which illustrates the loss surface of Example 1 with one hidden neuron. The point (v, W ) = (1, 1) is a bad non-strict local minimum. However, after a generic perturbation within a sufficiently small neighbourhood of (1, 1), there exists a strictly decreasing path to the global minimum (-2, -1).

6.2. BAD (NON-STRICT) LOCAL MINIMA CAN EXIST FOR WIDE NETWORKS:

Although Property PT does not imply the non-existence of bad local minima, one may wonder whether it can be proved by other proof techniques. In particular, is it possible to prove the nonexistence of bad local minima under the same setting of Yu et al. Yu & Chen (1995) ? Below, we Example 1 (Bad non-strict local minimum) Consider a 1-hidden-layer neural network with 1 data sample, 1 input dimension, and d hidden-layer neurons. The data sample satisfies x, y = 0. The activation function σ is analytic and has non-vanishing derivatives at zero up to N -th order. Thus, Property PT holds. Moreover, suppose that there exists t = 0 and δ such that σ(t) = 0 and σ(t

) ≤ 0 for t -δ < t < t + δ. Now, let v * = (sign(y), sign(y), • • • , sign(y)) and W * = (t/x, t/x, • • • , t/x) .

Then, v * σ(W * x) = 0 and the corresponding loss l(v * , W * ) = y 2 > 0. In addition, since y • v σ(W x) is always non-positive in the neighborhood of (v * , W * ), l(v, W ) is always at least y 2 in the neighborhood of (v * , W * ), implying that (v * , W * ) is a bad local minimum.

Example 1 shows that the loss surface can have bad non-strict local minimum even if the activation function has Property PT and the neural network is arbitrarily wide. It also shows the necessity of rigorous mathematical analysis: while it is widely believed that over-parameterized networks can "smooth" the landscape, the exact notion of "smoother landscape" was not clearly stated.

7. CONCLUSIONS:

In this paper, we studied the loss surface of over-parameterized fully connected deep neural networks. We show that if the last hidden layer has no less neurons than the number of samples, for any continuous activation functions, the loss function is a weakly global function, i.e., the loss landscape has no setwise strict local minima (bad basins). We also show that for almost all analytic activation functions, starting from any point, after a small perturbation there exists a strictly decreasing path to the global infimum. We then extend our result to the deep neural network with one wide layer (not necessarily the last hidden layer) under extra assumptions. On the other hand, for a single-hiddenlayer network with hidden neurons less than the data samples, we construct an example to show that sub-optimal strict local minimum exists. A geometric explanation is further provided to demonstrate how over-parameterization helps in eliminating bad basins.

In a word, our work shows that over-parameterization cannot bring perfect landscape to deep neural networks. However, it does really benefit the landscape by eliminating setwise strict local minimum.

Our work clarify the role of over-parameterization alone in smoothing the loss landscape.

A PRELIMINARIES:

In order to provide rigorous proof and analysis, we re-introduce the considered network model and relevant notations in a more detailed ways.

Consider a fully connected neural network with H hidden layers. Assume that the h-th hidden layer contains d h neurons for 1 ≤ h ≤ H, and the input and output layers contain d 0 and d H+1 neurons, respectively. Given an input sample x ∈ R d0 , the output of the i-th neuron in the h-th hidden layer, denoted by t h,i , is given by

EQUATION

where w h,i,k is the weight from the k-th neuron of the (h -1)-th layer to the i-th neuron of the h-th layer, b h,i is the bias added to the i-th neuron of the h-th layer, and σ h is the neuron activation function for the h-th hidden layer. Then, the i-th output of the network, denoted by t H+1,i , is given by

EQUATION

where w H+1,i,k is the weight to the output layer, defined similarly to that of the hidden layers. In what follows, we rewrite all the training samples in matrix forms, which allows us to represent the input-output relation of the neural network in a more compact way. Specifically, let X

[x (1) , x (2) , • • • , x (N ) ] ∈ R d0×N and Y [y (1) , y (2) , • • • , y (N ) ] ∈ R d H+1 ×N

as the input and output data matrices, respectively. Then, we define W h ∈ R d h-1 ×d h as the weight matrix from the (h-1)-th layer to the h-th layer, b h ∈ R d h as the bias vector of the h-th layer, and T h ∈ R d h ×N as the output matrix of the h-th layer. The entries of each matrix are given by

EQUATION

Based on the above definition, we can immediately rewrite the output of each layer as

EQUATION

EQUATION

EQUATION

)

where the activation function σ h (•) is applied entry-wise to the input matrix and outputs a matrix with the same size. That is, (σ(A)) i,j = σ(A i,j ) for any input matrix A.

In the rest of this paper, we simplify the feed-forward operation equation 7 by ignoring all the bias neurons, yielding

EQUATION

EQUATION

EQUATION

We note that this simplification does not affect our analysis, and therefore the main results also hold for feed-forward deep neural networks with bias. Let W = (W 1 , • • • , W H+1 ) denote all the weights and define the empirical loss as

EQUATION

)

where l is the loss function. Then, the training problem of the considered network is to find W to minimize the empirical loss E(W ).

B PROOF OF PROPOSITION 1:

Proof:

Denote x = (x 1 , • • • , x N ) . Let the neural network be defined by ŷ = v σ(wx ) where v = (v 1 , • • • , v N -1 ) and w = (w 1 , • • • , w N -1

) are weights to the output layer and the hidden layer, respectively. Let l(y, ŷ) = y -ŷ 2 , then

E(•) = E(v, w) = N i=1 (y i -v σ(wx i )) 2 .

In the following, we generically choose w and v, and then in turn determine the activation function σ(•) and the output data y to obtain the empirical loss E(v, w) with bad strict local minimum.

Denote

z j = (σ(w j x 1 ), • • • , σ(w j x N )) , j = 1, • • • , N -1. Since z 1 , • • • , z N -1 are N -1 vectors in R N , they must be in a N -1-dimensional hyperplane. Assume that this hyperplane, namely H, is represented as a 1 e 1 + • • • + a N e N = 0, where e 1 , • • • , e N are the N orthogonal unit vectors. Denote a = (a 1 , • • • , a N ) , then we have a z j = N i=1 a i σ(w j x i ) = 0, ∀j = 1, • • • , N -1.

Without loss of generosity, assume that

• σ(•) is twice-differentiable; • w j x i = w j x i if i = i or j = j ; • a i = 0 for all i = 1, • • • , N . • z 1 , • • • , z N -1 are linearly independent.

Otherwise we can perform an arbitrarily small perturbation of w to make the assumptions hold.

We now come to the key step: determine σ(•) to guarantee that there exists a neighborhood B(w, δ) such that

N i=1 a i σ(w j x i ) > 0, ∀j = 1, • • • , N -1.

for all w ∈ B(w, δ)\{w}. Since σ(•) is twice-differentiable, we can properly determine the firstorder and second-order derivative of σ(•) at all points of w j x i for j = 1,

• • • , N -1 and i = 1, • • • , N . Specifically, let N i=1 a i x i σ (w j x i ) = 0, ∀j = 1, • • • , N -1, a i • σ (w j x i ) > 0, ∀j = 1, • • • , N -1, i = 1, • • • , N.

Then, by Taylor expansion, we have

EQUATION

After σ(•) is determined, choose arbitrary v > 0 and obtain ŷ = v σ(wx). Let y = ŷ -a, then E(v, w) = y -ŷ 2 = a 2 . Now consider any (v , w ) such that w ∈ B(w, δ). Denote ŷ = (v ) σ(w x) and z j = (σ(w j x 1 ),

• • • , σ(w j x N )) , j = 1, • • • , N -1. If w = w, then v = v and thus ŷ = ŷ due to linear independency of z 1 , • • • , z N -1 . Since z j = z j for all j, ŷ = N -1

j=1 v j z j is also in hyperplane H. On the other hand, note that a is the normal vector of H, we have a ŷ = a ŷ = 0. Therefore, (y

-ŷ) (ŷ -ŷ ) = -a (ŷ -ŷ ) = 0. Thus E(v , w ) = y -ŷ 2 = y -ŷ 2 + ŷ -ŷ 2 > E(v, w). If w = w, since w ∈ B(w, δ), we have a z j = N i=1 a i σ(w j x i ) > 0 by 12. Since v > 0, we have a ŷ = N -1 i=1 v j • a z j > 0. Therefore, (y -ŷ) (ŷ -ŷ ) = -a (ŷ -ŷ ) = a ŷ -a ŷ > 0. Thus E(v , w ) = y -ŷ 2 = (y -ŷ) + (ŷ -ŷ ) 2 = y -ŷ 2 + ŷ -ŷ 2 + (y -ŷ) (ŷ -ŷ ) > E(v, w).

Therefore we show that E(v , w ) > E(v, w) for all (v , w ) ∈ B((v, w), δ)\{(v, w)}, which means that (v, w) is a bad strict local min of E(•).

C RELATIONSHIP BETWEEN ACTIVATION FUNCTION AND PROPERTY PT:

Given the strong connection between Property PT and the loss surface, a natural but crucial question is that what activation functions can guarantee Property PT. Intuitively, it seems that Property PT can be easily met as long as the activation function is non-linear. Unfortunately, this is not true. In Section 5, we mention that it is necessary for the output matrix Z to be full rank so that Property PT holds in (3). Below we provide a simple rank-1 example of rank-deficient output matrix with activation function σ(z) = z p .

Example 2 (Rank-deficient output matrix) Consider a 1-hidden-layer neural network with 2 data samples, 1 input dimension, 2 hidden-layer neurons, and monomial activation σ(z) = z p , p > 0. We have W ∈ R 2×1 , X ∈ R 1×2 , and therefore W X is always of rank

1. Denote W X = a 1 a 2 ta 1 ta 2 where t ∈ R. Then, Z = σ(W X) = a p 1 a p 2 t p a p 1 t p a p 2

is always rank-deficient. This implies that we cannot find any W such that Z is of full column rank. Property PT does not hold.

In fact, for polynomial activation functions, rank-deficient output is common if the number of samples is sufficiently greater than the input dimension. The following is an example of rank-deficient output matrix with general polynomial activation functions.

Example 3 (Rank-deficient output matrix) Consider a 1-hidden-layer fully-connected neural network with N data samples, d 0 input dimension, d 1 hidden-layer neurons, and a polynomial activation

σ 1 (z) = a 0 + a 1 z + • • • + a n z p . Assume N d 0 , d 1 = N . We have W 1 ∈ R N ×d0 , X ∈ R d0×N

, and therefore W 1 X is at most rank-d 0 . Denote • as the Hadamard product, then

EQUATION

By the property of Hadamard product, we have

EQUATION

This implies that T 1 is rank-deficient if N d 0 .

D PROOF OF THEOREM 1: SINGLE-HIDDEN-LAYER CASE:

In this section, we provide the proof of Theorem 1 for 1-hidden-layer case. Following the ideas in Section 5, our proof strategy consists of three steps.

Step 1: Prove the result for a specific class of activation functions.

We first introduce a special class of activation functions, specified in the following assumption. Note that to ease notations, we will omit the subscript of activation function σ 1 when considering a 1-hidden-layer network.

Assumption 3 (Special Activation Functions) The activation function σ is analytic, and its first n derivatives at 0, i.e., σ(0), σ (0), • • • , σ (n-1) (0), are all non-zero.

Assumption 3 covers many commonly used activation functions such as sigmoid and softplus, but it does not cover ReLU since it requires smoothness (as mentioned before, ReLU is covered by using the approximation trick). Activation functions satisfying Assumption 3 have the following nice property:

Lemma 1 If Assumption 3 holds, then for any N scalars z 1 , z 2 , • • • , z N ∈ R such that z n = z n for all n = n , the following matrix

EQUATION

is non-singular.

Next, we borrow an important result of Mityagin (2015) which states that the zero set of an analytic function is either the whole domain or zero-measure. The result is formally stated as the following lemma.

Lemma 2 For any m ∈ Z + , let f : R m → R be a real analytic function on R m . If f is not identically zero, then its zero set

Ω = {z ∈ R m | f (z) = 0} has zero measure.

Based on Lemma 2, we have the following result.

Lemma 3 Suppose that σ is an analytic function satisfying Assumption 3. Given a, b ∈ R N , let

Ω = {z ∈ R N | σ(a z) = σ(b z)}. If a = b, then Ω is of measure zero.

Based on the above lemmas, we show that the output matrix of the hidden layer has full column rank for almost all W 1 , specified by the following proposition.

Proposition 2 (General two-layer Case) Consider a two-layer neural network with output

T 1 = σ(W 1 X), where X ∈ R d0×N and W 1 ∈ R d1×d0 . Let Ω 1 = {W 1 ∈ R d1×d0 | rank(T 1 ) < min{d 1 , N }}.

If Assumption A1, A2, and 3 hold, then Ω 1 is of measure zero.

Here we only provide the proof of Proposition 2 for a simple 1-dimensional-input case. We note that it can be readily extended to the general case, detailed in Appendix L.

Proposition 3 (1-dimensional-input Two-layer Square Case) Consider a two-layer neural network with one input neuron and d 1 neurons in the hidden layer. Given an activation function σ and one-dimensional input data

x ∈ R N , let Ω = {w 1 ∈ R d | det(σ(w 1 x )) = 0}. If d 1 = N

and Assumption A1, A2, and 3 hold, then Ω is of measure zero.

Proof: We prove this result by induction on N . The conclusion is obvious when N = 1.

We consider the case with N > 1. Since f (w 1 ) det(w 1 x ) is an analytic function with respect to w 1 , from Lemma 2 we know that Ω is either R N or a zero-measure set. We now prove that Ω cannot be R N .

Assume on the contrary that Ω = R N , i.e., f (w 1 ) = 0, ∀w 1 ∈ R N . Denote w 1,i as the i-th entry of w 1 , 1 ≤ i ≤ d 1 . For any k ≥ 0, the k-th order partial derivative of f (w 1 ) with respect to w 1,1 is given by -1) . According to the induction hypothesis, the set

G k (w 1 ) ∂ k f (w) ∂w k 1,1 = det     x k 1 σ (k) (w 1,1 x 1 ) x k 2 σ (k) (w 1,1 x 2 ) • • • x k N σ (k) (w 1,1 x N ) σ(w 1,2 x 1 ) σ(w 1,2 x 2 ) • • • σ(w 1,2 x N ) . . . . . . . . . σ(w 1,N x 1 ) σ(w 1,N x 2 ) • • • σ(w 1,N x N )     (16) As f (w 1 ) = 0, ∀w 1 ∈ R N , we have G k (w 1 ) = 0, ∀w 1 ∈ R N and ∀k ≥ 0. Denote the n-th row of G k (w 1 ) by u n = [σ(w 1,n x 1 ), • • • , σ(w 1,n x N )] , n = 2, • • • , N . We show there exist some w 1,2 , • • • , w 1,N such that u 2 , • • • , u N are linearly independent. We denote ûn = [σ(w 1,n x 1 ), • • • , σ(w 1,n x N -1 )] , n = 2, • • • , N , and Ĝ = [û 2 , • • • , ûN ] ∈ R (N -1)×(N

{(w 1,2 , • • • , w 1,N ) | det( Ĝ) = 0} is zero-measure in R N -1 , implying that there exist some w 1,2 , • • • , w 1,N such that û2 , • • • , ûN are linearly independent.

This also implies that u 2 , • • • , u N are linearly independent. Now we have found some

w 1,2 , • • • , w 1,N such that u 2 , • • • , u N are linearly independent. Fix w 1,2 , • • • , w 1,N and let w 1,1 = 0.

Denote the first row of G k as a k . Since det(G k ) = 0 for any k ≥ 0, a k must be a linear combination of u 2 , • • • , u N for any k ≥ 0, so all a k 's lie in an (N -1)dimension subspace of R N . However, according to Lemma 1, the N vectors a 0 , • • • , a N -1 are linearly independent, which is a contradiction.

Therefore we have proved that Ω cannot be R N , so it must be a zero-measure set.

Proposition 3 states that the output matrix of the hidden layer is generically full-column-rank. This property implies that the loss surface is a weakly global function. We have the following theorem.

Theorem 3 Consider a fully connected neural network with 1 hidden layer, activation function σ and empirical loss function E(W ) = l(Y, W 2 T 1 ). Suppose that Assumption 1 and Assumption 3 hold. Then E(W ) is a weakly global function.

Step 2: Show that the activation function in Assumption 2 can approximate any continuous function.

In order to extend Theorem 3 to all continuous activation functions without dealing them directly, we use a mathematical trick that approximates the continuous activation by a class of analytical functions.

Lemma 4 For any continuous function f : R → R, there exists a sequence of functions (f k ) k∈N , all satisfying Assumption 3, such that f k converges to f uniformly.

Lemma 4 means that the analytic functions satisfying Assumption 3 constitute a dense set (in the sense of uniformly convergence) of the space of continuous function. As we will show in the next step, this property allows us to approximate a neural network with any continuous activation function by a sequence of neural networks under Assumption 3.

Step 3: Show that the property of weakly global function is preserved under compact convergence.

Having built the relation between the neural network with analytic activation functions and the neural network with continuous activation function, the last step is to show that the weakly global property is preserved under this relation. The following result is a modification of a result in Josz et al. (2018) .

Proposition 4 Consider a sequence of functions (f k ) k∈N and a function f , all from S ⊂ R m to R. 2018): here we assume that f k are weakly global functions instead of global functions. Nevertheless, we can still prove that f is weakly global by using similar techniques as in Josz et al. (2018) .

EQUATION

Based on Proposition 4, to prove Theorem 1 it suffices to find a sequence of weakly global functions that compactly converges to the loss surface. Below we present the formal proof of Theorem 1 for 1-hidden-layer case.

Proof: We denote the considered network by N . From Lemma 4, there exists a sequence of activation functions (σ k ) k∈N that uniformly converges to σ. For each k ∈ N, we construct a neural network, denoted by N k , by replacing the activation function in N with σ k . For all N k , we assume the training dataset to be identical to that of N . We also denote the output matrix of the hidden layer by T (k) 1 and the empirical loss by

EQUATION

)

From Theorem 3, E k is a weakly global function with respect to W , ∀k ∈ N. In what follows, we prove that the sequence of the empirical loss functions (E k ) k∈N compactly converges to E.

Consider an arbitrary compact subset S in the space of W . For any W ∈ S, denote t(k)

1,i,n (W ) = (T (k)

1 ) i,n and t1,i,n (W ) = (T 1 ) i,n for any k ∈ N, 1 ≤ i ≤ d 1 , and 1 ≤ n ≤ N . That is, we rewrite the output of each neuron in the hidden layer as a function of W . Then, we have

EQUATION

)

Since σ k uniformly converges to σ, t(k) 1,i,n also uniformly converges to t1,i,n on S for all

1 ≤ i ≤ d 1 , 1 ≤ n ≤ N .

Now we consider the empirical loss equation 18. As every component of T (k) 1:

uniformly converges to the corresponding component of T 1 , it can be shown that W H+1 T (k) 1 also uniformly converges to W H+1 T 1 on S. By the continuousness of the loss function l, we have that E k uniformly converges to E on S.

Finally, noting that S is an arbitrary compact subset in the space of W , the empirical loss E k compactly converges to E on the space of W . Since E k (W ) is a weakly global function for every k ∈ N, by Proposition 4, E(W ) is also a weakly global function. We complete the proof.

E PROOF OF THEOREM 1: EXTENSION TO DEEP NETWORKS:

In this section, we extend the proof of Theorem 1 from 1-hidden-layer case to deep neural networks. It turns out that the extension is simpler than expected, as we only need to follow the same idea as Section D and generalize some of the propositions and lemmas.

In the first place, we show that if the activation function of each hidden layer satisfies Assumption 3, the output matrix of the last hidden layer, i.e., T H , is of full column rank for almost all W . Formally, we have the following extended version of Proposition 2.

Proposition 5 Given a fully connected neural network with H hidden layers, activation function σ h for each hidden layer, and empirical loss function

E(W ) = l(Y, W H+1 T H ). Let Ω = {(W 1 , • • • , W H ) | rank(T H ) < min{d H , N }}.

Suppose that Assumption 1 hold and σ h satisfies Assumption 3 for all 1 ≤ h ≤ H, then Ω is a zero-measure set.

Proposition 5 immediately gives rise to the following theorem, which generalizes Theorem 3 to deep neural networks.

Theorem 4 Given a fully connected neural network with H hidden layers., activation function σ h for each hidden layer, and empirical loss function E(W ) = l(Y, W H+1 T H ). Suppose that Assumption 1 hold and σ h satisfies Assumption 3 for all 1 ≤ h ≤ H, then E(W ) is a weakly global function.

To completely prove Theorem 1, what remains is to find a sequence of weakly global functions that compactly converges to the loss surface. We have the following lemmas.

Lemma 5 Consider two continuous functions f : S → R n and g : R n → R, where S ⊂ R m is a compact set. Suppose that there exists two sequences of functions (f k ) k∈N and (g k ) k∈N , such that f k uniformly converges to f on S, and g k compactly converges to g on R n . Then,

g k • f k converges to g • f uniformly on S.

Lemma 6 Given a fully connected neural network with H hidden layers, activation function σ h for each hidden layer, and empirical loss function E(W ) = l(Y, W H+1 T H ). Suppose that Assumption 1 holds. Then, there exists a sequence of weakly global functions that compactly converges to E(W ).

Combining Proposition 4 and Lemma 6, we complete the proof of Theorem 1.

F PROOF OF THEOREM 2:

Similar to that of Theorem 1, the proof of Theorem 2 consists of three steps.

Step 1: Prove the result for networks with specific activation functions.

From Assumption 2, there exists a wide layer of the network, i.e., the h 0 -th hidden layer. We show that if the activation functions satisfy some specific conditions, the resulting empirical loss function is a weakly global function. We first specify a class of activation functions for the pyramid structure.

Assumption 4 (Special Activation for Pyramid Structure) The activation function σ h is continuous, strictly increasing or strictly decreasing, and its range is R, i.e., σ(R) = R.

Clearly, the activation functions satisfying Assumption 4 also satisfies Assumption B2. Further, we have the following theorem.

Theorem 5 Given a fully connected neural network with H hidden layers., activation function σ h for each hidden layer, and empirical loss function E(W ) = l(Y, W H+1 T H ). Suppose that Assumption 1 and 2 hold, and 1. For any 1 ≤ h ≤ h 0 , σ h satisfies Assumption 3; 2. For any h 0 < h ≤ H, σ h satisfies Assumption 4.

Then, E(W ) is a weakly global function.

Theorem 5 identifies a special class of deep over-parameterized networks with pyramid structure, whose empirical loss function is weakly global.

Step 2: Show that for each hidden layer, the activation function in Theorem 5 can approximate the activation function in Theorem 2.

We use the same approximation trick as in the proof of Theorem 1. For the activation functions satisfying Assumption 3, we have Lemma 4. Regarding the activation functions satisfying Assumption 4, we have the following lemma.

Lemma 7 For any continuous and non-increasing (or non-decreasing) function f : R → R, there exists a sequence of functions (f k ) k∈N , all continuous and satisfying Assumption 4, such that f k converges to f compactly.

Step 3: Under compact convergence, show that the neural network considered in Theorem 2 is weakly global.

We denote the considered network by N . From Lemma 4, for any 1 ≤ h ≤ h 0 , there exists a sequence of activation functions (σ h,k ) k∈N , each satisfying Assumption 3, that uniformly converges to σ h . From Lemma 7, for any h 0 < h ≤ H, there exists a sequence of activation functions (σ h,k ) k∈N , each satisfying Assumption 4, that compactly converges to σ h . Since uniform convergence implies compact convergence, for all 1 ≤ h ≤ H, σ h,k compactly converges to σ h .

In the following, we show that the empirical loss of N can be approximated by a sequence of weakly global function, which is identical to the analysis in Appendix E For each k ∈ N, we construct a neural network, denoted by N k , by replacing the activation function of the h-th hidden layer with σ h,k , for all h = 1, 2, • • • , H. For all N k , we assume the training dataset to be identical to that of N . We also denote the output matrix of the h-th hidden layer by T (k) h and the empirical loss by

EQUATION

)

From Theorem 3, E k is a weakly global function with respect to W , ∀k ∈ N.

Consider an arbitrary compact subset S in the space of W . For any W ∈ S, define

t(k) h,i,n (W ) = (T (k) h ) i,n and th,i,n (W ) = (T h ) i,n for any k ∈ N, 1 ≤ h ≤ H, 1 ≤ i ≤ d h , and 1 ≤ n ≤ N .

That is, we rewrite the output of each neuron in the hidden layers as a function of W . We prove by induction that every sequence ( t(k) h,i,n ) k∈N converges to th,i,n uniformly on S.

For h = 1, we have

EQUATION

Since σ k uniformly converges to σ, t(k) 1,j,n also uniformly converges to t1,j,n on S for all

EQUATION

By the induction hypothesis, it is easy to show that

d h-1 j=1 (W h ) i,j t(k) h-1,j,n (W ) uniformly con- verges to d h-1

j=1 (W h ) i,j th-1,j,n (W ) on S. Note that (σ h,k ) k∈N converges to σ h uniformly, and uniform convergence implies compact convergence. It directly follows from Lemma 5 that t(k) h,i,n (W ) converges to th,i,n (W ).

Therefore, we conclude that t(k) h,i,n converges to th,i,n uniformly on S for every 1 ≤ h ≤ H, 1 ≤ i ≤ d h , and 1 ≤ n ≤ N . Now we consider the empirical loss

EQUATION

As every component of T

H converges uniformly to the corresponding component of T H on S, it can be shown that W H+1 T (k) H converges uniformly to W H+1 T H on S. By Lemma 5, where we set both g k and g to the loss function l, we have that E k uniformly converges to E on S. Noting that S is an arbitrary compact subset in the space of W , the empirical loss E k converges to E compactly on the space of W . Since E k (W ) is a weakly global function for every k ∈ N, by Proposition 4, E(W ) is also a weakly global function. We complete the proof.

G PROOF OF THEOREM 3:

Note that the proof of Theorem 3 is essentially the same with that of Theorem 4 if we set H = 1. We omit the proof of Theorem 3 here and refer the readers to Appendix H.

H PROOF OF THEOREM 4:

The proof consists of three steps. First, we show that for any W , we can perturb it to a point W whose corresponding T H is full rank. Second, we prove that starting from the perturbed point W , there exists a strictly decreasing path to the global infimum. Finally, we combine the two previous steps to show that the loss function is weakly global.

Proof: We first prove that from any initial weight

W o = (W o 1 , • • • , W o H+1

), there exists a strictly decreasing path towards inf W E(W )4 after an arbitrarily small perturbation. According to Proposition 5, all W 's that entail a non-full-rank T H only constitute a zero-measure set. Therefore, for any initial weight W o and an arbitrarily small δ > 0, there exists

W p = (W p 1 , W p 2 , • • • , W p H+1 ) ∈ B(W o , δ) such that the corresponding T p H is full rank. Since d H ≥ N , we have rank(T p H ) = N .

In what follows, we show that starting from W p , there exists a continuous path along which the empirical loss E(W ) strictly decreases to inf W E(W ). Denote W 1:H = (W 1 , • • • , W H ), i.e., the weights in the first H layers. By the feed-forward operation equation 8, T H is a function of W 1:H . Thus, E(W ) can be rewritten as l(Y, W H+1 T H (W 1:H )). Since l(Y, Ŷ ) is convex to Ŷ , for any W H+1 , W H+1 , and λ ∈ [0, 1], we have

EQUATION

Thus, with the weights to the first H hidden layers fixed, E(W ) is convex with respect to W H+1 . This implies that starting from W p , we can find a strictly decreasing path towards

EQUATION

Therefore, the constructed path is strictly decreasing towards inf W E(W ). Moreover, E(W * ) = sup W ∈W E(W ) + ε for some ε > 0.

Consider an arbitrary point W o ∈ W. Since E(W ) is a continuous function, there exists δ > δ 0 > 0 such that for any

W ∈ B(W o , δ 0 ), |E(W ) -E(W o )| < ε/2.

According to the first conclusion, we can find W p ∈ B(W o , δ 0 ) such that there exists a strictly decreasing path from W p to inf W E(W ) . Since W is a bad local minimum, inf W ∈W δ E(W ) > inf W E(W ). Therefore, the above strictly decreasing path starting from W p must pass through the boundary ∂W δ . However,

E(W p ) < E(W o ) + ε/2 < sup W ∈W E(W ) + ε = E(W * ) = inf W ∈∂W δ E(W ).

This implies that the considered path can never be strictly decreasing, leading to a contradiction. Therefore, we conclude that there is no bad strict local minima in the sense of sets, and therefore E(W ) is a weakly global function.

I PROOF OF THEOREM 5:

First, we show that for any initial weight W o , we can perturb it to a point W p , and starting from the perturbed point W p , there exists a strictly decreasing path towards the global infimum.

Denote Θ as the space of W and let W 1:h = (W 1 , W 2 , • • • , W h ) denotes the weights for the first h hidden layers. We consider the following set:

EQUATION

Since σ h satisfies Assumption 3 for any 1 ≤ h ≤ h 0 , according to Lemma 5, all W 1:h0 's that entail a non-full-rank T h0 only constitute a zero-measure set. That is, all W 1:h0 's such that T h0 is rank(N ) constitute a dense set. Further, note that full-rank matrices are dense. For all h 0 < h ≤ H + 1, since

d h ≤ d h-1 from Assumption B1, {W h |rank(W h ) = d h } is dense in R d h ×d h-1 .

From the above analysis, we conclude that Ω is dense in Θ. Therefore, for any initial weight W o and an arbitrarily small δ > 0, there exists

W p = (W p 1 , W p 2 , • • • , W p H+1 ) ∈ B(W o , δ) such that W p ∈ Ω.

In what follows, we show that if E(W p ) > inf W (E(W )), there exists a continuous path starting from W p , and the empirical loss along which strictly decreases to inf W E(W ).

Case 1: There exists Ŷ ∈ R d H+1 ×N such that l(Y, Ŷ ) = inf Ŷ l(Y, Ŷ ).

Denote T p:

h as the output of the h-th hidden layer at weight W p , and Ŷ p = W p H+1 T p H as the network output at weight W p . Since the loss function l(Y, Ŷ ) is convex with respect to Ŷ , it is also continuous with respect to Ŷ . Further, we have

EQUATION

and hence Ŷ p is not a global minimum of l(Y, Ŷ p ). Then, there exists a continuous path Ŷ (λ) :

[0, 1] → R such that Ŷ (0) = Ŷ p , l(Y, Ŷ (1)) = inf Ŷ l(Y, Ŷ )

, and l(Y, Y (λ)) is strictly decreasing with respect to λ, i.e.,

EQUATION

By Assumption 4, for each h 0 < h ≤ H, σ h has a continuous inverse σ -1 h : R → R. Also, since W p h is of full row rank for each h 0 < h ≤ H, it has a right inverse (W p h ) † such that W p h (W p h ) † = I. Further, as T p h0 has full column rank, it has a left inverse T p h0 † such that T p h0 † T p h0 = I. We construct W (λ) : [0, 1] → Θ as follows

EQUATION

where W h (λ) is defined recursively as follows

EQUATION

For the constructed W (λ), we verify the following three facts.

(1) W (λ) is a continuous path.

In fact, since Ŷ (λ) is continuous, σ -1 h is a continuous function for all h 0 < h ≤ H, therefore each T h (λ) is continuous with respect λ for all h 0 < h ≤ H. Thus, W (λ) is also continuous with respect to λ.

(2) W (0) = W p , and W (1) is a global minimum of E(W ).

Note that Ŷ (0) = Ŷ p . From equation 34, we have

EQUATION

EQUATION

Notice that W (λ) is identical to W p except the weights to the (h 0 + 1)-th layer. Thus, W (0) = W p . Now consider the output of each hidden layer at weight W (λ), denoted by T λ h . For W (λ) and W p , the weights to the first h 0 hidden layers are the same, and hence T λ h0 = T p h0 . From equation 34, we have

EQUATION

For

EQUATION

)

And similarly, for the network output at W (λ), denoted by Ŷ λ we have

EQUATION

Then, the empirical loss

EQUATION

Therefore we must have E(W (1)) = inf W E(W ). That is, E(1) is a global minimum of E(W ).

(3) E(W (λ)) is strictly decreasing with respect to λ. From (2), we have

EQUATION

Then for any λ 1 , λ 2 ∈ [0, 1] and λ 1 < λ 2 , we have

EQUATION

E(W (λ)) is strictly decreasing with respect to λ.

We conclude that W (λ) starts at from W p and is a strictly decreasing path towards the global infimum.

Case 2: There does not exist Ŷ ∈ R d H+1 ×N such that l(Y, Ŷ ) = inf Ŷ l(Y, Ŷ ).

Similar to Case 1, there exists a continuous path Ŷ (λ) : [0, 1) → R such that Ŷ (0) = Ŷ p , lim λ→1 l(Y, Ŷ (λ)) = inf Ŷ l(Y, Ŷ ), and l(Y, Y (λ)) is strictly decreasing with respect to λ. We can then construct a continuous path W (λ) : [0, 1) → Θ, such that E(W (λ)) is strictly decreasing, and lim λ→1 E(W (λ)). Since the construction and analysis are identical to that in Case 1, we omit the details here.

Then we prove by contraposition that E(W ) is a weakly global function. Assume in contrast that there exists a bad strict local minimum of E(W ) in the sense of sets, denoted by W. Note by Definition 2, W is a compact set. Let W δ = {W | inf W ∈W W -W 2 ≤ δ}, then there exists δ > 0 such that for all W ∈ W and W ∈ W δ \ W, E(W ) < E(W ). Denote ∂W δ as the boundary of W δ . Note that both W δ and ∂W δ are closed, there exists

W * ∈ ∂W δ such that E(W * ) = inf W ∈∂W δ E(W ).

Moreover, E(W * ) = sup W ∈W E(W ) + ε for some ε > 0.

Consider an arbitrary point W o ∈ W. Since E(W ) is a continuous function, there exists δ > δ 0 > 0 such that for any W

∈ B(W o , δ 0 ), |E(W ) -E(W o )| < ε/2.

According to the first conclusion, we can find W p ∈ B(W o , δ 0 ) such that there exists a strictly decreasing path from W p to inf W E(W ) . Since W is a bad local minimum, inf W ∈W δ E(W ) > inf W E(W ). Therefore, the above strictly decreasing path starting from W p must pass through the boundary ∂W δ . However,

E(W p ) < E(W o ) + ε/2 < sup W ∈W E(W ) + ε = E(W * ) = inf W ∈∂W δ E(W ).

This implies that the considered path can never be strictly decreasing, leading to a contradiction. Therefore, we conclude that there is no bad strict local minima in the sense of sets, and therefore E(W ) is a weakly global function.

J PROOF OF LEMMA 1:

Notice that A is a Vandermonde matrix multiplied by σ n-1 (0) to the n-th row, n = 1, 2, • • • , N . Since σ n-1 (0) = 0 according to Assumption 3, A is a non-singular matrix.

K PROOF OF LEMMA 3:

Assume that Ω is not of zero measure. Since σ(a z) -σ(b z) is an analytic function of z, Ω must be R N according to Lemma 2. That is, σ(a z) = σ(b z) for all z ∈ R N . We will show that this leads to a contradiction.

If a = 0 or b = 0, assume a = 0 without loss of generality. Since b = 0, there exists some z 0 such that b z 0 = 1. Therefore, for any λ ∈ R, we have

EQUATION

Thus, σ is a constant function and therefore σ ≡ 0, a contradiction to Assumption 3.

If a, b = 0, then the set of all z satisfying a z = 0 or b z = 0 is of measure zero. Since a = b, the set of all z satisfying a z = b z is also of zero measure. Therefore, there exists some z 0 such that a z 0 = 0, b z 0 = 0, and a z 0 = b z 0 . Denote a 0 = a z 0 and b 0 = b z 0 . Since Ω = R N , we conclude that for any λ = 0, σ(λa 0 ) = σ(a z 0 ) = σ(b z 0 ) = σ(λb 0 ). Note that a 0 b 0 = 0, a 0 = b 0 , and σ(λa 0 ) = σ(λb 0 ) for all λ = 0. Letting λ → 0, we have

EQUATION

where the second equality holds since σ is analytic. This also contradicts Assumption 3.

We conclude that for any a = b, Ω cannot be R N , and therefore must be of zero measure.

L PROOF OF PROPOSITION 2

Let w i be the i-th row of W 1 , i = 1, 2, • • • , d 1 .

According to Assumption A1, we can assume without loss of generality that the first row of X has distinct entries, i.e., x

1 , x

(2)

1 • • • , x (N ) 1 are distinct from each other. Notice that T 1 ∈ R d1×N . If d 1 < N , we select the first d 1 columns of T 1 and obtain a sub-matrix T1 ∈ R d1×d1 . Let Ω 1 = {W 1 ∈ R d1×d0 | rank( T1 ) < d 1 }. We can show that Ω 1 is a zero-measure

set by applying a similar analysis to T1 as in the proof of Proposition 3. The only change to make is that here we calculate the partial derivatives with respect to w 1,1,1 . Notice that for any W 1 ∈ Ω 1 , any d 1 × d 1 sub-matrix of T 1 should be singular. Since Ω 1 is a subset of Ω 1 , it should also be zero measure.

If d 1 ≥ N , we select the first N rows of T 1 and obtain a sub-matrix T1 ∈ R N ×N . Similarly, let Ŵ1 ∈ R N ×d0 be the first N rows of W 1 . Let Ω 1 = { Ŵ1 ∈ R N ×d0 | rank( T1 ) < N }. Following a similar analysis as in the case d 1 < N , Ω 1 is of measure zero in R N ×d0 . Note that for any W 1 ∈ Ω 1 , its submatrix consisting of the first N rows is in Ω 1 . Thus, Ω 1 is of measure zero in R d1×d0 . for all k > √ 2/( s) -1 and x ∈ R. Therefore, f k converges uniformly to g.

We conclude that function class specified by Assumption 3 is dense in the space of analytic functions. Now we come to the second part. By the Carleman Approximation Theorem Kaplan (1955) , the space of analytic functions is dense in the space of continuous functions. That is, for any continuous function f : R → R, there exists a sequence of analytic functions (g k ) k∈N such that g k converges to f uniformly. Following the idea of Cantor's diagonal argument, we can construct a sequence of functions satisfying Assumption 3, which also converges to f . Note that each g k is an analytic function. By the analysis in the first part, for each k ∈ N, we can construct a sequence of functions (f (k) j ) j∈N , all satisfying Assumption 3, such that f (k) j converges to g k uniformly. Further, we can require that for each k ∈ N,

EQUATION

In fact, if equation 52 is not satisfied, we can always delete a finite number of functions at the beginning of the sequence, so as to produce a new sequence that meets equation 52. Now considered the sequence (f

EQUATION

Therefore, f

converges to f uniformly. Noting that f is an arbitrary continuous function from R to R, we complete the proof.

N PROOF OF PROPOSITION 4:

Consider a sequence of weakly global functions f k that converges compactly towards f . Since S ⊂ R m and R m is a compactly generated space, it follows that f is continuous. We proceed to prove that f is a weakly global function by contradiction. Suppose S M ⊂ S is a strict local minimum that is not global minimum. There exists > 0 such that the uniform neighborhood V := {y ∈ S | ∃ x ∈ S M : x -y 2 ≤ } satisfies f (x) < f (y) for all x ∈ S M and for all y ∈ V \ S M . Since f is continuous on the compact set S M , it attains a minimal value on it, say inf S M f := α + inf S f where α > 0 since S M is not a global minimum. Consider a compact set V ⊂ K ⊂ S such that inf K f ≤ α/2 + inf S f . Since f is continuous on the compact set ∂V , it attains a minimal value on it, say inf ∂V f := β + inf S M f where β > 0 by strict optimality. Let γ := min{α/2, β}. For a sufficiently large value of k, compact convergence implies that |f k (y) -f (y)| ≤ γ/3 for all y ∈ K. Since the function f k is compact on V , it attains a minimum, say z ∈ V . Consider the compact set defined by Z

EQUATION

Thus, z ∈ int(V ). So Z ⊆ int(V ). Since both Z and ∂V are compact, we have d(∂V, Z) > 0. We now proceed to show by contradiction that Z is a strict local minimum of f k . Assume that for all > 0, there exists y ∈ S \ Z satisfying d(y , Z) ≤ such that f k (z) ≥ f k (y ) for some z ∈ Z. We can choose < d(∂V, Z) to guarantee that y belongs to V since Z ⊆ int(V ). The point y then contradicts the strict minimality of Z on V . This means that Z ∈ V is a strict local minimum of f k . Now, observe that for any z ∈ Z,

EQUATION

Thus, Z is not a global minimum of f k . This contradicts the fact that f k is a weakly global function.

O PROOF OF PROPOSITION 5

The proof for Proposition 5 is a natural extension of Proposition 2. Specifically, we show that Assumption A1 can be preserved for the input of every hidden layer, which allows us to prove Proposition 5 by induction. (57) Ω h is the set of W 1:h such that the output matrix of the h-th hidden layer is not full rank, which generalizes Ω 1 defined in Proposition 2. Ωh is the set of W 1:h such that there exist identical entries in every row of T h . That is, for any W 1:h ∈ Ωh , the resulting T h , if regarded as an input data matrix, violates Assumption A1.

In the following, we prove by induction that Φ h Ω h ∪ Ωh is of measure zero for all 1 ≤ h ≤ H.

We first consider the case with h = 1. By Proposition 2, Ω 1 is of measure zero . Further, note that (T 1 ) i,n = σ((w 1 ) i x (n) ), where (w 1 ) i and x (n) are the i-th row of W 1 and the n-th column of X (i.e., the n-th training data), respectively. Noting that Assumption A1 guarantees that x (1) , x (2) , • • • , x (N ) are distinct from each other, from Lemma 3, Ω1 is of measure zero. As a result, Φ 1 = Ω 1 ∪ Ω1 is also of measure zero. Now assume that Φ h-1 is of measure zero. Then Φ h can be decomposed into

Φ h = W 1:h | W 1:(h-1) ∈ Φ h-1 , W 1:h ∈ Ω h ∪ Ωh ∪ W 1:h | W 1:(h-1) / ∈ Φ h-1 , W 1:h ∈ Ω h ∪ Ωh (58)

By the induction hypothesis, the first component of the set union in equation 58 has zero measure in the space of W 1:h . Moreover, for W 1:(h-1) / ∈ Ωh-1 , the resulting T h-1 , if regarded as an input data matrix, satisfies Assumption A1. Noting that σ h satisfies Assumption 3, following a similar procedure as in the case of h = 1, we obtain that the set of W h satisfying (W 1:(h-1) , W h ) ∈ Ω h has zero measure in R d h ×d h-1 . This implies that the second component of the set union in equation 58 also has zero measure in the space of W 1:h . Therefore, Φ h is of measure zero for all 1 ≤ h ≤ H.

Noting that Ω = Ω H , we complete the proof of Proposition 5 Since σ k uniformly converges to σ, t(k) 1,j,n also uniformly converges to t1,j,n on S for all 1 ≤ j ≤ d 1 , 1 ≤ n ≤ N .

For h > 1, assume that t(k) h-1,i,n uniformly converges to th-1,i,n on S for all 1 ≤ i ≤ d h-1 , 1 ≤ n ≤ N . For the h-th layer, we have

EQUATION

)

By the induction hypothesis, it is easy to show that d h-1 j=1 (W h ) i,j t(k) h-1,j,n (W ) uniformly converges to d h-1 j=1 (W h ) i,j th-1,j,n (W ) on S. Note that (σ h,k ) k∈N converges to σ h uniformly, and uniform convergence implies compact convergence. It directly follows from Lemma 5 that t(k) h,i,n (W ) converges to th,i,n (W ).

Therefore, we conclude that t(k) h,i,n converges to th,i,n uniformly on S for every 1 ≤ h ≤ H, 1 ≤ i ≤ d h , and 1 ≤ n ≤ N . H converges uniformly to W H+1 T H on S. By Lemma 5, where we set both g k and g to the loss function l, we have that E k uniformly converges to E on S. Noting that S is an arbitrary compact subset in the space of W , the empirical loss E k converges to E compactly on the space of W . Since E k (W ) is a weakly global function for every k ∈ N, by Proposition 4, E(W ) is also a weakly global function. We complete the proof.

R PROOF OF LEMMA 7:

Consider an arbitrary continuous and non-increasing (or non-decreasing) function f : R → R. In this proof we assume that f is non-increasing. Note that the non-decreasing case can be proved by following the same idea, and we omit the details therein.

We construct a sequence of function (f k ) k∈N as

f k (x) =      -x -k -1 + f (-k -1) x < -k -1 f (x) -x+k+1 (k+1) 2 -k -1 ≤ x ≤ k + 1 -x + k + 1 + f (k + 1) -2 k+1 x > k + 1 (70)

First, we show that f k is continuous. To this end, we only need to verify that f k is left-continuous at x = -k -1 and right continuous at x = k + 1. From equation 70, we have lim

EQUATION

Thus, f k (x) is continuous for all k ∈ N.

Second, we show that f k is strictly decreasing and f (R) = R. On both (-∞, -k -1) and (k + 1, +∞), f k is linear with negative slope, and hence strictly decreasing. Noting that f k is non-increasing, for any x 1 , x 2 ∈ [-k -1, k + 1] and x 1 < x 2 , we have 

f k (x 1 ) = f (x 1 ) - x 1 + k + 1 (k + 1) 2 ≥ f (x 2 ) - x 1 + k + 1 (k + 1) 2 > f (x 2 ) - x 2 + k + 1 (k + 1) 2 = f k (x 2 ).

EQUATION

Thus, f k converges to f uniformly on S. As S is an arbitrary compact set on R, f k converges to f compactly on R.

We complete the proof.

:

This setting of network structure is more general than the first setting, and is quite close to practice: for instance, ImageNet dataset in ILSVRC competition has around 1.2 million training samples, while VGG and Inception network have 3 and 1.3 million neurons in the widest layer respectively.

assuming generic data. For very special data, constructing bad local-min is possible but it is not that interesting, since the proofs of positive results often assume generic data.

AlthoughYu et al. Yu & Chen (1995) assumes sigmoid activation, their proof only uses the property that the activation has non-vanishing derivatives up to the N -th order, which holds for sigmoid. Such property also holds for a broad range of activations considered in the counter-example Example 1, thus this counter-example can be viewed as a counter-example to the setting ofYu & Chen (1995).

To be more specific, if the global infimum is achievable (i.e., global minimum), then the decreasing path ends exactly at some point with empirical loss infW E(W ). Otherwise, the empirical loss along the path converges to infW E(W )

Figures and Tables:

Figure 1: An example of a weakly global function (a) and a non-weakly-global function (b). Both functions have bad non-strict local minima, consisting a plateau of (-3, -1). The plateau in the right figure is the bottom of a basin, entailing a bad strict local minimum in the sense of sets.

(a). Intuitively, weakly global functions may have flat regions of local minima (Figure 1(a)), but do not have "truly bad" local minima that are surrounded by barriers (Figure 1(b)).

Figure 2: The figure of the output data (a) and activation function σ(•) (b) in the proposed 1-hidden-layer-1-neuron example. In (a), (y 1 , y 2 ) = (2, 0) is the true data, (ŷ 1 , ŷ2 ) = (1, 1) is the current output and the cyan area is the feasible region of (ŷ 1 , ŷ 2 ) if we perturb both v and w. In (b), wx 1 = wx 2 = 0 is the current input of σ(•), while w x 1 and w x 2 are possible inputs after perturbation.

Figure 3: The loss surface of Example 1 with d = 1, (x, y) = (1, 1), and σ(z) = -(z -1) 2 /8. The point (v, W ) = (1, 1) is a bad non-strict local minimum.

Consider a training dataset consisting of N samples. Denote the n-th sample by (x(n) , y (n) ), n = 1, • • • , N , where x (n) ∈ R d0 and y (n) ∈ R d H+1 are the input and output samples, respectively.

17) and if f k are weakly global functions on S, then f is a weakly global function on S. Proposition 4 is slightly different from its original version in Josz et al. (

Now we prove by contraposition that E(W ) is a weakly global function. Assume in contrast that there exists a bad strict local minimum of E(W ) in the sense of sets, denoted by W. Note by Definition 2, W is a compact set. Let W δ = {W | inf W ∈W W -W 2 ≤ δ}, then there exists δ > 0 such that for all W ∈ W and W ∈ W δ \ W, E(W ) < E(W ). Denote ∂W δ as the boundary of W δ . Note that both W δ and ∂W δ are closed, there exists W * ∈ ∂W δ such that E(W * ) = inf W ∈∂W δ E(W ).

Proof:(Proof of Proposition 5) Denote W1:h = (W 1 , W 2 , • • • , W h ), i.e., the weights of the first h hidden layers. DefineΩ h = {W 1:h | rank(T h ) < min{d h , N }} (56) Ωh = {W 1:h | ∀i = 1, • • • , d h , ∃n i = n i , s.t. (T h ) i,ni = (T h ) i,n i }.

Now we consider the empirical lossE k (W ) = l Y, W H+1 T ) = l (Y, W H+1 T H ). converges uniformly to the corresponding component of T H , it can be shown that W H+1 T (k)

(72) Therefore f k is strictly decreasing on [-k -1, k + 1]. As f k is continuous, we conclude that f k is strictly decreasing on R. Further, from equation 70 we have lim x→-∞ f k (x) = +∞ and lim x→+∞ f k (x) = -∞. Again, from the fact that f k is continuous, we have f k (R) = R.Finally, we show that f k converges to f compactly. Consider an arbitrary compact set S ⊂ R and > 0. Since S is bounded, there exists K ∈ N such that S ⊂ [-K -1, K + 1]. For any k > max{K, /2 -1} and x ∈ S, we have x ∈ [-k -1, k + 1], and

Peer review (iclr2020):
This paper theoretically studies the benefit of overparameterization for the loss landscape in fully connected deep neural networks. Here the definition of overparameterization is the number of training samples larger than the number of neurons in a hidden layer. This paper shows that if the last hidden layer is overparameterized (with some more mild assumptions) than loss function is weakly global. This implies there are no bad strict local minima. Authors also show by example that overparameterization networks could have bad non-strict local minima could exist. Due to last minute request, I have not been able to digest the proof so I won*t be able to say anything regarding the correctness of the paper. While there are interesting observations one could find on overparamerized network*s loss landscape, with current form the paper*s presentation is unclear and I wan not convinced on its relevance to realistic settings. Pros: The paper is tackling an important question regarding the benefits of overparameterization. As authors note isolating benefits coming from overparameterization is important study. Assumptions used to prove the theorems are general enough except for the overparameterized assumption. Cons: There are few problems I encountered reviewing. I found paper unclear to read and understand. Maybe due to last minute submission, the paper does not appear to be polished and needs more work making the presentation clear. Beyond various typos, broken reference (unnecessary Yu et al. infront of Yu & Chen (1995)), I did not find section 2 from 1-dimensional case especially helpful for understanding impact of the paper. Also since various previous works have similar claims to this paper, it would be clear to distinguish how current results are distinguished in the contribution section. For example as authors say Nguyen et al (2018)/ Venturi et al (2018) also show that non-existence of bad strict local minima. The contribution section may become clear if authors could describe specific contributions beyond what already have been described in literature. Is the relaxation to continuous activation function that is significant for example? I have concerns about the applicability of the results. For example, in realistic data would A3 or B1 hold? For example with 50k MNIST, one would need 50k hidden layer and the benefit of overparameterization in practice appears for much smaller networks. Also for Theorem 2 assumption B2 is quite strict which doesn’t include ReLU/TanH/Sigmoid activation functions. For applicability, I wonder if there would be a practical guidance based on findings in the paper which would make the results more impactful. While it is important to understand what type of minima overparameterization network brings in, wouldn’t more relevant true phenomenology of deep networks would be captured through statistical arguments in terms of how likely our initialization and optimization algorithm would fall into a certain type of minima. I was not convinced some of the particular examples in low dimensional settings reflects what realistic over/under parameterized neural networks are showing. Questions and Comments: How is counter example in section 6.1 an example of overparameterized case? I only see one hidden unit with 1 data point which is not overparameterized by paper’s definition. Please remove unnecessary “Yu et al.” Typo p1 last paragraph “has -> have”