Bounds on Over-Parameterization for Guaranteed Existence of Descent Paths in Shallow ReLU Networks
Authors: Arsalan Sharifnassab
Saber Salehkaleybar
S. Jamaloddin Golestani
Venue:  (2020)
Keywords: Spurious local minima
Loss landscape
Over-parameterization
Theory of deep learning
Optimization
Descent path

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\geq 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\le 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. 

Published as a conference paper at ICLR 2020
BOUNDS ON OVER-PARAMETEERIZATON FOR GUARANTEED EXISTENCE OF DESCENT PATHS IN SHALLOW RELU NETWORKS
Arsalan Sharifnassab'
Saber Salehkaleybar'
Department of Electrical Engineering
Department of Electrical Engineering
Sharif University of Technology
Sharif University of Technology Tehran, Iran sa saleh@sharis f.edu
Tehran, Iran
a. shaariiii fnassabegma com
S. Jamaloddin Golestani Department of Electrical Engineering Sharif University of Technology Tehran, Iran
golestan @sharif edeu
ABSTRACT
We study the landscape of squared loss in neural networks with one-hidden layer and ReLU activation functions. Let 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 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 no descent path to global optima. It is known that for from all initial weights. In this perspective, our results provide a somewhat sharp characterization of the over-parameeeriizaion required for "existence of descent paths" in the loss landscape.
2d 2. By positive curvature
m, there always exist descent paths to global optima
INTRODUCTION
We consider shallow neural networks of the form shown in Fig. [ The network comprises a hidden layer and input layer of widths and d, respectively; and is to be trained over training set of size n. Our results concern the slightly over-parament perameeeeeeee regime where n ~ m. We study the existence of poor local minima that have positive curvature in the empirical squared loss landscape.
is well-known that poor local minima exist in the loss landscape of shallow networks of arbitrary width. In fact, in shallow network with ReLU activation functions, it easy construct training sets whose empirical loss landscape has high plateaus Itt 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: loss landscape is said to have the descent path property if starting from any initial point there is path of descent loss to 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 poor local minima is known be a favorable property for guaranteed convergence (Ge et al. 2015; Jin al.) 2017 Lee et al.) 2016). The descent path property is shown to be satisfied in over weerparameterizeed shallow networks with sufficiently large widths (Venturi et al. 2018). The
"Webpage:
ht http:///.....tt...t///eieiiiiaee
Webpage: http://siaa..haai..
c.g. for training and of weights which all neurons inactive.

---

Published as a conference paper at ICLR 2020
results present in this work, tighten the existing bounds on the over-parameeterization 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 computer vision, reinforcement learning, and natural language processing, etc. Despite their remarkable success in practice, theoretical aspects of this success remain 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. 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 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 [ (2d 2)] Re (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 (aa//dd)aaaaann
exponentially if d = (2(vn) and m = ((n/d). Safran and Shamir 2016) showed that if the number of neurons in the hidden layer is =ankk((()) (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 (017)) the same authors provide a computer- that spurious local minima are common in the expected loss landscape of shallow mnder-parameteriin (small-width) networks. Xie et al. (2016) showed that if the input data drawn uniformly at random from the unit sphere, and if m 32(n") and d (nn") with 3 E (0, 1) being the decay exponent of the smallest eigenvalue of kernel matrix, then every critical point is global minimum. Li et al. (2018) proved that for any continuous activation function and under the assumption that data samples distinct, there exist poor local minima with positive curvature if m Venturi et al. (2018) showed that for any continuous activation function, there is always a descent path to optimal solution with zero loss in the empirical loss landscape if m n.
proof to show
In the same spirit,
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 2 n//.. 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, (Solanolkooabii 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. [u and Lee (2018) established similar results for quadratic activation functions, assuming m 2 V2n. 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 similar property under the assumptions that the number of neurons some hidden layer is greater than sample size and the network has 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, 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
2

---

Published as a conference paper at ICLR 2020
V1
122
Vm
Xax1
W
Architecture of the shallow network considered in this paper. The network has single hidden layer m neurons with ReI.U activation functions, and a neuron with linear activation function in its output layer.
Figure I:
pure gradient descent and SGD without assuming such properties for the loss landscape (Du et al. Allen-Zhu et al. 2018: Du al. 2018).
2018
1.2 OUR CONTRIBUTIONS
We study the amount of werrparrameterization 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 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 2 n neurons in the hidden layer (Venturi et al. 2018). Prior to the present work, it not known whether the "descent path property" holds for m7 < n. Even for m E (2n/d. 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, tighten this gap and prove that there are training sets, under which in any network of width m S 2d + 2, there exist initial weights that have no descent path 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 which, if true, provides sharp characterization of the wver-parameterization required for guaranteed existence descent paths. We also wish to point that unlike most previous works, we do not restrict to differentiable local minima; for 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 the system model and introducing our key definitions Section We then present, in Section 3, the main results of the paper. Proof of the main results are then given in Section We finally diseuss implications and possible extensions our results in Section aloog with number of open problems and directions for future research.
2
PRELIMINARIES
2.1
MODEL
We consider shallow networks of the form shown in Fig. The network takes d-dimensional inputs denoted by X. There 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 d'dimennsionl vector w,, for r = I,..., m. We then let w E Rmd be the vector representation of all weights in the first layer.
The output layer has single neuron, whose activation function is linear with an m-dimensional weight vector denoted by The network outputs a scalar ÿ(w, v) = D v, X1 X > 0). We fix a training set (X1, 11), (Xnz Bn) of size n, and consider the landscape of empirical squared loss function:
F(w, v) 4 (Be(w, v) v1))
(1)
3

---

Published as a conference paper at ICLR 2020
2.2 PROPERTIES OF THE LANDSCAPE
We first provide formal definition for the descent path property, which is a necessary condition for guaranteed performance of descent optimization algorithms.
Definition (Descent path property). Consider a continuous function f :R - R. and let f infzeRs f()) be its infimum. We say that f has the descent path property for any E R,, there exists a continuous curve with 7 [0, 1] + B2 such that ((0) = z, f(((1) = f", and f(r(t) is
non-increusing fanction of l.
The descent path property is necessary condition for any descent optimization algorithm provably find 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 S m. We now characterize class of local minima of specific form in the following definition.
Definition (Cupped minima), Given a function f IR + R. we call x E IR a cupped minimum of if there are e, ô > 0 such that for any y in the ô-neighborhood of x, we have [y) 2 [<ll--ll-== By a sub-optimal cupped minimum we mean a cupped minimum that is not a global minimum.
Note that every cupped minimum 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 function is not necessarily differentiable at its cupped minima. We study cupped minima of the loss function in equation I Note however that for any a >> 0, F(aw, v/a)) = 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 and consider F(:, u) as 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 7 and a pair of weights (w, v). Suppose that w is sub-optimal cupped minimum of F(., v), and that wr o O, for 1,...,m, m. Then, F(.))) has no descent path (w(t), u(t)), initiated at (w, v), to its global minima.
3 MAIN RESULTS
The following theorem and corollary state the main results of the paper.
(d33333))] ], and n 2 m + 2d there exists a training set of size n such that the empirical loss function F of shallow neural network of width m has the following property. For any m-dimensional vector u. with m/2 number of positive and m/2 number of negative entries, F(..v) has exponentially many sub-optimal cupped minima.
Theorem 1. For any d > 4, m 2 8 4/3 2
The proof is constructive and is given in Section 4 In particular, we devise training sequence (X1, 11), ......., (Xn, yn) such that for weights (w, v) at the cupped minima, we have ||,,,,, Vm, for r = 1 m. Moreover, |XI,|| < 1, 1yal I 2, and |cs| = for i = I,...,, n (cf. Remark
According to Theorem [ 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-7ero incidents like placement of several data points on low dimensional plane. In fact, in view of Lemma [ any path that starts from a cupped minimum and end up in a global minimum would have an uphill climb of at least e, for some E >> O. Since the loss surface is a continuous function of (X,, 34), small perturbation of (X,, y1)'s leads continuously to small change in F. Therefore, for small enough perturbations of (X,. Vs). 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
Corollary 1. For any d d 4, 1mmm3 8+ 4/3 and 2 + 2d 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.
AA formal proof is pretty tedious, and is not presented here.
4

---

Published as a conference paper at ICLR 2020
Note that Corollary does not imply Theorem 1 it the descent path property is not satisfied.
because landscape could be cupped min-free
It was shown in Venturi et al. (2018) that S is sufficient for the descent path property hold. In
contrast, Corollary show that if n 2 m + 2d - 2, then the descent path property is not necessarily in effect. This leave gap of size 2d for the edge of pree-parameterization required to guarantee the descent path property. We believe that this edge lies sharp at nt = m. We conjecture a stronger version of Theorem [
that cupped minima can emerge for training data sizes as small m 4.
Conjecture 1. Statement of Theorem holds for all d 2 4, m 2d + 4, and 2 + 4.
See Remark for insights into the possibility of this conjecture.
4 PROOF OF THE MAIN RESULT
In this section, we present the proof of Theorem organized in sequence of four subsections. We first present some preliminaries in Subsection 4.1 In Subsection 4.2 we introduce geometric structure called "(d, f, k) >confiiuuratio"" 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 make a short note on different types of cupped minima Appendix/A [A] We also defer the proofs of some lemmas from this section appendices for improved readability.
construction of the training set in Subsection 4.3
4.1 PRELIMINARIES
Consider weights (w, v) and let (w', o²) be another set of weights such that for 1,...; m, U, and of have the same sign and we (Cr/u())w, Then, F(w, v) F(w', v²). Moreover, it is no difficult see that this reason, it suffices to prove existence of cupped minima for fixed vector u. Note also that where w, 's are distinct, any permutation of the order of neurons would give rise new cupped minimum. Hence, existence of cupped minimum for F(. v) implies existence of exponentially many cupped minima for u(.,)).
a cupped minimum of F-, v) if and only if w' is a cupped minimum of F(-, e'). For
We denote by a d-dimensional vector with the last entry equal to one and other entries equal to zero For region P C Rdd we denote its interior and and its convex-hull by int(P) and Conv respectively. Assuming diffcrentiability of at w, the partial derivatives of the loss function with respect to wr. m, as follows
(w, u) - the estimation error for input X,. We let un = [o..... O. 1_1 be
a
Vw, F(,, = Ur
Eex1 x, x, 20.
(2)
1=1
4.2
GEOMETRIC CONFIGURATION
We introduce a geometric structure for sets of points in Rd, This configuration will be used in Subsection 4.3 to construct a landscape with cupped minima.
Definition ((d, I, k.))) Given integers d, 1, 2 0 and disjoint sets A, A, B, and B of points in Rd,, we say that (A, A, B, B) forms a (d, t, k)-configurrttoon if the following properties are satisfied:
(pl) Each of A and B consists of points, and each of À and B consists of k points.
(p2) (A) The convex hull of A AU A forms polytope PA that has exactly lently, point in A U Á is convex combination of other points in A A Á. (B) Similarly, the convex hull of B BU B forms polytope PB that has exactly t + k vertices.
vertices. Equiva-
(p3) We have 0 E (Pa( and 0 E int(Pp).
(p4) There exists constant 3 E (0, 1) such that
(A) For any a E A, Ba lies on facet P B. We denote this facet by Sn(a).
5

---

Published as a conference paper at ICLR 2020
(B) For any b B, B,gb lies a facet PA. We denote this facet by Sa(b).
(p5) (A) For any a E A, (p(a) is (d 1) dimeenniil simplex.
(B) For any b B, (b) is (d 1) dimennsoonal simplex.
(p6) (A) For any E A, there exist scalars o1,...,,0.. E (0, 1) such that Ei= (;8((a). where 81 (i(a)..... 8a(a) are the vertices of simplex SB (B)
(B) For any E B. there exist scalars oi....., Odd E (0. 1) such that b En (4s;(b), where s1 (b)...... (().......)) sa(b) are the vertices of simplex Sb(
(p7) (A) For any pair a and a' of distinct points in A, we have Sy(a) F SB(a'). Moreover, letting Ha the hyperplane that contains Sn(a), a and a" lie on opposite sides of Ha. for all o" E AU A with a" + #a
(B) For any pair b and d' of distinct points in B, we have Sa(b) # SA(B). Moreover, letting Ho be the hyperplane that contains (b(b), b and D" lie opposite sides of Ho. for all D" E BBB with V" b.
(p8) Consider 21. 21 matrix M whose rows and columns are associated points p EAUB and E AUB, B, and whose entries are as follows
[d(p, Hy), (0
p= OR p E and q E B, OR p E B and q E A,
Mpg
(3)
otherwise,
where Hg 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
involves the same 3 for all points in A U B. In fact, elimination of Property (p4) gives rise to trivial configurations.
In the two dimensional space, for any 2 4 there exists (2, t, 0) configgurratinn of the form illustrated the following proposition, we generalize this observation to higher dimensions.
Fig. 2
Proposition 1. For any d > 2 and 2 4, there exists (d, d 2)-configuration.
The proof is constructive, and given Appendix configurations.
We conjecture that there also exist (d, t, 0)-
Conjecture 2. For any 2 2 and t 2 2d, there exists a (d, t, 0) -)ccoofiguration.
Remark 1. Using configuration given by Conjecture Senettureeeiisteeeee instead of the configuration from Proposi- tion 7 in the construction and the proof that follow, we obtain a proof for Conjecture 7 In this view,
establishing Conjecture would also resolve Conjecturel 7
4.3 CONSTRUCTING A LANDSCAPE WITH CUPPED MINIMA
Here we present set of training data (X1,y1;; v1).......,. .X........(... and a set of wights (wi, vi),..., (Wm, Um) such that the empirical loss surface corresponding to (X1.31)..... ........ (Xn Da) has a sub-optimal cupped minimum at (W1, vI),.... (Wm Um)). Without loss of generality, we assume 2d 2. Extension to larger values of straightforward via replication.
Let (4, B, B) be (d 1. m 3) conffiguration in the (d - 1)-dimensional space, as let 6g 0 be such that PA and Pg contain the eg-
in Proposition I In view of Property (p3) neighborhood of 0. Let
1 60
Σ
al
+
Σ
b1]
+ + 3
G
BEBU B
We proceed by introducing the data points
X
X,, An illustration of these data points in the
three dimensional space is shown in Fig.
Pc.g., for A and À chosen uniformly random over the unit sphere, and letting (B, B) be small rotation of
(A, A) around an arbitrary axis, it is not difficult to see that all properties except (p4) would be satisfied with high probability.

---

Published as a conference paper at ICLR 2020
XA
XA*
Xa
X
X p*
Xg
Figure 2: A (2, conofiigurrai with = 8. The blue dots show the points in A and red crosses are the points in B.
Figure 3: Illustration of data points
Xi,..., Xn for and m 12.
Data points X: We consider total number of = m 2d data points as follows.
For each a E AU Å, we consider new data point X, follows. Let [21 ,.,,...; ; RR be the representation of a in the Cartesian coordinates. We let X, = (2,,... 2d-1, 1].
For each b E B BUB B, we consider new data point X, as follows. Let [Z]...., 2d Rd-1 be the representation of b in the Cartesian coordinates. We let Xo = [2,,..,, 7d-1, 1].
We consider two extra points XAI, XA XBI, and XB as follows. We XA Eud
x - -Eud, and
XAI A
XA
Σ
Xa + (1/3 1)ud
(5)
aE AEAUA Ā
XB+ A XB-
Σ
Xb (1/3 1)us
(6)
BEBU
B
where ua respectively.
[0,....00 11T, and & and B defined in equation and Property
(p4)
Weights cupped minimum: We associate each of m neurons to point p in AU B, in one-one manner; and denote the vector of input weights and the output weight of that neuron by wp and Up. respectively. These weights are chosen follows:
For each E A, we let -1/ym.
For each e B, we let Uh = 1/vm.
For each
A, consider the facet Sp(a) defined in Property (p4) and let
$1 si. (a-1(a) be the vertices of SB(a) (as in Property (p6). We let wa be the unique vector such that [| and
w
T X (1) 0,
i i= i=.,..,,
T ud 0.
(8)
For each b B, consider the facet (b) and let (b). .... sa-1(b) be the vertices of (b))..
We let wh be the unique vector such that || = and
Ih (x.()) 0, i 1, 1,...,d d 1,
w uu > 0.
(10)
Labels y: Having determined the data points X and the weights (w, u), the output (w, v) of the network is determined for all input X. In the following, we choose the true labels y to obtain desired error ÿ y for each input data. In particular:
7

---

Published as a conference paper at ICLR 2020
For each AUA, associate to Xa label yo that ca _ (w yo 1.
For each BU we associate to X, label yb so that es - so(w, v) ybb
We choose the labels associated to XA+. Xa-, X and x-- such that CA+ e 1 and 6A-
This completes the description of the training set. As shown in Soudry and Carmon (2016), there exist weights that achieve zero loss if m > 4 ///2(2d - 2) In our case, n = m 2d 2. and its easy to check that m > 4 (m + 2d 22d - 2)] for all d 2 and m 2 8 8 + 3/3 - 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. we scale down the inputs such that ||ll < 11//m.fo for = 1,... n. and modify the corresponding labels y: such that e, remains unchanged, then a same set of weights will still be cupped minimum for the landscape defined in terms of new (X,, ya) 's. Moreover, for this setting, it is easy to check that
||w 1, |ea/l 1, and lyil
4.4
PROVING THE CUPPED MINIMA PROPERTY
Let
| X,l
e min
w x: + 0, r 1...., m, i 1, I....,,7!
(11)
|X,||
Then, For any E mmd with ||0]| = and for any t [0, 8). let
Fa(t) F(w + 0t, v).
(12)
We show that there is an > 0 such that for any unit-norm and any E [0, 6].
(t 2 (o +
(13)
Lemma 2. For any E gnd with ||]| 1, Fo(-) is a quadratic and convex function over [0, 6].
The proof is give in Appendix Dad relies on the fact that neuron activations do not alter + At for t E [0, 6). Consider now the following m-dimennional subspace of Rd
on
H
a1 oi,,..,, Om E R
(14)
O'm Om
For any inndd let @ll and 0- be the orthogonal projections of on Hw and H respectively. Then, 9 = اlو + 8+_ In order to establish equation we need lower bounds on (0) and Fø' which derive in the next two lemmas.
Lemma 3. There exists μ > 0 such that for any 0 E IRand with ||O|| = 1, we have
(FF
2 11|0+|||
(15)
d+i
1=
The proof is given in Appendix E and relies in subtle way the choice of data points in subsection 4.3 We now bound the curvature of Fg.
Lemma 4. There exist constants mı, 722 > 0 such that for any mnd with ||ll| 1, and for any e (0,
d Fo d12
> max (2mllo 1|2 20 11, o).
(16)
The proof is given in Appendix F and relies on Property (p8) of the underlying configuration.
Consider now the second order polynomial p(æ) 77 6(1 x²)
d2 jaz. where μ,, 7/1 and 7/2
are the constants in Lemmas 3 root in the interval (0, 1). which denote by Zg. Let
and Since p(0) > 0 and p(1) < O. the polynomial has exactly one
c A p 8
(17)
8

---

Published as a conference paper at ICLR 2020
Lemma 5. For any A E Rnd with ||0]| 1, and any E [0, 6). we have Fo(t) Fo + et.
This lemma is simple consequence of Lemmas and I 4 and its proof is given in Appendix G It
follows from Lemma 5 for any w' in the d-neighborhood of w. we have F(w', u) 2 F(w,
ellw' w|l?. This shows that w is cupped minimum for F(.,)), and completes the proof of Theorem
5 DISCUSSION
The guaranteed existence of descent paths in shallow networks of ReLU neurons was previously established (Venturi et al., 2018), given an over-paramettrizzaion of m 2 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 2 2n/d) (Soudry and Hoffer 2017), D. but the existence of descent paths was in question. In this work, we have tightened this
uncertaunty gap to n 2d + 2 < m < n, by proving that for any m S. n 2d + 2, there are input data and initial weights for which descent path does not exist. This conclusion we reach by establishing the existence of cupped minima for m S 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 of over- paareeerrrtriiiioonnnn required for elimination of sub-optimal cupped minima in ReLU networks is much higher than that of networks with quadratic activation functions, R /2n (uu and Lee 2018), and linear activation functions, m Rs n/d (Kawaguchi 2016). and is almost as high as general continuous activation functions of any form, S n2 (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 casier to analyze and also help study the SGD dynamics. On the other hand, from a practical view, convergence of SGD in oocl-mii-frre landscapes is well-studied.
Aside from addressing Conjecture 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- parameterizaaion. In particular, we showed in Corollary [ 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 step toward this goal, one might characterize the true over- over- wver-parameterization regime in which the basins of poor local minima have considerabl volume.
Among other directions are extensions of our results deep ReLU networks, shallow non-ReLU networks, and shallow ReL.U networks under loss functions more general than the squared loss.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint ArXiv:I881.0338 2018.
Anna Choromanska, Yann LeCun, and Gérard Ben Arous. Open problem: The landscape of the loss
surfaces of multilayer networks. Conference on Learning Theory, pages 1756-1760, 2015.
Simon S Du and Jason D Lee. On the power of over wer-parramttiization in neural networks with quadratic activation. arXiv preprint 18 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizee neural networks. arXiv preprint urXiv: 2018.
Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: /6/ 1.15400, 2016.

---

Published as a conference paper at ICLR 2020
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. Conference on Learning Theory, pages 797-842, 2015.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1724-1732. JMLR. org, 2017.
Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594, 2016.
Jason D Lee, Max Simchowitz. Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference learning theory, pages 1246-1257, 2016.
Dawei Li, Tian Ding, and Ruoyu Sun. piee-parameterized deep neural networks have strict local
minima for any continuous activations. arXiv preprint arXiv: 2018.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Proceedings of the 34th International Conference on Machine Learning- Scarning-Volume 70, pages 2603-2612. JMLR. org, 2017.
Itay Safran and Ohad Shamir. On the quality of the initial basin in overspecified neural networks. In International Conference on Machine Learning, pages 774-782, 2016.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. arXiv preprint arXiv: 1712.08968, 2017.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2),742-766, 2019.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint 20XX::66050088000 2016.
Daniel Soudry and Elad Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural networks. arXiv preprint 1rXiv:1702.05777 2017.
Luca Venturi, Afonso S Bandeira, and Joan Bruma. Spurious valleys in two-layer neural network optimization landscapes. arXiv preprint arXiv: 1802.06800.6384 2018.
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. arXiv preprint ar arXiv:1611.03131 2016.
10

---

Published as a conference paper at ICLR 2020
APPENDICES
A DIFFERENT TYPES OF CUPPED MINIMA IN TERMS OF DIFFERENTIABLLTTY
Here we discuss different types of cupped minima and provide elementary intuitions on the loss landscape at cupped minima.
We first characterize curvature of the loss function at differentiable points. For r ro =1..... m, let Jr be diagonal matrix whose (i, i) entry equals 1 (w X, 0). Let G' be md matrix of the form:
G = v1J1X
Um J X
(18)
where X is d x n matrix that has X; in its i-th column. V Fw, v) = GT [ei..... Cm] where e; = y yi is the output error for input X,. Moreover, if F is differentiable at (w, v), its Hessian with respect to w equals
differentiable at (w, v), its gradient
F=F(,,) G.G.
(19)
We classify cupped minima into three categories in terms of differentiability. Specifically, for cupped minimum w of F(-, v), we consider three cases:
Type 1) F is differentiable at w.
Type 2) F(w + 0t, function of is non-differentiable at = 0, for all 0 E RRdd.
Type 3) is non-differentiable at O.
There are 01,02 02 E mm such that F(w++11, v) is differentiable at / = 0, while F(w+022, v)
Fig. 4 illlustrates examples of loss surface the above three types of cupped minima. We now argue that the first two types are not possible in the loss landscape of shallow networks.
v) is differentiable at w, Hessian given equation 19 equals Gº G. Since G an n x md matrix, assuming md >> G G would have zero eigenvalues. Therefore, cannot be cupped minimum of F)) It follows that there exists no differentiable cupped minimum (nor saddle point) if md >
For non-differentiable points, note that F(w- + wt, v) as a function of is a differentiable quadratic function. This is because the output scales proportionally with Therefore, cupped minima of the second type are not possible, as well. In the same spirit, can be shown that F(w + 0t, v) is differentiable as a function of if E Rund belongs to the dimensional subspace H., defined in equation 14
For the above reasons, all cupped minima, if any, are of the third type. Therefore in the construction of Subsection 4.3 we introduce a training set and a pair of weights (w, v) such that w is a cupped minimum of F.. v). and F'ww Ot, v) is differentiable only for H..
B PROOF OF LEMMA
v has a zero entry, e = 0 for some r, then F(.,v) a constant function with respect to wy, and thereby has cupped minima. Therefore, we assume that has zero entries. Let
to inf {t 3r, v, (1) 0}.
For >> O, we define
(1)/vil wi wi(
@(t)
(20)
Im (1) [/ml (f)/mm)
x wmm (1)
Let
inf (() + w)
11

---

Published as a conference paper at ICLR 2020
(a) Type
(b) Type 2
(c) Type 3
Figure 4: Different types of cupped minima in terms of differentiability. discussed in Appendix A
We show that 1 to- to < co, then continuity of v(t) implies that e, (to) 0, for some r S m. Therefore, w. (fo) # wy. It then follows from the continuity of (i-(-) that there is an >> 0 such that (to c) + wy. Consequently, 1 < tu-
The inequality t < to implies that there is an >> 0 such that ūū, + e) of w, and for any e [0, 4 + c), we have sgn(u, (t)) = sgn(e,), r 1,.... m. Therefore, for any E [0, 1 + c). we have F()(t), = (ww(),, v()). Since w is a cupped minimum of F(., v), there is an E [ti, + cl such that (t) > F(w, v). This shows that (w(t), e(t) cannot be descent path for F(.,). and completes the proof of Lemma] [
C PROOF OF PROPOSITION
For i = ...... d, let
1
G
(21)
1 1 cos( (1
Fix constant
i 2 cos( (l)
+ 2 cos(( (T/1)
8 II
11 c:)
II 2=3
(22)
i + 2 cOs(TT/)
2 2 cos 1T (t/))
2=3
Let y be uniform random variable
? unif cOs(sT/)) cos cos(22/t))
cos(x/t) (2 /t)
(23)
4č
2č
We take sample from the above distribution and fix y for the rest of the proof.
We now introduce the points in the configuration. For i O....,t 1, we consider points at E A and b' B as follows
2nT(i - 1/2)
2T - 1/2)
a²
cos
sin
703, YC4. YaCd
(24)
1
2mi
2Ti
b²
cos
sin
-703, -74..... YaCo
(25)
For i = ....., d, we consider points ăt E Á and E B as follows
0, O,...,0, 0, 1.c44....,,cd
(26)
i-1
J = 0 O,..., 0, G4+1, -.tt,,....,
(27)
i-1
Fig. 5 shows an illustration of these points for d = 3.
We proceed by verifying Properties (pl) (p8)
Property (p1) Property (pl) is straightforward from the above construction.
Property (p2); Considering only the first two coordinates, is easy that no point of A is
convex combination of other points in A U Å. Also note that for -.. d, ät is the only point
12

---

Published as a conference paper at ICLR 2020
B
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 UUA Å and the blue dots correspond to the points in B BUB. B.
in AUA whose i-th entry is negative, Therefore, no point in À can be represented as convex combination of other points in AUA. A. A similar argument works for Part (B) of Property (p2)
Property p3) Let
== l....,t, à; (cs + +)
a; =
(28)
y
(G-1 1)c,
i= i= .....d d.
(29)
A simple induction shows that
0j
- 1.
(30)
Cj
1=3
for j = 4,...,d d. We show that
d
aqa" + Σ im3
=
0.
(31)
E a; + Ei αi
For the first two coordinates, equation respectively. For the j-th coordinate, j ... d, we then have
31 is easy. Let o² and àj be the j-th entries of a' and ă'
t-1
Σ
a,a
Σ 1=3
ag = tx
x 7oj
+
Cj
ā
āj
by
1=0
1=3
āj - 1) āj
= ej + cj
0,
where the second equality is due to equation 30 This establishes equation 31 It then follows from equation 31 that 0 is convex combination of points in AU Á. Consequently, E int(PA). A similar argument shows that E int(Pp).
Properties (p4) (p)) We only prove Part (B) for each of these properties; similar proofs work also for Part (A) s. Moreover, because of the rotational symmetry of and B in the first two coordinates, it suffices to prove of the Properties (p4) (p4) (p7) only for 80.
13

---

Published as a conference paper at ICLR 2020
Properties (p4) and (p5)
For the j-th coordinate, j -3...,, we have
1-1
of + aj +
a = 7yy + +70 +
Σ
-7
1=3
1=3
>((j - 1)cg -1)
(j j 1 + 2 cosl (T//t) -1)
(32)
- 27 cos((T (T//T)
1 + 2 (To(st/t)
- -(2 cos((T/T/) ycj
cOs( /t) bJ.
where 69 is the j-th entry of 6d defined in equation 25 Similarly, for the first two coordinates, have:
d
ai + dj + 7
dj
cos(Ttt) + cos(TT/) = 2 cos(TT/)) 6t.
1=3
(33)
d
2 + 0 +
0
sin(x/t) sin (T/t) = 0 2 cos( (OS((T/) (T/t) 62.
1=3
It then follows from equation
32 and equation 33 that
c (a'a' +
60
Σ δz
(34)
2 (TT(Tt/t)
1=3
Let
8 A 2c0s(T//)
(35)
(d 2)7 +
Then, from equation 34
36
(d> a + a
7
(36)
1=3
Therefore, (319 is convex combination of a., a= _a3 ...., ad and therefore lies on the simplex S that has a², at, _,, ,,a,,..,, ad its vertices. Next, we show that facet of PA
Consider vector Idd with entries
(2 1) cOs(T//) ,
21
42 O,
d
(37)
2; II j=it1
(cj + 1),
i= 3= 1,
2d -1
Then, simple backward induction, with base case d, shows that for 3....,d d, have Ed Ej Cj3j = 24 + In the same vein,
G2j = - 1.
(38)
3=3
follows that for = 3....,d d,
Taa
Σ
2jCj
2,
(39)
j=it1
14

---

Published as a conference paper at ICLR 2020
Moreover, for i 0, 1,
z a' Σ
2370 + 21 cos(a/t) j=3
- + 1) + 21 cos((10))))00 (T/()
(40)
-7 1) + 11-1)7 +1
cos(TT/)
cos(TT/)
1,
where the second equality is due to equation 38 Let H. be the hyperplane that passes through a",a', a², ,....'" a.. It follows from equation 39 and equation 40 that for any p {a a' a² ,..., a we have 2" p = Therefore, z is orthogonal to H. Consequently,
H. = {x E Rd
2 =x==}
(41)
For ,,..., 1, we have
TTa x" 2T(a' d²) + =Taa
= I 2T(a' - a +
(42)
= 21 coss(2 1/2)/t) - cos(z/t)) +
1,
where the second equality is due to equation 40 and the inequality is because 21 > 0 and cos (
1/2)/t) cos( T /t) < 0. It follows from equation 41 and equation 42 that all points of A fa a
lie on one side of H. while all points of Å Uaa } lie on H. Then, H. is tangent hyperplane to
PA. Thus, the simplex is facet of PA. This completes the proofs of Properties (p4) and (p5) Moreover, from the definition Hs Property (p7) have
Hgo H.
(43)
Property (p6); Since 2 4, we have cos(x//2 > 1. Moreover, recall from equation 23 that y < 1. Property (p6) then follows from equation 34 and the fact that S is facet of P..
Property p7) For O.....t- 1,
2 bi = = - + at
21( cos((2rit)) - cos(*/t)) - - 2yyc +
(44)
3=3
21 coss(22i/1) cos( / (1) 2-(ē - 1) + 1.
and definitions of a" and b², and the third equality is where the second equality is due to equation 40 and from equation 38 follows that
-T60 21 (1 - (TT(t))) + 1
(45)
where the inequality is because the first two terms the left hand side of the inequality are positive. In the same vein, for = 1, 1,...,t 1
bT
21 (2tott2tt/) cos(TT/t) + 2x(2 - 1) + 1
2 ( cos((2T) (2TT/) coS(TT/t) + 27ē + 1
( (cos(20T/t) /t) cos( + 24ē + 1
(46)
(cos(2(T/) /t) cos(TT/)) + (cos(TT()) - cos((27/)) /t) +
where the second inequality follows from the definition of 21 in equation 37 and the fact that 21 1, and the third inequality is from the definition of r in equation 23 and the fact that 2- S
15

---

Published as a conference paper at ICLR 2020
cos(sT/t) (2T/t). It then follows from equation 41 lie on opposite sides of H. for = 1....,t -1.
equation 45 and equation 46 that 6 and B
On the other hand, since D' -', for 3, ..... d, follows from equation 39 that z²6 -² = -1 < Therefore, for = 1,.... 3, b' and 6 lie on opposite sides of H. This completes the proof of Property (p7)
Property (p8) We have
d(b", Haa)
|=|| (2 -1)
1
(1 cos(TT/t) + 2-(0 1)
(47)
|||||
21 (1 -
cos((t()) (o_co)
+ 2(ē 111
2(2-11)
|
21
where the first equality is due equation the equality equation 45 Similarly, from equation 42 we have for = O,....t
43 and equation 41 and the second equality follows from
1 (==aa== -1-
d(a',Hoo) Hoo)
||
(48)
cos (2T(i (i- 1/2)/t) cos(TT/t))
|||||
For j E (0.....,t-) 1), let mag & cos - j + 1/2)/t) cos(T//). (T).. Then, it follows from equation 48 and rotational symmetry of A and B in the first two coordinates that for i,j E (0....,. 1).
cos(IT /t) and my: - cos (2n(i-
d(a', aa, Hos) =
21 mar |=|||
d(b', Has)
21 |||||
my .ss.
(49)
Note that for any p,q AUB, B, mp.a is constant independent of the value of Let AM be 2t 2t matrix, with entries
cos(s/t),
if p= g. if E A and q B, OR p B and A. otherwise,
Mpg
mp...
(50)
0,
for p.q E AUB. Then, all entries of M are constants independent of Let , Sex be the
eigenvalues of m.. It follows that , A2t also constants independent of 7-
Consider the matrix M defined in equation B any p.q AUB, B,
It follows from equation 47 and equation 49 that for
2 2,2 1)). ((c-1)) |=]l (1 cos((t/t))
if p=
21
Mpg
[ mpp97
Z1
if P A and g E B, OR p B and q A, otherwise.
0,
(51)
Consider the order (a...... .d.,,.... a'=1 (a'....a'-l. a'.......... on the elements of A.B. Then,
M
21
M
2 2(2 - 1)7)
21 | ( (Ar
2(č 2(ē- 1) 2)
1):
(52)
|>||
21
غ 2-1+1/7
where 7 is the 2/ 2/ identity matrix and the second equality is from the definition of 21 in equation Denote the eigenvalues M by X1 >i,..., Aze. Then, from elementary linear algebra,
37
p.....,ay.
21 |
2(2 - 1) cos(s//)) T/1)
A
(53)
غ ट- 1-1+11 1 1/7
for 1..... Therefore, there is most one value of y for which X; Then, in view of equation 23 we have Pr(A; 0) 0. over the random choice of y. Thus, with probability one, M has no zero eigenvalues and thereby full-rank. As an immediate consequence, .M full-rank for suitable choice of y. This establishes Property (p8)land and completes the proof of Proposition [
16

---

Published as a conference paper at ICLR 2020
D
PROOF OF LEMMA 2
Consider a block representation as follows
01
0 =
(54)
On
where each 0, a d-dimensional vector.
It follows from the definition of å that for any E (0, 8), if , X; > 0, then (w, 0,t) > 0;
and if _ X; < O, then (w, + +,t)) 0. Therefore, for r 1,.... m and i == 1..... n2 and for any E [0.8).
1( + 0, X; 2 0) (w x; 0) + 1 ( x = 0, 8 20)
(55)
Consequently, for any / E [0, and i ,,..., we have
w + v) = Σ Ur (w X; + 10 X:) 1( (w,, + 0,
(56)
m
= Σ Uy [w 2 X; x.) (1( > 0) + 1, 0, 2)).
It follows that ūe( 0t, is linear function of t over the interval t [0, Therefore, (t)
E (0:(w + v) y4 is quadratic and convex function of t, for t [0,
E PROOF OF LEMMA 3
We first characterize active neurons for different inputs. For two subsets S1, S2 C R2d we let
S VS, = S1 n St. Recall the definition of s;(a) and (b( from Property (p6)
Claim 1. For any a E A. we have
w X (a)
== L=
(57)
w Xg > 0,
(58)
T X6 > 0, W a
be (B \
(59)
I' w Xx+ > 0,
(60)
/ I XB-
(61)
w X O,
(62)
w XAA < 0,
(63)
w Xx < 0,
d'e (AU Ma}.
(64)
Similarly, for any E B, we have
w X (b) 0,
i == 1= I....,d d-1, 1,
(65)
w T X₂ 0,
(66)
w X, 0,
a (AUA) \ (0,10),.....1110)
(67)
w X 0,
(68)
w X'X > 0,
(69)
T "Xp: < 0,
(70)
T w "x 0,
(71)
T w Xy 0,
8' [ (BUB) ((6).
(72)
17

---

Published as a conference paper at ICLR 2020
Proof of Claim 1 Fix a b E B. We begin by introducing some notations. Let 7/ be the (d 2) dimensional hyperplane in the (d di-dimensi space that passes through $1 (b).... Sd sd- (b). In the same spirit, let H be the (d 1) -iiimensioa subspace the d-dimensional space that passes through X.., Na- equivalently H is the subspace orthogonal to wh. We denote the convex hull of (b)) ...,)) (b) by CB - Conv (( X.
(.. (t))) Similarly, we let Q^ - conv ({ Xx a E A)A and 2B Conv (f X E BUBB).
Before presenting the proofs of properties equation 57 equation 72 we review make some easy observations. Recall the definition of En from the paragraph proceeding equation 4 Let B be the intersection the eg-ball centered O with the orthogonal space of us. Then, from the definition of we have
5% + udd C QA.
B
C QB.
773)
For E Rd, let (Ix) be the projection of æ on the span of first coordinates, i.e. the orthogonal space of ug. Then,
K (xx)))
IEnEAUa(Xa -
5 + 1/3
E 1/3 - |ErEAUA
E 5+1/3 -n 1
E E all 5-n n
(74)
EaEAU
E all/co
60
where the first equality is from the definition of XA+ and the second inequality follows from the definition of & in equation Therefore, x(Xa-)/(E + 1/3 n 1) E Bd-1, Consequently,
7(A++)
(uTXA+) )
XA+ = ++ 1/B -
+
+ 1/8
5 -
(Xx+))
(5+1/8 -1)ud
& 1/3 - 12
+ 1/3 - n -
(75)
T(X+t)
+ Ud
& -
E Bd-1 + Udd
QA
where the first equality is orthogonal decomposition of Xx-, and last inclusion follows from equa- tion 73 In the same vein, we can show that
XB- E QA- + 5+n+1-1/8 1/8
(76)
We proceed verify equation 65 equation 72 Eq. equation (65 follows from equation 9 Recall the definitions XA Eua and X -uua Then, equation I0 implies equation 69 and equation 71
Since (e)())..... (0. define boundary of the (d 1)-dimensional convex set Qa. and H passes through (b) X ( then all points QA lie on a same side of H. In other words, either we have wo. x 2 0, for all x E ex: or we have w/. x < 0. for all x E Q In view of Property (p3). ua E (Qx). It then follows from equation 10 that for any QA. have
18

---

Published as a conference paper at ICLR 2020
w/ 2 0. Consequently, for any QA\H, we have w > 0. In particular,
EE (AUAA) Moi((),..... ................................ ................................ (6)),
w X. > 0, wh X > 0,
Wh XB+ > 0,
where the first inequality is because Property
(p5) implies that X. (AUA) (b), (a) and the last two inequalities are due equation 75 and equa-
for a
tion 76 respectively. This establishes equation 67 equation 68 and equation 70
For equation 66) it follows from Property (p4) that b and the origin, lie on opposite sides of hyperplane H. Consequently, -X, and uy also lie on opposite sides of hyperplane H. Therefore, wf' X6 and w Un have same sing. It then follows from equation 10 that wi Xb. > O, and equation 66 follows.
For equation 72 it follows from Property (p7) that for any b' E BU B with V' + b. X, and Xy lie
on opposite sides of H.. Eq. equation 66 then implies that wi X < O. This establishes equation 72
and completes the proof of Claim I
In light of Claim it is easy for 1,..., and i l.... that if u X, 0, then
0,C
Vm
In our next claim, we examine linear combination of data points for which particular neuron is active.
Claim 2. For I..... m, there exist constants T. ......... Vin such that
n
Σ Tax 0) + Σ ex X, > 0) =
(78)
Proof of Claim Claim that
ai B. We prove the claim for the neuron associated to follows from
n
Σ exx,1 (x,,, 0) ebNo +
Σ
coXa + CA+XAt + CA-XA-
aE(AUA)) (1.0))...6-110000
=-66 +
Σ
Xa + (XA+ (AA-)
aE(AU ADV ( (1((0)
= +
Σ
Xa
Σ TEAUA
Xa (1/3 1) ud
aE(AU (1(())...,G6-1(()))
d-1
= =- Σ
X..0)) + (1/3 - 1
(79)
where the second equality is due the definitions of cas eb CA+, and CA-, and the third equality is from the definitions of X in equation 5
On the other hand, it follows from Property (p6) that there exist scalars a ag (0, 1) such that
b = I (b). Therefore, from the definition of X
d-1
-(Xo + ud) = Σe as (X,,()) - ud)
(80)
i=1
19

---

Published as a conference paper at ICLR 2020
Moreover, Property (p4) implies that EES as 1/B. Then, from equation 80
d-1 -Xb = Σ
d-1
d-1
Σ a
1
Ud Σ
o aiXai
(1/B 1) und
(81)
t=1
For i = 1 1,....d d
let 7/2 Ozj. Then, Claim implies that
12
d-1
Σ
neXx1(w x;-,, =0
Σ ne.Xs.0))
_ (1 0: x.,())
(82)
(0) Σ
ai Xix)
i=1
1
Σ (b) + Xb
-
Udd
where last equality due to equation 8T] Combing equation 79] equation 82 we obtain equation 78
for Wi w/. A similar argument implies equation 78 for we Wap a E A. This completes the proof of Claim
Back to the proof of Lemma 3 for 1,...,m. m, let
G, min
min (1t (1 x())),
(83)
for the constant Yf defined in Claim It follows that e,, 0, for 1,..., m.
For any r < m, (r,(r)..... X (r) are linearly independent and, by definition, are all orthogonal to Wy, Therefore, there exists a constant e, > 0 such that for any Ed with ||G/|| 1. have max |,, (r)) 2 & where 5,- is the projection of G, on the null-space of w,. Consequently, for any Gr E Rdd with ||< 1,
1
x 1 W X; 0) > 1
max
In particular, considering the block-vector representation of 0 in equation 54 we obtain for 1 I....,m, m,
max E
10"x,,
1 X; 0) > max 4,10
(84)
20

---

Published as a conference paper at ICLR 2020
Let μ _ min, G,// Then, μ > 0. It then follows from Claim that, for ,....,m..
l X 10 X; 0, 07 x, 0) 24 Σ
X 10 x;>
20) 0)
c X;1 W X; = 0, x 20) - 2r
Ye X (w =0)
e X [10 x, x(uf
2/-
1
0f (1 2 0) - (w, =0)
Vm
(85)
1
x [10,,x, > 0) -w' X, = 0)
1
Σ
10 1 (,,
t=1
Ey
X 1 1w, 0)
max
i=!...
1-10-11
1 110
where the third equality due to equation 77 the fourth equality because 0% X; and 1 X, > 0) - of have always the same sign, the first ineuuliit is by definition of 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 iiplies that
dFo(t)
lim E00
Σ O
Σ
(x, 20)
d+b
1==
0 eex,
0, +1 x0) 20)
0.0 X, + &0 Σ Se (x,,, 20)
1=1
# ||,
M II
(86)
where the second equality is due to equation 55 and the first inequality follows from equation This completes the proof of Lemma 3
85
F PROOF OF LEMMA 4
We begin by a claim. Given a q E U, recall the definition of hyperplane H.y from Property (p7)
Claim 3. For any pair of points p. E AUB, we have
W Xpl = V1+ d(0, Hop
d(p, H.g)
(87)
21

---

Published as a conference paper at ICLR 2020
Proof of Claim 3 In the (d - 1) dimensional space, let be the unit normal vector of Mq- Recall
from Property p6) that $1 (9). ................................ Sd-1 (9) are located on Hg. Let,
w s1(4) d(0, Hq).
(88)
Then,
d(p, Hyg = IW" 7|.
(89)
Without loss of generality suppose that q E A. Let ã be the lifting of w from the (d - di-dimensional space the d-dimensional space by appending w new coordinate with coefficient, i.e., @ is a d-dimensional vector with W = wi, for = l,..., d 1, and wa O. For y defined in equation 88
let
+ 72 (o -Wud)-
(90)
Then, we have ||||| = 1 and zuua ua < O. Moreover, for = I,..., d -11, 1,
27 Xx((a)
+1+ Nw7 (w (x((1) uuu (.:(w)
(-w" (i(() uu
v1 + 72
(91)
(-7+ +
v + 72
= 0,
where the second equality is because (g) E B BUB for 9 E A. It follows from equation 91 and the definition of Wg in equation 7 and equation g that wa 2. Therefore,
T Xpl
= |: Xpp
9
33 Xp - yul Xpl
V1 + 72
wp'' - -uus unl
V1 + 72
(92)
WTP 71
V1 + 72
d(p. H,y,
V1 + d(0, Hz
90 and the last equality is due to equation 88 and equation 89 This completes the proof of Claim
where the second equality is from the definition of in equation
We now proceed to the proof of Lemma Fix an arbitrary 0 E Rd with ||0|| 1. Without loss
of generality" assume that F(.-)) is differentiable (w + 50/2, v). For l,..., m. let J, be diagonal matrix whose (i, i) entry, for 1, 1,...., n, equals
1(w, + 0, X; 2 0)
1(w x; > 0)
= =, 20)) 0).
(93)
where the equality is due to equation
55 Recall the definition of matrix equation 18
G viJiXT .... Um m XT
(94)
Then, for any E (0,8),
d Fo
d + t0, v)
0t Ve Fl +0,,0) of o ||GO|
(95)
di2
d12
'This is because otherwise. (w + 50/2, v) is the limit point of a sequence of weights at which F is differentiable. Since arguments carry over to the weights in this sequence, we conclude that all bounds also apply to their limit point, (w + 50/2,
22

---

Published as a conference paper at ICLR 2020
where the third equality is due equation 19 On the other hand, since @ll 600, have
GI
Goll + GO-.
(96)
In the following claim, we elaborate on ||G0 ||.
Claim 4. There exists constant yn >> 0 such that ||GO 1|2 2m 100 for all 0 E Rd.
Proof of Claim Recall that 0ll is the projection of 0 subspace H, defined in equation 14 Then, there exist constants 01 Oy such that
01 W1
All
(97)
Omm Wm
Let be the vector representation of a
Om Then,
||@l||2
a Σ af ||a||
1wil2
(98)
Consider the matrix
G =
01 J1 J
W1
...
Um Jm X2" X-
Wim
(99)
Then, from the definition of matrix in equation 18
Cn W1
Goll
U1 ... Um Jm
=
Omm W/
(100)
= = W1 .... Um X Wm
= Ga.
Each column of & corresponds to a neuron, and thereby associated to a point in A AUB B. In the same vein, every row of G is associated to an input vector. By removing some rows G, we devise a matrix M so that each row of A is associated to an input X, for p E A AUB. Therefore, M an m x m matrix, whose rows and columns are associated to the points in AU B. It follows that Ma is vector obtained by removing some entries from vector Ga. As result,
||a
||Gai]|-
(101)
In the following, we capitalize on Property (p8) to show that M is full-rank.
For q AU let
Uq
+ d(0, Hgg
For p.q E AU B, the entry in row p and column g of M equals
Mpg
Gpg Ui XxX We 1 (w/ T X, > 0) + 1m X, 00 xx 2 2))
Ng w.y 1 (wig Xp 0)
(102)
d(p, H.) ( x, 0)
VT+ d(0 H.y
7i dlp, Hl,))
w X, 0).
where the first equality is from the definition of M. the second equality follows from the definitions
of G and Jg in equation 19 and equation 93 the third equality is because X w. 1 (w: X, = 0) 0. and the fourth equality is due to Claim 3 Then, Claim | implies that for any p. q E A AUB,
Th d(p, Hy), if p = 4, OR p A and q B, OR p B and g E A, otherwise.
Map
(103)
0,
23

---

Published as a conference paper at ICLR 2020
Compared matrix M defined in equation B each column of M equals the column q of M multiplied by non-zero constant "N.- 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,
||Ma|| 2 o||||||
(104)
Then,
|| - |/aoll 2
|Ma] 2
=
(105)
where the equations are due to equation 100 equation 101 Claim then follows for 7/1 = o²/ /2.
equation 104 and equation 98 respectively.
Back to the proof of Lemma Then,
we denote by max the largest singular value of G. Let 1/2 2 o
||@0|
|GBll
+ G0 1
|| + ||GBL|22 - ((Gol))) (GO+)
||
2||G0||| x ||GO'1
||
max
||@|||| Tmax |
(106)
|
20 max
||01||
|G 2022
||
2 2m ||00| 1|2
20/110~11 I1.
where the second inequality is from the definition of maxx the third inequality because ||o |||| 1, the last equality is by the definition of and the last inequality follows from Claim 4
This completes the proof of Lemma
G PROOF OF LEMMA 5
Fix a E Red with ||||| = 1. Recall the definition of so from the paragraph proceeding equation 17 If ||0d To. then for any E [0, 8].
(t( Fo( z OO)
u1 |t
uoot
2 et²,
where the first inequality is from convexity of Fg in Lemma 2 the second inequality is due to
Lemma the equality is by the definition of e in equation 17 and the last inequality is because t 8.
On the other hand, if ||0-1 || < zo. then for any t [0,5].
1
Et) Fo(0)
(0)t + 2 F
2 Fd t²
(1llol111 -1-11110011)
(m - -10--12) - malll=1) I)
(m =²6) - -22
6
et?
24

---

Published as a conference paper at ICLR 2020
where the first equality is because Fø is quadratic (c.f. Lemma 2), the first inequality follows from Lemma 3 the second inequality is due to Lemma the third inequality is because ||0 < Zo. and the last two equalities are due to p(zn) 0 and the definition of in equation 17 respectively. Combining the above two cases, we obtain Lemma
25


Reviews:
[{"review_id": "r1lu5o0TtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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:\n\n1. 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.\n\n2. 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:\n\n- Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, Xiyu Zhai, Gradient Descent Finds Global Minima of Deep Neural Networks\n- Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song, A Convergence Theory for Deep Learning via Over-Parameterization\n- Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu, Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeUbodptr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the existence of descent paths from any initial point to the global minimum for the two-layer ReLU network and gives a better characterization of the network width that guarantees the descent path property. Concretely, the paper shows that there exists poor local minima under the case of $n > m+2d-2$ by constructing concrete examples of datasets.\n\nTo show the global convergence property of the optimization method, this kind of landscape analysis is very important. Basically, I like this paper and I think it makes a certain contribution to this line of researches. However, I did not verify the proof.\n\nA few questions:\n- I am not sure why the authors say that \"it was not known whether the descent path property holds for $m \\in (2n/d, n)$\" by citing [Soudry and Hoffer(2017)]. I think [Soudry and Hoffer(2017)] does not mention the descent path property. Is this my misunderstanding?\n- The theory is limited to 2-layer ReLU. Can it be extended to deep networks?\n- The datasets producing poor local minima seem quite artificial. Does this theory hold for a more natural setting (e.g., assume a true distribution or function having preferable properties)?\n\nTypos:\n- In abstruct: exit -> exist\n- Section 1.2: $m < n - 2d$ -> $m < n - 2d + 2$.\n- After Corollary 1: Note that 1 does not ... -> Note that Corollary 1 does not \n\n-----\nUpdate:\nI thank the authors for the response. My concerns have been well addressed and my review stands. I would like to keep the score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article investigates the optimization landscape of shallow ReLU networks, showing that for sufficiently narrow networks there are data sets for which there is no descent paths to the global minimiser. The topic and the nature of the results is very interesting. The reviewers found that this article makes important contributions in a relevant line of investigation and had generally positive ratings. The authors' responses addressed questions from the initial reviews, and the discussion helped identifying questions for future study departing from the present contribution.  
Decision: Accept (Poster)