Title: BOUNDS ON OVER-PARAMETERIZATION FOR GUARANTEED EXISTENCE OF DESCENT PATHS IN SHALLOW RELU NETWORKS

Abstract: We study the landscape of squared loss in neural networks with one-hidden layer and ReLU activation functions. Let m and d be the widths of hidden and input layers, respectively. We show that there exist poor local minima with positive curvature for some training sets of size n ≥ m + 2d -2. By positive curvature of a local minimum, we mean that within a small neighborhood the loss function is strictly increasing in all directions. Consequently, for such training sets, there are initialization of weights from which there is no descent path to global optima. It is known that for n ≤ m, there always exist descent paths to global optima from all initial weights. In this perspective, our results provide a somewhat sharp characterization of the over-parameterization required for "existence of descent paths" in the loss landscape.

1. INTRODUCTION:

We consider shallow neural networks of the form shown in Fig. 1 . The network comprises a hidden layer and an input layer of widths m and d, respectively; and is to be trained over a training set of size n. Our results concern the slightly over-parameterized regime where n ≈ m. We study the existence of poor local minima that have positive curvature in the empirical squared loss landscape.

It is well-known that poor local minima exist in the loss landscape of shallow networks of arbitrary width. In fact, in a shallow network with ReLU activation functions, it is easy to construct training sets whose empirical loss landscape has high plateaus. 1 It is however not fully understood that under what conditions poor local minima may have positive curvature. This paper presents results that improve this understanding.

Non-existence of spurious local minima is closely connected to the so called descent path property: a loss landscape is said to have the descent path property if starting from any initial point there is a path of descent loss to a global minimum. From optimization perspective, the descent path property favors descent optimization algorithms like the pure gradient descent (GD) method. For SGD as well, non-existence of poor local minima is known to be a favorable property for guaranteed convergence (Ge et al., 2015; Jin et al., 2017; Lee et al., 2016) . The descent path property is shown to be satisfied in over-parameterized shallow networks with sufficiently large widths (Venturi et al., 2018) . The results we present in this work, tighten the existing bounds on the over-parameterization required to guarantee this property.

1.1 BACKGROUND Over the past few years, deep neural networks have achieved tremendous performance in various artificial intelligence applications such as computer vision, reinforcement learning, and natural language processing, etc. Despite their remarkable success in practice, theoretical aspects of this success remain a mystery. It has long been an open problem why simple local search algorithms for training deep neural networks, like stochastic gradient descent (SGD), typically converge to local minima with low training error despite the highly non-convex behavior of empirical loss. It has been observed, e.g., in (Choromanska et al., 2015) , that these methods may get stuck in poor local minima (i.e., local minima with empirical loss much larger than the global optimum) for small networks, while the problem fades away as the number of parameters grows larger. Such observations are often explained by studying the loss landscape in over-parameterized regime where the number of parameters in the network exceeds the training sample size.

Recently, several attempts have been made to characterize properties of squared loss landscape by conditioning on the layers' dimensions and sample size. Soudry and Hoffer (2017) showed that weights of a neural network can be adjusted such that the empirical loss is zero almost surely if m > 4 n/(2d -2) ≈ (2n)/d. This result is consistent with experimental observations that neural networks can fit training data if the number of parameters (here approximately 2n) is greater than the sample size. They also proved for normally distributed input that as n goes to infinity, the ratio between the volume of poor flat local minima regions to the volume of flat global minima fades exponentially if d = Ω( √ n) and m = Ω(n/d). Safran and Shamir (2016) showed that if the number of neurons in the hidden layer is Ω(n rank(X) ) (where X is the matrix containing all input), then with high probability, random initialization of weights will put them in a region of parameter space at which the loss surface has a basin-like structure, i.e., every local minimum in that region is global. In another work (Safran and Shamir, 2017) , the same authors provide a computer-assisted proof to show that spurious local minima are common in the expected loss landscape of shallow under-parameterized (small-width) networks. Xie et al. (2016) showed that if the input data is drawn uniformly at random from the unit sphere, and if m = Ω(n β ) and d = Ω(n β ) with β ∈ (0, 1) being the decay exponent of the smallest eigenvalue of a kernel matrix, then every critical point is a global minimum. Li et al. (2018) proved that for any continuous activation function and under the assumption that data samples are distinct, there exist no poor local minima with positive curvature if m ≥ n . In the same spirit, Venturi et al. (2018) showed that for any continuous activation function, there is always a descent path to an optimal solution with zero loss in the empirical loss landscape if m ≥ n.

Several works have proposed similar results in other settings and under different assumptions. Soudry and Carmon (2016) showed that in a network of leaky ReLU activation functions with randomized perturbation of slopes, all differentiable local minima are global minima if m ≥ n/d. Kawaguchi (2016) proved that in shallow networks with linear activation functions, every local minimum is a global minimum and all the saddle points are strict in the sense that they have a direction of strictly negative curvature. Soltanolkotabi et al. (2019) showed that the same result carries over to quadratic activation functions under the assumption that the last layer comprises at east d positive and d negative weights. Du and Lee (2018) established similar results for quadratic activation functions, assuming m ≥ √ 2n. For deep neural networks with linear activation functions, Freeman and Bruna (2016) showed that all local minima are global minima if there is a hidden layer whose number of neurons exceeds the minimum of the widths of input and output layers. For deep neural networks with analytical activation functions, Nguyen and Hein (2017) proved a similar property under the assumptions that the number of neurons in some hidden layer is greater than sample size and the network has a pyramidal structure.

Such studies on the properties of loss landscape do not only provide insights into the complication of training, but are also beneficial for proving performance guarantees for some local search algorithms. For the class of loss functions whose landscape satisfy the properties of: a) all local minima are global, b) all saddle points are strict, it has been shown in several works (Ge et al., 2015; Jin et al., 2017; Lee et al., 2016) that perturbed gradient descent converges to global optima in polynomial time. Another direction of research concerns the convergence of specific optimization algorithm such as Figure 1 : Architecture of the shallow network considered in this paper. The network has a single hidden layer of m neurons with ReLU activation functions, and a neuron with linear activation function in its output layer. pure gradient descent and SGD without assuming such properties for the loss landscape (Du et al., 2018; Allen-Zhu et al., 2018; Du et al., 2018) .

1.2. OUR CONTRIBUTIONS:

We study the amount of over-parameterization required for guaranteed existence of descent paths to zero loss in the empirical loss landscape. Previous works suggest that zero loss is always possible for m ≥ 2n/d (Soudry and Hoffer, 2017) . On the other hand, the best existing bound for guaranteed existence of descent paths to this zero loss requires m ≥ n neurons in the hidden layer (Venturi et al., 2018) . Prior to the present work, it was not known whether the "descent path property" holds for m < n. Even for m ∈ (2n/d, n), where zero empirical risk is known to be achievable (Soudry and Hoffer, 2017) , the existence of descent paths was in question. In this work, we tighten this gap and prove that there are training sets, under which in any network of width m ≤ n -2d + 2, there exist initial weights that have no descent path to global minima. We do this by showing that the loss landscape, in this regime, admits poor local minima with positive curvature. We also provide evidences and make conjectures that these results carry over to networks of width m = n -4, which, if true, provides a sharp characterization of the over-parameterization required for guaranteed existence of descent paths. We also wish to point that unlike most previous works, we do not restrict to differentiable local minima; for a simple argument shows that local minima with positive curvature cannot be differentiable if m > n/d (cf. Appendix A).

1.3. OUTLINE:

We continue by discussing details of the system model and introducing our key definitions in Section 2. We then present, in Section 3, the main results of the paper. Proof of the main results are then given in Section 4. We finally discuss implications and possible extensions of our results in Section 5 along with a number of open problems and directions for future research.

2. PRELIMINARIES:



2.1. MODEL:

We consider shallow networks of the form shown in Fig. 1 . The network takes d-dimensional inputs denoted by X. There is a single hidden layer comprising m neurons with ReLU activation function. For simplicity of our proofs, we only consider even values of m. We denote the input weights of r-th neuron by a d-dimensional vector w r , for r = 1, . . . , m. We then let w ∈ R md be the vector representation of all weights in the first layer.

The output layer has a single neuron, whose activation function is linear with an m-dimensional weight vector denoted by v. The network outputs a scalar ŷ(w, v) = m r=1 v r w T r X1(w T r X ≥ 0). We fix a training set (X 1 , y 1 ), . . . , (X n , y n ) of size n, and consider the landscape of empirical squared loss function:

F (w, v) n i=1 ŷi (w, v) -y i 2 .

(1)

2.2. PROPERTIES OF THE LANDSCAPE:

We first provide a formal definition for the descent path property, which is a necessary condition for guaranteed performance of descent optimization algorithms.

Definition 1 (Descent path property). Consider a continuous function f : R d → R and let f * = inf x∈R d f (x) be its infimum. We say that f has the descent path property if for any x ∈ R d , there exists a continuous curve with γ : [0, 1] → R d such that γ(0) = x, f γ(1) = f * , and f γ(t) is a non-increasing function of t.

The descent path property is a necessary condition for any descent optimization algorithm to provably find a global minimum from all initial conditions. It was shown in Venturi et al. (2018) that the empirical loss landscape of a shallow neural network with ReLU activation and squared loss has the descent path property if the size of training data is no larger than the width of the hidden layer, i.e., n ≤ m. We now characterize a class of local minima of specific form in the following definition.

Definition 2 (Cupped minima). Given a function f : R d → R, we call x ∈ R d a cupped minimum of f if there are , δ > 0 such that for any y in the δ-neighborhood of x, we have f (y) ≥ f (x)+ y-x2 . By a sub-optimal cupped minimum we mean a cupped minimum that is not a global minimum.

Note that every cupped minimum is a local minimum, but not every local minimum is cupped (e.g., flat local minima are not curved downwards, and hence are not cupped). Also note that a function is not necessarily differentiable at its cupped minima. We study cupped minima of the loss function in equation 1. Note however that for any α > 0, F (αw, v/α) = F (w, v). Therefore, F (•, •) has no cupped minima if both arguments are taken as variables. For that matter, when talking about cupped minima of F , we fix a v and consider F (•, v) as a function of its first argument. Interestingly, existence of cupped minima for F (•, v) leads to violation of descent path property for F (•, •) over both arguments, as shown in the following lemma. The proof is given in Appendix B.

Lemma 1. Consider a shallow network with loss function F in equation 1, and a pair of weights (w, v). Suppose that w is a sub-optimal cupped minimum of F (•, v), and that w r = 0, for r = 1, . . . , m. Then, F (•, •) has no descent path w(t), v(t) , initiated at (w, v), to its global minima.

3. MAIN RESULTS:

The following theorem and corollary state the main results of the paper.

Theorem 1. For any d ≥ 4, m ≥ 8 + 4 3/(d -3) , and n ≥ m + 2d -2, there exists a training set of size n such that the empirical loss function F of a shallow neural network of width m has the following property. For any m-dimensional vector v, with m/2 number of positive and m/2 number of negative entries, F (•, v) has exponentially many sub-optimal cupped minima.

The proof is constructive and is given in Section 4. In particular, we devise a training sequence (X 1 , y 1 ), . . . , (X n , y n ) such that for weights (w, v) at the cupped minima, we have v r w r = 1/ √ m, for r = 1, . . . , m. Moreover, X i ≤ 1, |y i | ≤ 2, and |e i | = 1 for i = 1, . . . , n (cf. Remark 2).

According to Theorem 1, there are training sequences tailored to give rise to sub-optimal cupped minima. However, we wish to point that the existence of such cupped minima does not stem from measure-zero incidents like placement of several data points on a low dimensional plane. In fact, in view of Lemma 1, any path that starts from a cupped minimum and end up in a global minimum would have an uphill climb of at least , for some > 0. Since the loss surface is a continuous function of (X i , y i ), a small perturbation of (X i , y i )'s leads continuously to a small change in F . Therefore, for small enough perturbations of (X i , y i ), any path to the set of global minima would still witness a positive uphill-climb. Hence, the descent path property remains out of order, even when the training data is slightly perturbed. Based on the above intuition, we can establish the following corollary 2 , Corollary 1. For any d ≥ 4, m ≥ 8 + 4 3/(d -3) , and n ≥ m + 2d -2; and when the inputs X and labels y are randomly drawn from independent normal distributions, there is a non-zero probability that F (•, •) does not have the descent path property.

Note that Corollary 1 does not imply Theorem 1, because a landscape could be cupped-min-free even if it the descent path property is not satisfied.

It was shown in Venturi et al. (2018) that n ≤ m is sufficient for the descent path property to hold. In contrast, Corollary 1 show that if n ≥ m + 2d -2, then the descent path property is not necessarily in effect. This leave a gap of size 2d -2 for the edge of over-parameterization required to guarantee the descent path property. We believe that this edge lies sharp at n = m. We conjecture a stronger version of Theorem 1, that cupped minima can emerge for training data sizes as small as m = n -4. Conjecture 1. Statement of Theorem 1 holds for all d ≥ 4, m ≥ 2d + 4, and n ≥ m + 4. See Remark 1 for insights into the possibility of this conjecture.

4. PROOF OF THE MAIN RESULT:

In this section, we present the proof of Theorem 1 organized in a sequence of four subsections. We first present some preliminaries in Subsection 4.1. In Subsection 4.2, we introduce a geometric structure called "(d, t, k)-configuration", based on which we construct, in Subsection 4.3, the training set that gives rise to cupped minima in the loss landscape. Finally, in Subsection 4.4, we prove the existence of cupped mimima in the devised setting. In order to provide intuitions on the loss landscape at cupped minima and motivate our construction of the training set in Subsection 4.3, we make a short note on different types of cupped minima in Appendix A. We also defer the proofs of some lemmas from this section to appendices for improved readability.

4.1 PRELIMINARIES Consider weights (w, v) and let (w , v ) be another set of weights such that for r = 1, . . . , m, v r and v r have the same sign and

w r = (v r /v r )w r . Then, F (w, v) = F (w , v ). Moreover, it is no difficult to see that w is a cupped minimum of F (•, v) if and only if w is a cupped minimum of F (•, v ).

For this reason, it suffices to prove existence of cupped minima for a fixed vector v. Note also that where w r 's are distinct, any permutation of the order of neurons would give rise to a new cupped minimum. Hence, existence of a cupped minimum for F (•, v) implies existence of exponentially many cupped minima for F (•, v).

We denote by e i = ŷi (w, v) -y i the estimation error for input X i . We let u d = [0, . . . , 0, 1] T be a d-dimensional vector with the last entry equal to one and all other entries equal to zero. For a region P ⊆ R d , we denote its interior and and its convex-hull by int(P) and Conv(P), respectively. Assuming differentiability of F at w, the partial derivatives of the loss function with respect to w r , r = 1, . . . , m, is as follows

∇ wr F (w, v) = v r n i=1 e i X i 1 w T r X i ≥ 0 . (2) 4.2 A GEOMETRIC CONFIGURATION

We introduce a geometric structure for sets of points in R d . This configuration will be used in Subsection 4.3 to construct a landscape with cupped minima.

Definition 3 ((d, t, k)-Configuration). Given integers d, t, k ≥ 0 and disjoint sets A, Ã, B, and B of points in R d , we say that A, Ã, B, B forms a (d, t, k)-configuration if the following properties are satisfied:

(p1) Each of A and B consists of t points, and each of Ã and B consists of k points.

(p2) (A) The convex hull of A Ã forms a polytope P A that has exactly t + k vertices. Equivalently, no point in A Ã is a convex combination of other points in A Ã. (B) Similarly, the convex hull of B B forms a polytope P B that has exactly t + k vertices.

(p3) We have 0 ∈ int(P A ) and 0 ∈ int(P B ).

(p4) There exists a constant β ∈ (0, 1) such that (A) For any a ∈ A, βa lies on a facet of P B . We denote this facet by S B (a). (p8) Consider a 2t × 2t matrix M whose rows and columns are associated to points p ∈ A B and q ∈ A B, and whose entries are as follows

EQUATION

where H q is the hyperplane define in Property (p7), and d(•, •) is the euclidean distance.

The property requires M to be full-rank.

Among the above properties, the most difficult of all is Property (p4), and the requirement that it involves the same β for all points in A B. In fact, elimination of Property (p4) gives rise to trivial configurations. 3In the two dimensional space, for any t ≥ 4 there exists a (2, t, 0)-configuration of the form illustrated in Fig. 2 . In the following proposition, we generalize this observation to higher dimensions. Proposition 1. For any d ≥ 2 and t ≥ 4, there exists a (d, t, d -2)-configuration.

The proof is constructive, and is given in Appendix C. We conjecture that there also exist (d, t, 0)configurations.

Conjecture 2. For any d ≥ 2 and t ≥ 2d, there exists a (d, t, 0)-configuration.

Remark 1. Using a configuration given by Conjecture 2 instead of the configuration from Proposition 1 in the construction and the proof that follow, we obtain a proof for Conjecture 1. In this view, establishing Conjecture 2 would also resolve Conjecture 1.

4.3. CONSTRUCTING A LANDSCAPE WITH CUPPED MINIMA:

Here we present a set of training data (X 1 , y 1 ), . . . , (X n , y n ) and a set of wights (w 1 , v 1 ), . . . , (w m , v m ) such that the empirical loss surface corresponding to (X 1 , y 1 ), . . . , (X n , y n ) has a sub-optimal cupped minimum at (w 1 , v 1 ), . . . , (w m , v m ). Without loss of generality, we assume n = m + 2d -2. Extension to larger values of n is straightforward via replication.

Let A, Ã, B, B be a (d -1, m/2, d -3)-configuration in the (d -1)-dimensional space, as in Proposition 1. In view of Property (p3), let 0 > 0 be such that P A and P B contain the 0neighborhood of 0. Let

EQUATION

)

We proceed by introducing the data points X 1 , . . . , X n . An illustration of these data points in the three dimensional space is shown in Fig. 3 . Data points X: We consider a total number of n = m + 2d -2 data points as follows.

• For each a ∈ A Ã, we consider a new data point X a as follows.

Let [z 1 , . . . , z d-1 ] ∈ R d-1

be the representation of a in the Cartesian coordinates. We let

X a = z 1 , . . . , z d-1 , 1 . • For each b ∈ B B, we consider a new data point X b as follows. Let [z 1 , . . . , z d-1 ] ∈ R d-1

be the representation of b in the Cartesian coordinates. We let

X b = -z 1 , . . . , z d-1 , 1 .

• We consider two extra points X A + , X A -, X B + , and X B -as follows. We let X A - ξu d , X B - -ξu d , and

X A + X A -- a∈A Ã X a + 1/β -1 u d (5) X B + X B -+ b∈B B X b + 1/β -1 u d (6)

where u d = [0, . . . , 0, 1] T , and ξ and β are defined in equation 4 and Property (p4), respectively.

Weights at cupped minimum: We associate each of m neurons to a point p in A B, in a one-one manner; and denote the vector of input weights and the output weight of that neuron by w p and v p , respectively. These weights are chosen as follows:

• For each a ∈ A, we let v a = -1/ √ m. • For each b ∈ B, we let v b = 1/ √ m.

• For each a ∈ A, consider the facet S B (a) defined in Property (p4), and let s 1 (a), . . . , s d-1 (a) be the vertices of S B (a) (as in Property (p6)). We let w a be the unique vector such that w a = 1 and We let w b be the unique vector such that w b = 1 and

EQUATION

EQUATION

EQUATION

)

Labels y: Having determined the data points X and the weights (w, v), the output ŷ(w, v) of the network is determined for all input X. In the following, we choose the true labels y to obtain a desired error e = ŷ -y for each input data. In particular:

• For each a ∈ A Ã, we associate to X a a label y a so that e a ŷa (w, v) -y a = 1.

• For each b ∈ B B, we associate to X b a label y b so that e b ŷb (w, v) -y b = -1.

• We choose the labels associated to X A + , X A -, X B + , and X B -such that e A + = e B + = 1 and e A -= e B -= -1.

This completes the description of the training set. As shown in in Soudry and Carmon (2016) , there exist weights that achieve zero loss if m > 4 n/(2d -2) . In our case, n = m + 2d -2, and its easy to check that m > 4 (m + 2d -2)/(2d -2) for all d ≥ 4 and m ≥ 8 + 4 3/(d -3) . It follows that in our setting the global optimum has zero loss, showing that the above (w, v) is sub-optimal. Remark 2. In the above construction, the norms of inputs vectors may be very large. If we scale down the inputs such that X i ≤ 1/ √ m for i = 1, . . . , n, and modify the corresponding labels y i such that e i remains unchanged, then a same set of weights will still be a cupped minimum for the landscape defined in terms of new (X i , y i )'s. Moreover, for this setting, it is easy to check that w r = 1, e i = 1, and

EQUATION

Then, δ > 0. For any θ ∈ R md with θ = 1 and for any t ∈ [0, δ], let

EQUATION

We show that there is an > 0 such that for any unit-norm θ and any t ∈ [0, δ],

EQUATION

) Lemma 2. For any θ ∈ R md with θ = 1, F θ (•) is a quadratic and convex function over [0, δ].

The proof is give in Appendix D and relies on the fact that neuron activations do not alter at w + θt for t ∈ [0, δ]. Consider now the following m-dimensional subspace of R md

EQUATION

)

For any θ ∈ R md , let θ and θ ⊥ be the orthogonal projections of θ on H w and H ⊥ w , respectively. Then, θ = θ + θ ⊥ . In order to establish equation 13, we need lower bounds on F θ (0) and F θ , which we derive in the next two lemmas. Lemma 3. There exists µ > 0 such that for any θ ∈ R md with θ = 1, we have

EQUATION

)

The proof is given in Appendix E, and relies in a subtle way on the choice of data points in subsection 4.3. We now bound the curvature of F θ . Lemma 4. There exist constants η 1 , η 2 > 0 such that for any θ ∈ R md with θ = 1, and for any t ∈ (0, δ),

EQUATION

)

The proof is given in Appendix F, and relies on Property (p8) of the underlying configuration.

Consider now the second order polynomial p(x) = η 1 δ 1 -x 2 -η 2 δx -µx, where µ, η 1 , and η 2 are the constants in Lemmas 3 and 4. Since p(0) > 0 and p(1) < 0, the polynomial p has exactly one root in the interval (0, 1), which we denote by x 0 . Let

EQUATION

)

Lemma 5. For any θ ∈ R md with θ = 1, and any t ∈ [0, δ], we have

F θ (t) ≥ F θ (0) + t 2 .

This lemma is a simple consequence of Lemmas 3 and 4, and its proof is given in Appendix G. It follows from Lemma 5 that for any w in the δ-neighborhood of w, we have F (w , v) ≥ F (w, v) + w -w 2 . This shows that w is a cupped minimum for F (•, v), and completes the proof of Theorem 1.

5. DISCUSSION:

The guaranteed existence of descent paths in shallow networks of ReLU neurons was previously established (Venturi et al., 2018) , given an over-parameterization of m ≥ n (where m and n are the number of neurons and the size of training data, respectively). This left an uncertainty gap of 2n/d < m < n, where zero empirical risk is known to be achievable (for m ≥ 2n/d) (Soudry and Hoffer, 2017) , but the existence of descent paths was in question. In this work, we have tightened this uncertainty gap to n -2d + 2 < m < n, by proving that for any m ≤ n -2d + 2, there are input data and initial weights for which a descent path does not exist. This conclusion we reach by establishing the existence of cupped minima for m ≤ n -2d + 2, and for the right choice of input data.

Compared to similar existing results for other activation functions, our results suggest that the edge m ≈ n of over-parameterization required for elimination of sub-optimal cupped minima in ReLU networks is much higher than that of networks with quadratic activation functions, m ≈ √ 2n (Du and Lee, 2018) , and linear activation functions, m ≈ n/d (Kawaguchi, 2016) , and is almost as high as general continuous activation functions of any form, m ≤ n (Venturi et al., 2018) .

Non-existence of spurious local minima and the decent path property favor the convergence of decent optimization methods like GD. However, for different variants of noisy GD, like SGD and Langevin dynamics, it is quite common for the empirical loss to fluctuate during the training. Nevertheless, for theoretical analysis purposes it usually helps to take the noise away, for example by tending the step size to zero. The resulting GD, which always follows a descent path, is usually easier to analyze and can also help to study the SGD dynamics. On the other hand, from a practical view, convergence of SGD in local-min-free landscapes is well-studied.

Aside from addressing Conjecture 2, there remain several open problems, which we review next. As an important direction for future research, it would be interesting if one could obtain bounds on the probability of existence of cupped minima over random data sets, underneath the edge of over-parameterization. In particular, we showed in Corollary 1 that this probability is non-zero, however we gave no clue on either the size or scaling of this probability. Another class of problems concerns basins of local minima, and how they affect dynamics of first order optimization algorithms. As a step toward this goal, one might characterize the true over-parameterization regime in which the basins of poor local minima have considerable volume.

Among other directions are extensions of our results to deep ReLU networks, shallow non-ReLU networks, and shallow ReLU networks under loss functions more general than the squared loss. We show that t 1 < t 0 . If t 0 < ∞, then continuity of v(t) implies that v r (t 0 ) = 0, for some r ≤ m. Therefore, wr (t 0 ) = 0 = w r . It then follows from the continuity of wr (•) that there is an > 0 such that wr (t 0 -) = w r . Consequently, t 1 < t 0 .

The inequality t 1 < t 0 implies that there is an > 0 such that wr (t 1 + ) = w, and for any t ∈ [0, t 1 + ], we have sgn v r (t) = sgn(v r ), r = 1, . . . , m. Therefore, for any t ∈ [0, t 1 + ], we have w, v) . This shows that w(t), v(t) cannot be a descent path for F (•, •), and completes the proof of Lemma 1.

F w(t), = F w(t), v(t) . Since w is a cupped minimum of F (•, v), there is an s ∈ [t 1 , t 1 + ] such that F w(t), v > F (

C PROOF OF PROPOSITION 1:

For i = 3, . . . , d, let

EQUATION

Fix a constant

EQUATION

)

Let γ be a uniform random variable

EQUATION

)

We take a sample from the above distribution and fix a γ for the rest of the proof.

We now introduce the points in the configuration. For i = 0, . . . , t -1, we consider points a i ∈ A and b i ∈ B as follows

EQUATION

EQUATION

For i = 3, . . . , d, we consider points ãi ∈ Ã and bi ∈ B as follows ãi = 0, . . . ,

EQUATION

EQUATION

Fig. 5 shows an illustration of these points for d = 3.

We proceed by verifying Properties (p1)-(p8).

Property (p1): Property (p1) is straightforward from the above construction.

Property (p2): Considering only the first two coordinates, it is easy to see that no point of A is a convex combination of other points in A Ã. Also note that for i = 3, . . . , d, ãi is the only point in A Ã whose i-th entry is negative. Therefore, no point in Ã can be represented as a convex combination of other points in A Ã. A similar argument works for Part (B) of Property (p2).

Property (p3): Let

EQUATION

EQUATION

A simple induction on j shows that

EQUATION

)

for j = 4, . . . , d. We show that

EQUATION

)

For the first two coordinates, equation 31 is easy. Let a i j and ãi j be the j-th entries of a i and ãi , respectively. For the j-th coordinate, j = 3, . . . , d, we then have

t-1 i=0 α i a i j + d i=3 αi ãi j = t × 1 tγ × γc j + c j j-1 i=3 αi -αj = c j + c j αj c j -1 -αj = 0,

where the second equality is due to equation 30. This establishes equation 31. It then follows from equation 31 that 0 is a convex combination of points in A Ã. Consequently, 0 ∈ int(P A ). A similar argument shows that 0 ∈ int(P B ).

Properties (p4)-(p7): We only prove Part (B) for each of these properties; as similar proofs work also for Part (A)'s. Moreover, because of the rotational symmetry of A and B in the first two coordinates, it suffices to prove of the Properties (p4)-(p7) only for b 0 .

Published as a conference paper at ICLR 2020 Properties (p4) and (p5): For the j-th coordinate, j = 3, . . . , d, we have

EQUATION

where b 0 j is the j-th entry of b 0 defined in equation 25. Similarly, for the first two coordinates, we have:

EQUATION

)

It then follows from equation 32 and equation 33 that

EQUATION

Let

EQUATION

)

Then, from equation 34,

EQUATION

)

Therefore, βb 0 is a convex combination of a 0 , a 1 , ã3 , . . . , ãd , and therefore lies on the simplex S that has a 0 , a 1 , ã3 , . . . , ãd as its vertices. Next, we show that S is a facet of P A .

Consider a vector z ∈ R d with entries

EQUATION

)

Then, a simple backward induction, with base case i = d, shows that for i = 3, . . . , d, we have d j=i+1 c j z j = z i + 1. In the same vein,

EQUATION

)

It follows that for i = 3, . . . , d,

EQUATION

)

Moreover, for i = 0, 1,

EQUATION

where the second equality is due to equation 38. Let H be the hyperplane that passes through a 0 , a 1 , ã3 , . . . , ãd . It follows from equation 39 and equation 40 that for any p ∈ a 0 , a 1 , ã3 , . . . , ãd , we have z T p = 1. Therefore, z is orthogonal to H. Consequently,

EQUATION

)

For i = 2, . . . , t -1, we have

EQUATION

where the second equality is due to equation 40, and the inequality is because z 1 > 0 and cos(2π(i -1/2)/t) -cos(π/t) < 0. It follows from equation 41 and equation 42 that all points of A\{a 0 , a 1 } lie on one side of H, while all points of Ã {a 0 , a 1 } lie on H. Then, H is a tangent hyperplane to P A . Thus, the simplex S is a facet of P A . This completes the proofs of Properties (p4) and (p5). Moreover, from the definition H b in Property (p7), we have

EQUATION

Property (p6): Since t ≥ 4, we have 2 cos(π/2) > 1. Moreover, recall from equation 23 that γ < 1. Property (p6) then follows from equation 34 and the fact that S is a facet of P A .

Property (p7): For i = 0, . . . , t -1,

EQUATION

where the second equality is due to equation 40 and definitions of a 0 and b i , and the third equality is from equation 38. It follows that

EQUATION

where the inequality is because the first two terms on the left hand side of the inequality are positive.

In the same vein, for i = 1, . . . , t -1

EQUATION

where the second inequality follows from the definition of z 1 in equation 37 and the fact that z 1 > 1, and the third inequality is from the definition of γ in equation 23 and the fact that 2γc ≤ cos(π/t) -cos(2π/t). It then follows from equation 41, equation 45, and equation 46 that b 0 and b i lie on opposite sides of H, for i = 1, . . . , t -1.

On the other hand, since bi = -ã i , for i = 3, . . . , d, it follows from equation 39 that z T bi = -z T ãi = -1 < 1. Therefore, for i = 1, . . . , 3, bi and b 0 lie on opposite sides of H. This completes the proof of Property (p7).

Property (p8): We have

EQUATION

where the first equality is due to equation 43 and equation 41, and the second equality follows from the equality in equation 45. Similarly, from equation 42, we have for i = 0, . . . , t -1

EQUATION

For i, j ∈ {0, . . . , t-1}, let ma i ,b j cos 2π(i-j -1/2)/t -cos(π/t) and mb i ,a j cos 2π(ij + 1/2)/t -cos(π/t). Then, it follows from equation 48 and rotational symmetry of A and B in the first two coordinates that for i, j ∈ {0, . . . , t -1},

EQUATION

Note that for any p, q ∈ A B, mp,q is a constant independent of the value of γ. Let M be a 2t × 2t matrix, with entries

EQUATION

for p, q ∈ A B. Then, all entries of M are constants independent of γ. Let λ1 , . . . , λ2t be the eigenvalues of m. It follows that λ1 , . . . , λ2t are also constants independent of γ.

Consider the matrix M defined in equation 3. It follows from equation 47 and equation 49 that for any p, q ∈ A B,

EQUATION

Consider the order a 0 , . . . , a t-1 , b 0 , . . . , b t-1 on the elements of A B. Then,

EQUATION

)

where I is the 2t×2t identity matrix and the second equality is from the definition of z 1 in equation 37.

Denote the eigenvalues of M by λ 1 , . . . , λ 2t . Then, from elementary linear algebra,

EQUATION

for i = 1, . . . , 2t. Therefore, there is at most one value of γ for which λ i = 0. Then, in view of equation 23, we have Pr(λ i = 0) = 0, over the random choice of γ. Thus, with probability one, M has no zero eigenvalues and is thereby full-rank. As an immediate consequence, M is full-rank for suitable choice of γ. This establishes Property (p8) and completes the proof of Proposition 1.

D PROOF OF LEMMA 2:

Consider a block representation of θ as follows

EQUATION

where each θ r is a d-dimensional vector.

It follows from the definition of δ that for any t ∈ (0, δ), if w T r X i > 0, then (w r + θ r t) T X i > 0; and if w T r X i < 0, then (w r + θ r t) T X i < 0. Therefore, for r = 1, . . . , m and i = 1, . . . , n, and for any t ∈ [0, δ) ,

EQUATION

Consequently, for any t ∈ [0, δ] and i = 1, . . . , n, we have 

EQUATION

E PROOF OF LEMMA 3:

We first characterize active neurons for different inputs. For two subsets S 1 , S 2 ⊂ R d we let S 1 \S 2 = S 1 S c 2 . Recall the definition of s i (a) and s i (b) from Property (p6). Claim 1. For any a ∈ A, we have

EQUATION

w T a X a > 0, (58)

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

Similarly, for any b ∈ B, we have

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

)

Proof of Claim 1. Fix a b ∈ B. We begin by introducing some notations. Let H be the (d -2)dimensional hyperplane in the (d -1)-dimensional space that passes through s 1 (b), . . . , s d-1 (b). In the same spirit, let H be the (d -1)-dimensional subspace in the d-dimensional space that passes through X s1(b) , . . . , X s d-1 (b) , equivalently H is the subspace orthogonal to w b . We denote the convex hull of X s1(b) , . . . , X s d-1 (b) by C B Conv X s1(b) , . . . , X s d-1 (b) . Similarly, we let

Q A conv X a | a ∈ A Ã and Q B Conv X b | b ∈ B B .

Before presenting the proofs of properties equation 57-equation 72, we review make some easy observations. Recall the definition of 0 from the paragraph proceeding equation 4. Let B d-1 0 be the intersection of the 0 -ball centered at 0 with the orthogonal space of u d . Then, from the definition of , we have

EQUATION

For x ∈ R d , let π(x) be the projection of x on the span of first d -1 coordinates, i.e., the orthogonal space of u d . Then,

EQUATION

where the first equality is from the definition of X A + and the second inequality follows from the definition of ξ in equation 4. Therefore, π(X

EQUATION

where the first equality is orthogonal decomposition of X A + , and last inclusion follows from equation 73. In the same vein, we can show that In particular,

EQUATION

w T b X a > 0, a ∈ A Ã \ s 1 (b), . . . , s d-1 (b) , w T b X A + > 0, -w T b X B + > 0,

where the first inequality is because Property (p5) implies that X a ∈ H for a ∈ A Ã \ s 1 (b), . . . , s d-1 (b) , and the last two inequalities are due to equation 75 and equation 76, respectively. This establishes equation 67, equation 68, and equation 70. For equation 72, it follows from Property (p7) that for any b ∈ B B with b = b, X b and X b lie on opposite sides of H. Eq. equation 66 then implies that w T b X b < 0. This establishes equation 72, and completes the proof of Claim 1.

In light of Claim 1, it is easy to see for r = 1, . . . , m and i = 1, . . . , n that if w T r X i = 0, then

EQUATION

In our next claim, we examine a linear combination of data points for which a particular neuron is active.

Claim 2. For r = 1, . . . , m, there exist constants γ r 1 , . . . , γ r m such that

EQUATION

)

Proof of Claim 2. Fix a b ∈ B. We prove the claim for the neuron associated to b.

EQUATION

where the second equality is due to the definitions of e a , e b , e A + , and e A -, and the third equality is from the definitions of X A + in equation 5.

On the other hand, it follows from Property (p6) that there exist scalars α 1 , . . . , α d ∈ (0, 1) such that b

EQUATION

Moreover, Property (p4) implies that d-1 i=1 α i = 1/β. Then, from equation 80, 

EQUATION

EQUATION

EQUATION

for the constant γ r i defined in Claim 2. It follows that r > 0, for r = 1, . . . , m. For any r ≤ m, X s1(r) , . . . , X s d-1 (r) are linearly independent and, by definition, are all orthogonal to w r . Therefore, there exists a constant r > 0 such that for any

ζ r ∈ R d with ζ r = 1, we have max i=1,...,d-1 |ζ T r X si(r) | ≥ r ζ ⊥ r , where ζ ⊥ r is the projection of ζ r on the null-space of w r . Consequently, for any ζ r ∈ R d with ζ r = 1, max i=1,...,n |ζ T r X i | × 1 w T r X i = 0 ≥ r ζ ⊥ r .

In particular, considering the block-vector representation of θ in equation 54, we obtain for r = 1, . . . , m,

EQUATION

Let µ min r r r / √ m. Then, µ > 0. It then follows from Claim 2 that, for r = 1, . . . , m,

EQUATION

where the third equality is due to equation 77, the fourth equality is because θ T r X i and 1(θ T r X i > 0) -γ r i have always the same sign, the first inequality is by definition of r in equation 83, the third inequality follows from equation 84, and the last inequality is from the definition of µ.

On the other hand, equation 2 implies that dF θ (t)

d + t t=0 = lim t↓0 m r=1 v r θ T r n i=1 e i X i 1 (w r + θ r t) T X i ≥ 0 = m r=1 v r n i=1 θ T r e i X i 1 w T r X i = 0, θ T r X i ≥ 0 + 1 w T r X i > 0 = m r=1 v r n i=1 e i θ T X i 1 w T r X i = 0, θ T r X i ≥ 0 + v r n i=1 e i θ T r X i 1 w T r X i > 0 ≥ m r=1 µ θ ⊥ r ≥ µ θ ⊥ (86)

where the second equality is due to equation 55 and the first inequality follows from equation 85. This completes the proof of Lemma 3.

F PROOF OF LEMMA 4:

We begin by a claim. Given a q ∈ A B, recall the definition of hyperplane H q from Property (p7).

Claim 3. For any pair of points p, q ∈ A B, we have

EQUATION

)

where the third equality is due to equation 19. On the other hand, since θ = θ + θ ⊥ , we have

EQUATION

In the following claim, we elaborate on Gθ . Claim 4. There exists a constant η 1 > 0 such that Gθ 2 ≥ 2η 1 θ 2 , for all θ ∈ R d .

Proof of Claim 4. Recall that θ is the projection of θ on subspace H w defined in equation 14. Then, there exist constants α 1 . . . , α m such that

EQUATION

)

Let α be the vector representation of α 1 , . . . , α m . Then,

EQUATION

)

Consider the n × m matrix

EQUATION

Then, from the definition of matrix G in equation 18,

EQUATION

Each column of G corresponds to a neuron, and thereby is associated to a point in A B. In the same vein, every row of G is associated to an input vector. By removing some rows of G, we devise a matrix M so that each row of M is associated to an input X p for p ∈ A B. Therefore, M is an m × m matrix, whose rows and columns are associated to the points in A B. It follows that M α is a vector obtained by removing some entries from vector Gα. As a result, M α ≤ Gα .

In the following, we capitalize on Property (p8) to show that M is full-rank.

For q ∈ A B, let γ q v q 1 + d(0, H q ) .

For p, q ∈ A B, the entry in row p and column q of M equals Mpq = Gpq = v q X T p w q 1 w T q X p > 0 + 1 w T q X p = 0, θ T q X p ≥ 0 = v q X T p w q 1 w T q X p > 0 = v q 1 + d(0, H q ) d p, H q 1 w T q X p > 0 = γ q d p, H q 1 w T q X p > 0 .

(

EQUATION

where the first equality is from the definition of M , the second equality follows from the definitions of G and J q in equation 99 and equation 93, the third equality is because X T p w q 1 w T q X p = 0 = 0, and the fourth equality is due to Claim 3. Then, Claim 1 implies that for any p, q ∈ A B, Mpq = γ q d p, H q , if p = q, OR p ∈ A and q ∈ B, OR p ∈ B and q ∈ A, 0, otherwise.

Compared to matrix M defined in equation 3, each column q of M equals the column q of M multiplied by a non-zero constant γ q . In view of Property (p8), M is full-rank. It follows that M is full-rank, as well.

Let σ be the smallest singular value of M . Since M is full-rank, we have σ > 0. Moreover, M α ≥ σ α .

Then, Gθ 2 = Gα 2 ≥ M α 2 ≥ σ 2 α 2 = σ 2 θ 2 , (105) where the equations are due to equation 100, equation 101, equation 104, and equation 98, respectively. Claim 4 then follows for η 1 = σ 2 /2.

Back to the proof of Lemma 4, we denote by σ max the largest singular value of G. Let η 2 σ 2 max . Then,

EQUATION

where the second inequality is from the definition of σ max , the third inequality is because θ ≤ θ = 1, the last equality is by the definition of η 2 , and the last inequality follows from Claim 4. This completes the proof of Lemma 4.

G PROOF OF LEMMA 5:

Fix a θ ∈ R md with θ = 1. Recall the definition of x 0 from the paragraph proceeding equation 17. If θ ⊥ ≥ x 0 , then for any t ∈ [0, δ],

F θ (t) -F θ (0) ≥ F θ (0)t ≥ µ θ ⊥ t ≥ µx 0 t = δt ≥ t 2 ,

where the first inequality is from convexity of F θ in Lemma 2, the second inequality is due to Lemma 3, the equality is by the definition of in equation 17, and the last inequality is because t ≤ δ.

On the other hand, if θ ⊥ < x 0 , then for any t ∈ [0, δ],

F θ (t) -F θ (0) = F θ (0)t + 1 2 F θ t 2 ≥ 1 2 F θ t 2 ≥ η 1 θ 2 -η 2 θ ⊥ t 2 = η 1 1 -θ ⊥ 2 -η 2 θ ⊥ t 2 < η 1 (1 -x 2 0 ) -η 2 x 0 t 2 = µx 0 δ t 2 = t 2 ,

:

A formal proof is pretty tedious, and is not presented here.

e.g., for A and Ã chosen uniformly at random over the unit sphere, and letting (B, B) be a small rotation of (A, Ã) around an arbitrary axis, it is not difficult to see that all properties except (p4) would be satisfied with high probability.

This is because otherwise, w + δθ/2, v is the limit point of a sequence of weights at which F is differentiable. Since our arguments carry over to the weights in this sequence, we can conclude that all bounds also apply to their limit point, w + δθ/2, v .

Figures and Tables:

(B) For any b ∈ B, βb lies on a facet of P A . We denote this facet by S A (b). (p5) (A) For any a ∈ A, S B (a) is a (d -1)-dimensional simplex. (B) For any b ∈ B, S A (b) is a (d -1)-dimensional simplex. (p6) (A) For any a ∈ A, there exist scalars α 1 , . . . , α d ∈ (0, 1) such that a = d i=1 α i s i (a), where s 1 (a), . . . , s d (a) are the vertices of simplex S B (a). (B) For any b ∈ B, there exist scalars α 1 , . . . , α d ∈ (0, 1) such that b = d i=1 α i s i (b), where s 1 (b), . . . , s d (b) are the vertices of simplex S A (b). (p7) (A) For any pair a and a of distinct points in A, we have S B (a) = S B (a ). Moreover, letting H a be the hyperplane that contains S B (a), a and a lie on opposite sides of H a , for all a ∈ A Ã with a = a. (B) For any pair b and b of distinct points in B, we have S A (b) = S A (b ). Moreover, letting H b be the hyperplane that contains S A (b), b and b lie on opposite sides of H b , for all b ∈ B B with b = b.

Figure 2: A (2, t, 0)-configuration with t = 8. The blue dots show the points in A and red crosses are the points in B.

Figure 3: Illustration of data points X 1 , . . . , X n for d = 3 and m = 12.

For each b ∈ B, consider the facet S A (b) and let s 1 (b), . . . , s d-1 (b) be the vertices of S A (b).

Figure 4: Different types of cupped minima in terms of differentiability, discussed in Appendix A.

Figure 5: An illustration of the points in equation 24-equation 27 for d = 3 and t = 4. The red crosses indicate the points in A Ã and the blue dots correspond to the points in B B.

We proceed to verify equation 65-equation 72. Eq. equation 65 follows from equation 9. Recall the definitions X A -= ξu d and X B -= -ξu d . Then, equation 10 implies equation 69 and equation 71. Since X s1(b) , . . . , X s d-1 (b) define a boundary of the (d -1)-dimensional convex set Q A , and H passes through X s1(b) , . . . , X s d-1 (b) , then all points in Q A lie on a same side of H. In other words, either we have w T b x ≥ 0, for all x ∈ Q A ; or we have w T b x ≤ 0, for all x ∈ Q A . In view of Property (p3), u d ∈ int(Q A ). It then follows from equation 10 that for any x ∈ Q A , we have w T b x ≥ 0. Consequently, for any x ∈ Q A \ H, we have w T b x > 0.

equation 66, it follows from Property (p4) that b and the origin, 0, lie on opposite sides of hyperplane H. Consequently, -X b and u d also lie on opposite sides of hyperplane H. Therefore, w T b X b and w T b u d have a same sing. It then follows from equation 10 that w T b X b > 0, and equation 66 follows.

where last equality in due to equation 81. Combing equation 79 and equation 82, we obtain equation 78 for w r = w b . A similar argument implies equation 78 for w r = w a , a ∈ A. This completes the proof of Claim 2. Back to the proof of Lemma 3, for r = 1, . . . , m, let r min i=1,...,d-1

It follows that ŷi w + θt, v is a linear function of t over the interval t ∈ [0, δ]. Therefore, F θ (t) =

Table content: <table/>

Peer review (iclr2020):
This paper studies the landscape properties of over-parameterized two-layer neural networks, and proposes a network width lower bound for guaranteed existence of descent paths that is tighter than existing results. In particular, the authors prove that if the network width m leq n - 2d, then there exist training data sets and initial weights such that the square loss on the neural network has no descent path connecting the initial weights and global minima. Overall, I think this paper is of good quality. The presentation is clear and the logic is easy to follow. I did some high-level check and the theoretical analysis seems reasonable. However, I have the following questions: 1. As is stated in Corollary 1 and discussed below Theorem 1, the training sample sets that lead to suboptimal capped minima are not of measure-zero. However, it seems that no rigorous proof is provided for this result. Perhaps I have missed something, but is Corollary 1 straight forward given Theorem 1 and Lemma 1? How large is the probability? It would be better if the authors could provide a more rigorous proof. 2. A recent line of work has shown convergence of gradient-based algorithms for over-parameterized neural networks. It would be interesting if the authors could provide more comparison between this paper and the results of these works: - Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, Xiyu Zhai, Gradient Descent Finds Global Minima of Deep Neural Networks - Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song, A Convergence Theory for Deep Learning via Over-Parameterization - Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu, Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks